devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣经典题目解法记录（更新中）_给定两个字符s1串和s2,我们的目标是计算出将s1转换成s2所需的最少编辑操作次数。

作者：菜鸟追梦旅行 | 2024-04-26 04:11:33

赞

踩

给定两个字符s1串和s2,我们的目标是计算出将s1转换成s2所需的最少编辑操作次数。


力扣算法题库引用自：https://cloud.tencent.com/developer/article/167101

关于动态规划的几道基本题目：
（子序列：去除某些字符，相对顺序保持不变；子串：截取的）

  1. 最长递增子序列的长度（300 题，背下来思想，背下来解法）
    这个是子序列，不是子串。
    重点：设计dp 数组，dp[i] 为以数字nums[i] 结尾的最长递增子序列的长度。
      
    1.     public int lengthOfLIS(int[] nums) {
    2.  
    3.         if (nums.length ==  0) {
    4.             return 0;
    5.         }
    6.  
    7.         // 定义dp 数组，dp[i] 表示以第i 个数字结尾，最长上升子序列的长度。
    8.         int[] dp = new int[nums.length];
    9.         dp[0] = 1;
    10.         int maxAns = 1;
    11.         // 我们从小到大计算dp 数组的值，在计算dp[i] 之前，我们已经计算出dp[0…i−1] 的值，则状态转移方程为：
    12.         // dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
    13.         for (int i = 1; i < nums.length; i++) {
    14.             dp[i] = 1;
    15.             for (int j = 0; j < i; j++) {
    16.                 if (nums[i] > nums[j]) {
    17.                     dp[i] = Math.max(dp[i], dp[j] + 1);
    18.                 }
    19.             }
    20.             maxAns = Math.max(maxAns, dp[i]);
    21.         }
    22.         return maxAns;
    23.     }
    24.     
    25.     // 时间复杂度O(n^2)
  2. 最大子数组和（53 题，背下来思想，背下来解法）

    设计dp 数组，dp[i] 代表走到nums[i] 的时候，选还是不选，得到的结果是多少
    dp 数组每个元素的含义是以nums[i] （最后一个元素）结尾的最大子数组和。

    dp[i] 定义为数组nums 中以num[i] 结尾的最大连续子串和， 则有dp[i] = max(dp[i-1] + nums[i], num[i]);

    这个的理解其实也比较简单，因为dp 数组代表的就是遍历到了第i 个nums 的数字的时候最大子数组和。所以下面的逻辑也比较好解释了。


      
    1.    public int maxSubArray(int[] nums) {
    2.         if (nums.length == 0) {
    3.             return 0;
    4.         }
    5.         // 状态只能是遍历到nums 数组每个元素的时候，最大和为多少
    6.         int[] dp = new int[nums.length];
    7.  
    8.         dp[0] = nums[0];
    9.         int ans = nums[0];
    10.         for (int i = 1; i < nums.length; i++) {
    11.             // 做判断，选这个数字，还是不选，是加和，还是自己
    12.             dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    13.             ans = Math.max(dp[i], ans);
    14.  
    15.         }
    16.         return ans;
    17.     }
  3. 最大乘积子数组的乘积（152 题，背下来思想，背下来解法）

    因为这道题涉及乘法，乘法是负负得正。所以虽然类似最大子数组和，但是又不太一样
    dp 数组要弄两个，一个是最大的，一个是最小的

    在遍历找ans 的时候，要分别判断nums[i] 和前一个最大的乘积、和前一个最小的乘积、当前值，哪个大或者小，来做最终的更新。
      
    1. public int maxProduct(int[] nums) {
    2.         int length = nums.length;
    3.  
    4.         int[] maxF = new int[length];
    5.         int[] minF = new int[length];
    6.  
    7.         maxF[0] = nums[0];
    8.         minF[0] = nums[0];
    9.  
    10.         int ans = maxF[0];
    11.  
    12.         for (int i = 1; i < length; i++) {
    13.             maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
    14.             minF[i] = Math.min(maxF[i - 1] * nums[i], Math.min(nums[i], minF[i - 1] * nums[i]));
    15.  
    16.             ans = Math.max(ans, maxF[i]);
    17.         }
    18.         return ans;
    19.     }

     
  4. 最小编辑距离（72 题，

    给定两个字符串s1 和s2，计算出将s1 转换成s2 所使用的最少操作数。可以对一个字符串进行如下操作：插入、删除、替换。


    理解：s1 插入或者删除，就是对应s2 的删除或者插入。修改a 或者修改b，其实上都一样。

    本质不同的操作实际上只有三种：

    在单词 A 中插入一个字符；

    在单词 B 中插入一个字符；

    修改单词 A 的一个字符。

    对于这道题，dp 数组就是将s1 转为s2 的最小操作步骤。
     

    1.     public static int minDistance(String s1, String s2) {
    2.         int m = s1.length();
    3.         int n = s2.length();
    4.         // 初始化dp 二维数组，放入初始条件
    5.         int[][] dp = new int[m + 1][n + 1];
    6.         for (int i = 1; i <= m; i ++) {
    7.             dp[i][0] = i;
    8.         }
    9.         for (int j = 1; j <= n; j++) {
    10.             dp[0][j] = j;
    11.         }
    12.         for (int i = 1; i <= m; i++) {
    13.             for (int j = 1; j <= n; j++) {
    14.                 if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
    15.                     // 如果字符相同，那么就是上一个位置的结果
    16.                     dp[i][j] = dp[i - 1][j - 1];
    17.                 } else {
    18.                     // 如果字符不同，那么就取最小的一个
    19.                     // A 字符串增加一个；B 字符串增加一个；A 修改一个
    20.                     dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i - 1][j - 1])) +1;
    21.                 }
    22.             }
    23.         }
    24.         return dp[m][n];
    25.     }


     

  5. 最长公共子序列（1143 题，

    给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

    dp[i][j] 表示遍历到两个字符串第i 个和第j 个的时候，最长公共子序列的长度

      
    1.     // 自底向上的解法
    2.     public int longestCommonSubsequence(String s1, String s2) {
    3.         int m = s1.length();
    4.         int n = s2.length();
    5.         int[][] dp = new int[m + 1][n + 1];
    6.         // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
    7.         // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
    8.         // base case: dp[0][..] = dp[..][0] = 0
    9.         for (int i = 1; i <= m; i++) {
    10.             for (int j = 1; j <= n; j++) {
    11.                 // 现在 i 和 j 从 1 开始，所以要减一
    12.                 if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
    13.                     // s1[i-1] 和 s2[j-1] 必然在 lcs 中
    14.                     dp[i][j] = 1 + dp[i - 1][j - 1];
    15.                 } else {
    16.                     // s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
    17.                     dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
    18.                 }
    19.             }
    20.         }
    21.         return dp[m][n];
    22.     }
    23.     // 此解法可以使用状态压缩，使得空间复杂度为O(N)
    详解最长公共子序列问题，秒杀三道动态规划题目（看下面的“自底向上”解法）
  6. 最长回文子串（也就是最长回文子数组）第5 题，

    给你一个字符串 s，找到 s 中最长的回文子串。

    中心扩展法：经典面试题：最长回文子串


     

    1. class Solution {
    2.     public String longestPalindrome(String s) {
    3.         String result = "";
    4.         for (int i = 0; i < s.length(); i++) {
    5.             String s1 = findPalindrome(s, i, i);
    6.             String s2 = findPalindrome(s, i, i + 1);
    7.             result = s1.length() > result.length() ?  s1 : result;
    8.             result = s2.length() > result.length() ?  s2 : result;
    9.         }
    10.         return result;
    11.     }
    12.  
    13.     public String findPalindrome(String s, int l, int r) {
    14.         while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
    15.             l --;
    16.             r ++;
    17.         }
    18.         return s.substring(l + 1, r);
    19.     }
    20. }
    动态规划看官方题解

    这道题对比下面那道题，这道题求最长回文子串这个“字符串”的时候，二维数组要使用boolean 进行存储。对于求“长度” 的时候，要二维矩阵要使用数字





    此题比较重要的是，外循环要枚举“串的长度”，然后枚举左边界。

      
    1. class Solution {
    2.     public String longestPalindrome(String s) {
    3.  
    4.         int len = s.length();
    5.         if (len < 2) {
    6.             return s;
    7.         }
    8.         int maxLen = 1;
    9.         int begin = 0;
    10.         // dp[i][j] 表示s[i...j] 是否为回文串
    11.         boolean[][] dp = new boolean[len][len];
    12.  
    13.         for (int i = 0; i < len; i++) {
    14.             dp[i][i] = true;
    15.         }
    16.         char[] charArray = s.toCharArray();
    17.         // 递推开始
    18.         // 枚举子串长度，长度从2 开始，长度为2、3、4、5...
    19.         for (int L = 2; L <= len; L++) {
    20.  
    21.             // 枚举左边界，左边界上限设置可以宽松些
    22.             // 上面for 循环设置的是串的长度；下面的是左边界在哪里
    23.             for (int i = 0; i < len; i++) {
    24.                 // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
    25.                 int j = L + i - 1;
    26.                 // 如果右边界超限制，则退出循环
    27.                 if (j >= len) {
    28.                     break;
    29.                 }
    30.                 if (charArray[i] != charArray[j]) {
    31.                     dp[i][j] = false;
    32.                 } else if (charArray[i] == charArray[j]){
    33.                     // 字符相等，且长度小于等于2
    34.                     if (j - i <= 2) {
    35.                         dp[i][j] = true;
    36.                     } else {
    37.                         // 且字符相等，长度大于2
    38.                         dp[i][j] = dp[i + 1][j - 1];
    39.                     }
    40.                 }
    41.  
    42.  
    43.                 // 只要dp[i][j] == true 成立，就表示字符串s[i...j] 是回文子串，此时记录长度和起始位置
    44.                 // 每次循环要记录一下“最长的”
    45.                 if (dp[i][j] && j - i + 1 > maxLen) {
    46.                     maxLen = j - i + 1;
    47.                     begin = i;
    48.                 }
    49.  
    50.             }
    51.  
    52.         }
    53.  
    54.         return s.substring(begin, begin + maxLen);
    55.     }
    56. }
  7. 最长回文子序列的长度（516 题

    对 dp 数组的定义是：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
    子序列解题模板：最长回文子序列



    对于状态转移方程中的，如果i 和j 位置的两个字符不相等的情况：
    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) ,
    为啥不用考虑新增的某个字符是否构成新的“回文子序列”？
    因为dp[i + 1][j] 是已经算完了的。好好理解“已经算完了”是什么意思，就是已经包含了那个字符的结果了。

    注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了

    代码这么写的原因：最长回文子序列：子序列问题通用思路 - 知乎
    “为了保证每次计算的时候，左、左斜下、下 三个方向的值已经计算出来，所以有两种遍历方式。下面的代码选择的是‘反着遍历’”。


      
    1. class Solution {
    2.     public int longestPalindromeSubseq(String s) {
    3.         int n = s.length();
    4.         int[][] dp = new int[n][n];
    5.         // 因为是从长度较短的子序列向长度较长的转移
    6.         // 所以从i = n - 1 开始
    7.         for (int i = n - 1; i >= 0; i--) {
    8.             dp[i][i] = 1;
    9.             char c1 = s.charAt(i);
    10.             for (int j = i + 1; j < n; j++) {
    11.                 char c2 = s.charAt(j);
    12.                 if (c1 == c2) {
    13.                     dp[i][j] = dp[i + 1][j - 1] + 2;
    14.                 } else {
    15.                     // 因为本身第i 个和第j 个不一致，
    16.                     // 而下面转移方程中是dp[i][j - 1] 和dp[i + 1][j] 这样，
    17.                     // 就不涉及第i 个和最后一个字符相等怎么处理这种事情了
    18.                     dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
    19.                 }
    20.             }
    21.         }
    22.         // dp[0][n - 1] 的含义就是从第0 个字符串到第n - 1 个字符串的最长回文子序列的长度
    23.         return dp[0][n - 1];
    24.     }
    25. }

  8. 最长上升子序列的个数（673 题）
    给定一个未排序的整数数组，找到最长递增子序列的个数。
     

    1. class Solution {
    2.     public int findNumberOfLIS(int[] nums) {
    3.  
    4.         int n = nums.length;
    5.         int maxLen = 0;
    6.         int ans = 0;
    7.         // dp[i] 为以nums[i] 结尾的最长上升子序列的长度
    8.         int[] dp = new int[n];
    9.         // cnt[i] 为考虑以nums[i] 结尾的最长上升子序列的个数
    10.         int[] cnt = new int[n];
    11.  
    12.         for (int i = 0; i < n; i++) {
    13.             dp[i] = 1;
    14.             cnt[i] = 1;
    15.             for (int j = 0; j < i; j++) {
    16.                 // nums[i] > nums[j] 的情况是
    17.                 // nums[i] 可以接在nums[j] 后面形成上升子序列
    18.                 if (nums[i] > nums[j]) {
    19.                     // 求最长上升子序列的长度，正常状态转移方程如下
    20.                     // dp[i] = Math.max(dp[i], dp[j] + 1);
    21.                     // 就是下面两种情况
    22.                     // （1）if (dp[i] < dp[j] + 1);
    23.                     // 说明以nums[i] 结尾的最长递增子序列长度
    24.                     // 是小于等于以nums[j] 结尾的dp[j]
    25.                     // dp[i] 会被dp[j] + 1 直接更新
    26.                     // 所以这个时候，cnt[i] 就直接等于cnt[j]
    27.                     // （2）if (dp[i] == dp[j] + 1);
    28.                     // 说明找到了一个新的符合条件的nums[i]
    29.                     // 可以附加到以j 结尾的最长递增子序列之后了
    30.                     // 所以，对于cnt[i] 要直接累加cnt[j]
    31.                     // 举例来说，之前cnt[j] 是2，组成元素分别为{1, 7} 和{2, 7}
    32.                     // 这个时候来了个数字num[i] = 9，可以附加到最后
    33.                     // （这块还是没有太理解，以后再说吧...）
    34.                     if (dp[i] < dp[j] + 1) {
    35.                         dp[i] = dp[j] + 1;
    36.                         cnt[i] = cnt[j];
    37.                     } else if (dp[i] == dp[j] + 1) {
    38.                         // 对于dp[i]，因为相等，所以就不用重新赋值了
    39.                         cnt[i] += cnt[j];
    40.                     }
    41.                 }
    42.             }
    43.             // 最终结果判定 & 保存
    44.             if (dp[i] > maxLen) {
    45.                 maxLen = dp[i];
    46.                 ans = cnt[i];
    47.             } else if (dp[i] == maxLen) {
    48.                 ans += cnt[i];
    49.             }
    50.         }
    51.         return ans;
    52.     }
    53. }

以下思路及代码大部分来自于上述链接“王脸小”同学，同时有一部分摘抄自“labuladong 的算法小抄，以及网上的各个链接。

鸣谢@王脸小

同时题目参考：小浩算法

基础：
1. 读题后先想想有什么思路，不要让题解局限了想法，即使暴力解法也可以。
2. 懂得“递归”的思想。递归的基本思想是某个函数直接或者间接地调用自身，这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分为符合条件的子问题，而不需要研究这个子问题是如何解决的。递归的两个特征：自我调用（为了解决子问题）和结束条件（定义了最简子问题的答案）。

递归其实是有一个栈，每一层递归都是一个压栈的操作。
对于递归的内部逻辑理解：如果进入方法之后前几行代码就是判断某个条件，然后return，这样的操作其实是最底层的出栈，然后回到上一层的栈帧中，继续执行判断条件之后的代码。
 

关于其他的解释：

递归（recursion）：递归常被用来描述以自相似方法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使用函数自身的方法。（A调用A）

迭代（iteration）：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值。（A重复调用B）

递归：递推 + 回归。是一个树形结构。当“递推”到达底部时就会开始“回归”，其过程相当于树的深度优先遍历。

迭代：是一个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。

参考：递归与迭代的区别 - 简书

发现一个规律：

如果使用递归的话，会发现递归的方法里面是有很多参数的。

比如说针对数组的操作，需要包含start、end 这些参数。这样可以方便下次调用的时候，变换参数。

同时，递归方法中的代码大致分为三个结构。

第一个部分是结束操作返回临界条件

第二部分是递归函数的引入

第三部分是逻辑处理代码

参考下面的归并排序，很明显

基础

排序算法时间复杂度、空间复杂度、稳定性比较_排序算法的时间复杂度和空间复杂度

