81.给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
public int countSubstrings(String s) {
int len = s.length();
int res=0;
for(int i=0;i<len;i++){
//回文串为奇数 这里是从中心往两边走 所以中心是一个字符
res+=huiwen(s,i,i);
res+=huiwen(s,i,i+1);
//回文串为偶数
}
return res;
}
public int huiwen(String s,int start,int end){
int l = s.length();
int count = 0;
while (start>=0&&end>=0&&start<l&&end<l){
if(s.charAt(start)==s.charAt(end)){
count++;
start--;
end++;
}else{
return count;
}
}
return count;
}
82.给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
以右->根->左的顺序遍历二叉树，将遍历顺序的前一个结点的累加值记录起来，和当前结点相加，得到当前结点的累加值。
public int preNum = 0;
public TreeNode convertBST(TreeNode root) {
helper(root);
return root;
}
public void helper(TreeNode treeNode){
if(treeNode==null){
return;
}else{
//右子树
helper(treeNode.right);
//处理当前节点和更新累加和
treeNode.val+=preNum;
preNum=treeNode.val;
//左子树
helper(treeNode.left);
}
}
83.给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
原问题等同于： 找到nums一个正子集和一个负子集，使得总和等于target
我们假设P是正子集，N是负子集 例如： 假设nums = [1, 2, 3, 4, 5]，target = 3，一个可能的解决方案是+1-2+3-4+5 = 3这里正子集P = [1, 3, 5]和负子集N = [2, 4]
将其转换为子集求和问题
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
因此，原来的问题已转化为一个求子集的和问题： 找到nums的一个子集 P，使得sum(P) = (target + sum(nums)) / 2
请注意，上面的公式已经证明target + sum(nums)必须是偶数，否则输出为0
方法是
开辟一个长度为P+1的数组，命名为dp
dp的第x项，代表组合成数字x有多少方法。比如说,dp[0] = 1，代表组合成0只有1中方法，即什么也不取。比如说dp[5] = 3 ，代表使总和加到5总共有三种方法。
所以最后返回的就是dp[P]，代表组合成P的方法有多少种
问题是
怎么更新dp数组呢？
遍历nums，遍历的数记作num
再逆序遍历从P到num，遍历的数记作j
更新dp[j] = dp[j - num] + dp[j]
这样遍历的含义是，对每一个在nums数组中的数num而言，dp在从num到P的这些区间里，都可以加上一个num，来到达想要达成的P。
举例来说，对于数组[1,2,3,4,5]，想要几种方法能组合成4,那么设置dp[0]到dp[4]的数组
假如选择了数字2,那么dp[2:4]（也就是2到4）都可以通过加上数字2有所改变，而dp[0:1]（也就是0到1）加上这个2很明显就超了，就不管它。
以前没有考虑过数字2,考虑了会怎么样呢？就要更新dp[2:4]，
比如说当我们在更新dp[3]的时候，就相当于dp[3] = dp[3] + dp[1],即本来有多少种方法，
加上去掉了2以后有多少种方法。因为以前没有考虑过2,现在知道，只要得到了1,就一定可以得到3。
为什么以这个顺序来遍历呢？
假如给定nums = [num1,num2,num3]，我们现在可以理解dp[j] = dp[j-num1] + dp[j-num2] + dp[j-num3]。
但是如何避免不会重复计算或者少算？要知道，我们的nums并不是排序的，我们的遍历也不是从小到大的。
我们不妨跟着流程走一遍
第一次num1，仅仅更新了dp[num1] = 1，其他都是0+0都是0啊都是0
第二次num2，更新了dp[num2] = 1和dp[num1+num2] = dp[num1+num2] + dp[num1] = 1,先更新后者。
第三次num3，更新了dp[num3] = 1和dp[num1+num3] += 1和dp[num2+num3] += 1和dp[num1+num2+num3] += 1。按下标从大到小顺序来更新。
......
由此可见，这种顺序遍历能得到最后的答案。
public int findTargetSumWays(int[] nums, int S) {
int len = nums.length;
int sum=0;
for(int i:nums){
sum+=i;
}
if((sum+S)%2==1||S > sum||len==0){
return 0;
}
sum=(sum+S)/2;
int[] dp=new int[sum+1];
dp[0]=1;
for(int i=0;i<len;i++){
for(int j=sum;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[sum];
}
84.给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
滑动窗口思想
public List<Integer> findAnagrams(String s,String p){
List<Integer> res = new ArrayList<>();
int[] a = new int[26];
int[] b = new int[26];
int end=p.length()-1;
int len = s.length()-1;
if(end>len||len==0){
return res;
}
for(int i = 0;i<=end;i++){
a[p.charAt(i)-'a']++;
b[s.charAt(i)-'a']++;
}
if(Arrays.equals(a,b)){
res.add(0);
}
for(int i=1;i<=len-end;i++){
b[s.charAt(i-1)-'a']--;
b[s.charAt(i+end)-'a']++;
if(Arrays.equals(a,b)){
res.add(i);
}
}
return res;
}
85.给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。
举个例子：
原始数组：[4,3,2,7,8,2,3,1]
重置后为：[-4,-3,-2,-7,8,2,-3,-1]
结论：[8,2]分别对应的index为[5,6]（消失的数字）
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
int len = nums.length;
for(int i = 0 ;i<len;i++){
int temp = Math.abs(nums[i])-1;
if(nums[temp]<0){//因为会有重复得
continue;
}
nums[temp]=0-nums[temp];
}
for(int i=0;i<len;i++){
if(nums[i]>0){
res.add(i+1);
}
}
return res;
}
86.两个整数之间的[汉明距离]指的是这两个数字对应二进制位不同的位置的数目。
注意：
0 ≤ x, y < 2∧31
给出两个整数 x 和 y，计算它们之间的汉明距离。
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
X和Y的异或结果(相同为0，不同为1)
计算异或结果中1的个数
public int hammingDistance(int x, int y) {
int n = x^y;
int count=0;
while(n!=0){
n=n&(n-1);
count++;
}
return count;
87.给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
注意：不是根节点左右子树的深度和，而是每个结点左右子树深度和的最大值
1
/ \
2 3
/ \
4 5
/ \
6 7
/ \
8 9
这个就不是根节点最大 是2节点
public int maxint = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null)
return maxint;
deep(root);
return maxint;
}
public int deep(TreeNode treeNode){
if(treeNode==null){
return -1;//注意不是返回-1；
}
int left = deep(treeNode.left)+1;
int right = deep(treeNode.right)+1;
maxint = Math.max((left+right),maxint);
return Math.max(left,right);
}
88.给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
累计总和，在索引
i和j处相差k，即sum[i] - sum[j] = k，则位于索引i和j之间的元素之和是k。
使用了一个哈希表map，它用于存储所有可能的索引的累积总和以及相同累加和发生的次数。我们以以下形式存储数据：(sum_i，sum_i的出现次数)。我们遍历数组nums并继续寻找累积总和。每当我们遇到一个新的和时，我们在hashmap中创建一个与该总和相对应的新条目。如果再次出现相同的和，我们增加与map中的和相对应的计数。此外，对于遇到的每个总和，我们还确定已经发生sum−k总和的次数，因为它将确定具有总和k的子序列发生到当前索引的次数。我们将count增加相同的量。
在完成便利数组后，count记录了所需结果
public int subarraySum(int[] nums, int k) {
int len = nums.length;//因为数组长度至少为1
int count = 0;
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int sum=0;
for(int i=0;i<len;i++){
sum+=nums[i];
if(map.containsKey(sum-k)){//要先判断 因为 nums = [1] k =0 得情况会出错
count+=map.get(sum-k);
}
if(!map.containsKey(sum)){
map.put(sum,1);
}else{
map.put(sum,map.getOrDefault(sum,0)+1);
}
}
return count;
}
89.给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
从左到右循环，记录最大值为
max，若nums[i] < max, 则表明位置i需要调整, 循环结束，记录需要调整的最大位置i为high; 同理，从右到左循环，记录最小值为min, 若nums[i] > min, 则表明位置i需要调整，循环结束，记录需要调整的最小位置i为low。return high > low ? high - low + 1 : 0;
public int findUnsortedSubarray(int[] nums) {
int len = nums.length;
if(len <= 1) return 0;
int high = 0, low = len-1, max = nums[0], min = nums[len-1];
for(int i = 1; i < len; i++){
max = Math.max(max, nums[i]);
min = Math.min(min, nums[len-1-i]);
if(nums[i] < max) high = i;
if(nums[len-1-i] > min) low = len-1-i;
}
return high > low ? high - low + 1 : 0;
}
90.根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
根据题意，从最后一天推到第一天，这样会简单很多。因为最后一天显然不会再有升高的可能，结果直接为0。
再看倒数第二天的温度，如果比倒数第一天低，那么答案显然为1，如果比倒数第一天高，又因为倒数第一天
对应的结果为0，即表示之后不会再升高，所以倒数第二天的结果也应该为0。
自此我们容易观察出规律，要求出第i天对应的结果，只需要知道第i+1天对应的结果就可以：
若T[i] < T[i+1]，那么res[i]=1；
若T[i] > T[i+1]
res[i+1]=0，那么res[i]=0;
res[i+1]!=0，那就比较T[i]和T[i+1+res[i+1]]（即将第i天的温度与比第i+1天大的那天的温度进行比较）
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] dp = new int[len];
dp[len-1]=0;
if(len==1)
return dp;
for(int i=len-2;i>=0;i--){
//注意j+=dp[j] 还有俩个break
for(int j=i+1;j<len;j+=dp[j]){
if(T[i]<T[j]){
dp[i]=j-i;
break;
}else{
if(dp[j]==0){
dp[i]=0;
break;
}
}
}
}
return dp;
}
网友评论