【力扣刷题】_剑指&Top100复习

剑指&Top100复习

面试题2.实现singleton模式

• 单例模式

• 类加载机制

• 代码：

  /**
   * 单例模式(饿汉模式)
   */
  class Singleton{
      //构造方法的首字母需要大写。
      private Singleton(){}
  
      private static Singleton singleton = new Singleton();
  
      public static Singleton getSingleton() {
          return singleton;
      }
  }
  
  /**
   * 静态内部类(懒汉模式)
   */
  class Case2{
      private Case2(){}
  
      private static class InternClass{
          private static Case2 singleton = new Case2();
      }
  
      //只有在需要使用时，调用了getSingleton()方法，静态内部类才会被JVM加载，才会创建该Case2类的单例。
      public static Case2 getSingleton() {
          return InternClass.singleton;
      }
  }

• 一个类加载时，其内部的静态内部类与静态代码块和静态变量不同，静态代码块并不会被加载，静态内部类的方法或属性被调用时它才会被加载。

面试题10_1.斐波那契数列

• 使用动态规划而不用递归

• 代码：

  /**
   * 优化的动态规划
   */
  class Solution10_1 {
      public int fib(int n) {
          int dp1 = 0;
          int dp2 = 1;
          int temp = 0;
          for (int i = 0; i < n; i++) {
  
              //当n很大的时候可能会出现数字溢出，所以我们需要用结果对1000000007求余。
              temp = (dp1 + dp2) % 1000000007;
              dp1 = dp2;
              dp2 = temp;
          }
          return dp1;
      }
  }

面试题11.旋转数组的最小数字

• 重要：这道题的数组中可以包含相等元素，比不包含相等元素要难得多。
• 一定要注意，二分法中将中间点数值与左边界数值还是右边界数值比较是有不同意义的，在做题时可以尝试比较两者区别，选择更加合适比较方式。

面试题12.矩阵中的路径

• 本题中记忆化标记矩阵的回溯代码很容易忘记写，一定不能忘了。深度优先遍历时，一条路走不通了换另一条路时一定要先回溯。

面试题13.机器人的运动范围

• 就是遍历矩阵，判断每个格子是否有符合计算要求，并且左边或者上面的格子能够到达。

面试题14_1.剪绳子

• 高数推导得出：所有绳段长度都为3时乘积最大

• 也可以用动态规划的方法，这不过这种动态规划每次求一个状态值都需要用到前面所有的状态值。

• 代码：

  /**
   * 动态规划
   */
  class Solution14_1{
      public int result(int length) {
          int[] dp = new int[length + 1];
  
          dp[2] = 1;
          dp[3] = 2;
  
          for (int i = 4;i < length + 1;i++) {
              for (int j = 2;j <= length / 2;j++) {
                  dp[i] = Math.max(dp[i],Math.max(j,dp[j]) * Math.max(i - j,dp[i - j]));
              }
          }
  
          return dp[length];
      }
  }

面试题14_2.剪绳子2

• 本题中要求每次乘3之后都要取模，所以不能直接用Math.pow方法直接一下求出double类型结果。但是int类型的取值范围为-2147483648~+2147483647，计算结果有可能直接在一次乘3之后直接溢出了，这样就会导致这个计算结果错误。所以此处我们设置结果数据类型为long或者double，一次一次乘3的计算，每次乘3后都取模。

面试题15.二进制中1的个数

• 将树值与1进行与位运算（&），可以得到该数二进制形式的最低位；
• 将数值无符号右移（>>>），直到为零。

面试题16.数值的整数次方

• 递归+二分法

面试题17.打印从1到最大的n位数（未解决）

• 递归：个位从0到9，十位从0到9…这样一位一位的确认。

面试题18.删除链表的节点

• 双指针：两个指针分别指向相邻的两个节点。

面试题19.正则表达式匹配（非常重要）（未解决）

面试题21.调整数组顺序使奇数位于偶数前面

• 双指针：左右指针分别指向头尾，左指针一旦遇到偶数就与右指针交换数值，并将右指针左移一位。

面试题22.链表中倒数第k个节点

• 双指针：前后指针相隔k-1个节点，前指针到达队尾时，后指针即为所求。

面试题24.反转链表

• 三指针：也就是迭代的一个一个反转节点的指向。

面试题26.树的子结构

• 递归：两个递归方法的组合，太妙了。一个递归方法用于前序遍历，并一个递归方法用于比较两棵树。

• 代码：

  /**
   * 递归前序遍历
   */
  class Solution26 {
      public boolean isSon(TreeNode a,TreeNode b) {
          if (a == null || b == null) return false;
          return isEquel(a,b) || isSon(a.left,b) || isSon(a.right,b);
      }
      
      //注意这个方法并不是真的判断a、b是不是相同，而是判断b是不是与a的顶端几层相同。
      public boolean isEquel(TreeNode a,TreeNode b) {
          if (b == null) return true;
          if (a == null) return false;
          if (a.val != b.val) return false;
          return isEquel(a.left,b.left) && isEquel(a.right,b.right);
      }
  }

面试题31.栈的压入弹出序列（巧思）

• 辅助栈模拟：就是创建一个辅助栈来真正模拟该栈，将入栈队列依次压入栈中，每压入一个元素，检验出栈队列是否需要将栈顶元素出栈。若执行完上述操作之后，辅助栈正好为空，说明此出栈队列可以对应上入栈队列。