排序算法

  • 快速排序
    参考链接：https://zhuanlan.zhihu.com/p/26891027
    解题思路：这个写法很简单，在纸上画一画就可以写得出来。选择最左边的一个值作为flag，然后从右边开始找。整体一个大循环，是一次遍历，将小于flag 的移到左边，大于的移到右边。大循环内部是右侧向左，左侧向右的操作。一次大循环过后，对flag 左右的两段分别进行快排。-> 整体的方向就是一个大数组 -> 以flag 左右分，分别处理 -> 整体到细节，不用合并。因为这个是二分，二分完了之后还是相同的逻辑，所以是要调用自己的。

    记住函数签名：void quickSort(int[ ] nums, int start, int end)

    5 8 7 6 3 1 2 
    1.     // 对于start 和end，它们是每次循环，自身调用自己的时候的标志
    2.     public static void quickSort(int[] nums, int start, int end) {
    3.         // 所以在这里，需要使用start 和end 作为实际执行的时候的游标
    4.         int low = start;
    5.         int high = end;
    6.         int key = nums[low];
    7.         // 如果low 等于high，那么就说明不需要再向下执行了。所以这里只是小于而不是小于等于。
    8.         // 这是针对这个数组的一次循环
    9.         while (low < high) {
    10.             // 从右边开始，与key 的大小左对比
    11.             while (low < high && nums[high] >= key) {
    12.                 high --;
    13.             }
    14.             // 如果跳出了上面的while 循环，说明发现了比key 小的值，那么执行交换
    15.             // 同时因为上面的while 循环有个low < high 的判断，所以这里也要加一下
    16.             if (low < high) {
    17.                 nums[low] = nums[high];
    18.                 // 对low 赋值了，所以low 这个游标应该加一
    19.                 low ++;
    20.             }
    21.             // 然后再从左边开始
    22.             while (low < high && nums[low] <= key) {
    23.                 low ++;
    24.             }
    25.             //
    26.             if (low < high) {
    27.                 nums[high] = nums[low];
    28.                 high --;
    29.             }
    30.         }
    31.         // 此时说明low 和high 已经相遇了
    32.         nums[low] = key;
    33.         // 如果low - 1 还是大于start 的，那么对相遇点左边的继续执行此函数
    34.         if (low - 1 > start) {
    35.             quickSort(nums, start, low - 1);
    36.         }
    37.         // 如果high + 1 小于end，那么对相遇点右边的数组元素再执行此函数
    38.         if (high + 1 < end) {
    39.             quickSort(nums, high + 1, end);
    40.         }
    41.     }

    为什么先从右边开始：https://blog.csdn.net/he37176427/article/details/97795963
    因为选择左边为key 的时候，从右边开始向左找，最终左右游标相遇的时候，那个值肯定是小于key 的。这个时候交换key 和相遇时的值，是符合条件的。但是如果选择了最左边的值为key，同时又从左边开始，那么最终两个游标相遇的时候，那个值肯定是大于key 的，这样就不符合快排的思想了。

    快速排序的处理过程就是一个倒转的树结构，所以没有什么需要到最后进行“汇总”的代码。

  • 归并排序
    参考链接：【算法】排序算法之归并排序 - 知乎
    代码参考力扣讲解
    解题思路：整体思路就是一个拆分、合并的过程。

    记住函数签名：void mergeSort(int[ ] nums, int l, int r) 
    1. class Solution {
    2.     int[] tmp;
    3.  
    4.     public int[] sortArray(int[] nums) {
    5.         tmp = new int[nums.length];
    6.         mergeSort(nums, 0, nums.length - 1);
    7.         return nums;
    8.     }
    9.  
    10.     public void mergeSort(int[] nums, int l, int r) {
    11.         if (l >= r) {
    12.             return;
    13.         }
    14.         int mid = (l + r) >> 1;
    15.         mergeSort(nums, l, mid);
    16.         mergeSort(nums, mid + 1, r);
    17.         int i = l, j = mid + 1;
    18.         int cnt = 0;
    19.         while (i <= mid && j <= r) {
    20.             if (nums[i] <= nums[j]) {
    21.                 tmp[cnt++] = nums[i++];
    22.             } else {
    23.                 tmp[cnt++] = nums[j++];
    24.             }
    25.         }
    26.         while (i <= mid) {
    27.             tmp[cnt++] = nums[i++];
    28.         }
    29.         while (j <= r) {
    30.             tmp[cnt++] = nums[j++];
    31.         }
    32.         // 一共r - l + 1 个数字
    33.         // 把nums 中这些位置的元素替换掉，替换成tmp 中排好序的数字
    34.         for (int k = 0; k < r - l + 1; ++k) {
    35.             nums[k + l] = tmp[k];
    36.         }
    37.     }
    38. }

    注意上面return 逻辑的理解，因为是基于递归而实现，在最后拆分为只有一个元素的时候，return 是返回到递归的上一层，然后继续执行后面的代码。（递归的思想）
     

  • 堆排序

    时间复杂度O(n log n)  最好、最坏、平均都是
    空间复杂度O(1)

    堆排序三个过程：1）建堆；2）调整；3）输出
    建堆的过程就是把一个数组维护成每个点都比叶子节点大或者小的结构

    排序，一个参数：nums[i]
    建堆，两个参数：nums[i], int len
    调整，三个参数：nums[i], int i, int len
    其中，len 代表数组长度，i 代表
    记住函数签名：
    （1）调整：heapify(int[ ] nums, int i, int length)
    （2）建堆：buildMaxHeap(int[ ] nums, int len)

    举例：5 8 7 6 3 1 2

    1.     public static int[] sort(int[] sourceArray) {
    2.         // 对 arr 进行拷贝，不改变参数内容
    3.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    4.  
    5.         int len = arr.length;
    6.  
    7.         buildMaxHeap(arr, len);
    8.  
    9.         for (int i = len - 1; i > 0; i--) {
    10.             swap(arr, 0, i);
    11.             len--;
    12.             heapify(arr, 0, len);
    13.         }
    14.         return arr;
    15.     }
    16.  
    17.     // 建堆，过程就是从第一个非叶子节点开始调整
    18.     private static void buildMaxHeap(int[] arr, int len) {
    19.         for (int i = (int) Math.floor(len / 2) - 1; i >= 0; i--) {
    20.             heapify(arr, i, len);
    21.         }
    22.     }
    23.  
    24.     // 对每个节点i 进行调整
    25.     // 这是创建大顶堆的过程，创建大顶堆，然后可以进行正序排列
    26.     private static void heapify(int[] arr, int i, int len) {
    27.         int left = 2 * i + 1;
    28.         int right = 2 * i + 2;
    29.         int largest = i;
    30.  
    31.         if (left < len && arr[left] > arr[largest]) {
    32.             largest = left;
    33.         }
    34.  
    35.         if (right < len && arr[right] > arr[largest]) {
    36.             largest = right;
    37.         }
    38.  
    39.         if (largest != i) {
    40.             swap(arr, i, largest);
    41.             // 对于调整了的那个节点，还需要再继续向下进行调整
    42.             heapify(arr, largest, len);
    43.         }
    44.     }
    45.  
    46.     private static void swap(int[] arr, int i, int j) {
    47.         int temp = arr[i];
    48.         arr[i] = arr[j];
    49.         arr[j] = temp;
    50.     }

    正序排列，创建大顶堆。
    因为在后续处理的时候，是把堆顶元素放到数组最后，然后再调整堆。
    建堆的时候，是从第一个非叶子节点开始调整。从下往上调整。

    逆序排列，创建小顶堆。


    215 数组中第k 大的元素

     

  • 冒泡排序 
    1.     public static void bubble(int[] nums) {
    2.         int length = nums.length;
    3.         // 外层循环决定执行几次，只需要执行length - 1 次就好了
    4.         for (int i = 0; i < length - 1; i++) {
    5.             // 内层循环用来执行交换
    6.             for (int j = 0; j < length -1 - i; j++) {
    7.                 if (nums[j] > nums[j + 1]) {
    8.                     nums[j] = nums[j] + nums[j + 1];
    9.                     nums[j + 1] = nums[j] - nums[j + 1];
    10.                     nums[j] = nums[j] - nums[j + 1];
    11.                 }
    12.             }
    13.         }
    14.         for (int i = 0; i < nums.length; i++) {
    15.             System.out.println(nums[i]);
    16.         }
    17.     }
  • 树的前中后遍历，迭代
    前序遍历：根左右。使用栈，先把根节点push，然后while 判断栈是否为空，不空则pop 出一个node，然后右不空push 右，左不空push 左（因为FILO）。结束。
    中序遍历：左根右。do-while 循环。先把所有左子树节点放入栈中，直到最后，是最后一个左子树节点。然后出栈，再判断其右子树，处理右子树。如果由子树继续为空，则继续pop；不空，则继续push。
    后序边拆：左右根，可以根、右、左，然后反转。
    参考：Java迭代实现二叉树的前序、中序、后序遍历_yangfeisc的专栏-CSDN博客_java二叉树的前序遍历

二分查找

做二分法需要自己理解并总结出，需要怎么进入循环，需要怎么退出循环。
即怎么判断边界条件。如果用数学方法表示mid，mid = (l + r)/2，这种是很明确的表示方法。但是到了编程的时候，就涉及mid 是应该(l + r)/2 还是(l + r + 1) / 2，判断l <= r 为结束条件，还是l < r 为结束条件。具体参考：算法浅谈——人人皆知却很多人写不对的二分法 - 知乎
二分法要注意不要造成死循环

