leetcode题解(含解题思路)(持续更新中)

数组 & 字符串 & 双指针

两数之和

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

• 思路：使用哈希表，把数组中的值依次存入 map，存入时判断 map 中是否有target-num[i]，若有就把两个下标存入新数组返回

  class Solution {
      public int[] twoSum(int[] nums, int target) {
          Map<Integer, Integer> map = new HashMap<Integer, Integer>();
          int[] num = new int[2];
          for (int i = 0; i < nums.length; ++i) {
              if (map.containsKey(target - nums[i])) {
                  num[0] = map.get(target - nums[i]);
                  num[1] = i;
               }
              map.put(nums[i], i);
          }
          return new int[0];
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

三数之和

• 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

• 思路：将 nums 排序，然后确定k为第一个数，再确定k左边的数left以及数组最右边的数right，让后面这两个数形成对撞指针，当sum < 0时，说明left太小，让left右移；若sum > 0，则说明right太大，right–；

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums); // 先将nums排序
        for (int k = 0; k < n; k++) {
            // 当前数字已经大于0，那么之后的数子在相加也不可能等于0，结束程序
            if (nums[k] > 0) {
                break;
            }   
            // 跳过重复结果
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            // 定义左右指针
            int left = k + 1, right = n - 1;      
            // 不断地缩小范围
            while (left < right) {
                // sum为总和
                int sum = nums[k] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    // sum == 0，记录当前结果
                    res.add(Arrays.asList(nums[k], nums[left], nums[right]));
                    // 避免记录重复结果
                    while (left + 1 < right && nums[left + 1] == nums[left]) {
                        left++;
                    }
                    while (left < right - 1 && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    // 缩小窗口
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

螺旋矩阵——顺时针打印矩阵

• 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

• 思路：将矩阵看成 k 层，按照数组大小设定4个边界值，逐层遍历

class Solution {
    /* 记录上下左右四个指针用来标识矩阵 */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int rows = matrix.length;
        if (rows == 0) {
            return res;
        }
        int cols = matrix[0].length;
        // 左、右、上、下指针
        int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            // 从左到右收集
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            // 从上到下收集
            for (int i = top + 1; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            // 从右到左收集(需要防止第一次收集过)
            if (top != bottom) {
                for (int i = right - 1; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
            }
            // 从下到上收集(需要防止第二次收集过)
            if (left != right) {
                for (int i = bottom - 1; i >= top + 1; i--) {
                    res.add(matrix[i][left]);
                }
            }
            // 收集完一圈，缩小矩阵
            left++;
            right--;
            top++;
            bottom--;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

构建乘积数组

• 给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

• 先计算下三角的乘积，再计算上三角的乘积并且拼接

public class Solution {
    /* 画图可知，每个区域对应的下三角已经上三角的区域 */
    public int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        if(length != 0 ){
            B[0] = 1;
            //计算下三角连乘，初始化第一行
            for(int i = 1; i < length; i++){
                B[i] = B[i-1] * A[i-1];
            }
            int temp = 1;
            //计算上三角连乘，初始化最后一行
            for(int j = length-2; j >= 0; j--){
                temp *= A[j+1];
                B[j] *= temp;
            }
        }
        return B;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

约瑟夫环问题

• 让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演拿到礼物

• 思路：方法一：用约瑟夫环递推公式；

  方法二：用链表模拟淘汰过程，当人数大于1就淘汰，计算要淘汰的索引，然后索引自减，继续淘汰

//方法一：递推公式
public class Solution {
public int LastRemaining_Solution(int n, int m) {
    // 约瑟夫环
    if (n == 0) {
        // 当前没有人参与
        return -1;
    }
    if (n == 1) {
        // 剩余该人生还，索引为0
        return 0;
    }
    // 约瑟夫环递推公式:f(n, m) = (f(n - 1, m) + m) % n
    return (LastRemaining_Solution(n - 1, m) + m) % n;
}
}
//方法二：链表模拟
public class Solution {
/* 使用链表来模拟这一淘汰过程 */
public int LastRemaining_Solution(int n, int m) {
    if (n <= 0 || m <= 0) {
        return -1;
    }
    ArrayList<Integer> list = new ArrayList<>();
    // 先将数组添加到链表中
    for (int i = 0; i < n; i++) {
        list.add(i);
    }
    // 初始化索引-1
    int index = -1;
    // 当幸存者大于1时，进行淘汰
    while (list.size() > 1) {
        // 计算出需要淘汰的索引
        index = (index + m) % list.size();
        list.remove(index);
        // 记得让索引自减，以达下一轮的目标
        index--;
    }
    // 只剩一个元素时就是幸存者
    return list.get(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

左旋转字符串——循环左移字符串

• 有种移位指令叫做循环左移，用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出（保证 K 小于等于 S 的长度）。例如，字符序列S=”abcXYZdef”,要求输出循环左移 3 位后的结果，即“XYZdefabc”

• 思路：方法一：return str.substring(n) + str.substring(0, n)

  ​ 方法二：将字符串分三部分反转，然后拼接

public class Solution {
    /* 首先反转整体字符串，然后反转前半部分，再反转后半部分即可 */
    public String LeftRotateString(String str,int n) {
        if (str == null || str.length() == 0) {
            return str;
        }
        // 分三部分反转即可
        int len = str.length();
        n = n % str.length();
        // 反转全部
        char[] chars = str.toCharArray();
        reverse(chars, 0, len - 1);
        // 反转第一部分
        reverse(chars, 0, len - n - 1);
        // 反转第二部分
        reverse(chars, len - n, len - 1);
        return new String(chars);
    }
    
    /*
    * 反转left到right之间的字符
    */
    private void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

丑数

• 给你一个整数 n ，请你判断 n 是否为 丑数 。(包含质因子2、3和5的数是丑数)

• 思路：依次除以2、3、5，然后判断最后为不为1即可知是否为丑数

class Solution {
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        return num == 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第 N 个丑数

• 给你一个整数 n ，请你找出并返回第 n 个 丑数

• 思路：方法一：用最小堆；

  ​ 方法二：动态规划，定义数组 dp，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n]。

  由于最小的丑数是 1，因此 dp[1]=1。

  定义三个指针 p2,p3,p5 ，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。

  初始时，三个指针的值都是 1。

  当 2≤i≤n 时，令 dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，然后分别比较 dp[i] 和 dp[p2],dp[p3],dp[p5] 是否相等，如果相等则将对应的指针加 1。

class Solution {
    /* 使用dp存储第n个丑数，定义p2、p3、p5分别指向dp中的第n个2、3、5类型的丑树，每次选出一个最小值用于作为当前的丑数*/
    public int nthUglyNumber(int n) {
        if (n < 1) {
            break;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 =0;
        for (int i = 1; i < n; i++) {
            // 获取丑数队列的最小值作为下一个丑数
            int min = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
            // 将符合条件的丑数索引递增
            if (min == dp[p2] * 2) {
                p2++;
            }
            if (min == dp[p3] * 3) {
                p3++;
            }
            if (min == dp[p5] * 5) {
                p5++;
            }
            // 设置最小值为当前丑数
            dp[i] = min;
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

调整数组使奇数位于偶数前面

• 实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

• 思路：使用插入排序，原地交换，遍历为奇数时，往前交换，直到遇到表示当前奇数末尾的cur

public class Solution {
     /* 使用插入排序，原地交换，能保证最后结果的有序性 */
     public void reOrderArray(int [] A) {
        if (A == null) {
            throw new RuntimeException("数组不能为空");
        }
        int cur = 0; // cur表示当前奇数的末尾
        for (int i = 0; i < A.length; i++) {
            // 为奇数时，往前交换，直到遇到cur
            int temp = i;
            if (A[temp] % 2 == 1) {
                while (temp > cur) {
                    swap(A, temp, temp - 1);
                    temp--;
                }
                cur++;//奇数位后移
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

替换字符串中的空格

• 将一个字符串中的每个空格替换成“%20”

• 思路：方法一：return str.toString().replace(" ", "%20");

  方法二：统计空格数然后加上字符数创建一个新的字符数组，再从头到尾填充，最后转化为字符串

public class Solution {
    /* 统计空格数然后加上字符数创建一个新的字符数组，再从头到尾填充，最后转化为字符串 */
    public String replaceSpace(StringBuffer str) {
        char[] chars = str.toString().toCharArray();
        // 统计空格数和非空格数
        int spaceCount = 0, charCount = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                spaceCount++;
            } else {
                charCount++;
            }
        }
        // 计算最终所需长度
        int len = charCount + 3 * spaceCount;
        // 声明新数组
        char[] res = new char[len];
        int index1 = 0, index2 = 0;
        while (index1 < res.length && index2 < chars.length) {
            if (chars[index2] != ' ') {
                res[index1++] = chars[index2++];
            } else {
                // 遇到了空格，插入%20
                char[] aux = new char[]{'%', '2', '0'};
                for (char c:aux) {
                    res[index1++] = c;
                }
                index2++;
            }
        }
        return new String(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

实现 pow 函数

• 实现 pow(x, n) ，即计算 x 的 n 次幂函数

• 思路：将a^n 递归拆分为a^(n/2) * a^(n/2) (偶数)或拆分为a^(n/2) * a^(n/2)*a(奇数),最后考虑符号

class Solution {
    public double myPow(double x, long n) {
        // 边界条件
        if (n == 0) {
            return 1.0;
        }
        // 递归终止条件，当n==1或-1时返回x或1/x
        if (n == 1 || n == - 1) {
            return (n == 1) ? x : 1 / x;
        }
        // 递归拆分： a^b = a^(b/2) * a^(b/2) （b为偶数）
        // 递归拆分： a^b = a^(b/2) * a^(b/2) * a （b为奇数）
        long temp = Math.abs(n);
        double res = myPow(x, temp / 2);
        if (temp % 2 == 0) {
            // 偶数次幂
            res *= res;
        } else {
            // 奇数次幂
            res *= res * x;
        }
        // 是否为正数次幂
        if (n >= 0) {
            return res;
        } else {
            return 1 / res;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

实现 sqar 函数

• 计算并返回 x 的平方根，1不要求精度，结果整数的部分 | 2要求精度

• 思路：利用夹逼法则，设定左边界、右边界，计算中间数，然后更换更换边界值

class Solution {
    /* 1.夹逼法，int型，无需精度,舍弃小数点，只保留整数 */ 
    public int mySqrt(int x) {
        // 使用夹逼定理，一直缩小区间逼近
        long left = 0, right = x, mid = left + (right - left) / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (mid*mid == x || mid*mid < x && (mid+1)*(mid+1) > x) {
                break;
            }
            if (mid*mid < x) {
                // 向右区间逼近
                left = mid + 1;
            } else {
                // 向左区间逼近
                right = mid - 1;
            }
        }
        return (int)mid;
    }
    
    /* 2.夹逼法，double型，需讨论精度 */
    public double mySqrt(double x) {
        // 使用夹逼定理，一直缩小区间逼近,附带精度校验
        double precision = 0.001;
        double left = 0.0, right = x, mid = left + (right - left) / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            // 符合精度要求
            if (Math.abs(mid*mid - x) <= precision) {
                break;
            }
            if (mid*mid < x) {
                // 向右区间逼近
                left = mid + precision;
            } else {
                // 向左区间逼近
                right = mid - precision;
            }
        }
        return mid;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

有序二维数组中查找某数

• 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，输入一个二维数组和一个整数，判断数组中是否含有该整数。

• 思路：在左下角开始寻找，若小于target，则往右寻找，若大于target，则往上寻找

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array.length == 0) {
            return false;
        }
        int rows = array.length;
        int cols = array[0].length;
        int i = rows - 1, j = 0;
        while (i >= 0 && j < cols) {
            if (array[i][j] < target) {
                // 需要更大的数，往右侧走
                j++;
            } else if (array[i][j] > target) {
                // 需要更小的数，往上走
                i--;
            } else {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

数组中出现次数超过一半的数字

• 找出数组中出现次数超过一半的数字

• 思路：方法一：排序取中间数 方法二：投票算法

class Solution {  
	//方法一
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    //方法二
    public int majorityElement(int[] nums) {
        int target = nums[0];   //候选人暂定为首个数组元素
        int count = 1;          //票数记为1
        for(int i = 1; i < nums.length; i++){           //遍历所有候选人，依次投票
            if(nums[i] == target){                      //给候选人投票，增加票数
                count++;
            }else if(nums[i] != target && count != 0){  //给另一候选人投票，减之前候选人人票数
                count--;
            }else if(nums[i] != target && count == 0){  //当之前候选人的票数已经为0，更换候选人，票数记为1
                target = nums[i];
                count = 1;
            }
        }
        return target;      //所有候选人投票结束
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

盛最多水的容器

• 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

• 思路：从两端开始，取 高度最小的值 x 距离 = 水量，再移动短板，找新的水量进行比较取最大值

class Solution {
    /* 对撞指针法，时间复杂度O（n） */
    public int maxArea(int[] height) {
        if (height == null) {
            break;
        }
        int left = 0, right = height.length - 1, res = 0;
        while (left < right) {
            // 比较当前的面积和之前的面积哪个更大
            res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
            // 不断地移动短板才有可能扩大面积
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除有序数组的重复项

• 给一个有序数组 ，请原地删除重复出现的元素，使每个元素 最多出现两次 ，返回数组的新长度

• 思路：直接从第2个元素开始考虑，从第3个元素开始考虑重复项，当当前元素不等于cur-1位置的元素，说明没有两个以上重复项，cur继续往右走并交换

class Solution {
	public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int cur = 1; // 直接从第2个元素开始考虑
        // 从第3个元素开始考虑重复项
        for (int i = 2; i < n; i++) {
            // 当当前元素不等于cur-1位置的元素，说明没有两个以上重复项，cur继续往右走并交换
            if (nums[i] != nums[cur - 1]) {
                nums[++cur] = nums[i];
            }
        }
        // 返回最后的长度
        return cur + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在有序数组中查找目标元素的首末位置

• 给定一个按照升序排列的整数数组 和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置

• 思路：先设定两个边界值，利用二分法找中间值，比较中间值与target，若中间值小于target，将区间左边界右移，若中间值大于target，则有边界左移，若中间值等于target，分类判断，起始位置与左侧元素比较，结束位置与右侧元素比较

class Solution {
    /* 使用二分搜索获取第一个和最后一个元素，时间复杂度O（logn） */
    public int[] searchRange(int[] nums, int target) {
        if (nums == null) {
            throw new RuntimeException("input cant be null");
        }
        int[] res = {-1, -1};
        res[0] = getBegin(nums, target);
        res[1] = getEnd(nums, target);
        return res;
    }
    private int getBegin(int[] array, int k) {
        int left = 0,right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] < k) {
                // 搜索右边
                left = mid + 1;
            } else if (array[mid] > k) {
                // 搜索左边
                right = mid - 1;
            } else {
                // 获取到第一个出现的位置
                if (mid == 0 || array[mid - 1] != array[mid]) {
                    return mid;
                } else {
                    // 继续往左搜索
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
     private int getEnd(int[] array, int k) {
         int left = 0,right = array.length - 1;
          while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] < k) {
                // 搜索右边
                left = mid + 1;
            } else if (array[mid] > k) {
                // 搜索左边
                right = mid - 1;
            } else {
                // 获取到最后一个出现的位置
                if (mid == array.length -1 || array[mid + 1] != array[mid]) {
                    return mid;
                } else {
                    // 继续往右搜索
                    left = mid + 1;
                }
            }
        }
         return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

二维矩阵旋转90°

• 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

• 思路：方法一：利用辅助空间，找旋转图像与原图像的关系aux[i][j] = matrix[n-j-1][i]

  ​ 方法二：枚举：n 为偶数时，枚举 n^2 / 4 = (n/2) X (n/2)个位置(分成四个部分)

  ​ n 为奇数时，(n^2-1) / 4 = ((n-1)/2) X ((n+1)/2)个位置(中间元素不变)

class Solution {
	//方法一：
    public void rotate(int[][] matrix) {
        if (matrix == null) {
            throw new RuntimeException("input cant be null");
        }
        int rows = matrix.length;
        if (rows == 0) {
            return;
        }
        int cols = matrix[0].length;
        int[][] aux = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                aux[i][j] = matrix[rows-j-1][i];
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = aux[i][j];
            }
        }
    }
    //方法二：利用 temp 变量存储元素，防止覆盖
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

最大子序和

• 给定一个整数数组 ，找到一个具有最大和的连续子数组，返回其最大和。

• 思路：利用动态规划，最大连续和从数组初始元素算起，依次与之前的连续和作比较取较大的值

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        // dp[i]表示i及之前的最大连续和
        // dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])-->接上之前的连续和，或从当前开始作为最大连续和
        int[] dp = new int[n];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < n; i++) {
            // 接上最大子序列和或直接从当前开始算起
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

接雨水

• 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算此排列的柱子，下雨后接多少雨水。

• 思路：方法一：暴力搜索法，每到一个位置，就从当前位置向左搜索最大值并记录，再从当前位置向右搜索最大值并记录，然后取两者之间的较小值减去当前高度即可得到当前位置的雨水量

  ​ 方法二：利用动态规划，找每个柱子左边最大高度和右边最大高度的两个数组，再运算

class Solution {
	//暴力搜索法：O(n^2)：效率低的原因是每个位置都要向两边去找最大高度
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int res = 0, n = height.length;
        for (int i = 1; i < n - 1; i++) {
            int leftMax = 0, rightMax = 0;
            // 向左找最大的
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            // 向右找最大的
            for (int j = i; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            // 累加结果
            res += Math.min(leftMax, rightMax) - height[i];
        }
        return res;
    }
    
    /* 动态规划：先构建leftMaxs和rightMaxs数组，最后再进行累加，时间复杂度O（n） */
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int res = 0, n = height.length;
        int[] leftMaxs = new int[n];
        int[] rightMaxs = new int[n];
        leftMaxs[0] = height[0];
        rightMaxs[n - 1] = height[n - 1];
        // 从左往右构建leftMaxs数组
        for (int i = 1; i < n; i++) {
            leftMaxs[i] = Math.max(leftMaxs[i - 1], height[i]);
        }
        // 从右往左构建rightMaxs数组
        for (int i = n - 2; i >= 0; i--) {
            rightMaxs[i] = Math.max(rightMaxs[i + 1], height[i]);
        }
        // 进行累加
        for (int i = 1; i < n - 1; i++) {
            res += Math.min(leftMaxs[i], rightMaxs[i]) - height[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

颜色分类

• 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。0、 1 和 2 分别表示红色、白色和蓝色。

• 思路：方法一：将所有0放在数组头部，将所有1放在数组0后方(两次遍历)

  ​ 方法二：使用双指针：将0放在数组头部，将1放在数组0元素后方(一次遍历)

class Solution {
	//方法一：
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
    //方法二：
     public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

杨辉三角形

• 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。

• 每个数是它左上方和右上方的数的和

class Solution {
    /* 注意要首先在最左边填充1，填充完中间部分后，在最右边填充1 */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) {
            return res;
        }
        res.add(Arrays.asList(1));
        for (int i = 1; i < numRows; i++) {
            ArrayList<Integer> oneRes = new ArrayList<>();
            // 第一个1
            oneRes.add(1);
            for (int j = i - 1; j > 0; j--) {
                // 根据上一行填充中间部分
                List<Integer> lastRows = res.get(i - 1);
                oneRes.add(lastRows.get(j - 1) + lastRows.get(j));
            }
            // 最后一个1
            oneRes.add(1);
            // 将本次结果添加进res
            res.add(oneRes);
        }
        return res;
    }
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

和为 k 的子数组

• 给定一个整数数组和一个整数 k，找到该数组中和为 k 的连续的子数组的个数。

• 思路：方法一：使用双层循环，逐个相加，如果有和为k的子数组，就将计数器加一

  ​ 方法二：动态规划：规定第i个元素是由第i-1个元素和之前元素的和相加得到的，然后考虑以 i 结尾的和为 k 的连续子数组的个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可

class Solution {
    /* 暴力破解法，O(n^2) */
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int temp = 0;
            for (int j = i; j < nums.length; j++) {
                temp += nums[j];
                if (temp == k) {
                    res++;
                }
            }
        }
        return res;
    }
    
    /* 动态规划法 + 哈希表，时间复杂度O(n) */
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // dp[i]表示[0, i - 1]的累计和
        int[] dp = new int[nums.length + 1];
        dp[0] = nums[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            if (map.containsKey(dp[i] - k)) {
                res += map.get(dp[i] - k);
            }
            map.put(dp[i], map.getOrDefault(dp[i], 0) + 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

求众数

• 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

• 思路：投票算法：要求超过数量的1/3，那么最多有两个众数，则选两个候选人。投A则A++，投B则B++，都不投则看A、B票数，若为0则更换候选人，若都不为0，则票数都减一，

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        // 定义两个候选者和它们的票数
        int cand1 = 0,cand2 = 0;    
        int cnt1 = 0, cnt2 = 0;
        // 投票过程
        for (int num : nums) {
            // 如果是候选者1，票数++
            if (num == cand1) {
                cnt1++;
                continue;
            }
            // 如果是候选者2，票数++
            if (num == cand2) {
                cnt2++;
                continue;
            }
            // 既不是cand1也不是cand2，如果cnt1为0，那它就去做cand1
            if (cnt1 == 0) {
                cand1 = num;
                cnt1++;
                continue;
            }
            // 如果cand1的数量不为0但是cand2的数量为0，那他就去做cand2
            if (cnt2 == 0) {
                cand2 = num;
                cnt2++;
                continue;
            }
            // 如果cand1和cand2的数量都不为0，那就都-1
            cnt1--;
            cnt2--;
        }
        // 检查两个票数符不符合
        cnt1 = cnt2 = 0;
        for (int num : nums) {
            if (num == cand1) {
                cnt1++;
            } else if (num == cand2) {  
                // 这里一定要用else if
                // 因为可能出现[0,0,0]这种用例，导致两个cand是一样的，写两个if结果就变为[0,0]了
                cnt2++;
            }
        }
        int n = nums.length;
        if (cnt1 > n / 3) {
            res.add(cand1);
        }
        if (cnt2 > n / 3) {
            res.add(cand2);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

返回数据流中第 k 大元素

• 设计一个找到数据流中第 k 大元素的类,注意是排序后的第 k 大元素

• 思路：使用一个大小为 k 的优先队列来存储前 k 大的元素，其中优先队列的队头为队列中最小的元素，也就是第 k 大的元素。在单次插入的操作中，先把元素 val 加入到优先队列中。如果此时优先队列的大小大于 k，就要将优先队列的队头元素弹出，以保证优先队列的大小为 k。

class KthLargest {
    private PriorityQueue<Integer> pq;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.pq = new PriorityQueue<Integer>();
        for (int x : nums) {
            add(x);
        }
    }
    
    public int add(int val) {
        pq.offer(val);
        if (pq.size() > k) {
            pq.poll();
        }
        return pq.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

滑动窗口最大值

• 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只能看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

• 思路：暴力法：每次取到一个滑动窗口时，遍历元素找到滑动窗口的最大值

  ​ 方法二：初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我向右移动窗口时，就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。但是这个最大值可能并不在滑动窗口中，这个值在数组的位置出现在滑动窗口左边界的左侧。只要继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。通过不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值

class Solution {
    /* 暴力破解法, 依次收集滑动窗口的最大值，时间复杂度 O（n * k） */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return new int[]{};
        }
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            int temp = nums[i];
            // 收集当前窗口的最大值
            for (int j = i; j < i + k; j++) {
                temp = Math.max(temp, nums[j]);
            }
            res[i] = temp;
        }
        return res;
    }
    //方法二：
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

滑动窗口中的中位数

• 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。找出每次窗口移动后得到的新窗口中元素的中位数，并输出组成的数组。

• 思路：暴力法：每次取到一个滑动窗口时，遍历元素找到滑动窗口的中位数

class Solution {
    /* 暴力搜索 O(n^2) */
    public double[] medianSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return new double[]{};
        }
        double[] res = new double[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            res[i] = getMedian(nums, i, i + k - 1);
        }
        return res;
    }
    private double getMedian(int[] nums, int i, int j) {
        // 获取[i, j]间的中位数
        int len = j - i + 1;
        double[] temp = new double[len];
        int cur = 0; double res = 0;
        for (int k = i; k <= j; k++) {
            temp[cur++] = nums[k];
        }
        Arrays.sort(temp);
        if (len % 2 == 0) {
            res = (temp[len / 2 - 1] + temp[len / 2]) / 2;
        } else {
            res = temp[len / 2];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

设计添加数 和 寻找中位数方法

• 设计一个支持以下两种操作的数据结构：

  void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  double findMedian() - 返回目前所有元素的中位数。

• 思路：使用大顶堆和小顶堆的方法，添加数时，判断是否为奇数，是奇数的话，需要把小顶堆中删去堆头并添加到大顶堆中，保持大顶堆元素比小顶堆多一个；寻找中位数时，当大顶堆比小顶堆元素多1时，去大顶堆的堆头即为中位数，当大顶堆与小顶堆元素相同时，取两者堆头/2即获得中位数

class MedianFinder {
    /* 使用大顶堆和小顶堆的解法 */
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    private int count;
    
    /** initialize your data structure here. */
    public MedianFinder() {
    	//Lambda表达式(参数列表->所需要执行的功能)
        maxHeap = new PriorityQueue<>((x, y) -> y - x);
        minHeap = new PriorityQueue<>();
        count = 0;
    }

    public void addNum(int num) {
        count += 1;
        maxHeap.offer(num);        
        minHeap.offer(maxHeap.poll());
        // 是奇数的话，需要把小顶堆中删去堆头并添加到大顶堆中，保持大顶堆元素比小顶堆多一个
        if ((count & 1) == 1) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (!maxHeap.isEmpty()) {
            if (maxHeap.size() - minHeap.size() == 1) {
                // 当大顶堆比小顶堆元素多1时，去大顶堆的堆头即为中位数
                return (double)maxHeap.peek();
            } 
            if (maxHeap.size() == minHeap.size()) {
                // 当大顶堆与小顶堆元素相同时，取两者堆头/2即获得中位数
                return (double)(maxHeap.peek() + minHeap.peek()) / 2;
            }
        }
        return 0.0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

子数组最大平均数

• 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

• 思路：题目可以转化成寻找长度为k的的子数组的最大元素和，利用滑动窗口，长度为 n 的数组，有 n-k+1 个长度为 k 的子数组，用temp变量记录删除窗口头元素，加上窗口尾部新元素的子数组之和与其他的和对比，取较大值

class Solution {
        public double findMaxAverage(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0 || nums.length < k) {
                throw new RuntimeException("数组和k参数不合法");
            }
            double max = 0;
            // 第一个窗口
            for (int i = 0; i < k; i++) {
                max += nums[i];
            }
            double temp = max;
            // 遍历，删头加尾确定窗口最大值
            for (int i = 1; i <= nums.length - k; i++) {
                temp = temp - nums[i - 1] + nums[i + k - 1];
                max = Math.max(max, temp);
            }
            return max / k;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

有效字母异位词

• 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

• 思路：遍历S的每个字母，记录每个字母出现的次数，然后遍历T的每个字母，若与S的字母相同，则抵消一个，最后遍历数组，如果全部抵消，即为字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] nums = new int[26]; 
        // 每个位置记录字符出现次数
        for (int i = 0; i < s.length(); i++) {
            nums[s.charAt(i)-'a']++;
        }
        // 字符抵消
        for (int i = 0; i < t.length(); i++) {
            nums[t.charAt(i)-'a']--;
        }
        // 如果仍有字符没有被抵消，说明不是异位词
        for (int count: nums) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

翻转单词序列

public class Solution {
    /* 先将整体反转，然后对单词进行逐个反转，时间复杂度O(n) */
    public String ReverseSentence(String str) {
        if (str == null || str.trim().equals("")) {
            return str;
        }
        char[] chars = str.toCharArray();
        // 反转整个单词序列
        reverse(chars, 0, chars.length - 1);
        // 依次反转每个单词
        int left = 0, right = 0;
        while (left < chars.length) {
            // 如果开头就是空格，那么两者一起跳过
            if (chars[left] == ' ') {
                left++;
                right++;
            } else if (right == chars.length - 1) {
                // 如果right已经走到结尾，直接反转
                reverse(chars, left, right);
                break;
            } else if (chars[right] != ' ') {
                // 如果right遇到的不是空格，那么继续寻找单词的末尾空格
                right++;
            } else if (chars[right] == ' ') {
                // right已经走到一个单词的空格处,反转
                reverse(chars, left, --right);
                left = ++right;
            }
        }
        return new String(chars);
    }
    private void reverse(char[] chars, int i , int j) {
        while (i < j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            i++;
            j--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

无重复字符的最长子串

class Solution {
    /* 使用HashSet保存窗口出现的字符，时间复杂度O（n） */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        HashSet<Character> set = new HashSet<>();
        int left = 0, right = 0, res = 0;
        while (left <= right && right < chars.length) {
            if (!set.contains(chars[right])) {
                // 滑动窗口右扩张
                set.add(chars[right++]);
                res = Math.max(res, right - left);
            } else {
                // 滑动窗口左缩小
                set.remove(chars[left++]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

七进制转换

class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        boolean flag = false; // 是否为负数
        if (num < 0) {
            num = -1 * num;
            flag = true;
        }
        StringBuilder builder = new StringBuilder();
        // 商为下一次的值，余数为当前的七进制值，从后往前追加
        while (num > 0) {
            int v = num % 7;// 余数
            num /= 7; // 商
            builder.insert(0, v);
        }
        // 负数处理
        if (flag) {
            builder.insert(0, "-");
        }
        return builder.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

位运算

数字位数为 “ 1 ” 的个数

public class Solution {
    /* 解法1，循环n次,n为二进制数长度 */
    public int hammingWeight(int n) {
        int res = 0;
        String bin = Integer.toBinaryString(n);
        for (int i = 0; i < bin.length(); i++) {
            if (bin.charAt(i) == '1') {
                res++;
            }
        }
        return res;
    }
    
     /* 解法2，循环k次,k为二进制数中最高位的1的位数 */
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                res++;
            }
            // 无符号右移，消去末尾1位
            n >>>= 1;
        }
        return res;
    }

    /* 解法3，循环res次 */
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res++;
            n = (n - 1) & n;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2 的幂

• 判断是否是 2 的次幂

class Solution {
    public boolean isPowerOfTwo(int n) {
        // 一个数是2的幂，那么这个数的二进制中只有1个1，使用(n-1)&n消去1后为0
        if (n == 0) {
            return false;
        }
        // 转化为long型防止溢出
        long ln = (long)n;
        if (((ln - 1) & ln) != 0) {
            return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        // 1.任何数异或0都等于原数
        // 2.相同的数异或为0
        int res = 0;
        for (int value: nums) {
            res ^= value;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

只出现一次的数字

public class Solution {
    /* 使用HashMap记录数字出现的次数, 时间复杂度O（n），空间复杂度O（k），k为不重复的元素个数 */
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length == 0) {
            return;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            // 记录每个元素出现的次数
             map.put(array[i], map.getOrDefault(array[i], 0) + 1);
        }
        boolean first = false;
        for (int i = 0; i < array.length; i++) {
             if (map.getOrDefault(array[i], 0) == 1) {
                 if (!first) {
                     // 填充第一个元素
                     num1[0] = array[i];
                     first = true;
                     // 标识已经找到
                     map.put(array[i], -1);
                 } else {
                     // 第二个元素
                     num2[0] = array[i];
                 }
             }
        }
    }
    
    /*
    使用位运算，先将所有的元素异或一遍，相当于两个不重复的元素之间做了一次异或，
    然后根据异或得到的结果，获取结果的最低位1出现的位置，再通过该位置将数组分割成两个部分，
    这两个部分分别含有一个唯一的元素，再次异或即可分别获取。时间复杂度O（n），空间复杂度O（1）
    */
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length == 0) {
            return;
        }
        // 全体异或
        int res = 0;
        for (int value: array) {
            res ^= value;
        }
        // 获取异或结果的最低位1的位置
        int index = getLower1Index(res);
        // 根据这个位置将数组分割成两个部分来进行异或，就可以得到相应的唯一元素
        int res1 = 0, res2 = 0;
        for (int value: array) {
            if (getLower1Index(value) == index) {
                res1 ^= value;
            } else {
                res2 ^= value;
            }
        }
        num1[0] = res1;
        num2[0] = res2;
    }
    /* 获取低位的1位置 */
    private int getLower1Index(int num) {
        int index = -1;
        while ((num & 1) != 1) {
            // 当最低位不为1，则无符号右移动
            index++;
            num >>>= 1;
        }
        return index;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

回溯

全排列

class Solution {
    // 存储结果
    private List<List<Integer>> res = new ArrayList<>();
    // 是否已使用该位置
    private boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
            used = new boolean[nums.length];
            // 单个答案的数据数
            int count = 0;
            ArrayList<Integer> oneRes = new ArrayList<>();
            // 回溯搜索
            backTraceSearch(count, nums, oneRes);
            return res;
    }
    private void backTraceSearch(int count, int[] nums, ArrayList<Integer> oneRes) {
        // 回溯终止条件
        if (count == nums.length) {
            res.add(new ArrayList<>(oneRes));
            return;
        }
        // 回溯搜索
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // 没有使用过
                used[i] = true;
                oneRes.add(nums[i]);
                backTraceSearch(count + 1, nums, oneRes);
                // 状态回溯
                oneRes.remove(oneRes.size() - 1);
                used[i] = false;
            }
        }
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

组合总数

class Solution {
    // 存储结果
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
            // 开始索引
            int index = 1;
            ArrayList<Integer> oneRes = new ArrayList<>();
            // 回溯搜索
            backTraceSearch(index, k, n, oneRes);
            return res;
    }
    private void backTraceSearch(int index, int k, int n, ArrayList<Integer> oneRes) {
        // 回溯终止条件
        if (oneRes.size() == k) {
            res.add(new ArrayList<>(oneRes));
            return;
        }
        // 回溯搜索
        for (int i = index; i <= n; i++) {
            oneRes.add(i);
            backTraceSearch(i + 1, k, n, oneRes);
            // 状态回溯
            oneRes.remove(oneRes.size() - 1);
        }
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

N 皇后问题

class Solution {
    private int res = 0;
    // 记录已经摆放了的皇后位置
    private int[] record;

    public int totalNQueens(int n) {
        record = new int[n];
        int row = 0;
        backTraceSearch(row, n);
        return res;
    }
    private void backTraceSearch(int row, int n) {
        // 回溯终止条件
        if (row == n) {
            res++;
            return;
        }
        // 回溯搜索，逐列寻找摆放皇后的位置
        for (int col = 0; col < n; col++) {
            if (check(row, col)) {
                // 该位置可以摆放皇后，继续往上一行放置皇后
                record[row] = col;
                backTraceSearch(row + 1, n);
                // 状态回溯
                record[row] = 0;
            }
        }
        return;
    }
    /* 检查该位置是否可放置皇后 */
    private boolean check(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 检查该列以下是否存在皇后 
            if (record[i] == col) {
                return false;
            }
             // 检查对角线是否含皇后
             if (Math.abs(i - row) == Math.abs(record[i] - col)) {
                 return false;
             }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

复原 IP 地址

class Solution {
    private List<String> res = new ArrayList<>();
    
    public List<String> restoreIpAddresses(String s) {
        // 当前索引
        int index = 0;    
        // 当前结果 
        ArrayList<String> oneRes = new ArrayList<>();
        backTraceSearch(s, index, oneRes);
        return res;
    }
    private void backTraceSearch(String s, int index, ArrayList<String> oneRes) {
        // 回溯终止条件
        if (oneRes.size() == 4) {
            // 已经是最后一个位置
            if (index == s.length()) {
                res.add(String.join(".", oneRes));
            }
            return;
        }
        // 回溯搜索
        for (int i = 1; i <= 3; i++) {
            // IP段最长为3位
            if (index + i > s.length()) {
                break;
            }
            // 获取分段
            String segment = s.substring(index, index + i);
            // 分段校验
            if (segment.startsWith("0") && segment.length() > 1 || 
                 segment.length() == 3 && Integer.valueOf(segment) > 255) {
                break;
            }
            oneRes.add(segment);
            backTraceSearch(s, index + i, oneRes);
            // 状态回溯
            oneRes.remove(oneRes.size() - 1);
        }
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

括号生成

• 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
• 思路：
  • 当前左右括号都有大于 00 个可以使用的时候，才产生分支
  • 产生左分支的时候，只看当前是否还有左括号可以使用；
  • 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
  • 在左边和右边剩余的括号数都等于 0 的时候结算。

public class Solution {

    // 做减法

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }

        // 执行深度优先遍历，搜索可能的结果
        dfs("", n, n, res);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, List<String> res) {
        // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
        // 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }

        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }

        if (right > 0) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

岛屿数量

• 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

  岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

  此外，你可以假设该网格的四条边均被水包围。

• 思路：

  • 目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。
  • dfs方法： 设目前指针指向一个岛屿中的某一点 (i, j)，寻找包括此点的岛屿边界。
    • 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
    • 终止条件：
      • (i, j) 越过矩阵边界；
      • grid[i][j] == 0，代表此分支已越过岛屿边界。
    • 搜索岛屿的同时，执行 grid[i][j] = ‘0’，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。
  • 主循环：遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。
  • 最终返回岛屿数 count 即可

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

动态规划

• 划分阶段
• 确定状态和状态变量
• 确定决策并写出状态转移方程
• 寻找边界条件

买卖股票的最佳时机

• 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

  你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

• 思路：找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i] = Math.max(0, dp[i - 1] + prices[i] - prices[i - 1])
        // dp[i] 表示第i天卖出可以获取到第最大利润
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int res = 0;
        int[] dp = new int[prices.length];
        dp[0] = 0;// 第一天利润为0
        for (int i = 1; i < prices.length; i++) {
            // 当今天可以买时则累加，不然则为0
            dp[i] = Math.max(0, dp[i - 1] + prices[i] - prices[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

买卖股票的最佳时期(含冷冻期)

class Solution {
    public int maxProfit(int[] prices) {
        // 定义dp[i][j]表示第i天处于j状态时的利润
        // j = 0，不持股；昨天可不持股或持股卖出
        // j = 1，持股；昨天一直持股或冷冻期买入
        // j = 2，冷冻期；前天持股卖出 ，冷冻期为卖出股票后的一天，所以昨天不持股
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][3];
        // 第一天边界条件
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for (int i = 1 ; i < prices.length; i++) {
            // 不持股，可能昨天不持股或持股卖出
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 持股，可能昨天持股或冷冻期买入
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][2] - prices[i]);
            // 冷冻期，昨天不持股
            dp[i][2] = dp[i - 1][0];
        }
        // 最后的最大利润在不持股或冷冻期两者中
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

买卖股票最佳时机(含手续费)

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // dp[i][j]表示在i天之前各状态可获取的最大利润
        // j定义不持有状态为0，持有状态为1
        // j = 0，昨天不持有或昨天持有卖出
        // j = 1，昨天持有或昨天不持有买入（需要算手续费）
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 不持股，昨天不持股或卖出（含手续费）
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            // 持股，昨天持股或买入
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        // 最大值在不持股的情况下发生
        return dp[prices.length - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

不同路径

• m x n 网格，每次只能向下或者向右移动一步。机器人试图达到网格的右下角共有多少条不同的路径？

• 思路：

  • 我们令 dp[i][j] 是到达 i, j 最多路径

  • 动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

    注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1

    时间复杂度：O(m*n)O(m∗n)

    空间复杂度：O(m * n)O(m∗n)

    优化：因为我们每次只需要 dp[i - 1][j] + dp[i][j - 1]

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

最长回文子串

class Solution {
    /*
    * 中心扩散法,时间复杂度O(n^2)
    */
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            int len1 = lenOfPalindrome(s, i, i);// 从i为分界点扩散
            int len2 = lenOfPalindrome(s, i, i + 1);// 以i与i+1之间为分界点扩散
            int max = Math.max(len1, len2);
            if (max > res.length()) {
                // 确定以i为中心的和max为直径的回文起始点和结束点
                int left = i - (max -1) / 2;
                int right = i + max / 2;
                // 截取出最长子串
                res = s.substring(left, right + 1);
            }
        }
        return res;
    }
    private int lenOfPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
        }
        return right - left - 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

编辑距离[二维 dp]

class Solution {
    public int minDistance(String word1, String word2) {
         int rows = word1.length();
         int cols = word2.length();
         // 状态转移方程: dp[i][j] = min{dp[i][j - 1] + 1//增, dp[i - 1][j] + 1//删, dp[i - 1][j - 1] + 0或1//改}
         // 其中dp[i - 1][j - 1] + 0代表着word1和word2的第i,j个位置元素相同，所以无需改；
         //dp[i - 1][j - 1] + 1代表着word1和word2的第i,j个位置元素不相同，所以要改
         int[][] dp = new int[rows + 1][cols + 1];
         // 填充word1为""时转化为word2的编辑距离
         for (int i = 1; i <= cols; i++) {
             dp[0][i] = i; 
         }
         // 填充word2为""时转化为word1的编辑距离
         for (int i = 1; i <= rows; i++) {
             dp[i][0] = i; 
         }
         // 填充dp
         for (int i = 1; i <= rows; i++) {
             for (int j = 1; j <= cols; j++) {
                 int addCount = dp[i - 1][j] + 1; // 增
                 int deleteCount = dp[i][j - 1] + 1; // 删
                 int changeCount = dp[i - 1][j - 1];  // 改
                 if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                     changeCount++;
                 }

                 dp[i][j] = Math.min(addCount, Math.min(deleteCount, changeCount));
             }
         }
         return dp[rows][cols];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

最长公共子序列[二维 dp]

class Solution {
 public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        int rows = text1.length();
        int cols = text2.length();
        int[][] dp = new int[rows + 1][cols + 1];
        // 填充dp表,状态转移方程： 
        // 1.text1[i] == text2[j],dp[i][j] = dp[i - 1][j] + 1
        // 2.text1[i] != text2[j],dp[i][j] = max{dp[i - 1][j], dp[i][j - 1]}
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 相等，取dp[i - 1][j - 1]的值 + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 不想等，取dp[i - 1][j]和dp[i][j - 1]中的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[rows][cols];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

最长上升子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        // 状态转移方程 dp[i] = max{dp[i-1], dp[i-2],..., dp[0]} + 1,其中dp[i-1], dp[i-2]等需要小于nums[i],这个过程是往后寻找，接上最长上升子序列的过程，所以每个dp都表示了当前i能够与之前范围组成的最长的上升子序列长度。
        int[] dp = new int[nums.length];
        // 默认自身就是一个最长上升子序列
        int res = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;// 默认以自身开始
            for (int j = i; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    // 往后寻找
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

换钱最少货币数

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1 || coins.length == 0) {
            return 0;
        }
        // dp[i]表示凑i元最少所需的货币数
        // 状态转移方程: dp[i] = min(dp[i-j] + 1); j表示某货币数值
        int[] dp = new int[amount + 1];
        // 先对货币进行排序
        Arrays.sort(coins);
        // 默认不可换钱
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 边界条件
        for (int i = 0; i < coins.length; i++) {
            // 直接兑换
            if (coins[i] < dp.length) {
              dp[coins[i]] = 1;
            }
        }
        // 填充dp[i]
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                int coin = coins[j];
                // 可兑换
                if (i > coin && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin]+ 1);
                }
            }
        }
        return (dp[amount] == Integer.MAX_VALUE) ? - 1 : dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

矩阵最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        // dp[i]表示从起点走到该位置的最小和
        // 状态转移方程： dp[i] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        // 边界状态
        dp[0][0] = grid[0][0];
        // 第一行和第一列直接累加
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < cols; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        // 填充dp
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                // 从上一行或上一列中寻找最小的进行相加d
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

龙与地下城

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0) {
            return 0;
        }
        int rows = dungeon.length;
        int cols = dungeon[0].length;
        int[][] dp = new int[rows][cols];
        int identValue = dungeon[rows - 1][cols - 1];
        dp[rows - 1][cols - 1] = (identValue > 0) ? 1 : 1 - identValue;
        for (int i = rows - 2; i >= 0; i--) {
            int val = dp[i + 1][cols - 1] - dungeon[i][cols - 1];
            dp[i][cols - 1] = (val <= 0) ? 1 : val;
        }
        for (int i = cols - 2; i >= 0; i--) {
            int val = dp[rows - 1][i + 1] - dungeon[rows - 1][i];
            dp[rows - 1][i] = (val <= 0) ? 1 : val;
        }
        for (int i = rows - 2; i >= 0; i--) {
            for (int j = cols - 2; j >= 0; j--) {
                int min = Math.min(dp[i + 1][j], dp[i][j + 1]);
                // 不断填充dp,当当前期望值小于等于0，说明当前的补血多于扣血，当前血量设置为1
                int val = (min - dungeon[i][j]) <= 0 ? 1 : min - dungeon[i][j];
                dp[i][j] = val;
            }
        }
        return dp[0][0];
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

打家劫舍

class Solution {
    public int rob(int[] nums) {
        // dp[i]表示第i天获得的最高利益，有两种选择，不偷窃或放弃前一天的结果，偷窃
        // dp[i] = Math.max(dp[i-2] + nums[i] (隔天偷盗), dp[i - 1](不偷盗))
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length + 1]; 
        dp[1] = nums[0];
        // 从第2天开始
        for (int i = 2; i <= nums.length; i++) {
            // dp[i - 1],不偷窃
            // dp[i - 2] + nums[i - 1],隔天偷窃
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剪绳子

public class Solution {
    public int cutRope(int target) {
        // 动态规划解法，dp表示绳子的长度：
        // 当长度为1时，最大乘积只能为1
        // 当长度为2时，最大乘积为1
        // 当长度为3时，最大乘积为2
        // 当长度大于等于4时，可以换分为不同的小段，每一段即一个dp
        switch (target) {
                case 2 : return 1;
                case 3 : return 2;
        }
        // 以下是可以分段的情形，dp1 ，2， 3直接就可使用
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        // 构造dp
        for (int i = 4; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++) {
                // 将绳子切分成两段
                // dp[i - j] * dp[j] 表示两段的乘积
                dp[i] = Math.max(dp[i], dp[i - j] * dp[j]);
            }
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

爬楼梯

class Solution {
    /* 斐波那契数列类问题 */
    public int climbStairs(int n) {
        if (n <= 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            // 状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 动态规划解法，dp[i]=true表示[0,i）的单词可以使用wordDict表示，那么只需要判断[i,length）的单词可不可以表示即可
        // 状态转移方程：dp[i] = dp[0...j] && set.contains(0, j)
        // 将wordDict添加到hashSet中
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        // 初始条件，肯定可以拆分成空串
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            // 在该串中继续找子串，只要匹配即为true
            for (int j = 0; j <= i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

丑数

class Solution {
    public int nthUglyNumber(int n) {
        if (n < 1) {
            throw new RuntimeException("n不可小于1");
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 =0;
        for (int i = 1; i < n; i++) {
            int min = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
            if (min == dp[p2] * 2) {
                p2++;
            }
            if (min == dp[p3] * 3) {
                p3++;
            }
            if (min == dp[p5] * 5) {
                p5++;
            }
            dp[i] = min;
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

完全平方数

class Solution {
    public int numSquares(int n) {
        // dp[i]表示i含有的最小平方数个数
        // dp[i] = min(dp[i], dp[i - j^2]) (i - j^2 >=0)
        if (n <= 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        // 边界条件
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            // 默认所含有的完全平方数都为1的情况
            dp[i] = i;
            for (int j = 0; i - j * j >= 0; j++) {
                // 往前寻找完全平方数
                // dp[i - j * j] + 1
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); 
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        // dp[i][j]表示i， j这个位置的最小路径和
        // dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
        // 边界条件，第一列和最后的斜边直接填充
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }
        for (int i = 1; i < n; i++) {
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        // 填充dp中间部分
        for (int i = 2; i < n; i++) {
            List<Integer> list = triangle.get(i);
            // 填充该list中间部分
            for (int j = 1; j < list.size() - 1; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + list.get(j);
            }
        }
        // 寻找最后的路径最小和
        int res = dp[n - 1][0];
        for (int i = 1; i < n; i++) {
            res = Math.min(res, dp[n - 1][i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

乘积最大子序列

class Solution {
    public int maxProduct(int[] nums) {
        int[] dp_max = new int[nums.length+1];
        int[] dp_min = new int[nums.length+1];
        if(nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        // 由于存在负数，所以需要维护两个数组
        // dp_max[i] 指的是以第 i 个数结尾的 乘积最大 的连续子序列
        // dp_min[i] 指的是以第 i 个数结尾的 乘积最小 的连续子序列
        dp_max[0] = 1;
        dp_min[0] = 1;
        for (int i = 1;i <= nums.length;i++){
            // 如果数组的数是负数，那么会导致 max 变成 min，min 变成 max
            // 故需要交换dp 
            if(nums[i-1] < 0){
                int temp = dp_min[i-1];
                dp_min[i-1] = dp_max[i-1];
                dp_max[i-1] = temp;
            }
            dp_min[i] = Math.min(nums[i-1],dp_min[i-1]*nums[i-1]);
            dp_max[i] = Math.max(nums[i-1],dp_max[i-1]*nums[i-1]);
            max = Math.max(max,dp_max[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

二叉树

前序和后序重建二叉树

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return helper(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }
    private TreeNode helper(int[] pre, int[] in, int preLeft, int preRight, int inLeft, int inRight) {
        //
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        // 由前序遍历序列获取根节点
        int rootValue = pre[preLeft];
        TreeNode root = new TreeNode(rootValue);   
        // 在中序遍历序列中，搜索出根节点的位置
        int index = findRootIndex(rootValue, in);
        // 通过根节点位置，在中序遍历序列中可划分出左子树和右子树的中序遍历序列
        // 在前序遍历中，可划分出左子树和右子树的前序遍历序列,继续递归地构建树
        // preLeft + index - inLeft：通过preLeft + 左子树节点数（index - inLeft）确定左子树前序遍历的右边界
        // preLeft + index - inLeft + 1:通过前序遍历序列的右边界+1确定中序遍历序列的左边界
        root.left = helper(pre, in, preLeft + 1, preLeft + index - inLeft, inLeft, index - 1);
        root.right = helper(pre, in, preLeft + index - inLeft + 1, preRight, index + 1, inRight);
        return root;
    }
    private int findRootIndex(int target, int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }
     
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

序列化 反序列化二叉树

public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        return _Serialize(root, builder).toString();
    }
    private StringBuilder _Serialize(TreeNode root, StringBuilder builder) {
        // 递归终止条件
        if (root == null) {
            builder.append("#!");
            return builder;
        }
        // 使用前序的方式序列化
        builder.append(root.val + "!");
        _Serialize(root.left, builder);
        _Serialize(root.right, builder);
        return builder;
    }
    
    TreeNode Deserialize(String str) {
       return _Deserialize(str.split("!"));
    }
    
    private int index = -1;
    private TreeNode _Deserialize(String[] strs) {
        index++;
        if (index >= strs.length || "#".equals(strs[index])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(strs[index]));
        root.left = _Deserialize(strs);
        root.right = _Deserialize(strs);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

二叉树的子结构

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        boolean res = false;
        if (root1 != null && root2 != null) {
            // 判断该位置是否为子结构
            res = check(root1, root2);
        }
        if (!res) {
            // 在左子树中寻找
            res = HasSubtree(root1.left, root2);
        }
        if (!res) {
            // 在右子树中寻找
            res = HasSubtree(root1.right, root2);
        }
        return res;
    }
    private boolean check(TreeNode root1, TreeNode root2) {
        // 子结构判断条件
        if (root1 == null && root2 == null || root2 == null) {
            return true;
        }
        if (root1 == null && root2 != null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        // 再次校验左右子树是否都满足子结构
        return check(root1.left, root2.left) && check(root1.right, root2.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

二叉树镜像

public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        Mirror(root.left);
        Mirror(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

从上往下打印二叉树

public class Solution {
    /* 使用队列来存储节点 */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
            // 添加层序遍历结果
            res.add(poll.val);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

验证二叉搜索树的后序遍历序列

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 两个特殊情况处理
         if (sequence.length == 0){
            return false;
        }
        if (sequence.length == 1){
            return true;
        }
        int left = 0, right = sequence.length - 1;
        return check(sequence, left, right);
    }
    private boolean check(int[] sequence, int left, int right) {
        if (left >= right) {
            return true;
        }
        // 根节点
        int root = sequence[right];
        // 划分节点
        int index = -1;
        // 从右往左找第一个比根节点小的节点，划分左右子树
        for (int i = right - 1; i >= left; i--) {
            if (sequence[i] < root) {
                index = i;
                break;
            }
        }
        for (int i = index; i >= left; i--) {
            if (sequence[i] >= root) {
                return false;
            }
        }
        // 划分左右子树
        return check(sequence, left, index) && check(sequence, index + 1, right - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

二叉搜索树转化为双向链表

public class Solution {
    /* 使用栈模拟中序遍历过程 */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null || pRootOfTree.left == null && pRootOfTree.right == null) {
            return pRootOfTree;
        }
        Stack<TreeNode> stack  = new Stack<>();
        // 是第一个获取到的节点
        boolean first = true;
        TreeNode root = pRootOfTree, res = pRootOfTree, pre = null;
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode pop = stack.pop();
                root = pop.right;
                 
                if (first) {
                    res = pop;
                    pre = pop;
                    first = false;
                } else {
                    pre.right = pop;
                    pop.left = pre;
                    pre = pop;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

平衡二叉树校验

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 判断是否为平衡二叉树
        return getMaxDepth(root) != -1;
    }
    
    private int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);
        int right = getMaxDepth(root.right);
        // 判断左右子树的深度是否为-1
        if (left == -1 || right == -1) {
            return -1;
        }
        // 如果左右子树深度差值大于1则返回-1表示该树不是平衡二叉树，如果小于1则返回最大深度
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二叉树的深度

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10

二叉树的中序下一节点

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode root)
    {
        if (root == null) {
            return null;
        }
        // 1.有右子树，找右子树最左
        if (root.right != null) {
            return findMostLeft(root.right);
        } else {
            // 2.3.无右子树，当当前节点是父节点的左子树时，父节点就是后继节点
            TreeLinkNode parent = root.next;
            while (parent != null && parent.left != root) {
                root = parent;
                parent = parent.next;
            }
            return parent;
            
        }
    }
    private TreeLinkNode findMostLeft(TreeLinkNode root) {
        if (root.left == null) {
            return root;
        }
        return findMostLeft(root.left);
    }
//--------------------------------------------------------------
    private List<TreeLinkNode> list = new ArrayList<>();
        
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode == null) {
            return null;
        }
        TreeLinkNode root = pNode;
        // 找到树的根节点
        while (root.next != null) {
            root = root.next;
        }
        // 获取中序遍历结果集
        inOrder(root);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == pNode) {
                // 返回下一个节点
                return (i >= list.size() - 1) ? null : list.get(i + 1);
            }
        }
        return null;
    }
    
    private void inOrder(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        list.add(root);
        inOrder(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

”之“ 字形打印二叉树

class Solution {
    /* 层次遍历，带上深度条件 */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            ArrayList<Integer> oneRes = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                     queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                if ((depth & 1) == 0) {
                    // 从左到右添加结果
                    oneRes.add(poll.val);
                } else {
                    // 从右到左添加结果
                    oneRes.add(0, poll.val);
                }
            }
            res.add(oneRes);
            depth++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

有序数组转化二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {        
        return helper(nums);
    }
    /* 每次都取出数组的中间位置的值作为根节点，然后以此为分割取两边作为子树 */
    private TreeNode helper(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }
        int len = nums.length;
        // 有序数组的中间节点作为根节点
        TreeNode root = new TreeNode(nums[len / 2]);
        root.left = helper(Arrays.copyOfRange(nums, 0, len / 2));
        root.right = helper(Arrays.copyOfRange(nums, len / 2 + 1, len));
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

路径总和

class Solution {
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> oneRes = new ArrayList<>();
        _pathSum(root, sum, res, oneRes);
        return res;
    }
    /* 回溯搜索 */
    private void _pathSum(TreeNode root, int sum,  List<List<Integer>> res, List<Integer> oneRes) {
        if (root == null) {
            return;
        }
        // 回溯终止条件，遇到叶子节点
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                oneRes.add(sum);
                res.add(new ArrayList<Integer>(oneRes));
            }
            return;
        }
        // 左子树不为空，新开辟一个路径搜索
        if (root.left != null) {
            List<Integer> temp = new ArrayList<>(oneRes);
            temp.add(root.val);
            _pathSum(root.left, sum - root.val, res, temp);
        }
        // 右子树不为空，新开辟一个路径搜索
        if (root.right != null) {
            oneRes.add(root.val);
            _pathSum(root.right, sum - root.val, res, oneRes);
        }
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

二叉搜索树第 k 小节点

class Solution {

    /* 中序遍历第k次即获取到了第k小的元素 */
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        // 中序遍历
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                // 弹出的节点为中序遍历的节点
                TreeNode pop = stack.pop();
                root = pop.right;
                // 已经弹出了第k个节点
                if (++count == k) {
                    return pop.val;
                }
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

找树左下角的值

class Solution {
    /* 按层序遍历获取最后一层第一个节点的值即为最左节点值 */
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            // 当前的队列容量即为下一层的节点数量
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                // 该层的第一个节点即为树左下角的值（最后一次更新的）
                if (i == 0) {
                    res = poll.val;
                }
            }
        }
        return res;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

节点间最长同值路径

class Solution {
    private int res = 0;
    public int longestUnivaluePath(TreeNode root) {
       helper(root);
       return res;
    }
    /* 考虑同值情况下的最长路径 */
    private int helper(TreeNode root) {
       // 递归终止条件
       if (root == null) {
           return 0;
       }
       // 获取左子树最长同值路径
       int left = helper(root.left);
       // 获取右子树最长同值路径
       int right = helper(root.right);
       int leftNum = 0;
       int rightNum = 0;
       // 判断是否同值，同值则组成一条路径，累加+1，不同则为0
       if (root.left != null && root.left.val == root.val) {
           leftNum += left + 1;
       }
       if (root.right != null && root.right.val == root.val) {
           rightNum += right + 1;
       }
       // 更新最长路径
       res = Math.max(res, leftNum + rightNum);
       // 返回其中一条路径
       return Math.max(leftNum, rightNum);
    }
    
    
    /* 不考虑同值情况下的最长路径 */
    private int helper(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return 0;
        }
        // 递归获取左右子节点的最长同值路经
        int left = helper(root.left);
        int right = helper(root.right);
        res = Math.max(res, left + right);
        return Math.max(left, right) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

二叉树最近公共祖先

class Solution {

    private TreeNode res = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        helper(root, p, q);
        return res;
    }

    private boolean helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        int left = helper(root.left, p, q) ? 1 : 0; // 查看左子树含不含p或q
        int right = helper(root.right, p, q) ? 1 : 0; // 查看右子树含不含p或q
        int mid = (root == p || root == q) ? 1 : 0; // 当前节点是否等于p或1
        // 当满足以下条件，说明root就是最近公共祖先
        // 1. left = 1, right = 1, mid = 0 在左子树和右子树中分别含有pq
        // 2. left = 1, right = 0, mid = 1 在左子树中含有p或q，且root = p或q
        // 3. left = 0, right = 1, mid = 1 在右子树中含有p或q，且root = p或q
        if (left + right + mid >= 2) {
            res = root;
            return true;
        }
        // 当前至少有一边查找到了p或q
        return left + right + mid >= 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二叉搜索树最近公共祖先

class Solution {
    private TreeNode res = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        helper(root, p, q);
        return res;       
    }

    private boolean helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        int left = helper(root.left, p, q) ? 1 : 0;
        int right = helper(root.right, p, q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid >= 2) {
            res = root;
            return true;
        }
        return left + right + mid >= 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二叉树的右视图

class Solution {
    /* 层序遍历，收集右侧节点值 */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                // 已经是一层的最右边,收集结果
                if (i == size - 1) {
                    res.add(poll.val);
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

左叶子之和

class Solution {

    private int res = 0;

    /* 采用前序遍历 + 左叶子结点flag标识 */
    public int sumOfLeftLeaves(TreeNode root) {
        preOrder(root, false);
        return res;
    }
    private void preOrder(TreeNode root, boolean flag) {
        if (root == null) {
            return;
        }
        if (flag && root.left == null && root.right == null) {
            // 左叶子节点
            res += root.val;
        }
        preOrder(root.left, true); // 左直接子树一定会有左叶子结点
        preOrder(root.right, false); // 右直接子树不存在左叶子节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

链表

反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = head, cur = head.next, later = null;
        while (cur != null) {
            // 先记录好later的指针
            later = cur.next;
            // 反转
            cur.next = pre;
            // 后移一位
            pre = cur;
            cur = later;
        }
        head.next = null;
        return pre;
    }
    
    // 递归地反转
    public ListNode reverseList(ListNode head) { 
       return helper(null, head);
   }
    private ListNode helper(ListNode pre, ListNode cur) {
        //递归终止条件
        if (cur == null) {
            return pre;
        }
        //递归过程
        ListNode later = cur.next;
        cur.next = pre;
        return helper(cur, later);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

反转局部链表

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        // 获取到m、m前一个节点、n、n后一个节点
        ListNode preM = null, M = head, N = head, laterN = null;
        ListNode counter = head;
        int count = 0;
        while (counter != null) {
            count++;
            preM = count == m - 1 ? counter : preM;
            M = count == m ? counter : M;
            N = count == n ? counter : N;
            laterN = count == n + 1 ? counter : laterN;
            counter = counter.next;
        }
        // 连接preM和N
        if (preM != null) {
            preM.next = N;
        }
        // 反转M到N之间的链表
        ListNode pre = M, cur = M.next, later = null;
        while (cur != laterN) {
            // 记录后一个节点
            later = cur.next;
            // 反转
            cur.next = pre;
            // 后移
            pre = cur;
            cur = later;
        }
        // 连接M与laterN
        M.next = laterN;
        // 如果preM为null，说明是从head开始反转到N的，返回N即可；不为null则说明反转了中间部分，返回head
        return preM == null ? N : head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

删除链表重复节点

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 为null或只存在一个节点
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 定义pre、cur和later指针
        ListNode pre = dummy, cur = head, later = cur.next;
        while (cur != null && later != null) {
            if (later.val == cur.val) {
                // 当later和cur相等，则让later向后走，直到不等，然后pre与later连接，跳过相等部分
                while (later != null && later.val == cur.val) {
                    later = later.next;
                }
                // 跳过相等部分
                pre.next = later;
                cur = later;
                // later注意判空
                later = later == null ? null : later.next;
            } else {
                // later与cur不想等，三者都后移一位
                pre = pre.next;
                cur = cur.next;
                later = later.next;
            }
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

链表中环的入口

public class Solution {
    /* 使用HashSet记录遍历过的节点，当出现了重复节点时即为环的入口 */
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            } else {
                set.add(head);
                head = head.next;
            }
        }
        return head;
    }


    /* 使用快慢指针相遇找到环形链表的一点，然后从链表头开始于该节点一起往前走，链表头与该节点相遇即为环的入口 */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        // 寻找环状链表中的一点
        while (true) {
            if (slow == null || fast == null || fast.next == null) {
               // 不成环
               return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 相遇
                break;
            }
        }
        ListNode p1 = head, p2 = slow;
        // 寻找链表头与slow相遇的点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

链表是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head, fast = head;
        while (true) {
            if (slow == null || fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

相交链表公共节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先获取到headA和headB的长度，然后在进行长度的对其
        int len1 = 0, len2 = 0;
        ListNode counterA = headA, counterB = headB;
        while (counterA != null) {
            len1++;
            counterA = counterA.next;
        }
        while (counterB != null) {
            len2++;
            counterB = counterB.next;
        }
        // 头部对齐
        int x = Math.abs(len1 - len2);
        if (len1 > len2) {
            for (int i = 0; i < x; i++) {
                headA = headA.next;
            }
        }
        if (len2 > len1) {
            for (int i = 0; i < x; i++) {
                headB = headB.next;
            }
        }
        // 相遇则为起点
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

复杂链表的复制

class Solution {
    /* 使用HashMap存储旧节点对应新节点的映射，然后按照旧节点关系建立新节点的关系 */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        // 存储新旧节点映射关系
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        // 根据旧节点建立新节点件关系
        boolean first = true;
        Node res = null;
        while (head != null) {
            map.get(head).next = map.get(head.next);
            map.get(head).random = map.get(head.random);
            if (first) {
                res = map.get(head);
                first = false;
            }
            head  = head.next;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

合并两个有序链表

class Solution {
    /* 归并排序的mereg函数 */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                dummy.next = l1;
                l1 = l1.next;
            } else {
                dummy.next = l2;
                l2 = l2.next;
            }
            dummy = dummy.next;
        }
        if (l1 != null) {
            dummy.next = l1;
        }
        if (l2 != null) {
            dummy.next = l2;
        }
        return res.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

删除链表倒数第 k 个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        // 让fast节点比slow先走n步
        ListNode slow = head, fast = head;
        for (int i = 0; i < n; i++) {
            fast = (fast == null) ? null : fast.next;
        }
        // 删除倒数第N个节点
        ListNode pre = null;
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        // 判断是否删除的是头节点
        if (pre == null) {
            return head.next;
        }
        // 非头节点
        pre.next = slow.next;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int x = 0; // 进位
        // 1.双方都不为空都情况，累加并带上进位
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + x; // 考虑进位
            x = sum / 10; // 获取新的进位
            int val = sum % 10; // 获取新的节点值
            cur.next = new ListNode(val);
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        // 2.有一者为空的情况，只加上不为空的一方
        while (l1 != null) {
            int sum = l1.val + x;
            x = sum / 10;
            int val = sum % 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            int sum = l2.val + x;
            x = sum / 10;
            int val = sum % 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            l2 = l2.next;
        }
        // 3.最后判断是否发生溢出
        if (x == 1) {
            cur.next = new ListNode(1);
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

将有序链表转化为二叉搜索树

class Solution {
    /* 确定中间的节点作为根节点，不断地递归即可（类似于从前序和中序构造二叉树，不过这里直接从中序的中间节点取值） */
    public TreeNode sortedListToBST(ListNode head) {
        return helper(head);
    }
    private TreeNode helper(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        // 快慢指针确定中间节点以及中间节点前一个节点
        ListNode slow = head, fast = head, pre = null;
        while (slow != null && fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow即为根节点
        TreeNode root = new TreeNode(slow.val);
        // 获取到右区间
        ListNode right = slow.next;
        // 断链
        pre.next = null;
        slow.next = null;
        // 递归构建左右子树
        root.left = helper(head);
        root.right = helper(right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

栈

用两个栈实现队列

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>(); // 中转栈
        stack2 = new Stack<>(); // 值栈
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        move(stack2, stack1);
        stack1.push(x);
        move(stack1, stack2);
    }
    private void move(Stack<Integer> s1, Stack<Integer> s2) {
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        return stack2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack2.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

含有 getMin 的栈

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        // 更新minStack使得其栈头最小
        if (minStack.isEmpty() || !minStack.isEmpty() && x <= minStack.peek()) {
            minStack.push(x);
        }
    }
    
    public void pop() {
        int pop = stack.pop();
        // 如果弹出了当前最小值，删去minStack栈头
        if (pop == minStack.peek()) {
            minStack.pop();    
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

有效括号

class Solution {
    /* 使用栈来做匹配 */
    public boolean isValid(String s) {
        if ("".equals(s.trim())) {
            return true;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 左半括号直接入栈
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            }
            // 校验
            if (c == ')' || c == '}' || c == ']') {
                // 没有左括号可匹配或弹出不匹配返回falsea
                if (stack.isEmpty() || c != map.get(stack.pop())) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

下一个更大的元素

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 先使用单调栈获取到nums2中每个元素对应的下一个更大元素存储至HashMap中
        Stack<Integer> stack = new Stack<>(); // 由上之下递增
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                // 不满足单调栈
                map.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]);
        }
        // stack中剩下的即为找不到下一个更大元素的
        while (!stack.isEmpty()) {
            map.put(stack.pop(), -1);
        }
        // 遍历nums1，使用map获取对应元素的下一个更大元素
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

每日温度

class Solution {
    /* 使用单调栈来记录某个元素索引的下一个最大元素索引，之后相建减即为天数 */
    public int[] dailyTemperatures(int[] nums) {
        int[] res = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                // 不满足单调栈，弹出
                int index = stack.pop();
                // 计算天数
                res[index] = i - index;
            }
            // 满足单调栈结构
            stack.push(i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

验证栈序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int index = 0; // 当前匹配到的弹出序列位置
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            // 开始匹配
            while (!stack.isEmpty() && stack.peek() == popped[index]) {
                // 弹出以表示匹配
                stack.pop();
                // 索引++，表示匹配
                index++;
            }
        }
        // 匹配完则说明完全匹配
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最长有效括号

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其他

快速排序

public class QuickSort {
	//交换函数
    public static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    /**
     * 递归循环实现快排
     * @param arr 数组
     * @param startIndex 快排的开始下标
     * @param endIndex 快排的结束下标
     */
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if(arr != null && arr.length > 0) {
            int start = startIndex, end = endIndex;
            //target是本次循环要排序的元素，每次循环都是确定一个元素的排序位置，这个元素都是开始下标对应的元素
            int target = arr[startIndex];
            //开始循环，从两头往中间循环，相遇后循环结束
            while(start<end) {
                //从右向左循环比较，如果比target小，就和target交换位置，让所有比target小的元素到target的左边去
                while(start < end) {
                    if(arr[end] < target) {
                        swap(arr, start, end);
                        break;
                    }else {
                        end--;
                    }
                }

                //从左向右循环比较，如果比target大，就和target交换位置，让所有比target大的元素到target的右边去
                while(start < end) {
                    if(arr[start] > target) {
                        swap(arr, start, end);
                        break;
                    }else {
                        start++;
                    }
                }
            }
            //确定target的排序后，如果target左边还有元素，继续递归排序
            if((start-1)>startIndex) {
                quickSort(arr, startIndex, start-1);
            }
            //确定target的排序后，如果target右边还有元素，继续递归排序
            if((end+1)<endIndex) {
                quickSort(arr, end+1, endIndex);
            }
        }
    }
	//主函数
    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

SQL 排名排序

select s1.Score,
# 查询比s1.Score高的分数的去重数量，即为当前分数的排名
(select count(distinct s2.Score) from Scores s2 where s2.Score >= s1.Score) as Rank
from Scores s1
# 注意降序排序
order by s1.Score desc


# 第二种解法，MySQL 8之后可以使用窗口函数来统计排名，主要有RANK()/DENSE_RANK()/ROW_NUMBER()
select s1.Score, dense_rank(order by s1.Score DESC)  as Rank
from Score s1 
1
2
3
4
5
6
7
8
9
10
11

SQL 第二高的薪水

select 
# ifnull(xx, null)，当xx为null时，返回null
ifnull(
# 使用limit 1，1限制查找第1行开始的第一个数据，即第二高的排名
(select distinct e.Salary from Employee e order by e.Salary desc limit 1,1),
null)  
as SecondHighestSalary
1
2
3
4
5
6
7