面试题32_2.从上到下打印二叉树2

• 层序遍历二叉树，并将所有节点分好层：要解决这个问题就是在常规层序遍历的基础之上再加一层循环。每次计算队列的长度，以此为循环次数。

面试题32_3.从上到下打印二叉树3

• 与分层层序遍历相比，本题使用链表的双端链表特性来保存每层的数据。比如将结果添加到结果集的第一层时正常使用add()方法，而添加第二层时则使用addLast()方法。

面试题33.二叉搜索树的后序遍历序列（巧思）

• 递归：一个二叉搜索树的后序遍历结果的格式一定是 [ 小于根节点的节点，大于根节点的节点，根节点 ] 。

面试题34.二叉树中和为某一值的路径

• 递归回溯法一定要己得回溯，我第二次做的时候仍然忘了回溯。

面试题36.二叉搜索树与双向链表（未解决）

• 递归中序遍历

• 代码

  /**
   * 中序遍历递归
   * 二叉搜索树中序遍历得到的就是递增数组。
   */
  class Solution36 {
  
      //前驱节点
      TreeNode pre;
      //哑节点
      TreeNode god = new TreeNode(0);
  
      public TreeNode change (TreeNode root) {
          if (root == null) return null;
          dfs(root);
          pre.right = god.right;
          god.right.left = pre;
          return god.right;
      }
  
      //该递归方法可以将输入的二叉搜索树转变为双向链表，头节点左指针指向null，尾节点右指针指向null
      public void dfs (TreeNode head) {
          if (head == null) return;
  
          dfs(head.left);
  
          if (pre == null) god.right = head;
          else pre.right = head;
          head.left = pre;
          pre = head;
  
          dfs(head.right);
  
      }
  }

面试题37.序列化二叉树

• 二叉树层序遍历结果唯一的方法：只要把二叉树中度为0和1的节点都补上值为null的辅助空子节点，得到的层序遍历结果就可以与一棵唯一的二叉树对应。
• 反序列化需要借助辅助队列来实现，每次为一个节点创建左右子节点之后就放入队列中，然后循环弹出队列中的元素为其添加左右子节点。

面试题38.字符串的排列

• 递归回溯；
• 通过排序去除重复；
• 使用一个标记数组，用来标记哪些字符已经使用过了。

面试题40.最小的k个数（非常重要）

• 堆排序：使用大根堆而不是小根堆。
• 快速排序

面试题41.数据流中的中位数（巧思）

• 使用一个最大堆和一个最小堆共同组成数据结构；
• 每次添加数据要保证新数据与最大堆和最小堆中数据都比较过。

面试题43.前n个整数中1出现的次数（巧思）

• 分别计算个、十、百每一位中1出现的次数；
• 分三个部分高位high、当前位curr、低位low，按curr的不同情况计算每一位1出现的次数。

面试题44.数字序列中某一位的数字（巧思）（未解决）

面试题45.把数组排成最小的数（巧思）

• 这道题本质上是一个排序问题，需要借助JDK的Arrays工具类的sort()方法，排序规则为：取出任意两个元素a和b，如果ab小于ba则应该将a放在b前面。

面试题46.把数字翻译成字符串

• 动态规划

面试题47.礼物的最大价值

• 这是一个路径问题，是一个很典型的动态规划问题，一般看到路径问题首先就要想到动态规划。
• 优化思路：反正原矩阵中的元素只需要在计算该格状态时使用一次，所以直接在原矩阵的格子中记录状态。

面试题48.最长不含重复字符的子字符串

• 使用HashSet辅助的滑动窗口。

面试题49.丑数（巧思）

• 特殊的动态规划，特别巧妙的思路。

面试题50.第一个只出现一次的字符

• 不要想得太复杂，用HashMap辅助，key为字符值，value为字符出现次数；遍历字符串两遍，第一遍将字符存入哈希表，第二遍找到第一个只出现一次的字符。

面试题51.数组中的逆序对（非常重要）（未解决）

• 归并排序

面试题53_2.前n个数中缺失的数字（巧思）

• 二分查找：注意不要把此题和原地置换的题目搞混了，题目看起来很像。

面试题54.二叉搜索树的第k大节点

• 先右后左的中序遍历到第k个值

面试题55_1.二叉树的深度

• 递归回溯法，一定要记得回溯深度值。

面试题55_2.平衡二叉树（巧思）

• 记忆化递归

面试题56_1.数组中数字出现的次数（巧思）

• 异或 位运算：这个思路太强了，就是根据数字的二进制格式的某一位为0或1，将数组分成两组，两组分别全员异或得到的即为两个只出现一次的数字。

面试题56_2.数组中数字出现的次数2（巧思）

• 位运算：对于出现三次的数字，各二进制位出现的次数都是 3 的倍数。因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
• 用无符号右移>>>和左移<<<。

面试题57_2.和为s的连续正数序列（巧思）

• 滑动窗口：两指针都只能往右移，当窗口总值小于目标值时右指针右移，窗口总值小于或等于目标值时左指针右移。
• 使用连续整数和的计算公式：首项加末项乘以项数除以二。

面试题58_1.翻转单词顺序

• 双指针从后往前一个个找到单词。

面试题59_1.滑动窗口的最大值（巧思）