对于区间的设置，可以使用“左闭右开”，对于每个人，设置一个自己的固定模式，这样更容易记一些。

  • 数组
    • 4. 寻找两个正序数组的中位数 （hard）
      题目要求时间复杂度Olog(m+n)。如果有log 的时间复杂度，差不多应该都是使用二分法。
      根据数组的定义，其中一个数组长度为m，另一个数组长度为n。
      如果m + n 为奇数【如7】，那么中位数就是下标为(m + n) / 2 【7/2 = 3】的数字。如果m + n 为偶数【如10】，那么中位数就是下标为(m + n) / 2 和(m + n) / 2 - 1 【4，5】的数字。可以利用整数除法向下取整的特点，求数组中下标为(m + n - 1) / 2 和(m + n) / 2 的元素，然后求出两个数字的平均值，就是数组的中位数。




      以下题目来自
    • 查找排序数组给定target 的左边界，查找排序数组给定target 的右边界。代码来自labuladong

      按照题目的解法理解的话，给定target 的左边界，比如说下面的例子0 4 5 5，给定的target 是5，给定target 的左边界就是第一个5 的下标，就是2；右边界就是第二个5，下标是3

      查找给定数组的左边界的下标，相当于查找排序数组中元素小于target 的元素的个数
      比如说，[0, 4, 5, 5] target = 5，那么得到的结果就是2。 
      1. 查找给定数组的左边界的下标，相当于查找排序数组中元素小于target 的元素的个数。
      2. 所以在下面的代码中的判断，才返回的是nums.length。
      3. 重点在于num[mid] == target 时，right = mid。将范围逐步压缩。
      4.  
      5.     public static int left_bound(int[] nums, int target) {
      6.  
      7.         if (nums[nums.length - 1] < target) {
      8.             return nums.length;
      9.         }
      10.  
      11.         int left = 0;
      12.         int right = nums.length - 1;
      13.         while (left < right) {
      14.             int mid = (left + right) / 2;
      15.             if (nums[mid] == target) {
      16.                 right = mid;
      17.             } else if (nums[mid] > target) {
      18.                 right = mid;
      19.             } else if (nums[mid] < target) {
      20.                 left = mid + 1;
      21.             }
      22.         }
      23.  
      24.         if (nums[left] != target) {
      25.             return -1;
      26.         }
      27.  
      28.         return left;
      29.  
      30.     }
      31.  
      32.  
      33.  
      34. 或者
      35. 看这个，这个能看懂
      36.  
      37.     public static int left_bount(int[] nums, int target) {
      38.  
      39.         int left = 0;
      40.         int right = nums.length - 1;
      41.         while (left < right) {
      42.             int mid = (left + right) / 2;
      43.             if (nums[mid] == target) {
      44.                 right = mid;
      45.             } else if (nums[mid] < target) {
      46.                 left = mid + 1;
      47.             } else if (nums[mid] > target) {
      48.                 right = mid - 1;
      49.             }
      50.         }
      51.  
      52.         if (nums[right] == target) {
      53.             return right;
      54.         } else {
      55.             return -1;
      56.         }
      57.  
      58.     }
      59.  
      60.  
      61. 注意在wile 块里面的循环逻辑里，如果有“等于”的判断，那么while 条件里，就不能是“小于等于”的判断
      1. 查找右边界
      2.  
      3.     public static int right_bound(int[] nums, int target) {
      4.  
      5.         if (nums.length == 0) return -1;
      6.         int left = 0, right = nums.length;
      7.         while (left < right) {
      8.             int mid = (left + right) >> 1;
      9.             if (nums[mid] == target) {
      10.                 left = mid + 1;
      11.             } else if (nums[mid] > target) {
      12.                 right = mid;
      13.             } else if (nums[mid] < target) {
      14.                 left = mid + 1;
      15.             }
      16.         }
      17.         return left - 1;
      18.  
      19.     }
      20.  
      21.  
      22. 求mid 的时候要+1 就不会进入死循环。
      23. + 1 代表只剩两个数字的时候，选左边还是选右边
      24. 有时间再研究总结吧
      25.  
      26.     public static int right_bound(int[] nums, int target) {
      27.  
      28.         int left = 0;
      29.         int right = nums.length - 1;
      30.         while (left < right) {
      31.             int mid = (left + right + 1) / 2;
      32.             if (nums[mid] == target) {
      33.                 left = mid;
      34.             } else if (nums[mid] > target) {
      35.                 right = mid - 1;
      36.             } else if (nums[mid] < target) {
      37.                 left = mid + 1;
      38.             }
      39.         }
      40.         if (nums[right] == target) {
      41.             return right;
      42.         } else {
      43.             return -1;
      44.         }
      45.  
      46.     }




       

    • 33. 搜索旋转排序数组 直接使用二分法
      一个数组，已经排过序，在某个元素那里做了旋转。要求查找出数组中是否存在某个元素。要求olog(n) 的时间复杂度。
      olog(n) 时间复杂度即说明了使用二分法。
      旋转数组是原来一个有序数组，进行了旋转，得到一个“局部有序”的数组。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。
      这个旋转的方式是在下标K 处旋转，是数组变成（num[k], num[k + 1] ... nums[0], nums[1] ...）
      可以通过在常规的二分查找的时候，找到mid 为分割位的前半部分[1, mid]，和[mid + 1，r] 哪部分是有序的，然后在有序的部分判断target 是否存在，从而根据有序的部分可以推断出如何改变二分查找的上下界。
      思路：这道题的重点思想就在，无序的那部分可能是不太好处理，我们可以转头去处理有序的那部分。每次循环通过nums[l]，nums[r] 和nums[middle] 的大小，来判断l ~ middle 或者middle ~ r 的区间是否是递增的。       
      1. class Solution {
      2.     public int search(int[] nums, int target) {
      3.  
      4.         if (nums.length == 0) {
      5.             return -1;
      6.         }
      7.         int low = 0;
      8.         int high = nums.length - 1;
      9.  
      10.         while (low <= high) {
      11.             int middle = (low + high) >> 1;
      12.             if (nums[middle] == target) {
      13.                 return middle;
      14.             }
      15.  
      16.             // 说明此区间有序
      17.             if (nums[low] <= nums[middle]) {
      18.                 if (target >= nums[low] && target <= nums[middle]) {
      19.                     high = middle - 1;
      20.                 } else {
      21.                     low = middle + 1;
      22.                 }
      23.  
      24.             // 说明另外一个区间有序
      25.             } else {
      26.                 if(target >= nums[middle] && target <= nums[high]) {
      27.                     low = middle + 1;
      28.                 } else {
      29.                     high = middle - 1;
      30.                 }
      31.             }
      32.         }
      33.         return -1;
      34.  
      35.     }
      36. }
    •  287. 寻找重复数 dict
      包含n + 1 个数字，数字范围1 ~ n，存在一个重复的数字。找出这个数字。
      利用条件【一共有n + 1 个数字，数字的范围在1 ~ n】。

      这道题要注意的地方是，进行二分的不是数组，而是1 ~ n 这个数字区间。

       

      给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

      假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

      你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

      这道题二分的是1 ~ n 这n 个数字

        
      1. 首先，我们让中指针指向n/2， 由题意可得，小于n/2的元素只会有(n/2)-1个。
      2. 比如说，数组是4,1,3,2,5
      3. 对于数组中每个元素，小于1 的元素有0 个，小于2 的元素有1 个，小于3 的元素有2个...
      4.  
      5. 如果超过了(n/2)-1,说明在[1,n/2)区间有重复的数字，此时我们将待查找的数据规模缩小到[1, n/2)
      6. 如果数组没有超过(n/2)-1。说明在[n/2, n]区间有重复的数字，此时我们讲查找的数据规模缩小到[n/2, n]
      7. 不断重复上述过程，直到找到某一个重复的数字。
      8. 时间复杂度O(nlogn), 二分法本身是O(logn), 每次缩小规模时需要统计一次数组(O(n))
      9. 空间复杂度O(1)
      10. 代码中start 是数字范围1 ~ n 的1；代码中的end 是数字范围，一共n + 1 个数字，范围1 ~ n，所以最大的是nums.length - 1。
      11.  
      12.  
      13.     public static int findDuplicate(int[] nums) {
      14.         int start = 1, end = nums.length - 1;
      15.         int mid = (start + end) / 2;
      16.         while (start <= end){
      17.             int count = 0;
      18.             for(int num: nums){
      19.                 // 计算小于中间数字mid 的数字个数
      20.                 if(num < mid) {
      21.                     count += 1;
      22.                 } else {
      23.                     break;
      24.                 }
      25.             }
      26.             if( count >= mid) {
      27.                 // 说明重复数字在此区间内
      28.                 end = mid - 1;
      29.             } else {
      30.                 // 说明重复数字在另一个区间
      31.                 start = mid + 1;
      32.             }
      33.             mid = (start + end) / 2;
      34.         }
      35.  
      36.         return mid;
      37.     }
      38.  
      39.  
      40.  
      41. 参考：​​​​​​https://zhuanlan.zhihu.com/p/102298178
    • 34. 在排序数组中查找元素的区间
      原创（@王漂亮）提示解法：取开始下标(mid = (l + r) // 2); 取结束下标(mid = (a + b + 1) // 2)
      题目要求，o(log n) 时间复杂度，给定一个升序有序数组和一个目标值target，找出给定目标值在数组中开始和结束的位置
      要求o(log n) 即为“二分法”。考虑到要求找到target 在数组中的开始和结束位置，即找到第一个等于target 值的位置和第一个大于target 值的位置，然后减一。
      这道题的核心就是分两次，二分查找第一个等于target 的位置和第一个大于target 的位置。
      为了代码复用，定义方法binarySearch(nums, target, lower) 表示在nums 数组中二分查找target 的位置，如果lower 为true，则查找第一个大于等于target 的下标，否则查找第一个大于target 的下标。
      解释：lower = true，代表查找target 左下标那边，大于等于的原因是target 下标有可能不存在。
      因为target 有可能不存在，所以最后需要校验结果是否正确。
      8 
      1. public int[] searchRange(int[] nums, int target) {
      2.  
      3.         int low = binarySearch(nums, target, true);
      4.         int high = binarySearch(nums, target, false) - 1;
      5.         if (low <= high && high < nums.length && nums[low] == target && nums[high] == target) {
      6.             return new int[]{low, high};
      7.         }
      8.         return new int[]{-1, -1};
      9.  
      10.     }
      11.  
      12.  
      13.     private static int binarySearch(int[] nums, int target, boolean lower) {
      14.         int left = 0;
      15.         int right = nums.length - 1;
      16.         int ans = nums.length;
      17.         while (left <= right) {
      18.  
      19.             int mid = (left + right) / 2;
      20.             if (lower) {
      21.                 if (nums[mid] >= target) {
      22.                     right = mid - 1;
      23.                     ans = mid;
      24.                 } else {
      25.                     left = mid +1;
      26.                 }
      27.             } else {
      28.                 if (nums[mid] > target) {
      29.                     right = mid -1;
      30.                     ans = mid;
      31.                 } else {
      32.                     left = mid + 1;
      33.                 }
      34.             }
      35.  
      36.         }
      37.         return ans;
      38.     }

  • 矩阵
    记住递增矩阵的性质。
    1. 左上最小，右下最大
    2. 搜索某个元素，可以从右上角开始，如果大于target，则向左走；小于target，则向下走
    3. 给定一个target，小于等于target 的都在左上角，大于的都在右下角
    • 240. 搜索二维矩阵 II
      原创（@王漂亮）提示解法：从左下/右上开始search, O(m+n)
      这道题注意矩阵的性质，左上到右下是依次递增的。所以从右上角开始，对每个元素和target 比较大小。
        
      1.     public boolean searchMatrix(int[][] matrix, int target) {
      2.         int m = matrix.length;
      3.         int n = matrix[0].length;
      4.         int i = m - 1;
      5.         int j = 0;
      6.         while(i >= 0 && j < n) {
      7.             if (matrix[i][j] == target) {
      8.                 return true;
      9.             } else if (matrix[i][j] < target) {
      10.                 j ++;
      11.             } else {
      12.                 i --;
      13.             }
      14.         }
      15.         return false;
      16.     }

    • 378. 有序矩阵中第K小的元素
      原创（@王漂亮）提示解法：依次添加右和下，pop出其中较小的，每次pop k-1，pop k次返回
      使用矩阵的性质，矩阵左上角最小，右下角最大。同时这种矩阵如果指定一个元素target，在矩阵中可以得到，小于target 的元素都在左上角，大于的都在右下角。如果元素matrix[i][j] <= target，则matrix[0][j] ~ matrix[i][j] 的值都小于等于target。依据此思路，可以使用二分法一个个试出来有序矩阵中的第k 小的元素。

      这到题是针对数组值做二分，然后每次判断某个值在矩阵中的位置。 
      1. class Solution {
      2.     public int kthSmallest(int[][] matrix, int k) {
      3.  
      4.         int n = matrix.length;
      5.         int left = matrix[0][0];
      6.         int right = matrix[n-1][n-1];
      7.         while (left < right) {
      8.             int mid = (left + right) / 2;
      9.             if (check(matrix, mid, k, n)) {
      10.                 right = mid;
      11.             } else {
      12.                 left = mid +1;
      13.             }
      14.         }
      15.         return left;
      16.  
      17.     }
      18.  
      19.     // 检查当前数字【mid】在矩阵中的情况
      20.     // 返回结果：小于等于目标值mid 的数字个数是否大于等于k 个
      21.     // 传参需要用到：矩阵，要查询的数字mid，范围k
      22.     public boolean check(int[][] matrix, int mid, int k, int n) {
      23.         // 从左下开始寻找，i 行，j 列。
      24.         int i = n - 1;
      25.         int j = 0;
      26.         // 符合要求的个数
      27.         int num = 0;
      28.         while (i >= 0 && j < n) {
      29.             if (matrix[i][j] <= mid) {
      30.                 // 元素上面的那些都是符合要求的
      31.                 num += i + 1;
      32.                 j ++;
      33.             } else {
      34.                 i --;
      35.             }
      36.         }
      37.         // 因为要寻找第k 小的元素，返回一个boolean，判断寻找到的数字的个数，是否多于k 个
      38.         return num >= k;
      39.  
      40.     }
      41. }
  • 其他
    • 69. X的平方根
      原创（@王漂亮）提示解法：在[0, x]中二分查找
      二分查找，在[0,x] 范围内。设ans 为最终答案，x 的平方根整数部分ans 就是k方 <= x 的最大k 值，因此可以对k 进行二分查找。 
      1. class Solution {
      2.     public int mySqrt(int x) {
      3.         int l = 0, r = x;
      4.         int ans = -1;
      5.         while (l <= r) {
      6.             int mid = (l + r) / 2;
      7.             if ((long)mid * mid <= x) {
      8.                 ans = mid;
      9.                 l = mid + 1;
      10.             } else {
      11.                 r = mid - 1;
      12.             }
      13.         }
      14.         return ans;
      15.     }
      16. }

       

链表（适当使用哑结点，可命名为hair[head 上层为hair]）

无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。然而面试的时候经常碰见诸如：

  1. 获取倒数第k个元素（两个指针，第一个指针先走k步，然后第二个指针开始。等第一个指针走到了末尾，第二个指针指向的就是倒数第k个）
  2. 获取中间位置的元素（第一个指针每次走两步，第二个指针每次走一步）
  3. 判断链表是否存在环（快慢指针）
  4. 判断环的长度与位置（3 中两个指针相遇后继续移动，再次相遇移动的次数就是环的长度）

这些相关的问题都可以通过灵活运用双指针来解决。

  • 基础题
    • 206. 反转链表
      迭代、递归。
      迭代：当前节点的next 要指向前一个节点，同时当前节点的下一个节点也要存储。prev/curr/curr = head, 然后进入while 循环，判断条件为curr 不为空。取出curr 的next，改变curr.next 指向，改变prev 的指向，改变curr 为next。while 循环结束，返回prev，即为反转的头结点。
      递归：


      这个其实就直接mock 一个虚拟头结点。
      这里是有三个节点：pre，cur，next。
      next 的作用就是保存前面那些需要处理的节点的下一个节点，这样没处理的链就可以保留下来了。 
      1. /**
      2.  * Definition for singly-linked list.
      3.  * public class ListNode {
      4.  *     int val;
      5.  *     ListNode next;
      6.  *     ListNode() {}
      7.  *     ListNode(int val) { this.val = val; }
      8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      9.  * }
      10.  */
      11. class Solution {
      12.     public ListNode reverseList(ListNode head) {
      13.         ListNode prev = null;
      14.         ListNode cur = head;
      15.         while (cur != null) {
      16.             ListNode next = cur.next;
      17.             cur.next = prev;
      18.             prev = cur;
      19.             cur = next;
      20.         }
      21.         return prev;
      22.     }
      23. }
  • 反转链表II
    • 92
      给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从第left 到第right 位置的链表节点，返回 反转后的链表 
       
      这里也需要三个节点：pre，cur，next。
      其中pre 是不能变的，所以对比上面的反转一整个链表来说，就需要一个next.next 的存在。
      先赋值next 节点（next = cur.next）
      然后处理cur 的next
      然后处理next 的next
      然后处理pre 的next 
      1.     public ListNode reverseBetween(ListNode head, int left, int right) {
      2.         ListNode dummyNode = new ListNode(-1);
      3.         dummyNode.next = head;
      4.         ListNode pre = dummyNode;
      5.         for (int i = 0; i < left - 1; i++) {
      6.             pre = pre.next;
      7.         }
      8.         ListNode cur = pre.next;
      9.         ListNode next;
      10.         for (int i = 0; i < right - left; i++) {
      11.             next = cur.next;
      12.             cur.next = next.next;
      13.             next.next = pre.next;
      14.             pre.next = next;
      15.         }
      16.         return dummyNode.next;
      17.     }

       
  • 重难点 (M->H)
    • 138. 复制带随机指针的链表 di[node] = Node, key为原节点，val为新节点, di[node].next = di.get(node.next), O(2n)
        
      1. /*
      2. // Definition for a Node.
      3. class Node {
      4.     int val;
      5.     Node next;
      6.     Node random;
      8.     public Node(int val) {
      9.         this.val = val;
      10.         this.next = null;
      11.         this.random = null;
      12.     }
      13. }
      14. */
      15.  
      16. class Solution {
      17.     public Node copyRandomList(Node head) {
      18.  
      19.         if(head == null) {
      20.             return null;
      21.         }
      22.         Node pointer = head;
      23.         // 使用这个map 做原链表和老链表的映射，每个node 一一对应
      24.         Map<Node, Node> map = new HashMap<>();
      25.         while (pointer != null) {
      26.             Node newNode = new Node(pointer.val);
      27.             // 新链表节点只是存于map 中，还没有连接
      28.             map.put(pointer, newNode);
      29.             pointer = pointer.next;
      30.         }
      31.         pointer = head;
      32.         while (pointer != null) {
      33.             Node newNode = map.get(pointer);
      34.             // random 节点赋值
      35.             if (pointer.random != null) {
      36.                 newNode.random = map.get(pointer.random);
      37.             }
      38.             // next 节点赋值
      39.             if (pointer.next != null) {
      40.                 newNode.next = map.get(pointer.next);
      41.             }
      42.             pointer = pointer.next;
      43.         }
      44.         return map.get(head);
      45.     }
      46. }

       
    • 21. 合并两个有序链表 递归，迭代(dummy_node) 
      1. /**
      2.  * Definition for singly-linked list.
      3.  * public class ListNode {
      4.  *     int val;
      5.  *     ListNode next;
      6.  *     ListNode() {}
      7.  *     ListNode(int val) { this.val = val; }
      8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      9.  * }
      10.  */
      11. class Solution {
      12.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      13.  
      14.         ListNode preHead = new ListNode(-1);
      15.         ListNode prev = preHead;
      16.         while (l1 != null && l2 != null) {
      17.             if (l1.val <= l2.val) {
      18.                 prev.next = l1;
      19.                 l1 = l1.next;
      20.             } else {
      21.                 prev.next = l2;
      22.                 l2 = l2.next;
      23.             }
      24.             prev = prev.next;
      25.         }
      26.  
      27.         prev.next  = l1 == null ? l2 : l1;
      28.  
      29.         return preHead.next;
      30.  
      31.     }
      32. }


       
    • 23. 合并K个排序链表 for i in range(0, cnt-interval, interval*2)
      使用“堆”的数据结构完成，时间复杂度O(logKN) 
      1. /**
      2.  * Definition for singly-linked list.
      3.  * public class ListNode {
      4.  *     int val;
      5.  *     ListNode next;
      6.  *     ListNode() {}
      7.  *     ListNode(int val) { this.val = val; }
      8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      9.  * }
      10.  */
      11. class Solution {
      12.     public ListNode mergeKLists(ListNode[] lists) {
      13.  
      14.         Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
      15.         for (ListNode node : lists) {
      16.             if (node !=  null) {
      17.                 pq.offer(node);
      18.             }
      19.         }
      20.         ListNode dummyHead = new ListNode(0);
      21.         ListNode tail = dummyHead;
      22.         while (!pq.isEmpty()) {
      23.             ListNode minNode = pq.poll();
      24.             tail.next = minNode;
      25.             tail = tail.next;
      26.             if (minNode.next != null) {
      27.                 pq.add(minNode.next);
      28.             }
      29.         }
      30.         return dummyHead.next;
      31.     }
      32. }
    • 25. K 个一组翻转链表 cnt++, cnt--

      (看官方题解就好了，看官方题解，官方题解。但是官方题解看不懂。这是一道hard）

        
      1. public ListNode reverseKGroup(ListNode head, int k) {
      2.          ListNode hair = new ListNode(-1);
      3.          hair.next = head;
      4.          ListNode pre = hair;
      5.          while (head != null) {
      6.              ListNode tail = pre;
      7.              // 查看剩余部分长度是否大于k
      8.              for(int i = 0; i < k; i++) {
      9.                  tail = tail.next;
      10.                  if (tail == null) {
      11.                      return hair.next;
      12.                  }
      13.              }
      14.              ListNode pos = tail.next;
      15.              ListNode[] reserved = reverseList(head, tail);
      16.              // 翻转部分装回链表
      17.              pre.next = reserved[0];
      18.              reserved[1].next = pos;
      19.              pre = reserved[1];
      20.              head = pos;
      21.          }
      22.          return hair.next;
      23.     }
      24.  
      25.     public ListNode[] reverseList(ListNode left, ListNode right) {
      26.         ListNode[] result = new ListNode[]{right, left};
      27.         // 最后返回的时候，因为不是一个孤单的链表，所以反转之后，left 得指向rightNext
      28.         ListNode rightNext = right.next;
      29.         ListNode pre = rightNext;
      30.         ListNode leftNext;
      31.         while (left != rightNext) {
      32.             leftNext = left.next;
      33.             left.next = pre;
      34.             pre = left;
      35.             left = leftNext;
      36.         }
      37.         return result;
      38.     }

       
  • 双指针技巧

    有个简单的搞法，就把slow 和fast 的起始值都设置成head 就好了。

    对于快慢指针，寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
    如果是奇数个节点，那么slow 就是那个中点；如果是偶数个节点，那么slow 指向的就是前半个链表的最后一个节点。
    • 141. 环形链表
      环形链表即判断链表是否有环。使用快慢指针。fast指针走两步，slow 指针走一步。 
      1. public class Solution {
      2.     public boolean hasCycle(ListNode head) {
      3.  
      4.         if (head == null || head.next == null) {
      5.             return false;
      6.         }
      7.  
      8.         ListNode slow = head;
      9.         ListNode fast = head.next;
      10.  
      11.         while (fast != null && fast.next != null) {
      12.             slow = slow.next;
      13.             fast = fast.next.next;
      14.             if (slow == fast) {
      15.                 return true;
      16.             }
      17.         }
      18.  
      19.         return false;
      20.  
      21. //        第二种解法
      22. //        if (head == null || head.next == null) {
      23. //            return false;
      24. //        }
      25. //        ListNode slow = head;
      26. //        ListNode fast = head.next;
      27. //        while (slow != fast) {
      28. //            if (fast == null || fast.next == null) {
      29. //                return false;
      30. //            }
      31. //            slow = slow.next;
      32. //            fast = fast.next.next;
      33. //        }
      34. //        return true;
      35.     }
      36. }

       
    • 142. 环形链表 II
      可以设置一个set，走过一个就存一个，如果有重复，那第一个重复的就是相交节点。
      另外就是设置快慢指针。设置快慢指针依旧是快的走两步，慢的走一步。快慢指针相遇的时候，再设置一个可以判断快慢指针的解法可以直接看题解。

      利用链表的性质解题的时候，fast 和slow 要同时指向head，然后开始向后遍历才可以

      整体过程就是，先遍历找到重合的点；然后再找相交的点。
        
      1.     public ListNode detectCycle(ListNode head) {
      2.         if (head == null) {
      3.             return null;
      4.         }
      5.         ListNode slow = head;
      6.         ListNode fast = head;
      7.         while (fast != null) {
      8.             if (fast.next != null) {
      9.                 slow = slow.next;
      10.                 fast = fast.next.next;
      11.             } else {
      12.                 return null;
      13.             }
      14.             if (fast == slow) {
      15.                 ListNode ptr = head;
      16.                 while (ptr != slow) {
      17.                     ptr = ptr.next;
      18.                     slow = slow.next;
      19.                 }
      20.                 return ptr;
      21.             }
      22.         }
      23.         return null;
      24.     }

       
    • 160. 相交链表 di
      对于两个链表，一个指针flagA走链表a，一个指针flagB走链表b，flagA 走完了链表A 后，再走链表b，flagB 走完了链表b 后再走链表A，两个指针走过的距离一样，那么他们就会相遇。

      此题的“相交”如图

        
      1.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      2.  
      3.         if (headA == null || headB == null) {
      4.             return null;
      5.         }
      6.         ListNode preA = headA;
      7.         ListNode preB = headB;
      8.         while (preA != preB) {
      9.             if (preA != null) {
      10.                 preA = preA.next;
      11.             } else {
      12.                 preA = headB;
      13.             }
      14.             if (preB != null) {
      15.                 preB = preB.next;
      16.             } else {
      17.                 preB = headA;
      18.             }
      19.         }
      20.         return preA;
      21.     }


       
    • 19. 删除倒数第N个节点 快指针先走n步
      删除倒数第N 个节点，首先得找到这个节点。用first 指针和second 指针，first 先走n 个节点，然后second 再开始。这样当first 走到尾的时候，second 就到了倒数第n 割接点。具体实现要考虑怎么方便怎么来。
        
      1.     public ListNode removeNthFromEnd(ListNode head, int n) {
      2.  
      3.         ListNode hair = new ListNode(0, head);
      4.  
      5.         ListNode first = head;
      6.         ListNode second = hair;
      7.         for (int i = 0; i < n; i++) {
      8.             first = first.next;
      9.         }
      10.  
      11.         while (first != null) {
      12.             first =first.next;
      13.             second = second.next;
      14.         }
      15.  
      16.         second.next = second.next.next;
      17.  
      18.         return hair.next;
      19.  
      20.     }

  • 其他
    • 234. 回文链表 
      原创（@王漂亮）提示解法：left数组, left从后往前，指针从前往后，依次对比，slow, fast = head, head.next
      将值复制到数组中用前后双指针法；用递归；用快慢指针，找到中间，然后将其中一个进行翻转，然后进行比较  
      做法：找到第一个链表的结尾。如果奇数个，那么第一个链表多一个。然后翻转后面的链表，进行对比

              // 找到前半部分尾节点，并翻转后半部分链表（重点）
              // 这样就可以避免了链表奇偶性的判断 
      1. public boolean isPalindrome(ListNode head) {
      2.  
      3.         if (head == null) {
      4.             return true;
      5.         }
      6.         // 找到前半部分尾节点，并翻转后半部分链表（重点）
      7.         // 这样就可以避免了链表奇偶性的判断
      8.         ListNode firstHalfEnd = endOfFirstHalf(head);
      9.         ListNode reversedSecondHalfStart = reverseList(firstHalfEnd.next);
      10.         ListNode p1 = head;
      11.         ListNode p2 = reversedSecondHalfStart;
      12.         boolean result = true;
      13.         while (p1!= null && p2 != null) {
      14.             if (p1.val != p2.val) {
      15.                 result = false;
      16.                 break;
      17.             }
      18.             p1 = p1.next;
      19.             p2 = p2.next;
      20.         }
      21.         return result;
      22.     }
      23.  
      24.     private ListNode reverseList(ListNode head) {
      25.         ListNode prev = null;
      26.         ListNode cur = head;
      27.         while (cur != null) {
      28.             ListNode next = cur.next;
      29.             cur.next = prev;
      30.             prev = cur;
      31.             cur = next;
      32.         }
      33.         return prev;
      34.     }
      35.  
      36.     // 有可能返回的是技术个数的中间打那个；有可能返回的事偶数个，前面那个链表的最后一个节点
      37.     private ListNode endOfFirstHalf(ListNode head) {
      38.         ListNode fast = head;
      39.         ListNode slow = head;
      40.         while (fast.next != null && fast.next.next != null) {
      41.             fast = fast.next.next;
      42.             slow = slow.next;
      43.         }
      44.         return slow;
      45.     }

       
    • 328. 奇偶链表
      原创（@王漂亮）提示解法：保存下even_head, odd.next, even.next = odd.next.next, even.next.next
      奇偶链表就是将一个链表中的奇数位放到前部分，偶数位节点放到后部分。解法就是分离奇偶节点，然后合并。迭代解法的终止条件就是偶数节点为空或者偶数节点的next 为空。 
      1. class Solution {
      2.     public ListNode oddEvenList(ListNode head) {
      3.         if (head == null || head.next == null || head.next.next == null) {
      4.             return head;
      5.         }
      6.         ListNode evenHead = head.next;
      7.         ListNode odd = head;
      8.         ListNode even = evenHead;
      9.         while (even != null && even.next != null) {
      10.             odd.next = even.next;
      11.             odd = odd.next;
      12.             even.next = odd.next;
      13.             even = even.next;
      14.         }
      15.         odd.next = evenHead;
      16.         return head;
      17.     }
      18. }

       
    • 2. 两数相加
      原创（@王漂亮）提示解法：迭代(dummy_node), 最后不要忘了 if carry>0: h.next = ListNode(1)
      两数字相加，注意进位就好了 
      1. class Solution {
      2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      3.         int flag = 0;
      4.         ListNode head = null;
      5.         head = new ListNode();
      6.         ListNode temp = head;
      7.         while (l1 != null || l2 != null) {
      8.  
      9.             int l1Val;
      10.             int l2Val;
      11.             if (l1 == null) {
      12.                 l1Val = 0;
      13.             } else {
      14.                 l1Val = l1.val;
      15.                 l1 = l1.next;
      16.             }
      17.  
      18.             if (l2 == null) {
      19.                 l2Val = 0;
      20.             } else {
      21.                 l2Val = l2.val;
      22.                 l2 = l2.next;
      23.             }
      24.  
      25.             int result = l1Val + l2Val + flag;
      26.             ListNode listNode = new ListNode();
      27.             listNode.val = result % 10;
      28.             flag = result / 10;
      29.             temp.next = listNode;
      30.             temp = temp.next;
      31.         }
      32.  
      33.         if (flag >= 1) {
      34.             ListNode listNode = new ListNode();
      35.             listNode.val = flag;
      36.             temp.next = listNode;
      37.  
      38.         }
      39.         return head.next;
      40.     }
      41. }

       
    • 148. 排序链表
      原创（@王漂亮）提示解法：mergesort (slow, fast找到mid，再分别mergesort); merge dummynode
      （看不懂）



       

注：一般要分为两段的链表的双指针slow,fast = head, head.next; 不需要分为两段的slow,fast = head, head  对于slow 和fast，都设置head 为初始节点就行。

