LeetCode100题总结

前言

这是陈旧已久的草稿2022-10-20 00:07:01发布一下

这个是我的同学自己写的算法记录，我看了一看。
当时，准备寒假实习，后面也没有找到。

现在2024-5-12 22:06:18，发布到[LeetCode]专栏中。

LeetCode100题总结

题型梳理

双指针

思想：应对一组数据的走向有两种变化方案：向左或向右

通过不断改变左右边界来去最优解。

类型题目解决方案：
找到适合使用双指针的遍历点 + 找到适合题目的最优解方案的底层逻辑。

难点在于如何找到合适的底层逻辑，很多结果数据的处理很棘手。

11. 盛最多水的容器

这个题的底层逻辑：判断左移还是右移使得容量变大，从底层逻辑来看，纯纯数学问题。

我的想法：用假设发生的结果来决定接下来真实发生什么

题目想法：用真实发生的结果来决定接下路真实发生什么

我的逻辑	用假设发生的结果来决定接下来真实发生什么
题解的逻辑	用真实发生的结果来决定接下路真实发生什么
我的问题切入点	先判断左移、右移、同时移的影响，来决定接下来如何处理左右指针
题解的问题切入点	根据已知的两个指针所指结果，只改变两指针中数组值小的。
缺点（我）	考虑的情况要有6种，而且假设移动的写法，得保证数组不能越界。很难处理，没写出来。
优点（题解）	设计很巧妙，也比较难想这个问题的思考角度，需要较深的数学水平。

• 暴力解法：O（n^2）

  /*
  思路：暴力解法
  两层遍历，依次算出对应的面具area。比较选出最大的返回*/class Solution {public int maxArea(int[] height) {int fro,last,area;fro=0;area=0;last=height.length;for (int i=0;i<height.length;i++){for (int j=i+1;j<height.length;j++){area=Math.max(area,Math.min(height[i],height[j])*(j-i));}}return area;}
  }
  

• 双指针解法（我的）

   /*影响水体积的因素有： 所选数组的长度 & 所选数组所能决定的高度数组的长度是第一时间好确定的，改变长度的方式有两种，左边界+1 or 右边界—1，因为存在这两种变化，所以采用双指针的思想。不断去找适合本题的指针移动逻辑，    采用对的方法+找到每个题的逻辑=ac*/public  int maxArea(int[] height) {int  n=height.length;int left=0;int right=n-1;//用dp0，dp2/dp1来帮助实现比较逻辑int dp0,dp1,dp2;dp0=Math.min(height[left],height[right]);int area=dp0*(right-left);if(n==2)return area;while(left!=right){//6种情况//a>b>c//area(height,left+1,right),area(height,left,right-1),area(height,left+1,right-1)if (left+1<n&&right-1>0&&area(height,left+1,right)==max3(area(height,left+1,right),area(height,left,right-1),area(height,left+1,right-1))){left++;area=Math.max(area,area(height,left+1,right));}else  if (left+1<n&&right-1>0&&area(height,left,right-1)==max3(area(height,left+1,right),area(height,left,right-1),area(height,left+1,right-1))){right--;area=Math.max(area,area(height,left,right-1));}else  if (left+1<n&&right-1>0&&area(height,left+1,right-1)==max3(area(height,left+1,right),area(height,left,right-1),area(height,left+1,right-1))){left++;right--;area=Math.max(area,area(height,left+1,right-1));}elseleft++;}return area;}private int area(int []h,int l,int r){return (r-l)*(Math.min(h[l],h[r]));}//三数最大值private int max3(int a,int b,int c){if (a>b){if (c>a)return c;elsereturn a;}return b;}public static void main(String[] args) {int a[]={2,3,4,5,18,17,6};int b=new Solution().maxArea(a);System.out.println(b);}
  }
  