• 辅助双端队列：在该队列中保存滑动窗口中的递减序列。

面试题59_2.队列的最大值（巧思）

• 想要随时获得栈中的最大、最小值，就需要辅助栈，容量与主栈始终相等；
• 想要随实获得队列中的最大、最小值，就需要辅助双端队列，保存主队列中的单调序列，把非单调部分都去掉了。

面试题60.n个骰子的点数（非常重要）

• 背包问题：使用动态规划，n个筛子和为j的情况数是n-1个筛子和为6中不同情况数的总和。

面试题61.扑克牌中的顺子（巧思）

• 不要从正面找，从反面找不是顺子的情况，那么反面主要有两类：有重复数字、最大值-最小值>=5。

面试题62.圆圈中最后剩下的数字（非常重要）（巧思）

• 递归：这道题非常好得运用到了递归的本质：我们已经知道了上一步递归的结果，我们只需要使用上一步递归的结果来辅助实现本层的逻辑即可，不需要考虑上一步递归内部到底是怎样实现的。

面试题64.求前n个正整数之和（巧思）

• 递归

面试题65.不用加减乘除做加法（非常重要）（巧思）

• 位运算&得到的结果再左移一位，得到的就是两数相加时每个二进制位上的进位；位运算^得到的结果就是排除进位后，两个二进制数在每一位上的和。那么上述得到的进位结果和不进位和相加就是两数真正的相加和，而要求到进位结果与不进位和的相加和又要重复上述步骤，所以要不断迭代这个过程直到进位结果为0为止。

面试题66.构建乘积数组（巧思）

• 动态规划：第一次遍历求出每个元素对应的左边所有元素乘积，第二次遍历再乘上每个元素对应右边所有元素乘积。

面试题68_1.二叉搜索树的最近公共祖先

• 递归：运用二叉搜索数的特性简单很多

面试题68_2.二叉树的最近公共祖先

• 有返回值的递归方法是非常强大的

【力扣刷题】_1.两数之和

• HashMap的key保存元素值，value保存元素在数组中的索引。

【力扣刷题】_3.无重复字符的最长子串

• 滑动窗口+HashSet

【力扣刷题】_4.寻找两个正序数组的中位数

• 迭代合并数组，再找中位数。

【力扣刷题】_5.最长回文子串

• 中心扩散法：涉及到回文串，都用中心扩散法好一点。

【力扣刷题】_10.正则表达式匹配(非常重要)（未解决）

• 动态规划：dp[i][j]表示两个字符串的前i个字符和前j个字符是否正则匹配。

【力扣刷题】_11.盛最多水的容器（巧思）

• 双指针：初始时，双指针分别指向数组左右两端，计算盛水面积，每次向内移动两指中较小的那一个，直到两指针重合。这样移动指针可以保证我们不会错过每一个更大的盛水面积。

【力扣刷题】_15.三数之和

• 排序+双指针

【力扣刷题】_20.有效的括号（非常重要）（巧思）

• 方法一栈：当遇到匹配的括号则一起出栈，最后栈为空则说明正好配对成功。
• 方法二：见【力扣刷题】_22.括号生成。

【力扣刷题】_22.括号生成

• 递归回溯+枝剪
• 一种新的判断字符串是否有效的方法：
  • 每一个包含第一个括号的子序列中左括号个数不能小于右括号个数，因为无论后面再加上多少个左括号，都不能和前面多出来的右括号配对相消；
  • 总的左右括号个数一定要相等。

【力扣刷题】_23.合并K个升序链表（巧思）

• 分治合并：其实原理就和归并排序一样，只不过这个相当于已经分割好了，只需要进行后面的合并。

【力扣刷题】_31.下一个排列（巧思）

• 字典序的概念
• 思路很巧妙：第一步先从后往前找到第一个递减元素，然后找到后面比它大的元素中最小的一个元素，交换这两个元素位置；第二部将后面的递减数组反转成递增数组。

【力扣刷题】_32.最长有效括号

• 动态规划

【力扣刷题】_33.搜索旋转排序数组

• 二分搜索：与正常二分搜索差不多，一直判断在中点左边还是右边，只不过判断条件不同。

【力扣刷题】_39.组合总和

• 递归回溯：本题关键在于去除重复，所以最开始把数组排序，并在递归中设置好循环条件使得只能升序添加元素。

【力扣刷题】_42.接雨水（巧思）

• 遍历数组找出数组中每个数左边（包括该数自己）的最大值，在遍历找出每个数右边的最大值，这样就能计算每一列所能储存的雨水，然后加起来。每一列所能储存的雨水取决于它左右两边最高的列中更低的那一列。

【力扣刷题】_46.全排列

• 递归回溯：使用一个mark数组标记使用过的元素，这个mark数组也要记得回溯。

【力扣刷题】_49.字母异位词分组（巧思）

• 将字符串的字符重新排序后进行比较，看是不是字母异位词。
• 用HashMap的一个List类型的value来保存同一组字母异位词。

【力扣刷题】_55.跳跃游戏（巧思）

• 方法一动态规划：状态dp[i]表示能否到达索引为i的元素，每次计算dp[i]需要遍历一次前面所有的状态值，所以时间复杂度为O(n^2)。
• 方法二动态规划：状态dp[i]表示从索引为i的元素所能跳到的最远距离，dp[i] = nums[i]+i。