字符串

  • 滑动窗口
    • 76. 最小覆盖子串 - M while all(map(lambda x: s_c[x] >= t_c[x], t_c.keys())):

      题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
      保证如果有答案，那么保证它是唯一的答案。
      （看不懂）(hard 做不出来）
      1. //模板
      2. /* 滑动窗口算法框架 */
      3. void slidingWindow(string s, string t) {
      4.     Map<Character, Integer> need = new HashMap<>();
      5.     Map<Character, Integer> window = new HashMap<>();
      6.     for (char c : t.toCharArray()) 
      7.         need.put(c,need.getOrDefault(c,0)+1);
      8. 	int left = 0, right = 0;
      9. 	int valid = 0; 
      10. 	while (right < s.size()) {
      11.     	// c 是将移入窗口的字符
      12.    	 	char c = s.charAt(right);
      13.     	// 右移窗口
      14.     	right++;
      15.     	// 进行窗口内数据的一系列更新
      16.     	...
      17.  
      18.     	/*** debug 输出的位置 ***/
      19.     	System.out.println("window: ["+left+","+ right+")");
      20.     	/********************/
      21.     
      22.     	// 判断左侧窗口是否要收缩
      23.     	while (window needs shrink) {
      24.         	// d 是将移出窗口的字符
      25.         	char d = s[left];
      26.         	// 左移窗口
      27.         	left++;
      28.         	// 进行窗口内数据的一系列更新
      29.         	...
      30.     	}
      31. 	}
      32. }
      33. //题解
      34. class Solution {
      35.     public String minWindow(String s, String t) {
      36.         if (s == null || s == "" || t == null || t == "") {
      37.             return "";
      38.         }
      39.  
      40.         // 维护两个map记录窗口中的符合条件的字符以及need的字符
      41.         // 其中key 是字母本身，value 是字符出现的次数
      42.  
      43.  
      44.         // 存放t。含义是存储"需要的字符"（用它做标的去查询）以及需要的数量
      45.         Map<Character, Integer> needsMap = new HashMap<>();
      46.         // 滑动窗口中符合条件的字符
      47.         Map<Character, Integer> windowMap = new HashMap<>();
      48.  
      49.         // 将t 存入needsMap 中
      50.         for (int i = 0; i < t.length(); i++) {
      51.             char temp = t.charAt(i);
      52.             needsMap.put(temp, needsMap.getOrDefault(temp, 0) + 1);
      53.         }
      54.  
      55.         // 滑动窗口的左边界
      56.         int left = 0;
      57.         // 滑动窗口的右边界
      58.         int right = 0;
      59.  
      60.         // count 用来记录当前滑动窗口windowMap 中符合need 要求的字符的数量
      61.         // 当count == need.size() 的时候，即可shrink 窗口
      62.         int count = 0;
      63.         // 符合要求最优解的开始位置
      64.         int start = 0;
      65.  
      66.         int len = Integer.MAX_VALUE;
      67.  
      68.         // 一次遍历找"可行解"
      69.         while(right < s.length()) {
      70.             // 更新窗口
      71.             char c = s.charAt(right);
      72.             // 扩大窗口
      73.             right ++;
      74.  
      75.             if (needsMap.containsKey(c)) {
      76.                 windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
      77.                 if (needsMap.get(c).equals(windowMap.get(c))) {
      78.                     count ++;
      79.                 }
      80.             }
      81.             // shrink 左边界，找到符合条件的最优解
      82.             while (count == needsMap.size()) {
      83.                 // 不断"打擂"，寻找满足条件的len 的最短值，并记录最短子串起始start 位置
      84.                 if (right - left < len) {
      85.                     len = right - left;
      86.                     start = left;
      87.                 }
      88.                 // 更新窗口
      89.                 char d = s.charAt(left);
      90.                 // 窗口缩小
      91.                 left ++;
      92.                 if (needsMap.containsKey(d)) {
      93.                     // window.put(d,window.get(d)-1);
      94.                     // ——bug：
      95.                     // 若一进去就将window对应的键值缩小，
      96.                     // 就永远不会满足下面的if，while也会一直执行，
      97.                     // 直到left越界，因此，尽管和上面对窗口的处理几乎一样，
      98.                     // 但是这个处理的顺序还是很关键的！要细心！
      99.                     
      100.                     // 如果滑动窗口windowMap 中包含了
      101.                     if (needsMap.get(d).equals(windowMap.get(d))) {
      102.                         // count 用来记录当前滑动窗口windowMap 中符合need 要求的字符的数量
      103.                         count --;
      104.                     }
      105.                     windowMap.put(d, windowMap.get(d) - 1);
      106.                 }
      107.             }
      108.         }
      109.         return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
      110.     }
      111.     
      112. }

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

      给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

      异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

      （看不懂） 
      1.     public static List<Integer> findAnagrams(String s, String t) {
      2.  
      3.         List<Integer> result = com.google.common.collect.Lists.newArrayList();
      4.         int left, right;
      5.         left = right = 0;
      6.         Map<Character, Integer> needs = Maps.newHashMap();
      7.         Map<Character, Integer> windows = Maps.newHashMap();
      8.  
      9.         for (int i = 0; i < t.length(); i++) {
      10.             Character c = t.charAt(i);
      11.             needs.put(c, needs.getOrDefault(c, 0) + 1);
      12.         }
      13.  
      14.         int match = 0;
      15.         while (right < s.length()) {
      16.  
      17.             char c1 = s.charAt(right);
      18.             if (needs.containsKey(c1)) {
      19.                 windows.put(c1, windows.getOrDefault(c1, 0) + 1);
      20.                 if (Objects.equals(windows.get(c1), needs.get(c1))) {
      21.                     match ++;
      22.                 }
      23.             }
      24.             right ++;
      25.  
      26.             while (match == needs.size()) {
      27.                 if (right - left == t.length()) {
      28.                     result.add(left);
      29.                 }
      30.                 char c2 = s.charAt(left);
      31.                 if (needs.containsKey(c2)) {
      32.                     windows.put(c2, windows.get(c2) - 1);
      33.                     if (windows.get(c2) < needs.get(c2)) {
      34.                         match --;
      35.                     }
      36.                 }
      37.                 left ++;
      38.             }
      39.         }
      40.         return result;
      41.     }
    • 3. 无重复字符的最长子串 - M
      要求无重复字符的最长子串，即找出从每一个字符开始的，不包含重复字符的最长子串，最长的那个字符串即为答案。
      此题很明显特征，使用“滑动窗口”。使用两个指针，标识子串的前指针和后指针。同时还需要一个数据结构来判断是否有重复字符，可以用set。前指针移动的时候，从set 中移除；后指针移动的时候，向set 中添加。 
      1.     public static int lengthOfLongestSubString(String s) {
      2.  
      3.         int left, right;
      4.         left = right = 0;
      5.         int result = 0;
      6.         Map<Character, Integer> windows = new HashMap<>();
      7.         while (right < s.length()) {
      8.             char c1 = s.charAt(right);
      9.             windows.put(c1, windows.getOrDefault(c1, 0) + 1);
      10.             right++;
      11.  
      12.             while(windows.get(c1) >1) {
      13.                 char c2 = s.charAt(left);
      14.                 windows.put(c2, windows.get(c2) - 1);
      15.                 left ++;
      16.             }
      17.             result = Math.max(result, right - left);
      18.         }
      19.         return result;
      20.     }

    • 340. 至多包含 K 个不同字符的最长子串 - H if not di[s[start]]: di.pop(s[start]) # 记得pop if value == 0
      （被锁）

       

      给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。

      示例 1: 输入: s = "eceba", k = 2 输出: 3 解释: 则 T 为 "ece"，所以长度为 3。 示例 2: 输入: s = "aa", k = 1 输出: 2 解释: 则 T 为 "aa"，所以长度为 2。

      1. public static int lengthOfLongestSubStringKDistinct(String s, int k) {
      2.         int len = s.length();
      3.         char[] charArray = s.toCharArray();
      4.         // 这个数组用来统计遍历过程中字母出现的次数
      5.         int[] freq = new int[123];
      6.  
      7.         // 使用count 来记录有多少个不同的字符
      8.         int count = 0;
      9.         int result = 0;
      10.  
      11.         int left = 0;
      12.         int right = 0;
      13.  
      14.         while (right < len) {
      15.             if (freq[charArray[right]] == 0) {
      16.                 count ++;
      17.             }
      18.             // 遍历到了某个字符之后，用来记录字母是否出现过
      19.             freq[charArray[right]] ++;
      20.             right ++;
      21.  
      22.             // 缩小窗口
      23.             while (count > k) {
      24.                 freq[charArray[left]] --;
      25.                 if (freq[charArray[left]] == 0) {
      26.                     count --;
      27.                 }
      28.                 left ++;
      29.             }
      30.             result = Math.max(result, right - left);
      31.         }
      32.         return result;
      33.     }







       
  • DP

    最长回文子串，dp[i][j] 表示从i 到j 是否为回文子串。
    两个for 循环，第一个是循环是字符串的长度，从2 开始
    第二个for 循环是枚举左下标，从0 开始

    最长回文子序列的长度，dp[i][j] 代表字符串从i 到j 的回文子序列的长度。两次遍历，i 从最后开始。

    子序列可以不连续；子串必须是连续的
     
    • 5. 最长回文子串(最长回文子数组)
      原创（@王漂亮）提示解法：- M dp[i][j], dp[0][0]=1, 要for r再for l以确保dp[i+1][j-1赋值

      如果一个子串，是回文串，并且长度大于2，那么如果将其首尾两个字母去除，它仍然是回文串。通过这种思路，可以使用动态规划的方法解决本题。使用P(i,j) 表示字符串s 的第i 到j 个字母组成的串（表示为s[i:j] ）是否为回文串：
      · P（i，j） = true，如果S i ... S j 是回文串
      · P（i，j） = false，其他情况
      对于其他情况，包含两种可能
      · s[i,j] 本身不是一个回文串
      · i > j，此时s[i,j] 本身不合法
      那么可以写出动态规划的状态转移方程
      · P(i,j) = P(i+1, j-1) ∧ (Si == Sj)
      也就是说，只有s[i+1:j-1] 是回文串，并且s 的第i 和j 个字母相同时，s[i:j] 才会是回文串
      而上文是建立在子串长度大于2 的前提，我们还需要考虑动态规划的边界条件，即子串的长度为1 或者2。对于长度为1 的子串，它显然是回文串。对于长度为2 的子串，只要两个字母相同，也是一个回文串。因为可以写出其边界条件：
      · P(i, i) = true
      ` P(i, i+1) = (Si == S i+1)
      根据这个思路，就可以完成动态规划了。最终答案即为所有P(i, j) 中j - i + 1（即子串长度）的最大值。

        
      1. class Solution {
      2.     public String longestPalindrome(String s) {
      3.  
      4.         int len = s.length();
      5.         if (len < 2) {
      6.             return s;
      7.         }
      8.         int maxLen = 1;
      9.         int begin = 0;
      10.         // dp[i][j] 表示s[i...j] 是否为回文串
      11.         boolean[][] dp = new boolean[len][len];
      12.  
      13.         for (int i = 0; i < len; i++) {
      14.             dp[i][i] = true;
      15.         }
      16.         char[] charArray = s.toCharArray();
      17.         // 递推开始
      18.         // 枚举子串长度，长度从2 开始，长度为2、3、4、5...
      19.         for (int L = 2; L <= len; L++) {
      20.  
      21.             // 枚举左边界，左边界上限设置可以宽松些
      22.             // 上面for 循环设置的是串的长度；下面的是左边界在哪里
      23.             for (int i = 0; i < len; i++) {
      24.                 // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
      25.                 int j = L + i - 1;
      26.                 // 如果右边界超限制，则退出循环
      27.                 if (j >= len) {
      28.                     break;
      29.                 }
      30.                 if (charArray[i] != charArray[j]) {
      31.                     dp[i][j] = false;
      32.                 } else if (charArray[i] == charArray[j]){
      33.                     // 字符相等，且长度小于等于2
      34.                     if (j - i <= 2) {
      35.                         dp[i][j] = true;
      36.                     } else {
      37.                         // 且字符相等，长度大于2
      38.                         dp[i][j] = dp[i + 1][j - 1];
      39.                     }
      40.                 }
      41.  
      42.  
      43.                 // 只要dp[i][j] == true 成立，就表示字符串s[i...j] 是回文子串，此时记录长度和起始位置
      44.                 // 每次循环要记录一下“最长的”
      45.                 if (dp[i][j] && j - i + 1 > maxLen) {
      46.                     maxLen = j - i + 1;
      47.                     begin = i;
      48.                 }
      49.  
      50.             }
      51.  
      52.         }
      53.  
      54.         return s.substring(begin, begin + maxLen);
      55.     }
      56. }



       
    • 1143. 最长公共子序列 - M    [longest common subsequence (LCS)]

      dp[i+1][]j+1], dp = (max(dp[i-1][j], dp[i][j-1])) or dp[i-1][j-1]+1

      是典型的二维动态规划的问题。

      给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

      （在文章最开始有）

       
    • 91. 解码方法 dp[i] = dp[i-1] + dp[i-2] (有条件的), 1. s[i] != '0'; 10<=s[i-1:i+1]<=26
       

      一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

      'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 

      用dp 数组表示，dp[i] 表示到了第i 个字符的时候，共有多少种解法。
      进行到第i 个字符的时候，判断使用一个字符还是两个字符进行解码
        
      1. public static int numDecodings(String s) {
      2.  
      3.         int n = s.length();
      4.         int[] dp = new int[n + 1];
      5.         dp[0] = 1;
      6.         for (int i = 1; i <= n; i++) {
      7.             if (s.charAt(i - 1) != '0') {
      8.                 dp[i] = dp[i - 1];
      9.             }
      10.             // 这里包含条件"当前数字为0" 的情况
      11.             if (i > 1 && s.charAt(i - 2) != '0' && calculateSum(s.charAt(i - 2), s.charAt(i - 1)) <= 26) {
      12.                 dp[i] += dp[i - 2];
      13.             }
      14.         }
      15.         return dp[n];
      16.  
      17.     }
      18.  
      19.     public static Integer calculateSum(char a, char b) {
      20.         return (a - '0') * 10 + (b - '0');
      21.     }
  • 其他高频题
    • 28. 实现 strStr() - E
       

      给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

        
      1. public static int strStr(String haystack, String needle) {
      2.         int n = haystack.length();
      3.         int m = needle.length();
      4.  
      5.         for (int i = 0; i + m <= n; i ++) {
      6.             boolean flag = true;
      7.             for (int j = 0; j < m; j++) {
      8.                 if (haystack.charAt(i + j) != needle.charAt(j)) {
      9.                     flag = false;
      10.                     break;
      11.                 }
      12.             }
      13.             if (flag) {
      14.                 return i;
      15.             }
      16.         }
      17.         return -1;
      18.     }
    • 14. 最长公共前缀 - E 先排序再比较first,last; for z in zip(*strs): if len(set(z)) == 1:res += z[0]
       

      编写一个函数来查找字符串数组中的最长公共前缀。

      如果不存在公共前缀，返回空字符串 ""。


      LCP
       

      编写一个函数来查找字符串数组中的最长公共前缀。
      如果不存在公共前缀，返回空字符串 ""。

       

      1.     public String longestCommonPrefix(String[] strs) {
      2.         if (strs == null || strs.length == 0) {
      3.             return "";
      4.         }
      5.         // 第一个字符串的长度
      6.         int length = strs[0].length();
      7.         // 字符串数组的个数
      8.         int count = strs.length;
      9.         for (int i = 0; i < length; i++) {
      10.             char c = strs[0].charAt(i);
      11.             for (int j = 1; j < count; j++) {
      12.                 if (i == strs[j].length() || strs[j].charAt(i) != c) {
      13.                     return strs[0].subSequence(0, i).toString();
      14.                 }
      15.             }
      16.         }
      17.         return strs[0];
      18.     }

    • 125. 验证回文串 - E s[start].isalnum()
       

      如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

      字母和数字都属于字母数字字符。

      给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

      1.     public static boolean isPalindrome(String s) {
      2.         StringBuilder stringBuilder = new StringBuilder();
      3.         int length = s.length();
      4.         for (int i = 0; i < length; i++) {
      5.             char c = s.charAt(i);
      6.             if (Character.isLetterOrDigit(c)) {
      7.                 stringBuilder.append(Character.toLowerCase(c));
      8.             }
      9.         }
      10.         StringBuilder reversed = new StringBuilder(stringBuilder.toString()).reverse();
      11.         return reversed.toString().equals(stringBuilder.toString());
      12.     }
    • 49. 字母异位词分组 - M di["".join(sorted(s))].append(s)
       

      给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

      字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

      1.     public List<List<String>> groupAnagrams(String[] strs) {
      2.  
      3.         Map<String, List<String>> map = new HashMap();
      4.         for (String string : strs) {
      5.             char[] array = string.toCharArray();
      6.             Arrays.sort(array);
      7.             String key = new String(array);
      8.             List list = map.getOrDefault(map.get(key), new ArrayList());
      9.             list.add(array);
      10.             map.put(key, list);
      11.         }
      12.         return new ArrayList<List<String>>(map.values());
      13.     }

  • 其他杂题
    • 8. 字符串转换整数 (atoi) - M try: int(s[:idx]) except: break


       
    • 227. 基本计算器 II stack存数字和+-*/，数字一添加结束就看能不能做*/，最后一起算+- 
        
      1.     public int calculate(String s) {
      2.  
      3.         Deque<Integer> stack = new LinkedList<Integer>();
      4.         char preSign = '+';
      5.         int num = 0;
      6.         int n = s.length();
      7.         for (int i = 0; i < n; i++) {
      8.             if (Character.isDigit(s.charAt(i))) {
      9.                 num = num * 10 + s.charAt(i) - '0';
      10.             }
      11.             if (!Character.isDigit(s.charAt(i))
      12.                     && s.charAt(i) != ' '
      13.                     || i == n - 1) {
      14.                 switch(preSign) {
      15.                     case '+':
      16.                         stack.push(num);
      17.                         break;
      18.                     case '-':
      19.                         stack.push(-num);
      20.                         break;
      21.                     case '*':
      22.                         stack.push(stack.pop() * num);
      23.                         break;
      24.                     case '/':
      25.                         stack.push(stack.pop() / num);
      26.                         break;
      27.                 }
      28.                 preSign = s.charAt(i);
      29.                 num = 0;
      30.             }
      31.         }
      32.         int ans = 0;
      33.         while(!stack.isEmpty()) {
      34.             ans += stack.pop();
      35.         }
      36.         return ans;
      37.     }

       

二叉树

  • 二叉树的构造
    • 297. 序列化与反序列化 - H se: return " ".join(res); de: nums = iter(data.split()), num = next(nums)
        
      1.     public String serialize(TreeNode root) {
      2.         return rserialize(root, "");
      3.     }
      4.  
      5.     // 这是先根遍历，根、左、右。继续向下的时候，如果左边一直有，那么就是一直左左左
      6.     public String rserialize(TreeNode root, String str) {
      7.         if (root == null) {
      8.             str += "None,";
      9.         } else {
      10.             str += String.valueOf(root.val) + ",";
      11.             str = rserialize(root.left, str);
      12.             str = rserialize(root.right, str);
      13.         }
      14.         return str;
      15.     }
      16.   
      17.     public TreeNode deserialize(String data) {
      18.         String[] dataArray = data.split(",");
      19.         List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
      20.         return rdeserialize(dataList);
      21.     }
      22.   
      23.     // 所以在解析的时候，也是按照根、左、右的顺序处理
      24.     public TreeNode rdeserialize(List<String> dataList) {
      25.         if (dataList.get(0).equals("None")) {
      26.             dataList.remove(0);
      27.             return null;
      28.         }
      29.   
      30.         TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
      31.         dataList.remove(0);
      32.         root.left = rdeserialize(dataList);
      33.         root.right = rdeserialize(dataList);
      34.     
      35.         return root;
      36.     }

       
    • 144. 二叉树前序遍历 根左右（先根遍历，根被先遍历，所以是根、左、右）

       
    • 94. 二叉树中序遍历 左根右（中序遍历，根被中遍历，所以是左、根、右）

       
    • 145. 二叉树后序遍历 左右根; 迭代(dfs+stack从上到下右到左)：r, stack = [], [root] while stack:
      （后续遍历，根后便利，所以是左、右、根
        
      1.     public List<Integer> postorderTraversal(TreeNode root) {
      2.         List<Integer> result = new ArrayList<>();
      3.         postorder(root, result);
      4.         return result;
      5.  
      6.     }
      7.  
      8.     public void postorder(TreeNode root, List<Integer> res) {
      9.         if (root == null) {
      10.             return;
      11.         }
      12.         postorder(root.left, res);
      13.         postorder(root.right, res);
      14.         res.add(root.val);
      15.     }

    • 102. 层序遍历 单队列，q = deque([(root, layer)])，q.popleft()

       
    • 103. 锯齿形层次遍历 双队列, cur, nex = deque([root]), deque()
        
      1.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
      2.         List<List<Integer>> ans = new LinkedList<List<Integer>>();
      3.         if (root == null) {
      4.             return ans;
      5.         }
      6.  
      7.         Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
      8.         nodeQueue.offer(root);
      9.         boolean isOrderLeft = true;
      10.  
      11.         while (!nodeQueue.isEmpty()) {
      12.             Deque<Integer> levelList = new LinkedList<Integer>();
      13.             int size = nodeQueue.size();
      14.             for (int i = 0; i < size; ++i) {
      15.                 TreeNode curNode = nodeQueue.poll();
      16.                 if (isOrderLeft) {
      17.                     levelList.offerLast(curNode.val);
      18.                 } else {
      19.                     levelList.offerFirst(curNode.val);
      20.                 }
      21.                 if (curNode.left != null) {
      22.                     nodeQueue.offer(curNode.left);
      23.                 }
      24.                 if (curNode.right != null) {
      25.                     nodeQueue.offer(curNode.right);
      26.                 }
      27.             }
      28.             ans.add(new LinkedList<Integer>(levelList));
      29.             isOrderLeft = !isOrderLeft;
      30.         }
      31.  
      32.         return ans;
      33.     }

    • 二叉树的对角线遍历 递归，helper(node, layer)

       
    • 105. 前序与中序构造二叉树 递归，自调，idx = inorder.index(preorder[0])
       

      给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

       

    • 106. 中序与后序构造二叉树

       
  • 高频题目
    • 101. 对称二叉树 helper: isMatch(left, right)
       

      给你一个二叉树的根节点 root ， 检查它是否轴对称。

      使用递归：

      1.     public boolean isSymmetric(TreeNode root) {
      2.         if (root == null) {
      3.             return true;
      4.         }
      5.         return dfs(root.left, root.right);
      6.     }
      7.  
      8.     public boolean dfs(TreeNode left, TreeNode right) {
      9.         // 递归终止条件是两个节点都为空；或者其中只有一个为空；或者两个节点值不相等
      10.         if (left == null && right == null) {
      11.             return true;
      12.         }
      13.         if (left == null || right == null) {
      14.             return false;
      15.         }
      16.         if (left.val != right.val) {
      17.             return false;
      18.         }
      19.         // 再递归比较左节点左孩子、右节点有孩子等等
      20.         return dfs(left.right, right.left) && dfs(left.left, right.right);
      21.     }

      使用迭代：

      1.     public boolean isSymmetric(TreeNode root) {
      2.         if (root == null || (root.left == null && root.right == null)) {
      3.             return true;
      4.         }
      5.         // 用队列保存节点
      6.         LinkedList<TreeNode> queue = new LinkedList<>();
      7.         // 根节点的左右孩子分别放入队列中
      8.         queue.add(root.left);
      9.         queue.add(root.right);
      10.         while(queue.size() > 0) {
      11.             // 取出两个节点
      12.             TreeNode left = queue.removeFirst();
      13.             TreeNode right = queue.removeFirst();
      14.             // 判断
      15.             if (left == null && right == null) {
      16.                 continue;
      17.             }
      18.             if (left == null || right == null) {
      19.                 return false;
      20.             }
      21.             if (left.val != right.val) {
      22.                 return false;
      23.             }
      24.             queue.add(left.left);
      25.             queue.add(right.right);
      26.             queue.add(left.right);
      27.             queue.add(right.left);
      28.         }
      29.         return true;
      30.     }


       

    • 116. 填充每个节点的下一个右侧节点指针 对于任意一次递归，只需要考虑如何设置子节点的 next 属性

      递归： 
      1.     public Node connect(Node root) {
      2.         if (root == null) {
      3.             return null;
      4.         }
      5.         if (root.left != null) {
      6.             root.left.next = root.right;
      7.             if (root.next != null) {
      8.                 root.right.next = root.next.left;
      9.             }
      10.         }
      11.         connect(root.left);
      12.         connect(root.right);
      13.         return root;
      14.     }
      迭代：
        
      1.     public Node connect(Node root) {
      2.         if (root == null) {
      3.             return root;
      4.         }
      5.         LinkedList<Node> queue = new LinkedList<>();
      6.         queue.add(root.left);
      7.         queue.add(root.right);
      8.         while (queue.size() != 0) {
      9.             int length = queue.size();
      10.             Node tempNode = queue.poll();
      11.             if (tempNode == null) {
      12.                 return root;
      13.             }
      14.             queue.add(tempNode.left);
      15.             queue.add(tempNode.right);
      16.             for (int i = 0; i < length - 1; i++) {
      17.                 Node popedNode = queue.poll();
      18.                 queue.add(popedNode.left);
      19.                 queue.add(popedNode.right);
      20.                 tempNode.next = popedNode;
      21.                 tempNode = popedNode;
      22.             }
      23.         }
      24.         return root;
      25.     }
    • 117. 填充每个节点的下一个右侧节点指针 II 思路同上，在l&r的时候先设置好l，追加设置r or l，很复杂多看看

        
      1.     public Node connect(Node root) {
      2.         if (root == null) {
      3.             return root;
      4.         }
      5.         // cur 是当前层的没一层链表的指针
      6.         Node cur = root;
      7.         // 外层while 循环是针对二叉树的高度的遍历
      8.         while (cur != null) {
      9.             Node dummy = new Node(0);
      10.             Node pre = dummy;
      11.             while (cur != null) {
      12.                 // 遍历当前层，然后串联下一层
      13.                 if (cur.left != null) {
      14.                     pre.next = cur.left;
      15.                     pre = pre.next;
      16.                 }
      17.                 if (cur.right != null) {
      18.                     pre.next = cur.right;
      19.                     pre = pre.next;
      20.                 }
      21.                 cur = cur.next;
      22.             }
      23.             // 上面的逻辑的作用，就是把下面cur 层下面那层的串联起来
      24.             cur = dummy.next;
      25.         }
      26.         return root;
      27.     }
    • 104. 二叉树的最大深度 return max(maxdepth(root.left), maxdepth(root.right))+1

      可以递归，可以迭代。递归代码很简单： 
      1.     public int maxDepth(TreeNode root) {
      2.         if (root == null) {
      3.             return 0;
      4.         } else {
      5.             return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
      6.         }
      7.     }
    • 662. 二叉树最大宽度 self.left[], 每层碰到的第一个节点为left, dfs(node, layer, pos*2(+1))


      此题求二叉树所有层的最大宽度，比较直观的方法是求出每一层的宽度，然后求出最大值。
      注意：求每一层的宽度时，因为两端点间的null 节点也需要计入宽度，因此可以对节点进行编号。
      一个编号为index 的左子节点的编号记为2 * index；右子节点编号为2 * index + 1
      那么每层的最大宽度就是用每层节点的最大编号减去最小编号再加1。

      遍历节点时，可以用广度优先搜索来遍历每一层的节点，并求出最大值。


      迭代：

      1.     public int widthOfBinaryTree(TreeNode root) {
      2.         int res = 1;
      3.         // 存放当前层的节点。最开始的时候就只有root 层。
      4.         List<Pair<TreeNode, Integer>> arr = new ArrayList<>();
      5.         arr.add(new Pair<>(root, 1));
      6.         
      7.         while (!arr.isEmpty()) {
      8.             List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
      9.             for (Pair<TreeNode, Integer> pair : arr) {
      10.                 TreeNode node = pair.getKey();
      11.                 int index = pair.getValue();
      12.                 
      13.                 if (node.left != null) {
      14.                     tmp.add(new Pair<>(node.left, 2 * index));
      15.                 }
      16.                 
      17.                 if (node.right != null) {
      18.                     tmp.add(new Pair<>(node.right, 2 * index + 1));
      19.                 }
      20.             }
      21.             res = Math.max(res, arr.get(arr.size() - 1).getValue() - arr.get(0).getValue() + 1);
      22.             arr = tmp;
      23.         }
      24.         return res;
      25.     }

      递归dfs：

       

      遍历时如果是先访问左子节点，再访问右子节点，每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值，需要记录下来进行后续的比较。一次深度优先搜索中，需要当前节点到当前行最左边节点的宽度，以及对子节点进行深度优先搜索，求出最大宽度，并返回最大宽度。

      1.     Map<Integer, Integer> levelMin = new HashMap<Integer, Integer>();
      2.  
      3.     public int widthOfBinaryTree(TreeNode root) {
      4.         return dfs(root, 1, 1);
      5.     }
      6.  
      7.     public int dfs(TreeNode node, int depth, int index) {
      8.         if (node == null) {
      9.             return 0;
      10.         }
      11.         // 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
      12.         levelMin.putIfAbsent(depth, index);
      13.         return Math.max(index - levelMin.get(depth) + 1,
      14.                         Math.max(dfs(node.left, depth + 1, index * 2),
      15.                                  dfs(node.right, depth + 1, index * 2 + 1)));
      16.     }
    • 543.二叉树的直径 helper: maxgain, self.res = max(left + right + 1, self.res)
        
      1.         // 树的直径可以分解成子问题，就是每个节点的左右子节点的深度的和+1
      2.         // 而不是经过每个节点的子树的“直径”
      3.     int ans = 0;
      4.     public int diameterOfBinaryTree(TreeNode root) {
      5.         if (root == null) {
      6.             return ans;
      7.         }
      8.         dfs(root);
      9.         return ans - 1;
      10.     }
      11.  
      12.     public int dfs(TreeNode node) {
      13.         if (node == null) {
      14.             return 0;
      15.         }
      16.         int left = dfs(node.left);
      17.         int right = dfs(node.right);
      18.         ans = Math.max(left + right + 1, ans);
      19.         return Math.max(left, right) + 1;
      20.     }
    • 236. 二叉树的最近公共祖先 helper(root), if left + right + mid >=2: res, return left or right or mid
        
      1. Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
      2.     Set<Integer> visited = new HashSet<Integer>();
      3.  
      4.     public void dfs(TreeNode root) {
      5.         if (root.left != null) {
      6.             parent.put(root.left.val, root);
      7.             dfs(root.left);
      8.         }
      9.         if (root.right != null) {
      10.             parent.put(root.right.val, root);
      11.             dfs(root.right);
      12.         }
      13.     }
      14.  
      15.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      16.         dfs(root);
      17.         while (p != null) {
      18.             visited.add(p.val);
      19.             p = parent.get(p.val);
      20.         }
      21.         while (q != null) {
      22.             if (visited.contains(q.val)) {
      23.                 return q;
      24.             }
      25.             q = parent.get(q.val);
      26.         }
      27.         return null;
      28.     }

       
    • 112. 路径总和
       

      给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

      叶子节点 是指没有子节点的节点。


      这道题类似层序遍历，可以使用广度优先搜索算法。但是不需要像层序遍历那样，计算queue 中的节点的个数。

      广度优先搜索：
        
      1. public boolean hasPathSum(TreeNode root, int targetSum) {
      2.  
      3.         if (root == null) {
      4.             return false;
      5.         }
      6.         Queue<TreeNode> nodeQueue = new LinkedList<>();
      7.         Queue<Integer> valueQueue = new LinkedList<>();
      8.  
      9.         nodeQueue.offer(root);
      10.         valueQueue.offer(root.val);
      11.  
      12.         while (!nodeQueue.isEmpty()) {
      13.             // 这个不像层序遍历，这个不需要感知queue 的长度
      14.             TreeNode tempNode = nodeQueue.poll();
      15.             Integer tempVal = valueQueue.poll();
      16.  
      17.             // 如果当前节点是叶子节点，那么就进行判断
      18.             if (tempNode.left == null && tempNode.right == null) {
      19.                 if (tempVal == targetSum) {
      20.                     return true;
      21.                 }
      22.                 continue;
      23.             }
      24.  
      25.             // 子节点进队列
      26.             if (tempNode.right != null) {
      27.                 nodeQueue.offer(tempNode.right);
      28.                 valueQueue.offer(tempNode.right.val + tempVal);
      29.             }
      30.             if (tempNode.left != null) {
      31.                 nodeQueue.offer(tempNode.left);
      32.                 valueQueue.offer(tempNode.left.val + tempVal);
      33.             }
      34.         }
      35.         return false;
      36.     }
      递归：
        
      1.     public boolean hasPathSum(TreeNode root, int targetSum) {
      2.  
      3.         if (root == null) {
      4.             return false;
      5.         }
      6.         if (root.left == null && root.right == null) {
      7.             return targetSum == root.val;
      8.         }
      9.         return hasPathSum(root.left, targetSum - root.val)
      10.                 || hasPathSum(root.right, targetSum - root.val);
      11.  
      12.     }
    • 113. 路径总和 II



       
    • 437.路径总和 III
    • 124. 最大路径和 - H helper: maxgain, self.res = max(left + right + root.val, self.res)
  •  二叉搜索树
    • 98. 验证二叉搜索树 helper(root, low = float("-inf"), high = float("inf"))
      二叉搜索树的性质，中序遍历得到一个正序数组
    • 426. BST转排序的双向链表 中序, 处理当前节点，last.right = cur, cur.left = last
    • 450. 删除BST中的节点 - M 找到后三种情况, 无子节点/一个子节点/有两子结点(max,remove_max)
    • 删除区间内的节点

堆

使用大顶堆做正序排序；使用小顶堆做逆序排序。

构建堆，就是从最后一个非叶子节点开始，如果构建大顶堆，就是将每个parent 与child 进行对比，如果child 大于parent，那么进行调整。同时调整到child 位置的原parent 可能还是小于其child，所以要继续调整。

堆在算法题目中的应用主要包括以下几点：

  • TopK 问题 （尤其是大数据处理）
  • 优先队列
  • 利用堆求中位数
  1. // 以下代码都认为父节点序号为0
  2.  
  3. /**
  4.  * 调整为大顶堆（此方法只是一个调整的过程，并不是建堆的）
  5.  * @param arr   待调整的数组
  6.  * @param parent   当前父节点的下标
  7.  * @param length   需要对多少个元素进行调整
  8.  */
  9. private static void adjustHeap(int[] arr, int parent, int length){
  10.     //临时保存父节点
  11.     int temp = arr[parent];
  12.     //左子节点的下标
  13.     int child = 2 * parent + 1;
  14.     //如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
  15.     while(child < length){
  16.         //判断左子节点和右子节点的大小,若右边大，则把child定位到右边
  17.         if(child + 1 < length && arr[child] < arr[child + 1]){
  18.             child ++;
  19.         }
  20.         //若child大于父节点，则交换位置，否则退出循环
  21.         if(arr[child] > temp){
  22.             //父子节点交换位置
  23.             arr[parent] = arr[child];
  24.             //因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
  25.             //把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
  26.             parent = child;
  27.             child = 2 * parent + 1;
  28.         }else{
  29.             //如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
  30.             //因此无需继续循环
  31.             break;
  32.         }
  33.     }
  34.     //把当前节点值替换为最开始暂存的父节点值
  35.     arr[parent] = temp;
  36. }
  37.  
  38. public static void main(String[] args) {
  39.     int[] arr = {4,1,9,3,7,8,5,6,2};
  40.     // 构建一个大顶堆，从最下面的非叶子节点开始向上遍历
  41.     // 这才是建堆的过程
  42.     for (int i = arr.length/2 - 1 ; i >= 0; i--) {
  43.         adjustHeap(arr,i,arr.length);
  44.     }
  45.     System.out.println(Arrays.toString(arr));
  46. }     
  47.  
  48.  
  49.  
  50. //堆排序，大顶堆，升序
  51. private static void heapSort(int[] arr){
  52.     //构建一个大顶堆，从最下面的非叶子节点开始向上遍历
  53.     for (int i = arr.length/2 - 1 ; i >= 0; i--) {
  54.         adjustHeap(arr,i,arr.length);
  55.     }
  56.     System.out.println(Arrays.toString(arr));
  57.     //循环执行以下操作：1.交换堆顶元素和末尾元素 2.重新调整为大顶堆
  58.     for (int i = arr.length - 1; i > 0; i--) {
  59.         //将堆顶最大的元素与末尾元素互换，则数组中最后的元素变为最大值
  60.         int temp = arr[i];
  61.         arr[i] = arr[0];
  62.         arr[0] = temp;
  63.         //从堆顶开始重新调整结构，使之成为大顶堆
  64.         // i代表当前数组需要调整的元素个数，是逐渐递减的
  65.         adjustHeap(arr,0,i);
  66.     }
  67.  
  68. }
  69.

  • 347. 前 K 个高频元素 heapq.nlargest(k, c.keys(), key = c.get)；长度为k的堆


    首先使用map 来存储每个元素对应的出现次数；然后再使用堆来维护大小关系

    使用堆来实现 
    1.     public int[] topKFrequent(int[] nums, int k) {
    2.         Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
    3.         for (int num : nums) {
    4.             occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
    5.         }
    6.  
    7.         // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
    8.         PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
    9.             public int compare(int[] m, int[] n) {
    10.                 return m[1] - n[1];
    11.             }
    12.         });
    13.         for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
    14.             int num = entry.getKey(), count = entry.getValue();
    15.             if (queue.size() == k) {
    16.                 if (queue.peek()[1] < count) {
    17.                     queue.poll();
    18.                     queue.offer(new int[]{num, count});
    19.                 }
    20.             } else {
    21.                 queue.offer(new int[]{num, count});
    22.             }
    23.         }
    24.         int[] ret = new int[k];
    25.         for (int i = 0; i < k; ++i) {
    26.             ret[i] = queue.poll()[0];
    27.         }
    28.         return ret;
    29.     }
    生成map 的时间复杂度是O(n)；
    构建堆（k 个元素）的时间复杂度是log(K)；
    因为是对n 个元素遍历进行建堆&重建堆，所以整体时间复杂度nlog(k)

     
  • 215. 数组中的第K个最大元素 堆；二分搜索牛逼
    （1）使用堆，构建大顶堆；
             使用堆的时候，一个是调整的方法
             public void adjust(int[] nums, int parent, int length){}
             另外一个是建堆的方法
             public void heapify(int[] nums){}; 这个方法里面要从第一个非叶子节点开始从下往上整
             然后是堆排序的方法，找第k 大的元素，只需要执行k 次即可。每次把最大的堆顶元素和最后一个元素替换，循环执行k 次。则数组中倒数第k 个元素就是解。

    （2）使用快排的思想，以一个key，小于的放左边，大于的放右边
            
     
  • 378. 有序矩阵中第K小的元素 堆，klogk: 一次添加右和下，pop出其中较小的，每次pop k-1，pop k次返回

    利用矩阵的性质，使用二分法 
    1.     public int kthSmallest(int[][] matrix, int k) {
    2.         // 一共n 行
    3.         int n = matrix.length;
    4.         int left = matrix[0][0];
    5.         int right = matrix[n - 1][n - 1];
    6.         while (left < right) {
    7.             int mid = (left + right) / 2;
    8.             if (check(matrix, mid, k, n)) {
    9.                 right = mid;
    10.             } else {
    11.                 left = mid + 1;
    12.             }
    13.         }
    14.         return left;
    15.     }
    16.  
    17.     public boolean check(int[][] matrix, int mid, int k ,int n) {
    18.  
    19.         int i = n - 1;
    20.         int j = 0;
    21.         int num = 0;
    22.         while (i >=0 && j < n) {
    23.             if (matrix[i][j] <= mid) {
    24.                 num += i + 1;
    25.                 j ++;
    26.             } else {
    27.                 i --;
    28.             }
    29.         }
    30.         return num >= k;
    31.  
    32.     }



     
  • 218. 天际线问题（hard）

动态规划-

动态规划问题的一般形式就是“求最值”，比如求“最长递增子序列”，“最小编辑距离”。而求解最值的问题的核心就是“穷举”。这样最直观。
而动态规划的问题存在几个特点：

  1. 存在“重叠子问题”，如果暴力穷举，效率低下，所以需要“备忘录”或者“dp table”来优化穷举过程，避免不必要的计算。

  2. 存在“最优子结构”，这样才能通过子问题的最值得到原问题的最值。
    对最优子结构的理解，就是到了某一步的选择，可以得到一个最优的结果。所以说到了这个子选择的时候，结构是最优的。给它个名称，叫：最优子结构。

  3. 找出“状态转移方程”。动态规划的核心思想就是“穷举”，而动态规划问题中，穷举是通过状态转移方程来完成的。


解题步骤：
明确“状态” -> 定义dp 数组/函数的含义 -> 明确“选择” -> 明确base case
dp 数组中存的就是各个状态，通过选择各个状态，选择待选项，得到转移方程，结合base case，得到最终解。


举例： 

322. 凑零钱问题

1. 凑零钱 各个子问题间是相互独立的，互不干扰。
对于“凑零钱问题”，比如说求amount = 11 时的最少硬币数，如果凑出了amount = 10 的最少硬币数（子问题），只需要把子问题的答案加一就是原问题的答案。因为硬币的数量是不限制的，子问题之间没有相互制约，是互相独立的。
2. 列出状态转移方程。先确定“状态”，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount。
3. 确定dp 数组的定义：当前目标金额是n，至少需要dp(n) 个硬币凑出该金额（意思就是凑出金额n 最少需要的金币数是dp[n]）。
4. 然后确定“选择”并优化，也就是对于每个状态，可以做出什么选择改变当前状态。具体到此问题，无论目标金额是多少，选择就是从面额列表coins 中选择一个硬币，然后目标金额就会减少。
5. 最后明确base case。
（以上参考labuladong）


题目要求“最少”，即求最优解；要凑出总数为n 的最少枚硬币，和凑出n - coin 枚硬币是一样的问题，即存在子问题，是有重复子问题的；根据example 分析，f(11) = min(f(10), f(9), f(6)) + 1。
（参考：凑零钱问题 - 知乎）

上述寥寥几行，就把一个动态规划问题的基本点都描述出来了.

  • 1、首先是有重复子问题；
  • 2、其次需要最优规划，即是子问题中的最优解再去找上一级。
  • 3、列出状态转移方程，其中最重要的就是确定谁是变化的量，这里就是总价amount。
  1.     public static int coinChange(int[] coins, int amount) {
  2.         // dp 数组代表凑出金额i 的时候，最少需要走多少步
  3.         int[] dp = new int[amount+1];
  4.         // 初始化dp 数组，以方便后续的比较
  5.         Arrays.fill(dp, amount + 1);
  6.         // 初始化条件
  7.         dp[0] = 0;
  8.         // 循环amount 次，确认累积到金额i 需要多少次
  9.         for (int i = 1; i <= amount; i ++) {
  10.             // 按照每个硬币的面额做判断
  11.             for (int coin : coins) {
  12.                 // 当i < coin 的时候，证明没有解，不用做什么变化
  13.                 if (coin <= i) {
  14.                     dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  15.                 }
  16.             }
  17.         }
  18.         // 判断当前是否有结果，就和初始化的数字做呼应
  19.         return dp[amount] == amount + 1 ? -1 : dp[amount];
  20.     }

对于“最优子结构”，很多问题可能都具有“最优子结构”，但是不存在“重叠子问题”，所以不能被归为“动态规划系列”。如果想满足“最优子结构”，子问题间必须相互独立。

基础篇

对于动态规划，拿300 题和53 题举例子。两道题都是使用一维数组的，但是有点不一样，现在我总结不出来，理解一下，理解并总结不出来的话，那就记住好了。注意特点，300 是子序列，53 是子数组。

  • 300. 最长上升子序列（文章初始位置有）
    原创（@王漂亮）提示解法：dp[n], if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1)

    使用一维数组dp[n]，定义dp[i] 为考虑前i 个元素，以第i 个数字结尾的最长上升子序列的长度。其中nums[i] 必须被选取。
    在计算dp[i] 之前，已经计算出了dp[0 ... i-1] 的值，则状态转移方程为：
    dp[i] = max( dp[j] ) + 1, 其中 0 <= j < i 且nums[i] > nums[j]
    时间复杂度o(n方)，思想就是两个for 循环，对于每一个元素，比较前面所有元素和当前nums[i] 的大小，如果小，那么就+1
     
    按照上述解题步骤：
    1）明确状态：就是题目要求，最长递增子序列的最长长度。

    2）dp 数组定义：数组存的就是各种状态，定义一维数组，dp[i] 表示以第i 个元素结尾最长上升子序列的长度。

    3）明确选择：第i 个数字选或者不选，然后写出状态转移方程。

    4）basecase：第0 个数字，第1 个数字。
      
    1.     public int lengthOfLIS(int[] nums) {
    2.  
    3.         if (nums.length ==  0) {
    4.             return 0;
    5.         }
    6.  
    7.         // 定义dp 数组，dp[i] 表示以第i 个数字结尾，最长上升子序列的长度。
    8.         int[] dp = new int[nums.length];
    9.         dp[0] = 1;
    10.         int maxAns = 1;
    11.         // 我们从小到大计算 \textit{dp}dp 数组的值，在计算dp[i] 之前，我们已经计算出dp[0…i−1] 的值，则状态转移方程为：
    12.         // dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
    13.         for (int i = 0; i < nums.length; i++) {
    14.             dp[i] = 1;
    15.             for (int j = 0; j < i; j++) {
    16.                 if (nums[i] > nums[j]) {
    17.                     dp[i] = Math.max(dp[i], dp[j] + 1);
    18.                 }
    19.             }
    20.             maxAns = Math.max(maxAns, dp[i]);
    21.         }
    22.         return maxAns;
    23.     }
    题解：首先明确dp 数组所存数据的含义，假设dp[0...i-1] 都已知，想办法求出dp[i]。
    如果不能明确出dp 数组的含义，那么可能是dp 数组存储到信息不够，不足以存储下一步，需要把dp 数组扩大成二维或者三维数组。

     
  • 53. 最大子序和 dp[n], dp[i] = max(nums[i], dp[i-1] + nums[i])

    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

    使用一维数组f[n] 来进行动态规划设计，f[i] 代表以第i 个数字结尾的“连续子数组最大和”，那么答案就是max(f[i])
    因此就是求出每个未知的f(i)，然后返回f 数组中的最大值即可
    那么就是要考虑num[i] 单独成为一段，还是加入前面那一段，这取决于num[i] 和f(i-1)+num[i] 的大小。于是状态转移方程为：
    f(i) = max{f(i-1) + nums[i], nums[i]}

    按照上述四段式：状态确定；dp 数组确定（存放各个状态，用什么样的dp table）；判断如何选择（状态转移方程）；base case
      
    1. // 两种解法，一看就懂
    2.  
    3.  
    4. // 第一种
    5.     public int maxSubArray(int[] nums) {
    6.         if (nums.length == 0) {
    7.             return 0;
    8.         }
    9.         int[] dp = new int[nums.length];
    10.  
    11.         dp[0] = nums[0];
    12.         int ans = nums[0];
    13.         for (int i = 1; i < nums.length; i++) {
    14.  
    15.             dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    16.             ans = Math.max(dp[i], ans);
    17.  
    18.         }
    19.         return ans;
    20.     }
    21.  
    22.  
    23. // 第二种
    24.  
    25.  
    26.     public int maxSubArray(int[] nums) {
    27.         int pre = 0, maxAns = nums[0];
    28.         for (int x : nums) {
    29.             pre = Math.max(pre + x, x);
    30.             maxAns = Math.max(maxAns, pre);
    31.         }
    32.         return maxAns;
    33.     }

     
  • 152. 最大乘积子序列 dp[n][2], return max(dp, key=lambda x:x[1])[1]
    这道题是求子序列。类比53，可以知道，53 的解法对于此题不适用。因为当前位置的最优解未必是由前一个位置的最优解得到的。
    可以根据正负性进行分类讨论。
    考虑当前一位置如，如果是一个负数，那么希望它前一个位置结尾的某个段的积也是负数，这样就可以负负得正，并且希望这个积尽可能“负得更多”；如果当前一个数字是正数，那么就希望它前一个位置结尾的某个段的积也是正数，并且希望它尽可能的大。
    所以除了f max(i)，我们需要再维护一个f min(i)，状态转移方程为：
    f max(i) = max{f max(i - 1) * ai, f min(i - 1) * ai, ai}
    f min(i) = min{f min(i - 1) * ai, f max(i - 1) * ai, ai}

    而此题的状态转移方程，第i 个状态只和第i - 1 个状态有关，类比53 题，所以根据“滚动数组”的思想，可以用两个变量来维护i - 1 的状态，就不用两个数组了。
      
    1.     public int maxProduct(int[] nums) {
    2.         int length = nums.length;
    3.         int[] maxF = new int[length];
    4.         int[] minF = new int[length];
    5.         maxF[0] = nums[0];
    6.         minF[0] = nums[0];
    7.         int ans = maxF[0];
    8.         for (int i = 1; i < length; i++) {
    9.             maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
    10.             minF[i] = Math.min(maxF[i - 1] * nums[i], Math.min(nums[i], minF[i - 1] * nums[i]));
    11.  
    12.             ans = Math.max(ans, maxF[i]);
    13.         }
    14.         return ans;
    15.     }

  • 279. 完全平方数 dp[n+1],
    动态规划的技术建立在重用中间解的结果来计算最终解的思想之上。几乎所有动态规划，首先都会创建一个一维或多维数组DP 来保存中间子解的值，通常数组最后一个值代表最终解。此题是给定正整数n，找出最小的可以加和为此数的完全平方数的个数。

    可以依据题目要求写出状态表达式：f[i] 表示最少需要多少个数的平方来表示整数i。
    而这些数字肯定落在区间[1, 根号n] 区间。可以枚举找出这些数字，假设当前枚举到j，那么我们还需要若干数的平方，构成i - (j平方)。此时就发现了该子问题和原问题类似，只是规模变小了。
    ​
    其中f[0] = 0 为边界条件，实际上我们无法表示数字0，只是为了保证状态转移过程中遇到j 恰为（根号j）的情况合法。
    同时因为计算f[i] 时所需要用到的状态只有f[i - (j平方)]，必然小于i，因此我们只需要从小到大地枚举i 来计算f[i] 即可。
    ------------------------------------

    标签：动态规划
    首先初始化长度为 n+1 的数组 dp，每个位置都为 0
    如果 n 为 0，则结果为 0
    对数组进行遍历，下标为 i，每次都将当前数字先更新为最大的结果，即 dp[i]=i，比如 i=4，最坏结果为 4=1+1+1+1 即为 4 个数字
    动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i 表示当前数字，j*j 表示平方数

      
    1. class Solution {
    2.     public int numSquares(int n) {
    3.         int[] dp = new int[n + 1]; // 默认初始化值都为0
    4.         for (int i = 1; i <= n; i++) {
    5.             dp[i] = i; // 最坏的情况就是每次+1
    6.             for (int j = 1; j * j <= i; j++) { 
    7.                 dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
    8.             }
    9.         }
    10.         return dp[n];
    11.     }
    12. }



    ​​​
  • 322. 找零钱问题
      
    1.     public static int coinChange(int[] coins, int amount) {
    2.  
    3.         int[] dp = new int[amount + 1];
    4.         // 初始化数组，每个元素为amount + 1 的原因是为了避免混淆，初始化成别的也行，在最后做判断的时候确认一下就好
    5.         for (int i = 1; i <= amount; i++) {
    6.             dp[i] = amount + 1;
    7.         }
    8.  
    9.         // 第一层for 循环是对每个子结构做遍历查找，即amount 为1，为2，为3... 的时候
    10.         for (int i = 1; i <= amount; i++) {
    11.             // 对每个选择做判断
    12.             for (int c : coins) {
    13.                 if (i - c < 0) {
    14.                     continue;
    15.                 }
    16.                 // 找出最小的
    17.                 dp[i] = Math.min(dp[i], dp[i - c] + 1);
    18.             }
    19.  
    20.         }
    21.         // 判断当前是否有结果，就和初始化的数字做呼应
    22.         return dp[amount] == amount + 1 ? -1 : dp[amount];
    23.  
    24.     }

  • 其他
    • 70. 爬楼梯 dp[n+1], dp[0], dp[1], dp[2] = 0, 1, 2 ；dp[i] = dp[i-2] + dp[i-1]
        
      1.     public static int climbStairs(int n) {
      2.         if (n == 1) {
      3.             return 1;
      4.         }
      5.         if (n == 2) {
      6.             return 2;
      7.         }
      8.         int pre = 1;
      9.         int cur = 2;
      10.         int result = 3;
      11.         for (int i = 3; i <= n; i++) {
      12.             result = pre + cur;
      13.             pre = cur;
      14.             cur = result;
      15.         }
      16.         return result;
      17.     }
    • 198. 打家劫舍 dp[n], dp[i] = max(dp[i-1], dp[i-2]+nums[i])
       

      你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

      给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

      一维数组进行动态规划，dp[i] 代表到了第i 个屋子能偷窃到的最高金额。
        
      1.     public int rob(int[] nums) {
      2.         if (nums == null || nums.length == 0) {
      3.             return 0;
      4.         }
      5.         int length = nums.length;
      6.         if (nums.length == 1) {
      7.             return nums[0];
      8.         }
      9.         int dp[] = new int[length];
      10.         dp[0] = nums[0];
      11.         dp[1] = Math.max(nums[0], nums[1]);
      12.         for (int i = 2; i < length; i++) {
      13.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
      14.         }
      15.         return dp[length -1 ];
      16.     }
    • 62. 不同路径。

      题目为一个m x n 的网格，即m 行n 列，左上角有个机器人，每次只能往右或者往下移动一个格，请问移动到右下角一共有多少条路径。

      使用动态规划，用f(i, j) 表示从左上角走到(i, j) 的路径数量，其中i 和j 的范围分别是[0, m) 和[0, n)。使用二维数组进行动态规划。
      状态转移方程为：
      f(i, j) = f(i - 1, j) + f(i, j - 1)
      边界条件，第一行和第一列都是1。
        
      1.     public int uniquePaths(int m, int n) {
      2.  
      3.         int[][] f = new int[m][n];
      4.         for (int i = 0; i < m; i++) {
      5.             f[i][0] = 1;
      6.         }
      7.         for (int j = 0; j < n; j++) {
      8.             f[0][j] = 1;
      9.         }
      10.         for (int i = 1; i < m; i++) {
      11.             for (int j = 1; j < n; j++) {
      12.                 f[i][j] = f[i - 1][j] + f[i][j - 1];
      13.             }
      14.         }
      15.         return f[m - 1][n - 1];
      16.     }

       
    • 编辑距离（文章开始处有）
      给定两个字符串s1 和s2，计算出将s1 转换成s2 所使用的最少操作数。可以对一个字符串进行如下操作：插入、删除、替换。 
      1.     public static int minDistance(String s1, String s2) {
      2.  
      3.         int m = s1.length();
      4.         int n = s2.length();
      5.         int[][] dp = new int[m + 1][n + 1];
      6.         // base case
      7.         for (int i = 1; i <= m; i++) {
      8.             dp[i][0] = i;
      9.         }
      10.         for (int j = 1; j < n; j++) {
      11.             dp[0][j] = j;
      12.         }
      13.         for (int i = 1; i <= m; i++) {
      14.             for (int j = 1; j <= n; j++) {
      15.                 if (s1.charAt(i) == s2.charAt(j)) {
      16.                     dp[i][j] = dp[i - 1][j - 1];
      17.                 } else {
      18.                     dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));
      19.                 }
      20.             }
      21.         }
      22.         return dp[m][n];
      23.     }
    • 887.高楼扔鸡蛋
      框架：这个问题有什么“状态”，有什么“选择”，然后穷举。
      1. “状态”就是当前拥有的鸡蛋数k 和需要测试的楼层数N。随着测试的进行，鸡蛋个数减少，楼层搜索范围减少，对应的就是状态的变化。
      2. “选择”其实就是选择哪层扔鸡蛋。
      3. 明确了“状态”和“选择”，就基本形成了动态规划的基本思路。肯定是个二维的dp 数组或者带有两个参数的dp 函数来表示状态转移；外加一个for 循环来遍历所有的选择，选择最优的选择更新状态。

      我们在选择第i 层扔鸡蛋之后，就可能出现两种情况：鸡蛋碎了，鸡蛋没碎。这时候，状态转移方程就来了：
      1. 鸡蛋碎了，那么鸡蛋个数K 就减一，搜索的楼层区间应该从[1, N] 变为[1, i - 1]。
      2. 鸡蛋没碎，那么鸡蛋个数K 不变，搜索的楼层区间应该从[1, N] 变为[i + 1, N]。


       
    • 正方形问题
      1277. 统计全为 1 的正方形子矩阵的个数

      我们用 f[i][j] 表示以 (i, j) 为右下角的正方形的最大边长，同时这个最大边长也可以表示以(i, j) 为右下角的正方形的个数。

      看看1277 的题解就很清晰了。
        
      1.     public int countSquares(int[][] matrix) {
      2.         int row = matrix.length;
      3.         int column = matrix[0].length;
      4.         int[][] dp = new int[row][column];
      5.         int ans = 0;
      6.  
      7.         for (int i = 0; i < row; i++) {
      8.             for (int j = 0; j < column; j++) {
      9.                 if (i == 0 || j == 0) {
      10.                     dp[i][j] = matrix[i][j];
      11.                 } else if (matrix[i][j] == 0) {
      12.                     dp[i][j] = 0;
      13.                 } else {
      14.                     dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
      15.                 }
      16.                 ans += dp[i][j];
      17.             }
      18.         }
      19.         return ans;
      20.     }

      221. 最大正方形
      在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积

      使用动态规划，我们用dp[i][j] 表示以(i, j) 为右下角，且只包含1 的正方形的边长的最大值。
       

      1.     public int maximalSquare(char[][] matrix) {
      2.         int row = matrix.length;
      3.         int column = matrix[0].length;
      4.         int[][] dp = new int[row][column];
      5.         int ans = 0;
      6.  
      7.         for (int i = 0; i < row; i++) {
      8.             for (int j = 0; j < column; j++) {
      9.                 if (i == 0 || j == 0) {
      10.                     if (matrix[i][j] == '1') {
      11.                         dp[i][j] = 1;
      12.                     }
      13.                 } else if (matrix[i][j] == '0') {
      14.                     dp[i][j] = 0;
      15.                 } else {
      16.                     dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
      17.                 }
      18.                 ans = Math.max(ans, dp[i][j]);
      19.             }
      20.         }
      21.         return ans;
      22.     }


       

背包问题

dp对容量的init都是dp[v+1], 从空开始init 如果要减少空间的话，把dp[i]省掉，dp[v+1]的循环逆序

  • 01背包问题

    01  背包问题看这个，一看就懂：背包问题 - 知乎。只看文字，别看代码。
    这个也很不错：动态规划之背包问题系列 - 知乎
      
    1. class Solution {
    2.  
    3.     /**
    4.      * @param v v[i] 代表第i 个物品的体积
    5.      * @param w w[i] 代表第i 个物品的价值
    6.      * @param V 背包的总体积
    7.      * @return
    8.      */
    9.     public int findMax(int[] v, int[] w, int V) {
    10.  
    11.         // 物品个数
    12.         int n = v.length;
    13.  
    14.         // 构造二维dp 数组。这个二维数组整体多了一个0 行和0 列，所以不用初始化。
    15.         // 否则就要初始化第一行，小于第i 个物品体积的遍历体积都是0，大于等于第i 个物品体积的遍历体积的位置数字都是第i 个物品的价值。i = 0
    16.         // n 个物品，所以有n 行；因为背包总体积是V，所以遍历V，从0 开始
    17.         // 数组初始化，各个元素都是0
    18.         int[][] f = new int[n + 1][V + 1];
    19.  
    20.         for (int i = 1; i <= n; i++) {
    21.             for (int j = 1; j <= V; j++) {
    22.                 // 如果第i 个物品的体积大于当前遍历到的最大的体积，那么当前物品肯定不能选择
    23.                 if (v[i - 1] > j) {
    24.                     f[i][j] = f[i -1][j];
    25.                 } else {
    26.                     // 转移方程计算f(i,j) 的大小
    27.                     // 分为选择还是不选择
    28.                     f[i][j] = Math.max(f[i][j - v[i - 1]] + w[i-1], f[i - 1][j]);
    29.                 }
    30.             }
    31.         }
    32.         return f[n][V];
    33.  
    34.     }
    35.  
    36.  
    37.     public int findMax2(int[] v, int[] w, int V) {
    38.         // 可以优化控件，但是不能优化时间，时间还是O(n方)
    39.         // 由状态转移方程可以看出，第i 行结果只和第i - 1 行结果有关。而为了防止数据被覆盖，所以j 要从后往前遍历
    40.  
    41.         int n = v.length;
    42.         int[] dpTable = new int[V + 1];
    43.         // 需要初始化
    44.         for (int k = w[0]; k <= V; k++) {
    45.             dpTable[k] = w[0];
    46.         }
    47.  
    48.         for (int i = 1; i <= n; i++) {
    49.             for (int j = V; j >=1; j--) {
    50.                 if (v[i - 1] > j) {
    51.                     // 如果第i 个物品的体积大于遍历体积数字，那么不变（还是上一行的结果）
    52.                 } else {
    53.                     // 否则做状态转移，判断选不选第i 个物品
    54.                     dpTable[j] = Math.max(dpTable[j - v[i - 1]] + w[i - 1], dpTable[j]);
    55.                 }
    56.             }
    57.         }
    58.         return dpTable[V];
    59.     }
    60.  
    61.     public static void main(String[] args) {
    62.         Solution solution = new Solution();
    63.         int[] v = {5,3,4,2};
    64.         int[] w = {60,50,70,30};
    65.  
    66.         System.out.println(solution.findMax2(v, w, 5));
    67.     }
    68.  
    69. }
    • 416. 分割等和子集

      对于背包问题，要判断当前有几个“状态”。比如说，容量为w 的背包，n 个物品，就两个状态，用二维数组表示。如：dp[i][j]

      这道题定义dp[i][j] 为：前i 个元素是否有可以满足和为j 的子数组 
      1. public boolean canPartition(int[] nums) {
      2.  
      3.         int sum = 0;
      4.  
      5.         int length = nums.length;
      6.         if (length < 2) {
      7.             return false;
      8.         }
      9.  
      10.         for (int num : nums) {
      11.             sum += num;
      12.         }
      13.  
      14.         if (sum % 2 != 0) {
      15.             return false;
      16.         }
      17.  
      18.         int target = sum / 2;
      19.  
      20.         boolean[][] dp = new boolean[length + 1][target + 1];
      21.         dp[0][0] = true;
      22.  
      23.         for (int i = 1; i <= length; i++) {
      24.             for (int j = 1; j <= target; j++) {
      25.  
      26.                 if (nums[i - 1] > j) {
      27.                     // 不能选择
      28.                     dp[i][j] = dp[i - 1][j];
      29.                 } else {
      30.                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
      31.                 }
      32.  
      33.             }
      34.         }
      35.         return dp[length][target];
      36.     }


       
    • 494. 目标和 di={0:1}, nex_di, di.get(s, 0)

      回溯：       
      1.     // 回溯解法，其中选择列表就是加法或者减法，nums 的遍历在backtrack 中使用参数“i” 实现
      2.  
      3.     int result = 0;
      4.     public int findTargetSumWays(int[] nums, int S) {
      5.  
      6.         if (nums.length == 0) {
      7.             return 0;
      8.         }
      9.         backtrack(nums, 0, 0, S);
      10.         return result;
      11.     }
      12.  
      13.     void backtrack(int[] nums, int i, int additionResult, int target) {
      14.         // 判断条件等于length 而不是等于length - 1 的原因是，i == nums.length 的时候，还是需要继续进行循环的
      15.         if (i == nums.length) {
      16.             if (additionResult == target) {
      17.                 result ++;
      18.             }
      19.             return;
      20.         }
      21.  
      22.         additionResult += nums[i];
      23.         backtrack(nums, i + 1, additionResult, target);
      24.         additionResult -= nums[i];
      25.  
      26.         additionResult -= nums[i];
      27.         backtrack(nums, i + 1, additionResult, target);
      28.         additionResult += nums[i];
      29.     }
      动态规划：

       

  • 完全背包问题

    也看上面的链接就好（同下面的链接）。
    对于完全背包，先看这个链接：动态规划之背包问题系列 - 知乎
    再看这个链接：https://zhuanlan.zhihu.com/p/346625269对于完全背包的状态转移方程的理解：
     

    ​

    上面那个公式含义很明确，即不选择第i 种物品。

    对于下面的公式，如果确定放，背包中应该出现至少一件第i种物品，所以F[i][j]种至少应该出现一件第i种物品,即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]？因为F[i][j-C[i]]里面可能有第i种物品，也可能没有第i种物品。我们要确保F[i][j]至少有一件第i件物品，所以要预留C[i]的空间来存放一件第i种物品。
      
    1. class Solution {
    2.  
    3.     /**
    4.      * @param v 每个物品的体积
    5.      * @param w 每个物品的价值（重量）
    6.      * @param V 背包的容积
    7.      * @return 最大价值（重量）
    8.      */
    9.     public int findCompleteBackpackResult(int[] v, int[] w, int V) {
    10.  
    11.         // n 个物品
    12.         int n = v.length;
    13.  
    14.         int dp[][] = new int[n + 1][V + 1];
    15.  
    16.         for (int i = 1; i <= n; i++) {
    17.             for (int j = 1; j <= V; j++) {
    18.                 if (v[i - 1] > j) {
    19.                     dp[i][j] = dp[i - 1][j];
    20.                 } else {
    21.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i - 1]] + w[i - 1]);
    22.                 }
    23.             }
    24.         }
    25.         return dp[n][V];
    26.     }
    27.  
    28.     public int findCompleteBackpackResult2(int[] v, int[] w, int V) {
    29.  
    30.         // n 个物品
    31.         int n = v.length;
    32.  
    33.         int[] dp = new int[V + 1];
    34.  
    35.         // 初始化dp 数组
    36.         for (int k = v[0]; k <= V; k ++) {
    37.             // k 是当前遍历到的容量，v[0] 是第一个物品的体积，w[0] 是第一个物品的价值（重量）
    38.             dp[k] = k / v[0] * w[0];
    39.         }
    40.  
    41.         for (int i = 1; i <= n; i++) {
    42.             for (int j = 1; j <= V; j++) {
    43.                 if (v[i - 1] > j) {
    44.                     // 如果第i 个物品的体积大于当前遍历到的容积，则第i 个物品无法选择
    45.                 } else {
    46.                     dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
    47.                 }
    48.             }
    49.         }
    50.  
    51.         return dp[V];
    52.     }
    53.  
    54.     public static void main(String[] args) {
    55.         Solution solution = new Solution();
    56.         int[] v = {3,2,5,1,6,4};
    57.         int[] w = {6,5,10,2,16,8};
    58.  
    59.         System.out.println(solution.findCompleteBackpackResult(v, w, 10));
    60.  
    61.         System.out.println(solution.findCompleteBackpackResult2(v, w, 10));
    62.     }
    63.  
    64. }
    • 322. 零钱兑换 if i in coins: dp[i] = 1
    • 377. 组合总和 IV if i-c>=0: dp[i] += dp[i-c]
  • 二维费用的背包问题
    • 474. 一和零 dp[i][j] = max(dp[i][j], dp[i-c["0"]][j-c["1"]]+1)

进阶算法

回溯算法

回溯算法，就是一个决策树遍历的过程。
参考：回溯算法套路详解 - 知乎
决策树解释：比如说解决一个问题，一共有三个步骤，每个步骤可以选择“是”或者“否”。就是一个三层的二叉树（不考虑根节点）。决策选择哪个，形成的一棵树，就叫决策树。
解决这个问题，只需要考虑：
1）路径，即已经做出的选择。2）选择列表，就是当前可以做的选择。3）结束条件，就是已经到达决策树底层，无法再做选择的条件。
框架：

  1.     result = Lists.newArrayList();
  2.     void backtrack(路径, 选择列表) {
  3.         if 满足结束条件:
  4.         result.add(路径)
  5.         return
  6.  
  7.         for 选择 in 选择列表:
  8.         做选择
  9.         backtrack(路径, 选择列表)
  10.         撤销选择
  11.     }

其核心就是 for 循环里面的递归，在递归调用之前“做选择”，在递归调用之后“撤销选择”
 

  • 46. 全排列 used = [False]*len(nums)
    参考这个链接：回溯算法套路详解 - 知乎，回溯算法，遍历决策树，很简单。不要看力扣上的官方讲解。
      
    1. class Solution {
    2.  
    3.     List<List<Integer>> result = new ArrayList<>();
    4.  
    5.     List<List<Integer>> premute(int[] nums) {
    6.  
    7.         LinkedList<Integer> track = new LinkedList<>();
    8.         backTrack(nums, track);
    9.         return result;
    10.     }
    11.  
    12.     void backTrack(int[] nums, LinkedList<Integer> track) {
    13.  
    14.         // 出发结束条件
    15.         if (track.size() == nums.length) {
    16.             result.add(new ArrayList<>(track));
    17.             return;
    18.         }
    19.         for (int i = 0; i < nums.length; i ++ ) {
    20.             if (track.contains(nums[i])) {
    21.                 continue;
    22.             }
    23.             track.add(nums[i]);
    24.             backTrack(nums, track);
    25.             track.removeLast();
    26.         }
    27.  
    28.     }
    29.  
    30. }


     
  • 78. 子集 for j in range(i, len(nums)): backtrack(track+[nums[j]], j+1) 
    1. 参考：https://zhuanlan.zhihu.com/p/109523146
    2.  
    3.  
    4. 方法1：对于数组中每个元素，选择或者是不选择：
    5.  
    6.     List<List<Integer>> result = new ArrayList<>();
    8.     public List<List<Integer>> subsets(int[] nums) {
    10.         int len = nums.length;
    11.  
    12.         if (len == 0) {
    13.             return result;
    14.         }
    15.         Deque<Integer> deque = new LinkedList<>();
    16.         dfs(nums, len, 0, deque);
    17.         return result;
    18.  
    19.     }
    20.  
    21.     public void dfs(int[] nums, int len, int index, Deque<Integer> path) {
    22.  
    23.         if (index == len) {
    24.             result.add(new ArrayList<>(path));
    25.             return;
    26.         }
    27.         path.addLast(nums[index]);
    28.         dfs(nums, len, index + 1, path);
    29.         path.removeLast();
    30.         dfs(nums, len, index + 1, path);
    31.  
    32.     }
    33.  
    34.  
    35. 方法2：回溯法
    36.

    参考：回溯算法团灭子集、排列、组合问题 - labuladong - 博客园
     
  • 22. 括号生成 for p in ["(", ")"]: if counter[p] < n:
      
    1.     public List<String> generateParenthesis(int n) {
    2.  
    3.         List<String> resultList = new ArrayList<>();
    4.         backtrack(resultList, new StringBuilder(), 0, 0, n);
    5.         return resultList;
    6.  
    7.     }
    8.  
    9.     public void backtrack(List<String> ans, StringBuilder cur, int left, int right, int max) {
    10.         if (cur.length() == max * 2) {
    11.             ans.add(cur.toString());
    12.             return;
    13.         }
    14.         if (left < max) {
    15.             cur.append('(');
    16.             backtrack(ans, cur, left + 1, right, max);
    17.             cur.deleteCharAt(cur.length() - 1);
    18.         }
    19.         if (right < left) {
    20.             cur.append(')');
    21.             backtrack(ans, cur, left, right + 1, max);
    22.             cur.deleteCharAt(cur.length() - 1);
    23.         }
    24.     }




     
  • 131. 分割回文串 for i in range(1, len(s)+1): if s[:i] == s[:i][::-1]: backtrack()
     

图：拓扑排序和Union Find

拓扑排序详解 通俗易懂 - 知乎 拓扑排序

  • Union Find if self.parent[idx] != idx: self.parent[idx] = self.find(self.parent[idx])
    • 200. 岛屿数量 uf = UnionFind(row*col+1) dummy_node = row*col
      可以用深度优先搜索、广度优先搜索

      这道题的本质，无论是深度优先搜索还是广度优先搜索，都是在搜索的过程中，把原本的陆地标记为“已访问过”。

      深度优先搜索： 
      1.     public int numIslands(char[][] grid) {
      2.         int count = 0;
      3.         int height = grid.length;
      4.         int width = grid[0].length;
      5.         for (int i = 0; i < height; i++) {
      6.             for (int j = 0; j < width; j++) {
      7.                 if (grid[i][j] == '1') {
      8.                     // 遍历所有连接的陆地，将其置位"已访问"
      9.                     dfs(grid, i, j, width, height);
      10.                     count ++;
      11.                 }
      12.             }
      13.         }
      14.         return count;
      15.     }
      16.  
      17.     // 函数的目的是做dfs，把周边的是1 的那些都给置位"已遍历过"状态
      18.     public void dfs(char[][] grid, int i, int j, int width, int height) {
      19.         // dfs 的时候首先要记得basecase
      20.         if (i < 0 || j < 0 ||
      21.             i >= height || j >= width ||
      22.             grid[i][j] == '0' || grid[i][j] == '2') {
      23.             return;
      24.         }
      25.         grid[i][j] = '2';
      26.         dfs(grid, i + 1, j, width, height);
      27.         dfs(grid, i -1, j, width, height);
      28.         dfs(grid, i, j + 1, width, height);
      29.         dfs(grid, i, j -1, width, height);
      30.     }
      广度优先搜索： 
      1. public int numIslands(char[][] grid) {
      2.         int count = 0;
      3.         int height = grid.length;
      4.         int width = grid[0].length;
      5.         for (int i = 0; i < height; i++) {
      6.             for (int j = 0; j < width; j++) {
      7.                 if (grid[i][j] == '1') {
      8.                     count ++;
      9.                     // 然后进行广度优先搜索，对"已访问过的"陆地进行标记
      10.                     Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
      11.                     queue.add(new Pair<>(i, j));
      12. //                    grid[i][j] = '2';
      13.                     while (queue.size() != 0) {
      14.                         Pair<Integer, Integer> land = queue.poll();
      15.                         int r = land.getKey();
      16.                         int c = land.getValue();
      17.                         grid[r][c] = '2';
      18.                         // 然后分别对旁边的那些"陆地"做查询并入队列
      19.                         if (r + 1 < height && grid[r + 1][c] == '1') {
      20.                             queue.offer(new Pair<>(r + 1, c));
      21. //                            grid[r + 1][c] = '2';
      22.                         }
      23.                         if (r - 1 >= 0 && grid[r -1][c] == '1') {
      24.                             queue.offer(new Pair<>(r - 1, c));
      25. //                            grid[r-1][c] = '2';
      26.                         }
      27.                         if (c + 1 < width && grid[r][c + 1] == '1') {
      28.                             queue.offer(new Pair<>(r, c + 1));
      29. //                            grid[r][c + 1] = '2';
      30.                         }
      31.                         if (c - 1 >= 0 && grid[r][c -1] == '1') {
      32.                             queue.offer(new Pair<>(r, c - 1));
      33. //                            grid[r][c - 1] = '2';
      34.                         }
      35.                     }
      36.                 }
      37.             }
      38.         }
      39.         return count;
      40.     }
    • 323. 无向图中连通分量的数目
       

      给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

      注意:
      你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0]  相同，所以它们不会同时在 edges 中出现。

      用并查集、dfs、bfs 都可以做，但是我现在看不懂。




       
  • 拓扑排序 indegree记录流入个数, outdegree记录流出数组
    • 207. 课程表 初始化出入度, 找到入度为0的节点们, 从他们开始dfs, 不断找到入读为0的。



       
    • 210. 课程表 II



       
    • 269. 火星词典 建图，key为前序，value为后继，然后拓扑排序逐个添加入度为零的节点。



       

数据结构设计

  • 146. LRU缓存机制 init cache, capacity, head, tail

    LRU：最近最少使用（least recently used），是一种缓存机制的设计。
    实现：哈希表 + 双向链表
    （哈希链表：哈希表 + 双向链表 的结合）

    看这个的介绍：LRU算法实现（java） - 简书 
    1. class LRUCache {
    2.  
    3.     // 维护一个双向链表的节点结构
    4.     class Node {
    5.         int key, value;
    6.         Node pre, next;
    7.  
    8.         Node(int key, int value) {
    9.             this.key = key;
    10.             this.value = value;
    11.             pre = this;
    12.             next = this;
    13.         }
    14.     }
    15.  
    16.     // LRU Cache的容量
    17.     private final int capacity;
    18.     // dummy节点是一个冗余节点，dummy的next是链表的第一个节点，dummy的pre是链表的最后一个节点
    19.     private Node dummy;
    20.     // 保存key-Node对，Node是双向链表节点，为了“快速查找”
    21.     private Map<Integer, Node> map;
    22.  
    23.     public LRUCache(int capacity) {
    24.         this.capacity = capacity;
    25.         dummy = new Node(0, 0);
    26.         map = new HashMap<>();
    27.     }
    28.  
    29.     // get 的时候，除了正常取值，还要改变元素顺序，通过两个步骤完成
    30.     // 1. 在链表中删除node
    31.     // 2. 将node 添加到链表末尾
    32.     public int get(int key) {
    33.         Node node = map.get(key);
    34.         if (node == null) {
    35.             return -1;
    36.         }
    37.         remove(node);
    38.         add(node);
    39.         return node.value;
    40.     }
    41.  
    42.     // put 的时候要判断当前节点是否存在，分别分析
    43.     public void put(int key, int value) {
    44.         Node node = map.get(key);
    45.         // 如果不存在，需要判断当前容量大小，然后做删除最近最少未使用节点
    46.         if (node == null) {
    47.             if (map.size() >= capacity) {
    48.                 // 删除的时候，一个是要删除map 中的值
    49.                 map.remove(dummy.next.key);
    50.                 // 另一个是要删掉链表中的节点
    51.                 remove(dummy.next);
    52.             }
    53.             node = new Node(key, value);
    54.             // 然后map 中存
    55.             map.put(key, node);
    56.             // 然后链表中存
    57.             add(node);
    58.         } else {
    59.             // 如果结构中存在这个值，那么只需要改变这个node 的顺序即可
    60.             map.remove(node.key);
    61.             remove(node);
    62.             node = new Node(key, value);
    63.             map.put(key, node);
    64.             add(node);
    65.         }
    66.     }
    67.  
    68.     /**
    69.      * 在链表尾部添加新节点
    70.      *
    71.      * @param node 新节点
    72.      */
    73.     private void add(Node node) {
    74.         dummy.pre.next = node;
    75.         node.pre = dummy.pre;
    76.         node.next = dummy;
    77.         dummy.pre = node;
    78.     }
    79.  
    80.     /**
    81.      * 从双向链表中删除该节点
    82.      *
    83.      * @param node 要删除的节点
    84.      */
    85.     private void remove(Node node) {
    86.         node.pre.next = node.next;
    87.         node.next.pre = node.pre;
    88.     }
    89. }
  • 380. 常数时间插入、删除和获取随机元素
    return random.choice(arr); di的key为value, val为value在数组中的位置




     
  • 706. 设计哈希映射 size1000的1000个list，表头为空；Node(key, val, nex)


     
  • 155. 最小栈 stack, minstack



     
  • 295-. 数据流的中位数 最大堆+1，最小堆，每次入堆，都有从另一个堆里挤出一个元素


     
  • 208. 实现 Trie (前缀树)

高频系列专题

数组矩阵杂题

  • 双指针
    • 42. 接雨水 O(3n), res[i] = min(left_max, right_max), 一次性求好左边最大值和右边最大值

      参考这个解法：力扣



       
    • 11. 盛最多水的容器 l从前往后，r从后往前，每次移动l和r中较小的值，算当前面积
      就用双指针，先移动小的那个


       
  • 数组
    • 239. 滑动窗口最大值 - H

      优先队列
      单调队列


       
    • 41. 缺失的第一个正数 置换，保证数组的第x−1个元素为x
    • 51.上一个排列
    • 238. 除自身之外的乘积
      不能用除法，因为有可能出现0
      利用索引左侧所有数字的乘积乘以右侧所有数字的乘积即可
      方法：左右乘积列表
      初始化两个空数组L 和R。对于索引i，L[i] 代表左侧所有数字的乘积，R[i] 代表右侧所有数字的乘积。
      使用两个循环来初始化L 和R。
      然后迭代，可以得到结果。
  • 矩阵
    • 48. 旋转图像 - M
      (1) 对于矩阵中第i 行的第j 个元素，旋转后，它出现在第j 行，倒数第i 列的位置。利用一个新的二维矩阵，做中间存储。
      (2)  通过翻转代替旋转。先通过水平轴翻转，再通过主对角线翻转，就是顺时针旋转。
    • 54. 螺旋矩阵 - M
      一层一层地找，一层层地输出
    • 304. 2D区域和检索(不可变)
  • Math
    • 204. 计算质数

Board相关题

  • 200. 岛屿数量、547 省份数量

    这种题就是求一个图的连通分量。
    无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

    以下是547 的解决方法如下：
    • Solution-DFS 
      1. class Solution {
      2.     public int findCircleNum(int[][] isConnected) {
      3.         // int[][] isConnected 是无向图的邻接矩阵，n 为无向图的顶点数量
      4.         int n = isConnected.length;
      5.         // 定义 boolean 数组标识顶点是否被访问
      6.         boolean[] visited = new boolean[n];
      7.         // 定义 cnt 来累计遍历过的连通域的数量
      8.         int cnt = 0;
      9.         for (int i = 0; i < n; i++) {
      10.             // 若当前顶点 i 未被访问，说明又是一个新的连通域，则遍历新的连通域且cnt+=1.
      11.             if (!visited[i]) { 
      12.                 cnt++;
      13.                 dfs(i, isConnected, visited);
      14.             }
      15.         }
      16.         return cnt;
      17.     }
      18.  
      19.     private void dfs(int i, int[][] isConnected, boolean[] visited) {
      20.         // 对当前顶点 i 进行访问标记
      21.         visited[i] = true;
      22.         
      23.         // 继续遍历与顶点 i 相邻的顶点（使用 visited 数组防止重复访问）
      24.         for (int j = 0; j < isConnected.length; j++) {
      25.             if (isConnected[i][j] == 1 && !visited[j]) {
      26.                 dfs(j, isConnected, visited);
      27.             }
      28.         }
      29.     }
      30. }
      31.  
      32.  
      33. 作者：sweetiee
      34. 链接：https://leetcode-cn.com/problems/number-of-provinces/solution/dfs-bfs-bing-cha-ji-3-chong-fang-fa-ji-s-edkl/
      35. 来源：力扣（LeetCode）
      36. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    • Solution-BFS
        
      1. class Solution {
      2.     public int findCircleNum(int[][] isConnected) {
      3.         // int[][] isConnected 是无向图的邻接矩阵，n 为无向图的顶点数量
      4.         int n = isConnected.length;
      5.         // 定义 boolean 数组标识顶点是否被访问
      6.         boolean[] visited = new boolean[n];
      7.         
      8.         // 定义 cnt 来累计遍历过的连通域的数量
      9.         int cnt = 0;  
      10.         Queue<Integer> queue = new LinkedList<>();
      11.         for (int i = 0; i < n; i++) {
      12.             // 若当前顶点 i 未被访问，说明又是一个新的连通域，则bfs新的连通域且cnt+=1.
      13.             if (!visited[i]) {
      14.                 cnt++;
      15.                 queue.offer(i);
      16.                 visited[i] = true;
      17.                 while (!queue.isEmpty()) {
      18.                     int v = queue.poll();
      19.                     for (int w = 0; w < n; w++) {
      20.                         if (isConnected[v][w] == 1 && !visited[w]) {
      21.                             visited[w] = true;
      22.                             queue.offer(w);
      23.                         }
      24.                     }
      25.                 }
      26.             }
      27.         }
      28.         return cnt;
      29.     }
      30. } 
      31.  
      32. 作者：sweetiee
      33. 链接：https://leetcode-cn.com/problems/number-of-provinces/solution/dfs-bfs-bing-cha-ji-3-chong-fang-fa-ji-s-edkl/
      34. 来源：力扣（LeetCode）
      35. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

       
    • Solution-UF（并查集）
      并查集其实就是：合并、查询功能的一种实现。
      并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 
      1.     /**
      2.      * 并查集，要实现的功能：合并、查找
      3.      */
      4.  
      5.     public int findCircleNum(int[][] isConnected) {
      6.         // isConnected 是n x n 矩阵
      7.         int provinces = isConnected.length;
      8.         // 保存每个节点对应的祖宗节点下标
      9.         int[] parent = new int[provinces];
      10.         for (int i = 0; i < provinces; i++) {
      11.             // 初始化，每个节点是是自己本身的祖宗节点
      12.             parent[i] = i;
      13.         }
      14.         // 遍历isConnected 二维数组，只需要遍历右上角就可以
      15.         for (int i = 0; i < provinces; i++) {
      16.             for (int j = i + 1; j < provinces; j++) {
      17.                 if (isConnected[i][j] == 1) {
      18.                     union(parent, i, j);
      19.                 }
      20.             }
      21.         }
      22.         // 最后遍历parent 数组，确定结果
      23.         int circles = 0;
      24.         for (int i = 0; i < provinces; i++) {
      25.             if (parent[i] == i) {
      26.                 circles ++;
      27.             }
      28.         }
      29.         return circles;
      30.  
      31.     }
      32.  
      33.     // 合并功能。合并index1 和index2
      34.     public void union(int[] parent, int index1, int index2) {
      35.  
      36.         // 使index1 的祖宗节点等于index2 的祖宗节点。这样两个节点就联合了。
      37.         parent[find(parent, index1)] = find(parent, parent[index2]);
      38.  
      39.     }
      40.  
      41.     // 查找功能
      42.     public int find(int[] parent, int index) {
      43.         // 如果符合此条件，说明index 节点还有祖宗点，则需要继续寻找祖宗节点
      44.         if (parent[index] != index) {
      45.             parent[index] = find(parent, parent[index]);
      46.         }
      47.         return parent[index];
      48.     }

       

NSum及股票系列

  • NSum系列
    • 1. 2Sum

      给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

      解决方法1：一次遍历，使用map, O(n)  复杂度
      解决方法2：排序，双指针，Onlogn
      此题即在遍历nums 数组的时候，对于每一个x，寻找target - x。可以使用map 存储，对于。map 的性质，每个元素可以存储两个值（key，value）。所以遍历到x 的时候，在map 中寻找target - x，如果没找到，则将x 及x 的下标存储到map 中。
        
      1.     public int[] twoSum(int[] nums, int target) {
      2.  
      3.         Map<Integer, Integer> map = new HashMap<>(nums.length);
      4.         for (int i = 0; i < nums.length; i++) {
      5.             if (map.containsKey(target - nums[i])) {
      6.                 return new int[]{i, map.get(target - nums[i])};
      7.             } else {
      8.                 map.put(nums[i], i);
      9.             }
      10.         }
      11.         return null;
      12.     }
    • 15. 3Sum 排序+双指针，On2，固定一个i，l,r从左右开始扫描
      先排序，然后对于每个元素，寻找first，这是一次遍历。然后second & third 的寻找，这是使用双指针的操作方法。
      参考题解，从O(N3) 简化成O(N2) 的过程。
        
      1.     public List<List<Integer>> threeSum(int[] nums) {
      2.         int n = nums.length;
      3.         Arrays.sort(nums);
      4.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
      5.         // 枚举a
      6.         for (int first = 0; first < n; first ++) {
      7.             // 需要和上一次枚举的数不相同
      8.             if (first > 0 && nums[first] == nums[first - 1]) {
      9.                 continue;
      10.             }
      11.             // c 对应的指针初始指向数组的最右端
      12.             int third = n - 1;
      13.             int target  = - nums[first];
      14.             // 枚举b
      15.             for (int second = first + 1; second < third; second ++) {
      16.                 if (second > first + 1 && nums[second] == nums[second - 1]) {
      17.                     continue;
      18.                 }
      19.                 // 保证b 的指针在c 的左侧
      20.                 while (second < third && nums[second] + nums[third] > target) {
      21.                     -- third;
      22.                 }
      23.                 // 如果指针重合，随着b 的后续增加，就不会有满足a+b+c=0 并且b<c 的c 了，可以退出循环
      24.                 if (second == third) {
      25.                     break;
      26.                 }
      27.                 if (nums[second] + nums[third] == target) {
      28.                     List<Integer> list = new ArrayList<>();
      29.                     list.add(nums[first]);
      30.                     list.add(nums[second]);
      31.                     list.add(nums[third]);
      32.                     ans.add(list);
      33.                 }
      34.             }
      35.         }
      36.         return ans;
      37.     }

       
    • 18. 4Sum 和3Sum思路一样，固定两个再双指针，On3
      使用两重循环枚举前两个数字，使用双指针枚举剩下的两个数字。
        
      1.     public static List<List<Integer>> fourSum(int[] nums, int target) {
      2.  
      3.         List<List<Integer>> result = new ArrayList<>();
      4.         if (null == nums || nums.length < 4) {
      5.             return result;
      6.         }
      7.  
      8.         Arrays.sort(nums);
      9.  
      10.         int length = nums.length;
      11.         for (int i = 0; i < length - 3; i++) {
      12.             // 防止重复解
      13.             if (i > 0 && nums[i] == nums[i - 1]) {
      14.                 continue;
      15.             }
      16.             // 数组情况前提判断
      17.             if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
      18.                 break;
      19.             }
      20.             // 数组情况前提判断
      21.             if (nums[length - 1] + nums[length - 2] + nums[length - 3] + nums[length - 4] < target) {
      22.                 break;
      23.             }
      24.             // 数组情况前提判断
      25.             if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length -1] < target) {
      26.                 continue;
      27.             }
      28.             for (int j = i + 1; j < length - 2; j++) {
      29.  
      30.                 // 防止重复解
      31.                 if (j > i + 1 && nums[j] == nums[j - 1]) {
      32.                     continue;
      33.                 }
      34.                 // 数组情况前提判断
      35.                 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
      36.                     break;
      37.                 }
      38.                 // 数组情况前提判断
      39.                 if (nums[i] + nums[j] + nums[length - 1] + nums[length - 2] < target) {
      40.                     continue;
      41.                 }
      42.                 int left = j + 1;
      43.                 int right = length - 1;
      44.                 while (left < right) {
      45.                     int sum = nums[i] + nums[j] + nums[left] + nums[right];
      46.                     if (sum == target) {
      47.                         // 赋值
      48.                         result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
      49.                         // 因为有可能有多重情况，所以在这里面还需要继续执行左右指针的变动
      50.                         while (left < right && nums[left] == nums[left + 1]) {
      51.                             left ++;
      52.                         }
      53.                         left ++;
      54.                         while (left < right && nums[right] == nums[right - 1]) {
      55.                             right --;
      56.                         }
      57.                         right --;
      58.                     } else if (sum > target) {
      59.                         right --;
      60.                     } else if (sum < target) {
      61.                         left ++;
      62.                     }
      63.                 }
      64.             }
      65.         }
      66.         return result;
      67.     }
  • 股票系列
    • 121. 买卖股票的最佳时机 维护最小值minPrice，不断更新最大收益maxProfit
      只要用一个变量记录一个历史最低价格minPrice，就可以假设股票是在那天买的，那么在第i 天卖出的利润就是price[i] - minPrice
       

      给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
      你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

      （只能买卖一次）
        
      1.     public int maxProfit(int[] prices) {
      2.         int ans = 0;
      3.         int min = prices[0];
      4.         for (int i = 1; i < prices.length; i++) {
      5.             if (prices[i] > min) {
      6.                 ans = ans > prices[i] - min ? ans : prices[i] - min;
      7.             } else {
      8.                 min = prices[i];
      9.             }
      10.         }
      11.         return ans;
      12.     }

       
    • 122. 买卖股票的最佳时机 II 只要后一天比前一天大，就交易
      动态规划、贪心

      （可以买卖多次）

       

      给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
      设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。


      动态规划：

      1.     public int maxProfit(int[] prices) {
      2.         int n = prices.length;
      3.         // 定义状态dp[i][0] 表示第i 天交易完后，手里没有股票的最大利润
      4.         // 定义状态dp[i][1] 表示第i 天交易完后，手里有股票的最大利润
      5.         // 状态转移方程：
      6.         // dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]} 因为第i 天交易完成，股票卖出，所以要加price[i]。即当天股票卖出时的价格。
      7.         // dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}
      8.         int[][] dp = new int[n][2];
      9.         dp[0][0] = 0;
      10.         dp[0][1] = -prices[0];
      11.         for (int i = 1; i < n; i++) {
      12.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      13.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
      14.         }
      15.         return dp[n - 1][0];
      16.     }
      17.  
      18.  
      19.  
      20. // 升级版
      21.  
      22.     public int maxProfit(int[] prices) {
      23.         int n = prices.length;
      24.         int dp0 = 0, dp1 = -prices[0];
      25.         for (int i = 1; i < n; ++i) {
      26.             int newDp0 = Math.max(dp0, dp1 + prices[i]);
      27.             int newDp1 = Math.max(dp1, dp0 - prices[i]);
      28.             dp0 = newDp0;
      29.             dp1 = newDp1;
      30.         }
      31.         return dp0;
      32.     }
      33.

      贪心：

      1.     public int maxProfit(int[] prices) {
      2.         int ans = 0;
      3.         int n = prices.length;
      4.         for (int i = 1; i < n; ++i) {
      5.             ans += Math.max(0, prices[i] - prices[i - 1]);
      6.         }
      7.         return ans;
      8.     }

      什么时候用贪心？什么时候用动态规划？
      状态转移树中，若后一状态仅仅取决于上一个状态，就用贪心算法；若后一状态取决于之前的多个状态，就用动态规划。（不是太准确）
      更准确的说法应该是当局部最优解可以推导最终得出全局最优解时，用贪心，剩下的情况用动态规划

      有空看看，偶然发现的算法教程：搞定大厂算法面试之leetcode精讲

      https://www.zhihu.com/question/366752691/answer/2238372073
       
    • 123. 买卖股票的最佳时机 III
      王脸小提示：dp[i][s]，i为天数，s为状态

      题目：

      给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
      设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。


      动态规划，因为每天最多可以完成两笔交易，所以在任意一天结束之后，会处于五种状态之一。

      看官方题解，此题一共五个状态。只需要维护四个状态即可。
        
      1.     public int maxProfit(int[] prices) {
      2.         int n = prices.length;
      3.         int buy1 = -prices[0], sell1 = 0;
      4.         int buy2 = -prices[0], sell2 = 0;
      5.         for (int i = 1; i < n; ++i) {
      6.             buy1 = Math.max(buy1, -prices[i]);
      7.             sell1 = Math.max(sell1, buy1 + prices[i]);
      8.             buy2 = Math.max(buy2, sell1 - prices[i]);
      9.             sell2 = Math.max(sell2, buy2 + prices[i]);
      10.         }
      11.         return sell2;
      12.     }
    • 188. 买卖股票的最佳时机 IV dp[i][s]，i为天数，s为状态

      给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

      设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

      注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

252. 区间(会议室)

定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议

提示：
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106

  1. class Solution {
  2.     public boolean canAttendMeetings(int[][] intervals) {
  3.         Arrays.sort(intervals, (o1, o2) -> (o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]));
  4.  
  5.         for (int i = 1; i < intervals.length; i++) {
  6.             if (intervals[i][0] < intervals[i - 1][1]) {
  7.                 return false;
  8.             }
  9.         }
  10.         return true;
  11.     }
  12. }

参考：leetcode 252.会议室 Java_云水冰的博客-CSDN博客

Arrays.sort() 的使用：Arrays.sort()的用法_Lin的博客-CSDN博客_arrays.sort()
 

253. 会议室II

首先进行一下排序，然后用一个小顶堆，维护当前每个会议室的结束时间，
然后当一个新的时间安排出现的时候，只需要判断一下是否需要新申请一个会议室，还是继续使用之前的会议室。

使用小顶堆的实现方式就是，小顶堆存了会议的结束时间，首先把第一个会议的结束时间存入，作为初始化条件。

遍历其他会议日程。如果会议开始时间（intervals[i][0]）大于queue.peek()，就是大于当前最小的时间，那么就可以继续使用当前这个会议室。优先队列的操作方式就是把前一个会议日程踢出，然后add 进去当前会议的结束时间。否则不踢出。

  1.     public int minMeetingRooms(int[][] intervals) {
  2.         if (intervals == null || intervals.length == 0) {
  3.             return 0;
  4.         }
  5.         Arrays.sort(intervals, new Comparator<int[]>() {
  6.             @Override
  7.             public int compare(int[] o1, int[] o2) {
  8.                 return o1[0] - o2[0];
  9.             }
  10.         });
  11.         // 优先队列存放的是，之前的，最早结束的会议的，结束时间。
  12.         // 这是一个小顶堆
  13.         PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o1 - o2);
  14.         // 队列初始化存入第一个会议的结束时间
  15.         queue.offer(intervals[0][1]);
  16.         for (int i = 1; i < intervals.length; i++) {
  17.             // 如果当前的会议开始时间，大于队列里面的之前的会议的结束时间
  18.             if (intervals[i][0] >= queue.peek()) {
  19.                 // 那么之前的那个会议和现在的会议就可以使用一个会议室
  20.                 // 所以之前的会议的记录就可以出队列了
  21.                 queue.poll();
  22.             }
  23.             // 如果不是的话，那么就肯定得多一个房间了。
  24.             // 所以就将现在的会议结束时间入队。
  25.             // 使用小顶堆的意思是：越早结束的会议，房间的空余肯定越多，所以使用小顶堆的堆顶来比较
  26.             queue.offer(intervals[i][1]);
  27.         }
  28.         return queue.size();
  29.     }

参考：leetcode253. 会议室II(java)：最小堆_yinianxx的博客-CSDN博客

BFS

举例：994，腐烂的桔子。

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

主要就是看官方题解，主要就是细节

  1. public int orangesRotting(int[][] grid) {
  2.         int[] x = {1, 0, -1, 0};
  3.         int[] y = {0, 1, 0, -1};
  4.  
  5.         int row = grid.length;
  6.         int column = grid[0].length;
  7.  
  8.         // 存放所有腐烂的句子
  9.         Queue<Pair<Integer, Integer>> queue = new ArrayDeque<>();
  10.         // 存放每个橘子是第几分钟腐烂的。对于开局就已经腐烂的橘子，他们的value 是0
  11.         Map<Pair<Integer, Integer>, Integer> depth = new HashMap<>();
  12.         // 处理开局就腐烂的橘子
  13.         for (int i = 0; i < row; i++) {
  14.             for (int j = 0; j < column; j++) {
  15.                 if(grid[i][j] == 2) {
  16.                     // 存储腐烂橘子
  17.                     queue.add(new Pair<>(i, j));
  18.                     // 存储橘子变腐烂的时间，key为橘子的一维数组下标，value为变腐烂的时间
  19.                     depth.put(new Pair<>(i, j), 0);
  20.                 }
  21.             }
  22.         }
  23.         int ans = 0;
  24.         // 腐烂的橘子队列，不为空
  25.         while(!queue.isEmpty()) {
  26.             Pair<Integer, Integer> poppedPair = queue.poll();
  27.             int r = poppedPair.getKey();
  28.             int c = poppedPair.getValue();
  29.             for(int k = 0; k < 4; k++) {
  30.                 int tempI = r + x[k];
  31.                 int tempJ = c + y[k];
  32.                 if(tempI >= 0 && tempI < row && tempJ >= 0 && tempJ < column && grid[tempI][tempJ] == 1) {
  33.                     grid[tempI][tempJ] = 2;
  34.                     Pair<Integer, Integer> tempPair = new Pair<>(tempI, tempJ);
  35.                     queue.add(tempPair);
  36.                     // 记载橘子腐烂的时间
  37.                     // key 是中心节点散发的各个节点
  38.                     // value 是中心节点的腐烂时间 + 1
  39.                     depth.put(tempPair, depth.get(poppedPair) + 1);
  40.                     ans = depth.get(tempPair);
  41.                 }
  42.             }
  43.         }
  44.         for(int i = 0; i < row; i++) {
  45.             for(int j = 0; j < column; j++) {
  46.                 if (grid[i][j] == 1) {
  47.                     return -1;
  48.                 }
  49.             }
  50.         }
  51.         return ans;
  52.     }

 DFS

Radix/Bucket Sort

radix sort 基数排序，也叫做bucket sort。

基数排序（Radix Sort） - 简书

225. 队列实现栈

使用一个队列即可实现

主要是用top_elem 标识栈顶元素，和pop 操作，比较重要。

  1. class MyStack {
  2.  
  3.     private Queue<Integer> queue = new LinkedList<>();
  4.     int top_elem = 0;
  5.     public MyStack() {
  6.  
  7.     }
  8.  
  9.     // 添加元素到栈顶
  10.     public void push(int x) {
  11.         //x 是队列的队尾，是栈的栈顶
  12.         queue.offer(x);
  13.         top_elem = x;
  14.     }
  15.  
  16.     // 队列的性质是先进先出，pop 元素的时候只能从队头取出元素
  17.     // 但是栈是先进后出，解决办法就是
  18.     // 把队列前面的元素全部取出，再加入到队尾，让之前队尾元素排到队头，这样就可以取出了
  19.     public int pop() {
  20.         int size = queue.size();
  21.         // 留下两个元素是为了更新top_elem.
  22.         while (size > 2) {
  23.             queue.offer(queue.poll());
  24.             size --;
  25.         }
  26.         top_elem = queue.peek();
  27.         queue.offer(queue.poll());
  28.         // 之前的队尾已经到了队头
  29.         return queue.poll();
  30.     }
  31.  
  32.     public int top() {
  33.         return top_elem;
  34.     }
  35.  
  36.     public boolean empty() {
  37.         return queue.isEmpty();
  38.     }
  39. }

232. 栈实现队列

使用两个栈实现一个队列

添加元素的时候，把元素放到s1 里面，pop 的时候，把s2 作为中转

  1. class MyQueue {
  2.  
  3.     private Stack<Integer> s1, s2;
  4.     public MyQueue() {
  5.         s1 = new Stack<>();
  6.         s2 = new Stack<>();
  7.     }
  8.  
  9.     public void push(int x) {
  10.         s1.push(x);
  11.     }
  12.  
  13.     // 对于pop 操作，也只操作s2 就可以了
  14.     public int pop() {
  15.         // 先调用peek，保证s2 非空。
  16.         // 这样就保证，在s2 空了之后，再把s1 里面的值加进去
  17.         // 否则就先不动s1 的数据
  18.         peek();
  19.         return s2.pop();
  20.     }
  21.  
  22.     // 注意peek 是静态的，不会有元素的变更
  23.     public int peek() {
  24.         if (s2.isEmpty()) {
  25.             // 把s1 压入s2 中
  26.             while (!s1.isEmpty()) {
  27.                 s2.push(s1.pop());
  28.             }
  29.         }
  30.         return s2.peek();
  31.     }
  32.  
  33.     // 如果两个栈都空，就说明队列为空
  34.     public boolean empty() {
  35.         return s1.isEmpty() && s2.isEmpty();
  36.     }
  37. }

以上参考：队列实现栈|栈实现队列 - 知乎 

其他：

560. 560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
 

使用“前缀和”
前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。

  1. (题目解法来自“labuladong”）
  2.  
  3. 使用“前缀和”技巧
  4.  
  5.     public static int subArraySum(int[] nums, int k) {
  6.  
  7.         int n = nums.length;
  8.         // 构造
  9.         int[] preSum = new int[n + 1];
  10.         preSum[0] = 0;
  11.         for (int i = 0; i < n; i++) {
  12.             preSum[i + 1] = preSum[i] + nums[i];
  13.         }
  14.  
  15.         int ans = 0;
  16.         for (int i = 1; i <= n; i++) {
  17.             for (int j = 0; j < i; j++) {
  18.                 if (preSum[i] - preSum[j] == k) {
  19.                     ans ++;
  20.                 }
  21.             }
  22.         }
  23.         return ans;
  24.     }
  25.  
  26.  
  27.  
  28. 优化：第⼆层 for 循环在⼲嘛呢？翻译⼀下就是， 在计算， 有⼏个 j 能够使得
  29. sum[i] 和 sum[j] 的差为 k。 毎找到⼀个这样的 j ， 就把结果加⼀。
  30. 把第二个for 循环中的判断公式移项，可以得到if(sum[j] == sum[i] - k) ans ++;
  31. 直接记录下有⼏个 sum[j] 和 sum[i] - k 相等， 直接更
  32. 新结果， 就避免了内层的 for 循环。 我们可以⽤哈希表， 在记录前缀和的同
  33. 时记录该前缀和出现的次数。
  34.  
  35.     public static int subArraySum(int[] nums, int k) {
  36.  
  37.         int n = nums.length;
  38.         HashMap<Integer, Integer> preSum = new HashMap<>();
  39.         preSum.put(0, 1);
  40.         int ans = 0;
  41.         // 数组下标0 到下标i 的和
  42.         int sum0_i = 0;
  43.         for (int i = 0; i < n; i++) {
  44.             sum0_i += nums[i];
  45.             // 题目是要求有几个和为k 的子数组
  46.             // sum0_j 是数组下标0 到下标j 的和，也就是要找的前缀和。用sum0-i 减去sum0-j 得到的就是k
  47.             int sum0_j = sum0_i - k;
  48.             // 如果map 中存在这个前缀和
  49.             if (preSum.containsKey(sum0_j)) {
  50.                 ans += preSum.get(sum0_j);
  51.                 // 然后把前缀和sum0-i 加入记录，同时记录出现次数
  52.                 preSum.put(sum0_i, preSum.getOrDefault(sum0_i, 0) + 1);
  53.             }
  54.         }
  55.         return ans;
  56.     }

给⼀棵⼆叉树， 和⼀个⽬标值， 节点上的值有正有负， 返回树中和等于⽬标值的路径条数

  1. @Data
  2.     class TreeNode {
  3.         int val;
  4.         TreeNode left;
  5.         TreeNode right;
  6.     }
  7.  
  8.     public int pathNum(TreeNode root, int sum) {
  9.  
  10.         if (root == null) {
  11.             return 0;
  12.         }
  13.         
  14.         int pathNumMe = pathNum(root, sum);
  15.         int pathNumLeft = pathNum(root.left, sum);
  16.         int pathNumRight = pathNum(root.right, sum);
  17.         return pathNumLeft + pathNumRight + pathNumMe;
  18.     }
  19.     
  20.     public static int count(TreeNode node, int sum) {
  21.         
  22.         if (node == null) {
  23.             return 0;
  24.         }
  25.         int isMe = (node.val == sum) ? 1 : 0;
  26.         int leftBro = count(node.left, sum - node.val);
  27.         int rightBro = count(node.right, sum - node.val);
  28.         return isMe + leftBro + rightBro;
  29.         
  30.     }

归并排序：典型的分治算法；分治，典型的递归结构。

coupang

​​​​​​九章算法 | Coupang面试题：捡苹果 - 知乎​​​​​​

 coupang面试经验|面试题（共3条）- 职朋

2020 年面试记录 [Microsoft / Coupang / CoinMarketCap] - Popco - 博客园

「韩领网络科技（上海）有限公司面试|面试题」-看准网

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/488931
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号