力扣热题100， 力扣.167两数之和II 力扣80.删除有序数组中的重复项力扣99.恢复二叉搜索树力扣.110平衡二叉树

 

目录

 力扣.167两数之和II

 力扣80.删除有序数组中的重复项

力扣99.恢复二叉搜索树

力扣.110平衡二叉树

---

 力扣.167两数之和II

暴力解法，是通不过，所以我优化了第一步，但是我突然发现一个问题

class Solution {public int[] twoSum(int[] numbers, int target) {int a=0;int b=0;int n=numbers.length;for(int i=0;i<n;i++){a=numbers[i];if(numbers[i]+numbers[n-1]<target){continue;}for(int j=i+1;j<n;j++){b=numbers[j];if(a+b==target){return new int[]{i+1,j+1};}}}return new int[]{};}
}

我判断的第一个假如加上最后一个都比那个目标值小，那我就可以直接跳过这个目标了，

此时我好像发现了新大陆，那么我们按照道理，我们是否可以，慢慢这么缩小，

但是这里你就要注意不能使用for了，你的for,不能很好的控制谁加，谁减，而while可以很好的控制

public int[] twoSum(int[] numbers, int target) {int j=numbers.length-1;int i=0;while(i<j){int sum=numbers[i]+numbers[j];if(sum==target){return new int[]{i+1,j+1};}else if(sum<target){++i;}else{--j;}}   return new int[]{};}

 力扣80.删除有序数组中的重复项

难点:修改数组中，我修改一个，后面的元素发起搬运的问题

于是:left和right都是从2开始，因为前两个不用算，然后left作为我们随时开始搬运的东西，

我们的right作为先锋，往后面遍历，假如我和两个之前的元素不同，我需要把后面的元素全搬运到前面

left作为控制有效数组的长度，那么left-2作为什么呢

因为最多两个

从三个开始看，那么我的nums[right]=nums[left-1)]=nums[left-2]; 因为只有nums[r]=nums[l-1]没有就是两边等于，中间不等，因为是按照顺序的，因此我们可以这么做，只看前面和后面，相等的话，那么中间也一定相等。假如不等，那么就肯定不用担心相等的情况。 我们中间相等，当前slow是合法位置，我们就直接把东西插入给slow,然后我们进行替换就好。[1,1,1,2,2,3,3,3]

class Solution {public int removeDuplicates(int[] nums) {int n=nums.length;if(n<=2)return n;int left=2;int right=2;
//从2开始while(right<n){//这个核心的搬运数组if(nums[left-2]!=nums[right]){nums[left]=nums[right];//left相当于是有效的数字left++;}right++;}return left;}
}

力扣99.恢复二叉搜索树

首先这两个图，左边是正常，右边是他假如给的树，你自己按照代码去这么模拟一下

有几种情况（别看右下面那个1，是7，我打错了 嘿嘿♥️)

第一种，就是这种，两个不同节点，都要换 前一个节点是6，后一个节点是3

6>3 标记6，    5>2,标记2 ，因为有前一个6，所以这个我们第二个节点给2，换6，2。

第二种（别看右下面那个1，是7，我打错了 嘿嘿♥️)

这种情况，我们也一起处理，标记了前一个位置 3,标记后面的位置b

其实俩个都是一个情况，但是都是要改变两个节点，这个就是3是前一个位置，2是后一个位置，后面没有检查到别的条件，所以这个b就是2没有改变。

然后交换a,b就好(假如a之前有值（其实这个之前b也被赋值了，但是后面发现，有第二个不符合条件的情况），那么b就是不在他的下一个节点，假如a之前没有值，那么正好把a和b都给赋值了

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {TreeNode last=null;//我需要找到两个不符合条件的TreeNode a=null;TreeNode b=null;public void recoverTree(TreeNode root) {dfs(root);int val = a.val;a.val = b.val;b.val = val;
//对于二叉搜索树，他的中序遍历之后，获得的值有序（假如中序遍历的过程，上一个节点大于当前节点，违背有序性)}//中序遍历public void dfs(TreeNode root) {if(root==null) return ;dfs(root.left);if(last!=null&&last.val>root.val){if (a == null) {a = last; b = root;} else {b = root;}}last=root;dfs(root.right);}}

力扣.110平衡二叉树

最近的写递归题很奇怪，明明感觉不会，但是却能稀里糊涂写出来

首先你要知道，当前节点的高度是左右节点的最大值+1,然后，你这个left就是左节点的最大值，right是右节点的最大值，然后左右节点一个相减，就可以看看是不是大于1，假如大于1，你就直接剪枝返回

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return dfs(root)==-1?false:true;}//当前节点深度，等于左右节点的最大值+1public int dfs(TreeNode root){if(root==null)return 0;int left=dfs(root.left); if(left==-1)return -1;int right=dfs(root.right);if(right==-1)return -1;if(Math.abs(left-right)>1){return -1;}return Math.max(left,right)+1;
}
}