【力扣刷题】_56.合并区间（巧思）

• 先将各个区间按左边界正序排列，然后依次判断每两个相邻区间需不需要合并，需要合并则将第二个区间改为合并后区间，不需要合并则将第一个区间放入结果列表。

【力扣刷题】_72.编辑距离（非常重要）（巧思）

• 动态规划：其实使两个字符串相同的操作总结下来就是三个：在A中插入一个字符、在B中插入一个字符、修改A中的一个字符。

【力扣刷题】_75.颜色分类（巧思）

• 双指针：也可以说是三指针。

【力扣刷题】_76.最小覆盖子串（巧思）

• 滑动窗口：右指针先向后移动直到覆盖子串，左指针再向后移动直到即将不再覆盖子串，记录长度；然后将左指针后移一步，再循环上述步骤，比较得到最小覆盖子串。

【力扣刷题】_78.子集（非常重要）

• 递归回溯：本题的关键在于不考虑子集的顺序，所以需要通过设置好循环条件排除元素相同、顺序不同的情况。

• 代码

  class Solution {
      public List<List<Integer>> subsets(int[] nums) {
          List<List<Integer>> ans = new ArrayList<>();
          ans.add(new ArrayList<>());
          List<Integer> answer = new ArrayList<>();
  
          dfs(ans,answer,nums,0);
          return ans;
      }
  
      public void dfs(List<List<Integer>> ans,List<Integer> answer,int[] nums,int index) {
          for (int i = index; i < nums.length; i++) {
              answer.add(nums[i]);
  
              ans.add(new ArrayList<>(answer));
  
              dfs(ans,answer,nums,i + 1);
  
              answer.remove(answer.size() - 1);
          }
      }
  }

【力扣刷题】_84.柱状图中最大的矩形（非常重要）（巧思）

• 单调栈：本题和42.接雨水思路很像，从左往右和从右往左的两次遍历分别记录两个数组，只不过本题记录的是每个柱形两边首个比它矮的柱形的位置，所以需要单调栈来辅助记录。

• 代码

  class Solution0084 {
      public int largestRectangleArea(int[] heights) {
          int n = heights.length;
          int[] left = new int[n];
          int[] right = new int[n];
  
          Stack<Integer> stack = new Stack<>();
  
          //比较得出每个柱形左边第一个比它矮的柱形的位置；
          for (int i = 0; i < n; i++) {
              while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                  stack.pop();
              }
              if (stack.isEmpty()) {
                  left[i] = -1;
                  stack.push(i);
              }else {
                  left[i] = stack.peek();
                  stack.push(i);
              }
          }
  
          stack.clear();
          //比较得出每个柱形左边第一个比它矮的柱形的位置；
          for (int i = n - 1; i >= 0; i--) {
              while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                  stack.pop();
              }
              if (stack.isEmpty()) {
                  right[i] = n;
                  stack.push(i);
              }else {
                  right[i] = stack.peek();
                  stack.push(i);
              }
          }
  
          int ans = 0;
          for (int i = 0; i < n; i++) {
              ans = Math.max(ans,heights[i] * (right[i] - left[i] - 1));
          }
          return ans;
      }
  }

【力扣刷题】_85.最大矩形（巧思）

• 单调栈+动态规划：就是84.柱状图中最大的矩形的二维升级，注意一定要把一行中所有柱形的高度都先计算出来，再进行单调排序。

• 代码

  class Solution0085 {
      public int maximalRectangle(char[][] matrix) {
          int n = matrix.length;
          int m = matrix[0].length;
  
          int[] heights = new int[m];
          int[] left = new int[m];
          int[] right = new int[m];
  
          Stack<Integer> stack = new Stack<>();
  
          int ans = 0;
  
          for (int i = 0; i < n; i++) {
              //注意一定要把一行中所有柱形的高度都先计算出来，再进行单调排序
              for (int j = 0; j < m; j++) {
                  heights[j] = matrix[i][j] == '0' ? 0 : (1 + heights[j]);
              }
  
              stack.clear();
              for (int j = 0; j < m; j++) {
                  while (!stack.isEmpty() && heights[stack.peek()] >= heights[j]) {
                      stack.pop();
                  }
                  if (stack.isEmpty()) {
                      left[j] = -1;
                      stack.push(j);
                  }else {
                      left[j] = stack.peek();
                      stack.push(j);
                  }
              }
  
              stack.clear();
              for (int j = m - 1; j >= 0; j--) {
                  while (!stack.isEmpty() && heights[stack.peek()] >= heights[j]) {
                      stack.pop();
                  }
                  if (stack.isEmpty()) {
                      right[j] = m;
                      stack.push(j);
                  }else {
                      right[j] = stack.peek();
                      stack.push(j);
                  }
              }
  
              for (int j = 0; j < m; j++) {
                  ans = Math.max(ans,(right[j] - left[j] - 1) * heights[j]);
              }
          }
  
          return ans;
      }
  }

【力扣刷题】_96.不同的二叉搜索树（巧思）

• 动态规划：二叉搜索数的特点是左子孙节点一定都小于根节点，右子孙节点一定都大于根节点，所以只要是单调固定个数的数值，其所能组成的不同二叉搜索树的种数也是固定的。所以将每个数作为根节点的情况累加起来即为结果。其实这种思路一定程度上用到了递归的思想。