• 双指针：O（n）

  /*
  思路
  如何看待这个问题？
  可以将我们要计算的数字公式转化为直观的物理意义-面积，控制这个几何图形面积的因素有两个：底、高
  我们可以用两个指针来底因素，左指针指向最左，右指针指向最右。
  通过控制指针的移动来直接改变底，间接改变高，那该如何控制这个指针走向。
  分析可得：
  假设我们的左指针移动了，那么我们的底肯定小了，如果这时候高返回小了，那就没有移动的必要了，这样只让area越来越小。
  所以可以确定的一点是，指针移动势必会让底变小，想尽快找到答案就必须让高适当增高！
  那我们该如何控制高的问题呢？
  本题而言，高这个因素是由最小的hight决定的，那明确了这个点好办了，
  我们通过简单的判断高的问题，来控制左右指针的走向，指针发生移动之后，就可以通过计算面积，取对应的最大值来进行下一步的判断了，
  当整个循环走完的时候，就我们的问题找出答案的时候。*/
  public class Demo01 {public int maxArea(int[] height) {int f,l,area;f=0;area=0;l=height.length-1;while (f<l){//Math.min(height[f],height[l])表示几何图形的高area=Math.max(area,Math.min(height[f],height[l])*(l-f));if(height[f]<height[l]){f++;}else  l--;}
  //        for (int i=0;i<height.length;i++)
  //        {
  //            for (int j=i+1;j<height.length;j++)
  //            {
  //                area=Math.max(area,Math.min(height[i],height[j])
  //                *(j-i));
  //            }
  //        }return area;}public static void main(String[] args) {int []a={1,8,6,2,5,4,8,3,7};Demo01 demo01 = new Demo01();demo01.maxArea(a);System.out.println(demo01.maxArea(a));}}
  

• 总结：

  感觉这个移动有点博弈论的味了，每次都移动自己最差的一边，虽然可能变得更差，但是总比不动（或者减小）强，动最差的部分可能找到更好的结果，但是动另一边总会更差或者不变，兄弟们，这不是题，这是人生，逃离舒适圈！！
  

234.回文链表

• 双指针切入点：数组的双指针遍历

• 本题的应用逻辑，将链表转化成双指针，变成了常见的双指针遍历问题。

• 双指针：

  	public boolean isPalindrome(ListNode head) {List<Integer> list=new ArrayList<>();while (head!=null){list.add(head.val);head=head.next;}int n=list.size();int front=0;int last=n-1;while (front<last){if (list.get(front)!=list.get(last))return false;front++;last--;}return true;}
  

75.颜色分类

也叫荷兰国旗问题 -Dijkstra提出的

• 冒泡排序：

  时间复杂度：O（n^2）

   //插入排序public void sortColors(int[] nums) {int temp=0;for (int i=0;i<nums.length;i++){for (int j=0;j<nums.length-1;j++){if (nums[j]>nums[j+1]){temp=nums[j+1];nums[j+1]=nums[j];nums[j]=temp;}}}}
  

• 两次单指针

  时间复杂度为O(n)，在遍历外部加一个指针，遍历中进行交换，如果交换指针递增。
  逻辑：先让0放在数组的前面，再让1放在0的后面。

  //两次单指针public void sortColors(int[] nums){int ptr=0;int temp=0;for (int i=0;i<nums.length;i++){if (nums[i]==0){temp=nums[i];nums[i]=nums[ptr];nums[ptr]=temp;ptr++;}}for (int i=0;i<nums.length;i++){if (nums[i]==1){temp=nums[i];nums[i]=nums[ptr];nums[ptr]=temp;ptr++;}}}
  

• 双指针

  需要开辟一个新的数组空间，复杂度为O（n）
  本质上还是是将0放在前面，2放在后面

  public static void sortColors(int[] nums){int b[]=new int[nums.length];for (int i = 0; i < nums.length; i++) {b[i]=1;}int front=0;int back=nums.length-1;for (int i=0;i<nums.length;i++){if (nums[i]==0) {b[front] = 0;front++;}if (nums[i]==2) {b[back] = 2;back--;}}for (int i=0;i<nums.length;i++){nums[i]=b[i];}}
  

206.反转链表

• 栈

  利用栈先进后出的特性，这处理前后反序的问题。

  class Solution {public ListNode reverseList(ListNode head) {Stack<ListNode> stack=new Stack<ListNode>();ListNode top=head,tail,pre;while(top!=null){stack.push(top);top=top.next;}if (stack.isEmpty())return null;tail=stack.pop();pre=tail;while (true){if (!stack.empty()) {pre.next = stack.pop();pre = pre.next;}else break;}pre.next=null;return tail;}
  }

• 迭代

  创建一个前驱结点pre：
  迭代过程记录一个后继结点n，
  让当前结点指向前驱结点，让当前结点变成后继结点。
  

  public static  ListNode reverseList1(ListNode head) {if(head==null)return null;ListNode pre=null;ListNode cur=head;while(cur!=null){ListNode n=cur.next;cur.next=pre;pre=cur;if (n==null)return cur;cur=n;}return cur;}
  

• 递归

  和迭代的思想一样，能迭代的一般都能递归，写出来练练手。

  public static  ListNode reverseList(ListNode head){ListNode pre=null;ListNode cur=head;return method(pre,cur);}private static ListNode method(ListNode pre,ListNode cur){if (cur.next==null) {cur.next=pre;return cur;}ListNode nextnode=cur.next;cur.next=pre;return method(pre,nextnode);}
  

142.环形链表2

• 用栈写：

  时间复杂度：O(n^2)

  空间复杂度：O(n)

   public ListNode detectCycle(ListNode head) {Stack<ListNode> stack=new Stack<>();while (head!=null){if (stack.contains(head))return head;elsestack.add(head);head=head.next;}return null;}
  

• 双指针方法

  了解一下思路得了，这个问题是采用了快慢指针的模型，通过两次相遇来确定进入环的入口。开扩一下思路就好。

• 哈希（时间优话，空间复杂）

  这个比较实在，栈的时间复杂度是O（n^2），可以用哈希优化成O(n)

  public ListNode detectCycle(ListNode head) {Set<ListNode> set=new HashSet<>();while (head!=null){if (set.contains(head))return head;elseset.add(head);head=head.next;}return null;}
  

15.三数之和

这个题目跟两数之和有点像，介于三数和为0 ，遍历第一个数，只需要找到接下来范围内两数和为-绝对值第一个数即可。

• 双指针

  对于两数之和部分用双指针，能使时间复杂度从O(n^3）降到O(n方)

  List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> threeSum(int[] nums) {if (nums.length<3)return null;Arrays.sort(nums);if (nums[0]>0)return res;for (int i=0;i<nums.length-2;i++){int begin=i+1;int end=nums.length-1;while (begin<end){if (nums[begin]+nums[end]<Math.abs(nums[i]))begin++;else if (nums[begin]+nums[end]>Math.abs(nums[i]))end--;else if (nums[begin]+nums[end]==Math.abs(nums[i])){List<Integer> list=new ArrayList<>();list.add(nums[i]);list.add(nums[begin]);list.add(nums[end]);Collections.sort(list);if (!res.contains(list))res.add(list);begin++;end--;}}}return res;}
  

  解法分析：
  难度在于如何去除重复解。
  这种处理是采用排序数组，再检验是否res集中是否存在这样的数组。
  大大影响实际复杂度。数组排序O(N logN),遍历数组O(n),双指针遍历O(n)优化方向：
  既然找到了慢的原因是处理重复结果导致的，那就从这个方向开始优化，
  我是从数组生成的时候进行筛选的，如果从源头筛选，就能优化很多时间。
  

• 双指针（优化版）

  2030ms到18ms的巨大飞跃

  从重复的原因角度出发，处理了两个点，即第一次遍历时重复情况，第二次双指针出现重复。大大减少时间负担

  优化部分：

   //第一次遍历到大于0的就不用继续走了.if(nums[i]>0)return res; 
  //如果有连着两个 直接用一个if(i > 0 && nums[i] == nums[i-1])//优化了，如果连着挨着的一样，那就跳过。while (begin<end&&nums[begin+1]==nums[begin])begin++;while (begin<end&&nums[end-1]==nums[end])end--;
  

  优化完整版：

  List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> threeSum(int[] nums) {if (nums.length<3)return null;Arrays.sort(nums);if (nums[0]>0)return res;for (int i=0;i<nums.length;i++){if(nums[i]>0)return res; //如果有连着两个0直接用一个if(i > 0 && nums[i] == nums[i-1])continue;int begin=i+1;int end=nums.length-1;while (begin<end){if (nums[begin]+nums[end]<Math.abs(nums[i]))begin++;else if (nums[begin]+nums[end]>Math.abs(nums[i]))end--;else if (nums[begin]+nums[end]==Math.abs(nums[i])){List<Integer> list=new ArrayList<>();list.add(nums[i]);list.add(nums[begin]);list.add(nums[end]);res.add(list);//优化了，如果连着挨着的一样，那就跳过。while (begin<end&&nums[begin+1]==nums[begin])begin++;while (begin<end&&nums[end-1]==nums[end])end--;begin++;end--;}}}return res;}
  

滑动窗口

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

3. 无重复字符的最长子串

• 暴力解法：

  时间复杂度：On方

  空间复杂度：On

  超时

  public int lengthOfLongestSubstring(String s) {int count=0;for (int i=0; i<s.length();){Set<Character> set=new HashSet<>();for (int j=0;j<s.length();j++)if (!set.contains(s.charAt(j)))set.add(s.charAt(j));else {count=count>set.size()? count:set.size();break;}}return  count;}
  

• 双指针

  减少了从头遍历的情况，时间上优化了不少，但还有优化的空间，这里面的left指针没怎么用上。

   public int lengthOfLongestSubstring(String s) {int left,right;left=0;right=0;int count=0;List<Character> list=new ArrayList<>();while (left<=right&&right<s.length()&&left>=0){if (!list.contains(s.charAt(right))) {while (true) {if (right<s.length()&&!list.contains(s.charAt(right))) {list.add(s.charAt(right));right++;//right越界问题}else {count=Math.max(count,list.size());break;}}}else {while (list.contains(s.charAt(right))){list.remove(0);}left++;}}return count;}
  

• 双指针优化版

  while (list.contains(s.charAt(right))){
  list.remove(0);
  }

  优化开始的地方，这个采用删除想要数组的索引之前的元素，然后统计数组个数的策略来返回最大值。

  改为用hashmap来存储索引和字符，用字符来确定索引，从而确定左指针的值！

   public int lengthOfLongestSubstring(String s) {int left,right;left=0;right=0;int count=0;Map<Character,Integer> map=new HashMap<>();List<Character> list=new ArrayList<>();for (int i = 0; i <s.length() ; i++) {if (!map.containsKey(s.charAt(i))) {map.put(s.charAt(i), i);//right越界问题}else{left=Math.max(map.get(s.charAt(i))+1,left);map.put(s.charAt(i), i);}count=Math.max(i-left+1,count);}return count;}
  

209. 长度最小的子数组

做懂了第三题，再做类似的题有种酣畅淋漓的感觉。贼爽。

滑动窗口

public int minSubArrayLen(int target, int[] nums) {int left=0;int len=Integer.MAX_VALUE;int sum=0;for (int i=0;i<nums.length;i++){sum+=nums[i];while (sum>=target){len=Math.min(len,i-left+1);sum-=nums[left];left=left+1;}}len=len==Integer.MAX_VALUE? 0:len;return  len;}

438. 找到字符串中所有字母异位词

标准长度的滑动窗口，比较简单，难点在于处理是否是异位词这个点，如果能想到分割子串、排序、再比较的方式就更简单了，

就是排序比较的过程加长了时间复杂度。

• 滑动窗口

   public List<Integer> findAnagrams(String s, String p) {List<Integer> list= new ArrayList<>();if (s.length()<p.length())return list;if (p.length()==0)return list;int n=p.length();char[] sp=p.toCharArray();Arrays.sort(sp);for (int i=0;i<=s.length()-p.length();i++){char[] ss=s.substring(i,i+n).toCharArray();Arrays.sort(ss);if (xiangdeng(ss,sp)) list.add(i);}return list;}public boolean xiangdeng(char[] a,char[] b){boolean f=true;for (int i=0;i<b.length;i++){if (a[i]!=b[i])return false;} return f;}
  

广搜

按照数据结构中广搜的定义，bfs也是遍历的一种思想，核心策略采用当前节点能走的全都走。

102. 二叉树的层序遍历

• bfs：

  这里有一行错误代码，i <queue.size() 。

  错误原因，循环体内容要操作queue的size，动态变化的size不适合做循环判断条件

  /*
  102. 二叉树的层序遍历思路：
  这个题跟基础的算法层序遍历很像，基础算法可以用层序遍历，但区别于层序遍历，我们
  缺少对返回值List<List<Integer>>这个条件的控制，直接不分组的sout无法满足这个题的需求。针对这个需求有以下实现思路：
  1.通过进队列的时候我们放入list集合，可以用类似于之前的后序遍历，采用双栈，我想用一个队列
  加一个栈，队列来控制层序遍历，栈来控制加入list，但是每写出来。
  2.可以通过栈当前数量来加入，我们肯定要加入集合中，但是加入几个是个问题，获取队列的长度来
  代表我们加入集合的个数。每次加完一个集合都代表栈对应着更新一次。同步对应。很巧妙的设计。*/
  public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res=new ArrayList<>();if (root==null)return res;Queue<TreeNode> queue=new LinkedList<>();queue.add(root);while (!queue.isEmpty()){List<Integer> list=new ArrayList<>();int count=queue.size();for (int i = 0; i<count ; i++) {TreeNode node=queue.poll();list.add(node.val);if (node.left!=null)queue.add(node.left);if (node.right!=null)queue.add(node.right);}res.add(list);}return  res;}
  

200. 岛屿数量

bfs和递归结合，分为两组逻辑，进入逻辑和递归逻辑

递归逻辑，这片岛为1的全变成2

进入逻辑，遍历到当前为1的情况进入递归，让这片都为2 计数++；

• bfs+递归

  /*
  200. 岛屿数量
  输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
  ]
  输出：1
  思路：遍历岛这个二维数组，如果当前数为1，则进入感染函数并将岛个数+1
  感染函数：其实就是一个递归标注的过程，它会将所有相连的1都标注成2。
  为什么要标注？这样就避免了遍历过程中的重复计数的情况，一个岛所有的1都变成了2后，
  遍历的时候就不会重复遍历了。*/public static int numIslands(char[][] grid) {int row=grid.length;int column=grid[0].length;int sum=0;for (int i=0;i<row;i++){for (int j=0;j<column;j++){//进入递归的逻辑if (grid[i][j]=='1'){digui(grid,i,j);sum++;}}}return  sum;}public static void digui(char[][] grid,int i,int j){//终止条件if (i<0||i>=grid.length||j<0||j>=grid[0].length){return;}if(grid[i][j]!='1')return;if (grid[i][j]=='1')grid[i][j]='2';digui(grid,i-1,j);digui(grid,i+1,j);digui(grid,i,j-1);digui(grid,i,j+1);}
  

617.合并二叉树

• 递归实现

  递归创造新的节点，确定好每一步的返回值即可。

  出现了好多次空参报错都是因为返回点没有找好。

     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {TreeNode res=sum(root1,root2);return res;}public  TreeNode sum(TreeNode root1, TreeNode root2){TreeNode res=null;//终止条件if (root1==null&&root2==null)return null;if (root1==null&&root2!=null){res= root2;}if (root2==null&&root1!=null){res=root1;}if (root1!=null&&root2!=null) {res= new TreeNode(root1.val+root2.val);res.left=sum(root1.left,root2.left);res.right=sum(root1.right,root2.right);}return res;}
  

• 迭代bfs

  想把每一步的操作结果都体现在root1树上，迭代需要我们的数据结构-队列来支持，跟层序遍历的思路一样，对于每一步进队列和出队列的情况加上我们的逻辑限制，就能解决本题。

  哪体现了bfs思想呢

  本身在二叉树的遍历思想上，层序遍历本身也是一种能走就全走的思想，只不过这个能走是横向的，在同一层的都进入队列。

  某种意义上来讲，二叉树的遍历都可以归类为bfs或dfs，前中后三序遍历可看做是dfs，层序遍历可看成bfs

  public TreeNode mergeTrees(TreeNode root1, TreeNode root2){//挺美观的条件判断处理，学习一手if (root1==null||root2==null)return root1==null ?root2:root1;Queue<TreeNode> queue=new LinkedList<>();queue.add(root1);queue.add(root2);while (queue.size()>0){TreeNode r1=queue.poll();TreeNode r2=queue.poll();r1.val+=r2.val;if (r1.left!=null&&r2.left!=null){queue.add(r1.left);queue.add(r2.left);}//隐藏了一步逻辑，就是当右子树为空，r1还等于原值，不用写出来if (r1.left==null)r1.left=r2.left;if (r1.right!=null&&r2.right!=null){queue.add(r1.right);queue.add(r2.right);}if (r1.right==null)r1.right=r2.right;}return root1;}
  

深搜

104.二叉树的最大深度

• dfs递归

  思想很简单，只要能走，就一走到底，不能走的情况用我们的递归终止条件控制返回深度即可。

  public int maxDepth(TreeNode root) {int ans=depth(root);return ans;}public  int depth(TreeNode node){if (node==null)return 0;return Math.max(depth(node.left),depth(node.right))+1;}
  

• bfs递归

  /*
  104. 二叉树的最大深度
  用了广度优选，感觉这个题用广度优先不如深度优先好，深度优先能减少一些时间复杂度*/
  public class Solution {public int maxDepth(TreeNode root) {Queue<TreeNode> queue=new LinkedList<>();List<List<Integer>> a=new ArrayList<List<Integer>>();if (root==null)return 0;queue.add(root);TreeNode node=root;int max=0;while (!queue.isEmpty()) {List<Integer> b=new ArrayList<>();int count=queue.size();max++;for (int i=0;i<count;i++){node = queue.poll();b.add(node.val);if (node.left != null)queue.add(node.left);if (node.right != null)queue.add(node.right);}a.add(b);}return max;}
  }
  

543.二叉树的直径

这题第二次做又有了一个新理解的点，就是用一个全局变量，dfs的过程去记录我想要的结果，避免了dfs求深度之后再遍历二叉树拿值的情况。

• 特殊情况：
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cotXebxO-1666195548221)(C:\Users\Onlylove\AppData\Roaming\Typora\typora-user-images\image-20220726220506903.png)]

• 错误写法：

  以为只需要根节点的深度-1和左右子树深度和比较取max就可以

  其实最大值不一定出现了

   public int diameterOfBinaryTree(TreeNode root) {int c=depth(root.right)+depth(root.left);int b=depth(root)-1;return Math.max(b,c);}public int depth(TreeNode node){if (node==null)return 0;return Math.max(depth(node.left),depth(node.right))+1;}
  

• dfs：

  /*
  543.二叉树的直径
  深度优先搜索
  1.递归函数的三个关键点：退出条件、递归内容、相似条件。
  2.树的定义深度
  3.树的直径定义：树中任意两节点最短路径的最大值
  4.两节点间路径的定义：他们之间边的数目两叶子节点之间路径=祖先节点左右儿子的深度和*/int ans;public int diameterOfBinaryTree(TreeNode root) {ans=1;depth(root);return ans-1;}public int depth(TreeNode node){if (node==null)return 0;int l=depth(node.left);int r=depth(node.right);ans=Math.max(ans,l+r+1);//记录每一步能走的最大值，避免出现最大值不在根节点子树的情况。return Math.max(l,r)+1;}
  

111. 二叉树的最小深度

• dfs+递归

  时间On，空间On

  /*
  111. 二叉树的最小深度
  最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
  1.写出结束条件
  2.不要把树复杂化，就当做树是三个节点，根节点，左子节点，右子节点
  3.只考虑当前做什么，不用考虑下次应该做什么
  4.每次调用应该返回什么*/
  public int minDepth(TreeNode root) {int ans=0;if (root==null)return ans;ans=depth(root);return ans;}public int depth(TreeNode node){if (node.left==null&&node.right==null)return 1;else if (node.left==null&&node.right!=null)return depth(node.right)+1;else if (node.right==null&&node.left!=null)return depth(node.left)+1;elsereturn Math.min(depth(node.left),depth(node.right))+1;}
  

110.平衡二叉树

• dfs+递归

  这是一个双重遍历问题，用深搜求树的深度，再用遍历帮助我们求一下是否满足条件。

  public boolean isBalanced(TreeNode root) {if (root==null)return true;if (Math.abs(depth(root.right)-depth(root.left))>1)return false;return isBalanced(root.right)&&isBalanced(root.left);}//求深度public int depth(TreeNode node){if (node==null)return 0;return Math.max(depth(node.left),depth(node.right))+1;}
  

• dfs+迭代

  时间On 空间On

  这段代码是第一次写的，求深度这步写的比较蠢，

  整体思路还是层序遍历+dfs求深度

  /*
  110. 平衡二叉树
  高度=叶子节点到根节点的最长距离
  不可能从叶子到根反向寻找，只能是从根向下寻找
  用递归能少写个栈
  他说每个结点，那还得再遍历一下二叉树
  递归部分：
  1.结束条件：当前节点为叶子节点
  2.递归内容: 计数且进入下一次比较*/
  public class Solution2 {int h=0;boolean f=true;public boolean isBalanced(TreeNode root) {Queue<TreeNode> queue=new LinkedList<>();if (root==null)return true;TreeNode cur=root;queue.add(cur);while (!queue.isEmpty()) {cur=queue.poll();if (cur.left!=null)queue.add(cur.left);if (cur.right!=null)queue.add(cur.right);f=ok(cur);if (f==false) {break;}}return f;}//求高度的函数public int high(TreeNode node){if (node==null)return 0;if (node.left==null&&node.right==null)h=1;if (node.left!=null&&node.right==null)h=high(node.left)+1;if (node.right!=null&&node.left==null)h=high(node.right)+1;if (node.right!=null&&node.left!=null)h=Math.max(high(node.left),high(node.right))+1;return  h;}public  boolean ok(TreeNode node){if (Math.abs(high(node.left)-high(node.right))>1)return false;elsereturn true;}
  }
  

226.翻转二叉树

• dfs+递归

  时间On 空间On

  在我能走的基础上一直深搜，交换左右两边的值，操作，写好递归终止条件即可。

  public TreeNode invertTree(TreeNode root) {change(root);return root;}private void change(TreeNode node){TreeNode cur=node;if (node==null)return;else if (node.left==null&&node.right!=null){node.left=node.right;node.right=null;}else if (node.right==null&&node.left!=null){node.right=node.left;node.left=null;}else {cur=node.right;node.right=node.left;node.left=cur;}change(node.left);change(node.right);}
  

回溯

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

遍历阶段伪代码

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果
}

递归部分伪代码

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

可能遇到的结果处理

res.add(new ArrayList<>(list));

39.组合总和

• 回溯树：

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lgTXnaDx-1666195548223)(F:\截图\IMG_20220729_222638.jpg)]

• 回溯

  /*
  39. 组合总和
  核心三步骤：（回溯）22 23凑list.add(candidates[i]);back(candidates,list,target-candidates[i],i);list.remove(list.size()-1);
  剪枝：if (candidates[start]>target)//上来就大于目标值，直接不用考虑return;if(i > 0 && candidates[i] == candidates[i-1])   continue; 连续元素重复了，直接跳过一个//[2,2,3,5]*/
  public class Solution3 {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {List<Integer> list=new ArrayList<>();Arrays.sort(candidates);back(candidates,list,target,0);return res;}public void back(int[] candidates,  List<Integer> list,int target,int start){if (target==0){res.add(new ArrayList<>(list));return;}for (int i=start;i<candidates.length;i++){if (candidates[start]>target)return;//[2] [2,2] [2,2,3]   [7]list.add(candidates[i]);/*tar:5,start:1[2,2]  back3 [2,3] back2*/back(candidates,list,target-candidates[i],i);//[]list.remove(list.size()-1);}}
  }
  

77.组合

• 回溯

  我的思路是先将n转化为平时操作的数组，在for遍历上扩宽集合，在backtracking上深入集合，

  判断条件 长度

  剪枝角度 要放的必须比之前的得大（小的话一定已经放过了，为了避免重复）

  时间：173ms

  List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combine(int n, int k) {int [] a=new int[n];for (int i=0;i<n;i++){a[i]=i+1;}List<Integer> list=new ArrayList<>();backtracking(a,list,k);return res;}void backtracking(int []nums,List<Integer> list,int k){//递归终止条件if (list.size()>=k){{ res.add(new ArrayList<>(list));return;}}for (int i=0;i<nums.length;i++){//剪枝操作if (list.size()!=0&&nums[i]<=list.get(list.size()-1))continue;//深度和宽度的逻辑实现list.add(nums[i]);backtracking(nums,list,k);list.remove(list.size()-1);}}
  

• 优化版：

  既然上面都已经想到了剪枝操作，那可以从产生条件上就避免剪枝情况的出现，因为我放进入的数组必然是递增的。

  时间17ms，

  List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combine(int n, int k) {int [] a=new int[n];for (int i=0;i<n;i++){a[i]=i+1;}List<Integer> list=new ArrayList<>();backtracking(a,list,k,0);return res;}void backtracking(int []nums,List<Integer> list,int k,int start){//递归终止条件if (list.size()>=k){{ res.add(new ArrayList<>(list));return;}}for (int i=start;i<nums.length;i++){//剪枝操作// if (list.size()!=0&&nums[i]<=list.get(list.size()-1))//     continue;//深度和宽度的逻辑实现list.add(nums[i]);backtracking(nums,list,k,i+1);list.remove(list.size()-1);}}
  

• 优化版plus

  仔细想想这题还有能优化的地方，从遍历的次数来减少是一个很好的出发点。

  如果从1开始，k=3，那我们只需要遍历到4就OK了，没有必要再去遍历5、6、7…这样的数据了！

  时间：1ms

  i<=nums.length-(k-list.size())
  

  完整版：

  List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combine(int n, int k) {int [] a=new int[n];for (int i=0;i<n;i++){a[i]=i+1;}List<Integer> list=new ArrayList<>();backtracking(a,list,k,0);return res;}void backtracking(int []nums,List<Integer> list,int k,int start){//递归终止条件if (list.size()>=k){{ res.add(new ArrayList<>(list));return;}}for (int i=start;i<=nums.length-(k-list.size());i++){//剪枝操作// if (list.size()!=0&&nums[i]<=list.get(list.size()-1))//     continue;//深度和宽度的逻辑实现list.add(nums[i]);backtracking(nums,list,k,i+1);list.remove(list.size()-1);}}
  

46.全排列

• 回溯

  避免重复数据，遍历一下是否已经存在nums[i]

  if(list.contains(nums[i]))continue;
  

      List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> permute(int[] nums) {List<Integer> list=new ArrayList<>();backtracking(nums,list);return res;}void backtracking(int []nums,List<Integer> list){if (list.size()>=nums.length){res.add(new ArrayList<>(list));return;}for (int i=0;i<nums.length;i++){if(list.contains(nums[i]))continue;list.add(nums[i]);backtracking(nums,list);list.remove(list.size()-1);}}
  

79.单词搜索

• dfs错误写法

  看题目想到的是dfs，正常的dfs写完，发现面对abcb这样的样例无法通过，于是采用了跟LeetCode200题一样的策略，将已经遍历过的字符设为一个不相干的，来避免下次再遍历到。

  改进之后 发现 [[“C”,“A”,“A”],[“A”,“A”,“A”],[“B”,“C”,“D”]] “AAB” 这个测试是致命的，也就说用dfs就无法解决这样的情况

  public boolean exist(char[][] board, String word) {int m=board.length;int n=board[0].length;for (int i=0;i<m;i++){for (int j=0;j<n;j++){if (board[i][j]==word.charAt(0)&&dfs(board,word,0,i,j))return true;}}return false;}boolean dfs(char[][] board, String word,int start,int i,int j){boolean flag=false;if (i<0||i>=board.length||j<0||j>=board[0].length)return true;if (board[i][j]!=(word.charAt(start))){return  false;}board[i][j]='0';flag=true;return flag&&(dfs(board,word,start+1,i+1,j)||dfs(board,word,start+1,i-1,j)||dfs(board,word,start+1,i,j-1)||dfs(board,word,start+1,i,j+1));}
  

• 回溯

  用一个二维Boolean数组来表示当前节点走没走没，走过之后再撤销一下。

  /*** 回溯法：相比于DFS，多了一步『撤销修改节点状态』*/private boolean find;  // 定义为成员变量，方便以下两个成员方法使用和修改public boolean exist(char[][] board, String word) {if (board == null) return false;int m = board.length, n = board[0].length;boolean[][] visited = new boolean[m][n];find = false;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){backtracking(i, j, board, word, visited, 0);  // 从左上角开始遍历棋盘每个格子}}return find;}/*** i,j,board：棋盘格及当前元素的坐标* word: 要搜索的目标单词* visited：记录当前格子是否已被访问过* pos: 记录目标单词的字符索引，只有棋盘格字符和pos指向的字符一致时，才* 有机会继续搜索接下来的字符；如果pos已经过了目标单词的尾部了，那么便说明找到目标单词了*/public void backtracking(int i, int j, char[][] board, String word,boolean[][] visited, int pos){// 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了if(i<0 || i>= board.length || j<0 || j >= board[0].length || visited[i][j] ||find || board[i][j]!=word.charAt(pos))  return;if(pos == word.length()-1){find = true;return;}visited[i][j] = true;  // 修改当前节点状态backtracking(i+1, j, board, word, visited, pos+1);  // 遍历子节点backtracking(i-1, j, board, word, visited, pos+1);backtracking(i, j+1, board, word, visited, pos+1);backtracking(i, j-1, board, word, visited, pos+1);visited[i][j] = false; // 撤销修改}

22.括号生成

对检验函数的处理思路：

模拟了我们正常人脑检验括号时采用的消去法，即一个左括号和一个右括号能抵消，统计左右括号的个数，保证左括号的个数不小于右括号的个数即可。

字符串数据的处理：

不能用Stringbuffer，因为stringbuffer的处理是连续的，不能返回一个新的集合处理。

• 回溯：

   List<String> res=new ArrayList<String>();public List<String> generateParenthesis(int n) {
  //        List<String> list=new ArrayList<>();backtracking(new char[2*n],0,res);return res;}boolean check(char []a){ int count=0;for (int i = 0; i <a.length ; i++) {if (a[i]=='(')count++;elsecount--;if (count<0)return false;}return (count==0);}void backtracking(char [] current,int pos,List<String> result){if (pos == current.length) {if (check(current)) {result.add(new String(current));}} else {current[pos] = '(';backtracking(current, pos + 1, result);current[pos] = ')';backtracking(current, pos + 1, result);}}
  

17.电话号码的字母组合

• 回溯：

  数据的处理需要花时间想想，回溯的部分还是比较基础的

  先采用hashmap集合来将我们要用的abc这样的字符放进去，

  看来stringbuffer也能删除，只是我没用对。deleteCharAt才是真正的删除函数

  static Map<Character,String> map=new HashMap();StringBuffer sb=new StringBuffer();List<String> res=new ArrayList<>();public List<String> letterCombinations(String digits) {map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");int n=digits.length();backtracking(digits,0);return res;}void backtracking(String digits,int index){if (sb.length()==digits.length()){res.add(sb.toString());return;}String val=map.get(digits.charAt(index));for (char  ch:val.toCharArray()) {sb.append(ch);backtracking(digits,index+1);sb.deleteCharAt(sb.length()-1);}}
  

排序

二分

前提我数组必须是已经升序的

时间复杂度O logn

• 模板：

   public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1; // 注意while(left <= right) { // 注意int mid = (left + right) / 2; // 注意if(nums[mid] == target) { // 注意// 相关逻辑} else if(nums[mid] < target) {left = mid + 1; // 注意} else {right = mid - 1; // 注意}}// 相关返回值return 0;}
  

704.二分查找

• 解法：

  public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)/2;if (target==nums[mid])return mid;else if (target>nums[mid]){left=mid+1;}else {right=mid-1;}}return -1;}
  

35.搜索插入位置

• 二分：

  public int searchInsert(int[] nums, int target) {int left=0;int right=nums.length-1;int mid;while (left<=right){mid=(left+right)/2;if (target==nums[mid])return mid;if (target<nums[mid])right=mid-1;if (target>nums[mid]){left=mid+1;}}return left;}
  

动态规划

动规五部曲

- 确定dp数组（dp table）以及下标的含义- 确定递推公式- dp数组如何初始化- 确定遍历顺序- 举例推导dp数组

基础题目

509.斐波那契数

• 动规

  public int fib(int n) {if (n==0)return 0;if (n==1)return 1;int dp[]=new int[n];dp[0]=dp[1]=1;for (int i=2;i<n;i++){dp[i]=(dp[i-1]+dp[i-2])%1000000007;}return dp[n-1];}
  

70.爬楼梯

 public int climbStairs(int n) {if (n==1)return 1;if (n==2)return 2;int dp[]=new int[n+1];dp[1]=1;dp[2]=2;for (int i=3;i<=n;i++){dp[i]=(dp[i-1]+dp[i-2]);}return dp[n];}

746.使用最小花费爬楼梯

/*dp[0]代表吃 dp[1]代表不吃
我觉得这个题的描述应该改改：每个阶梯都有一定数量坨屎，一次只能跨一个或者两个阶梯，走到一个阶梯就要吃光上面的屎，问怎么走才能吃最少的屎？开局你选前两个阶梯的其中一个作为开头点，并吃光该阶梯的屎。
*/public int minCostClimbingStairs(int[] cost) {int n=cost.length;if(n==0)return 0;if(n==1)return cost[0];int [][]dp=new int[n+1][2];dp[1][0]=cost[0];dp[1][1]=0;for(int i=2;i<=n;i++){dp[i][0]=Math.min(dp[i-1][0]+cost[i-1],dp[i-1][1]+cost[i-1]);dp[i][1]=dp[i-1][0];}return Math.min(dp[n][0],dp[n][1]);}

62.不同路径

public int uniquePaths(int m, int n) {int [][]dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(i==1&&j==1){dp[i][j]=1;continue;}dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}

63.不同路径2

public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m=obstacleGrid.length;int n=obstacleGrid[0].length;int [][]dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(obstacleGrid[i-1][j-1]==1){dp[i][j]=0;continue;}if(i==1&&j==1){dp[i][j]=1;continue;}dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}

343.整数拆分

对于的正整数 nn，当 n \ge 2n≥2 时，可以拆分成至少两个正整数的和。令 kk 是拆分出的第一个正整数，则剩下的部分是 n-kn−k，n-kn−k 可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

 public int integerBreak(int n) {int [] dp=new int [n+1];dp[0]=dp[1]=1;for(int i=2;i<=n;i++){int curmax=0;for(int j=1;j<i;j++){curmax=Math.max(curmax,Math.max(j*(i-j),j*dp[i-j]));dp[i]=curmax;}}return dp[n];}

96.不同的二叉搜索树

1开头的情况、2开头的情况、3开头的情况。。。以此类推

 public int numTrees(int n) {//表示下标为i的ansint []dp =new int[n+1];dp[0]=1;dp[1]=1;for(int i=1;i<=n;i++){int size=0;for(int j=1;j<=i;j++){size+=dp[j-1]*dp[i-j];}dp[i]=size;}return dp[n];}

t [][]dp=new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(i1&&j1){
dp[i][j]=1;
continue;
}
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}

#### 63.不同路径2~~~java
public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m=obstacleGrid.length;int n=obstacleGrid[0].length;int [][]dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(obstacleGrid[i-1][j-1]==1){dp[i][j]=0;continue;}if(i==1&&j==1){dp[i][j]=1;continue;}dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}

343.整数拆分

对于的正整数 nn，当 n \ge 2n≥2 时，可以拆分成至少两个正整数的和。令 kk 是拆分出的第一个正整数，则剩下的部分是 n-kn−k，n-kn−k 可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

 public int integerBreak(int n) {int [] dp=new int [n+1];dp[0]=dp[1]=1;for(int i=2;i<=n;i++){int curmax=0;for(int j=1;j<i;j++){curmax=Math.max(curmax,Math.max(j*(i-j),j*dp[i-j]));dp[i]=curmax;}}return dp[n];}

96.不同的二叉搜索树

1开头的情况、2开头的情况、3开头的情况。。。以此类推

 public int numTrees(int n) {//表示下标为i的ansint []dp =new int[n+1];dp[0]=1;dp[1]=1;for(int i=1;i<=n;i++){int size=0;for(int j=1;j<=i;j++){size+=dp[j-1]*dp[i-j];}dp[i]=size;}return dp[n];}