• 代码

  class Solution0096 {
      public int numTrees(int n) {
          int[] dp = new int[n + 1];
          dp[0] = 1;
          dp[1] = 1;
  
          for (int i = 2; i <= n; i++) {
              for (int j = 1; j <= i; j++) {
                  dp[i] = dp[i] + dp[j - 1] * dp[i - j];
              }
          }
  
          return dp[n];
      }
  }

【力扣刷题】_101.对称二叉树

• 递归：给定两个指针始终沿着相反方向前进。
• 注意：两颗二叉树的中序遍历结果相同并不能保证两个树相同，因为不同二叉树可能有相同中序遍历结果。

【力扣刷题】_102.二叉树的层序遍历

• 广度优先遍历：使用一个辅助队列，每次遍历完一层的节点时，队列的长度正好是下一层节点的个数。

• 代码

  class Solution0102 {
      public List<List<Integer>> levelOrder(TreeNode root) {
          List<List<Integer>> ans = new ArrayList<>();
          Queue<TreeNode> queue = new LinkedList<>();
  
          queue.add(root);
          while (!queue.isEmpty()) {
              int length = queue.size();
              List<Integer> list = new ArrayList<>();
              for (int i = 0; i < length; i++) {
                  TreeNode node = queue.remove();
                  list.add(node.val);
                  if (node.left != null) {queue.add(node.left);}
                  if (node.right != null) {queue.add(node.right);}
              }
              ans.add(list);
          }
          return ans;
      }
  }

【力扣刷题】_114.二叉树展开为链表（非常重要）（巧思）

• 递归：从上到下，将每个节点的右子树砍下放到其前驱结点的右子树位置，然后将左子树砍下放到其右子树位置。

• 寻找前驱节点：其实前驱节点很好找，也是用递归，先进入左子树，然后一直往右走到最后一个节点即为前驱节点。

• 代码

  class Solution {
      public void flatten(TreeNode root) {
          if (root == null) {return;}
          if (root.left != null) {
              TreeNode preNode = findPreNode(root.left);
              preNode.right = root.right;
              root.right = root.left;
              root.left = null;
          }
          flatten(root.right);
      }
  
      public TreeNode findPreNode(TreeNode node) {
          if (node.right == null) {
              return node;
          }
          else {
              return findPreNode(node.right);
          }
      }
  }

【力扣刷题】_122.买卖股票的最佳时机2（巧思）

• 动态规划：创建两个动态规划数组，一个表示当天结束时持有股票的最大收益，另一个表示当天结束时不持有股票的最大收益。

• 代码

  class Solution0122 {
      public int maxProfit(int[] prices) {
          int n = prices.length;
  
          int dp0 = -prices[0];
          int dp1 = 0;
  
          for (int i = 1; i < n; i++) {
              dp0 = Math.max(dp0,dp1 - prices[i]);
              dp1 = Math.max(dp1,dp0 + prices[i]);
          }
  
          return dp1;
      }
  }

【力扣刷题】_123.买卖股票的最佳时机3（巧思）

• 动态规划：这个动态规划要是没有前面一题真是打死也想不到，创建四个动态规划数组，第一个表示当天结束时是第一次持有股票的最大收益，第二个表示当天结束时是第一次卖出股票的最大收益，第三个表示当天是第二次持有股票的最大收益，第四个表示当天结束时是第二次卖出股票的最大收益。

• 代码

  class Solution0123 {
      public int maxProfit(int[] prices) {
          int n = prices.length;
  
          int buy0 = -prices[0],sell0 = 0;
          int buy1 = -prices[0],sell1 = 0;
  
          for (int i = 1; i < n; i++) {
              buy0 = Math.max(buy0,-prices[i]);
              sell0 = Math.max(sell0,buy0 + prices[i]);
              buy1 = Math.max(buy1,sell0 - prices[i]);
              sell1 = Math.max(sell1,buy1 + prices[i]);
          }
  
          return sell1;
      }
  }

【力扣刷题】_128.最长连续序列（巧思）

• 不能用排序，排一下序时间复杂度就O(nlogn)了，这里要灵活运用HashSet的增删查复杂度都为O(1)的性质。

• 代码

  class Solution1 {
      public int longestConsecutive(int[] nums) {
          //Set为不含重复元素的集合，java中常用HashSet来实现。
          Set<Integer> numbers = new HashSet<>();
          for (int num : nums) {
              numbers.add(num);
          }
  
          int ans = 0;
  
          for (int num : numbers) {
              //HashSet.contains()方法的时间复杂度为O(1)。
              if (!numbers.contains(num - 1)) {//表示该元素为一个连续序列的起点，而不是中间一个点。
                  int length = 1;
                  while (numbers.contains(num + length)) {
                      length++;
                  }
                  ans = Math.max(ans,length);
              }
          }
          return ans;
      }
  }

【力扣刷题】_139.单词拆分（巧思）

• 动态规划：状态dp[i]表示前i个字符所组成的字符串是否可拆分，计算该状态值时需要用到前面每一个状态值。

• HashSet：使用set来判断数组是否包含某元素，往往能将复杂度降低一个n级别。

• 代码

  public class leetcode0139 {
      public boolean wordBreak(String s, List<String> wordDict) {
          Set<String> set = new HashSet<>(wordDict);
  
          //dp[i]表示前i个字符是否可以拆分为字典中单词
          boolean[] dp = new boolean[s.length() + 1];
  
          dp[0] = true;
  
          for (int i = 1; i <= s.length(); i++) {
              for (int j = 0; j < i; j++) {
                  //s.substring(j,i)每次都是一个从未出现过的字符串，时间复杂度没法再降低了。
                  if (dp[j] && set.contains(s.substring(j,i))){
                      dp[i] = true;
                      break;
                  }
              }
          }
          return dp[s.length()];
      }
  }

【力扣刷题】_141.环形链表（巧思）

• 双指针：设置快慢指正一直往后走直到为空，如果两指针相遇则为环形链表。

【力扣刷题】_142.环形链表加强（巧思）

• 双指针：这里其实是三指针法，当快慢指针相遇时，此时第三个指针从头部出发，同时慢指针继续前进，当两者相遇时，根据数学计算可得，它们相遇的点即为入环节点。计算过程详见官网答案，很精妙，由a+n(b+c)+b=2(a+b)得到a=(n-1)(b+c)+c。
• 快指针的速度是慢指针的两倍，所以慢指针不可能走完一圈还没被快指针追上。

【力扣刷题】_146.LRU缓存机制

• HashMap+双向链表
• 双向链表节点必须自己定义
• LRU底层结构为一个HashMap、size、capacity、伪头结点、伪尾结点，初始化时必须定义这两个伪节点，用来定位双向链表的头尾。

【力扣刷题】_152.乘积最大子数组（巧思）

• 动态规划：因为存在负负得正的情况，所以本题应创建两个状态队列，一个保存以第i个字符结束的最大乘积，一个保存以第i个字符结束的最小乘积。

• 代码

  public class leetcode0152 {
      public int maxProduct(int[] nums) {
          int large = nums[0];
          int small = nums[0];
          int ans = large;
          int temp = large;
  
          for (int i = 1; i < nums.length; i++) {
              temp = large;
              large = Math.max(Math.max(nums[i],large * nums[i]),small * nums[i]);
              small = Math.min(Math.min(nums[i],temp * nums[i]),small * nums[i]);
              ans = Math.max(ans,large);
          }
          return ans;
      }
  }

【力扣刷题】_160.相交链表（巧思）

• 双指针：一个遍历A+B，一个遍历B+A，当两指针同时为null则说明两链表并不相交。

【力扣刷题】_169.多数元素（巧思）

• 摩尔投票法

• 代码

  public class leetcode0169 {
      public int majorityElement(int[] nums) {
          int flag = 0;
          int king = nums[0];
          for (int i = 0; i < nums.length; i++) {
              if (flag == 0) {
                  king = nums[i];
                  flag = 1;
              }else {
                  if (king == nums[i]) {flag++;}
                  else {flag--;}
              }
          }
          return king;
      }
  }

【力扣刷题】_188.买卖股票的最佳时机4（巧思）

• 动态规划：在123.买卖股票的最佳时机3的基础上改写即可。

【力扣刷题】_200.岛屿数量（巧思）

• 递归：岛屿问题最关键的难点就是某节点是否已经遍历过了的判断，此题将所有已经遍历过了的陆地格子的值通过递归改写成’0’。

【力扣刷题】_206.反转链表（非常重要）（巧思）

• 方法一三指针迭代

• 方法二递归（非常体现递归的本质，如果一下就能想出该递归思路，则说明此刻的你对递归理解得很到位。）：本题的关键，将head.next作为递归方法的输入参数之后，head的next属性还是指向原来那个节点的，只不过那个节点现在变成了一个链表的尾端。

【力扣刷题】_207.课程表（非常重要）（巧思）

• 注意此题和399.除法求职都是有向图相关的题目，只不过要解决的问题不同。本题要检查图中是否存在环，所以使用邻接表的方法来解决；399要实现获取有向图中任意两节点之间的权值，所以使用带权并查集的方法来实现。

• 邻接表：维护两个map，分别记录每个节点的入度和所指向的其他节点。然后借助辅助队列，一个一个删除入度为0的节点，并删除指向节点，如果被指向节点入度降为0则将其加入辅助队列，循环上述操作。最后辅助队列为空却还有节点入度不为0，则说明有向图中存在环。

• 代码

  public class leetcode0207 {
      public static boolean canFinish(int numCourses, int[][] prerequisites) {
          Map<Integer, Set<Integer>> map = new HashMap<>();
          Map<Integer,Integer> input = new HashMap<>();
          Queue<Integer> queue = new LinkedList<>();
  
          //保存好每个节点的指向节点和入度
          int n = prerequisites.length;
          for (int i = 0; i < n; i++) {
              if (map.containsKey(prerequisites[i][0])) {
                  map.get(prerequisites[i][0]).add(prerequisites[i][1]);
              }else {
                  Set<Integer> set = new HashSet<>();
                  set.add(prerequisites[i][1]);
                  map.put(prerequisites[i][0],set);
              }
  
              if (input.containsKey(prerequisites[i][1])) {
                  int num = input.get(prerequisites[i][1]);
                  input.put(prerequisites[i][1],num + 1);
              }else {
                  input.put(prerequisites[i][1],1);
              }
          }
  
          //找出所有有向图的头节点
          for (int num: map.keySet()) {
              if (!input.containsKey(num)) {
                  queue.add(num);
              }
          }
  
          //从头节点开始一个一个减
          while (!queue.isEmpty()) {
              int temp = queue.remove();
              if (map.containsKey(temp)) {
                  Set<Integer> set = map.get(temp);
                  for (int num : set) {
                      if (input.get(num) == 1) {
                          input.remove(num);
                          queue.add(num);
                      }else {
                          int x = input.get(num);
                          input.put(num,x - 1);
                      }
                  }
              }
          }
  
          return input.isEmpty();
      }
  }

【力扣刷题】_208.实现Trie前缀树（未解决）

• 创建前缀树节点类，类中主要属性是大小为26的节点数组。

【力扣刷题】_215.数组中的第K个最大元素

• 堆排序

• 代码

  public class leetcode0215 {
      public static int findKthLargest(int[] nums, int k) {
          int n = nums.length;
  
          PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
              @Override
              public int compare(Integer o1, Integer o2) {
                  return o2 - o1;
              }
          });
  
          for (int i = 0; i < n; i++) {
              queue.add(nums[i]);
          }
  
          for (int i = 0; i < k - 1; i++) {
              queue.poll();
          }
  
          return queue.poll();
      }
  }

【力扣刷题】_221.最大正方形（巧思）

• 动态规划：状态dp[i][j]为以该索引位置点为右下角的最大正方形的边长，该状态值取决于上、左、左上三个点的值中的最小值。

• 测试可以发现，封装类Integer、Boolean等初始化时不会赋初值，而是直接为null。基本数据类型int、boolean等初始化时会赋初值，比如0、false等。

• 代码

  public class leetcode0221 {
      public int maximalSquare(char[][] matrix) {
          int n = matrix.length;
          int m = matrix[0].length;
          int ans = 0;
  
          int[][] edge = new int[n][m];
          for (int i = 0; i < m; i++) {
              if (matrix[0][i] == '1') {
                  edge[0][i] = 1;
                  ans = Math.max(ans,edge[0][i]);
              }
          }
          for (int i = 1; i < n; i++) {
              if (matrix[i][0] == '1') {
                  edge[i][0] = 1;
                  ans = Math.max(ans,edge[i][0]);
              }
          }
  
          for (int i = 1; i < n; i++) {
              for (int j = 1; j < m; j++) {
                  if (matrix[i][j] == '1') {
                      edge[i][j] = Math.min(Math.min(edge[i - 1][j - 1],edge[i - 1][j]),edge[i][j - 1]) + 1;
                      ans = Math.max(ans,edge[i][j]);
                  }
              }
          }
          return ans * ans;
      }
  
      //测试可以发现，封装类Integer、Boolean等初始化时不会赋初值，而是直接为null。
      //基本数据类型int、boolean等初始化时会赋初值，比如0、false等。
      public static void main(String[] args) {
          int[][] ans1 = new int[2][2];
          Integer[][] ans2 = new Integer[2][2];
  
          boolean[][] ans3 = new boolean[2][2];
          Boolean[][] ans4 = new Boolean[2][2];
          return;
      }
  }

【力扣刷题】_234.回文链表（巧思）

• 方法一辅助栈：先使用快慢指针找到链表中点，在寻找中点过程中将链表节点存入栈中，直到到达中点。

• 方法二反转链表：先使用快慢指针找到链表中点，在寻找中点过程中反转前半段链表，然后双指针从中点分别往左右出发，判断是否回文。

【力扣刷题】_236.二叉树的最近公共祖先（巧思）

• 递归：本题需要我们依靠自己的智慧去定义当该方法返回值为null时代表什么，此处我们定义当该方法返回null时表示p、q全都不在该二叉树root中。（这个还是太难想了，真正拿到可能还是会用自己想得递归方法）

• 代码：

  public class leetcode0236 {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          if (root == p || root == q) return root;
          if (root == null) return null;
  
          if (lowestCommonAncestor(root.left,p,q) == null) return lowestCommonAncestor(root.right,p,q);
          if (lowestCommonAncestor(root.right,p,q) == null) return lowestCommonAncestor(root.left,p,q);
  
          //以上两种情况都不符合，则说明两个目标节点分别分布在左右子树中，最近公共祖先即为该根节点。
          return root;
      }
  }

【力扣刷题】_239.滑动窗口最大值（巧思）

• 辅助双端队列：使用双端队列记录窗口中数值从大到小的序列，滑动窗口每次滑动，按固定规则处理双端队列的头尾，使得窗口每次滑动后双端队列尾部都是窗口中的最大值。

• 代码：

  public class leetcode0239 {
      public int[] maxSlidingWindow(int[] nums, int k) {
          Deque<Integer> deque = new LinkedList<>();
          int n = nums.length;
          int[] ans = new int[n - k + 1];
  
          for (int i = 0; i < k; i++) {
              while (!deque.isEmpty() && deque.peekFirst() < nums[i]) {
                  deque.pollFirst();
              }
              deque.addFirst(nums[i]);
          }
  
          ans[0] = deque.peekLast();
          for (int i = k; i < n; i++) {
              if (deque.peekLast() == nums[i - k]) {
                  deque.pollLast();
              }
              while (!deque.isEmpty() && deque.peekFirst() < nums[i]) {
                  deque.pollFirst();
              }
              deque.addFirst(nums[i]);
              ans[i - k + 1] = deque.peekLast();
          }
          return ans;
      }
  }

【力扣刷题】_279.完全平方数（巧思）

• 动态规划：典型的背包问题，具体见背包问题专题。

【力扣刷题】_297.二叉树的序列化与反序列化（巧思）

• 层序遍历+辅助队列：序列化时将每个实际存在的节点的null子节点全部加入序列中；
• 层序遍历+辅助队列：反序列化时也要用到辅助队列，不过在反序列化时null节点不得放入队列中。每次从队列头部中取出一个节点时，数组指针接下来所指的两个元素就刚好是该节点的子节点，这时如果这两个子节点不为空则将它们加入队列，并放到刚取出节点的左右子节点位置。然后接着循环进行以上操作，直到队列为空。

【力扣刷题】_300.最长递增子序列（巧思）

• 动态规划：计算每个状态值时，需要用到前面每一个状态值。其实就是计算每个状态值时，需要将该数与前面的每一个数比较一次大小。

【力扣刷题】_301.删除无效的括号（巧思）

• 递归回溯+枝剪：使用【力扣刷题】_20.有效的括号中的方法二中的两个条件来进行枝剪。

【力扣刷题】_309.最佳买卖股票时机含冷冻期（巧思）

• 动态规划：把买入股票看作亏钱，卖出股票看作赚钱，主要考虑三种状态，持有股票、冷冻期、卖出了股票且非冷冻期。

【力扣刷题】_312.戳气球（未解决）

【力扣刷题】_322.零钱兑换

• 背包问题

【力扣刷题】_337.打家劫舍3（巧思）

• 动态规划思路+递归：沿用了198.打家劫舍的解题思路，其实就相当于将状态看成偷窃每一层的金额。

【力扣刷题】_338.比特位计数（巧思）

• 方法一暴力法：直接用无符号右移计算每个数的二进制格式中的1的个数。
• 方法二动态规划：状态dp[i]表示数字i的二进制格式中1的数量。位运算i&(i-1)得到的就是将i的二进制表达式从右往左第一个1变成0所表示的数，所以dp[i] = dp[i & (i - 1)] + 1。

【力扣刷题】_394.字符串解码

• 递归：存粹就是体力活，没有太多巧思。

【力扣刷题】_399.除法求值（非常重要）

• 注意本题与【力扣刷题】_207.课程表的区别，虽然都是有向图的数据结构，但是一道是判断有无环形，另一道是计算任意两个节点直接的权值。

• 带权并查集：带权并查集的属性和方法：int[] parent表示每个节点的父节点；double[] weight表示每个节点到父节点的权值；UnionFind()方法为构造方法，设置每个节点的父节点为自己，权值为1.0；find()方法为寻找根节点方法，寻找过程中将该节点进行路径压缩使其直接指向根节点；isConnect()方法用于判断两个节点是否处于同一个集合中，是则可以返回这两个节点之间的权值；union()方法用于将两个节点所在的两个集合合并为同一个集合。

【力扣刷题】_406.根据身高重建队列（巧思）

• 先将原队列按身高排好序，然后按这个顺序一个一个将人插入结果队列中，这样就能保证后插入的人一定高于先插入的人。
• 如果我们在初始时建立一个包含n个位置的空队列，而我们每次将一个人放入队列中时，会将一个「空」位置变成「满」位置，那么当我们放入第i个人时，我们需要给他安排一个「空」位置，并且这个「空」位置前面恰好还有ki个「空」位置，用来安排给后面身高更高的人。也就是说，第i个人的位置，就是队列中从左往右数第ki+1 个「空」位置。

【力扣刷题】_448.找到所有数组中消失的数字（巧思）

• 原地置换升级版：要找到多个不在原位置的数，则需要先把数组中原本存在的数按顺序置换好，再遍历找出小时的数。

【力扣刷题】_494.目标和

• 这是一道背包问题，但是因为目标和可能为负值，所以不好设置状态范围，所以我觉得本题用递归反而更不容易写错。

【力扣刷题】_538.把二叉搜索树转换为累加树（巧思）

• 递归：从右往左中序遍历二叉树，把每个节点之前已遍历的节点之值的和加到该节点上。

【力扣刷题】_560.和为K的子数组（巧思）

• 本题的难点在于数组元素可以为负数，无法使用滑动窗口。
• 枚举：本题推荐直接使用暴力枚举法，枚举左右边界。（虽然也可以使用前缀和的方法来优化，但是优化方法太难想了）

【力扣刷题】_581.最短无序连续子数组（巧思）

• 方法一：可以先排序，然后将排序后的数组与原数组进行比较。
• 方法二：从前往后遍历找到出现降序之后最小的数min，反向遍历找到出现升序之后最大的数max，这两个数就是无序子序列重排之后的起点和终点；那么分别前序找到第一个比min大的数，反向找到第一个比max小的数，这两个数即为无序子序列的起点和终点。

【力扣刷题】_647.回文子串（巧思）

• 中心扩散法：回文子串的题目还是要最先考虑中心扩散法。

【力扣刷题】_714.买卖股票的最佳时机含手续费（巧思）

• 动态规划：不要想得太复杂，还是原来的思路，就是在卖出的同时要减去手续费即可。

【力扣刷题】_739.每日温度（巧思）

• 两个辅助栈：创建两个栈，主栈保存从下到上单调递减的温度数据，辅栈保存主栈中每一个温度在数组中对应的位置索引。