24khandsome's Blog

24khandsome's Blog

leetcode100-2

发表于 更新于 分类于
leetcode热题100

图论

200. 岛屿数量

image-20240202092200947

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 int numIslands1(char[][] grid) {
    int result = 0;
    int r = grid.length;
    int c = grid[0].length;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if(grid[i][j] == '1'){
                ++ result;
                dfs(grid,i,j);
            }

        }
    }
    return result;
}

public void dfs(char[][] grid,int r,int c){
    if(r >= grid.length || c >= grid[0].length || r < 0 || c < 0){
        return;
    }
    if(grid[r][c] != '1'){
        //海洋或者已标记
        return;
    }
    //标记已访问
    grid[r][c] = '2';
    dfs(grid,r+1,c);
    dfs(grid,r-1,c);
    dfs(grid,r,c+1);
    dfs(grid,r,c-1);
}

994. 腐烂的橘子

image-20240202093311492

利用队列+宽度遍历

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
public int orangesRotting(int[][] grid) {
    int r = grid.length;
    int c = grid[0].length;
    int count = 0; // count 表示新鲜橘子的数量
    int round = 0; // round 表示腐烂的轮数，或者分钟数
    Queue<int[]> queue = new ArrayDeque<>();
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if(grid[i][j] == 2){
                queue.add(new int[]{i,j});
            }else if(grid[i][j] == 1){
                count++;
            }

        }
    }
    while(!queue.isEmpty() && count > 0){
        round++;
        int n = queue.size();
        for (int i = 0; i < n; i++) {
            int[] orange = queue.poll();
            int row = orange[0];
            int col = orange[1];

            for (int k = 0; k < 4; k++) {
                int x = row + dx[k];
                int y = col + dy[k];
                if(x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == 1){
                    grid[x][y] = 2;
                    count--;
                    queue.add(new int[]{x,y});
                }
            }
        }
    }
    if (count > 0) {
        return -1;
    } else {
        return round;
    }
}

207. 课程表

image-20240203133932264

image-20240203133917768

解法：有向图 +入度+队列+ 宽度优先遍历

思路：先学没有前置课程的课程，维护所有课程的入度（前置课程数），学完对应课程C1后，维护其他以C1为前置课程的课程的入度-1，利用队列存储入度为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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    //维护每个节点的入度，下标表示第index课程
    int[] indegrees = new int[numCourses];
    //维护每个课程的后置课程
    List<List<Integer>> outSides = new ArrayList<>();
    Queue<Integer> queue = new ArrayDeque<>();
    int visitCount = 0;
    for (int i = 0; i < numCourses; i++) {
        outSides.add(new ArrayList<>());
    }
    for (int[] prerequisite : prerequisites) {
        indegrees[prerequisite[0]]++;
        outSides.get(prerequisite[1]).add(prerequisite[0]);
    }

    for (int i = 0; i < indegrees.length; i++) {
        if(indegrees[i] == 0){
            queue.offer(i);
        }
    }
    while (!queue.isEmpty()){
        Integer pre = queue.poll();
        visitCount ++;
        for (Integer node : outSides.get(pre)) {
            indegrees[node]--;
            if(indegrees[node] == 0){
                queue.offer(node);
            }
        }
    }

    return visitCount == numCourses;
}

208. 实现 Trie (前缀树)

image-20240203163828876

解题思路：实现一种数据结构，能够像树形结构那样层层向下检索字符串的每个字符，且字符都是小写，告诉了我们下一个字母只有26种可能，且需要支持search功能，说明得直到是否包含某个字符串。

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
public class Trie {
    private Trie[] children;
    //当前单词是否为某个字符串的结束符
    private boolean isEnd;

    public Trie() {
        this.isEnd = false;
        //实际不存储char，Trie的下标来标识
        children = new Trie[26];
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int index = c - 'a';
            if(Objects.isNull(node.children[index])){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie trie = prefixWith(word);
        if(trie != null && trie.isEnd){
            return true;
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        return prefixWith(prefix) != null;
    }
    public Trie prefixWith(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if(node.children[index]!=null){
                node = node.children[index];
            }else{
                return null;
            }
        }
        return node;
    }
}

回溯

46. 全排列

image-20240204212627612

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
List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permute1(int[] nums) {
    Deque<Integer> path = new ArrayDeque<>();
    boolean[] visited = new boolean[nums.length];
    dfs2(nums, path, visited);
    return result;
}


private void dfs2(int[] nums, Deque<Integer> path, boolean[] visited) {
    if (nums.length == path.size()) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if(!visited[i]){
            Integer num = nums[i];
            visited[i] = true;
            path.push(num);
            dfs2(nums,path,visited);
            visited[i] = false;
            path.pop();
        }
    }
}

78. 子集

image-20240204224047558

解法一：迭代+遍历前一个结果集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> before = new ArrayList<>();
    result.add(before);
    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> copy = new ArrayList<>(result.get(i));
            copy.add(num);
            result.add(copy);
        }
    }
    return result;
}

解法二：回溯+满二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsets2(int[] nums) {
    Deque<Integer> path = new ArrayDeque<>(nums.length);
    dfs2(nums,0,path);
    return result;
}

private void dfs2(int[] nums, int i, Deque<Integer> path) {
    if(i >= nums.length){
        result.add(new ArrayList<>(path));
        return;
    }
    int num = nums[i];
    //不选num
    dfs2(nums,i+1,path);
    path.push(num);
    //选num
    dfs2(nums,i+1,path);
    path.pop();
}

17. 电话号码的字母组合

image-20240205215928856

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
Map<Character,String> map = new HashMap<>();


/**
 * 递归+回溯+深度优先
 * @param digits
 * @return
 */
public List<String> letterCombinations1(String digits) {
    map.put('2',"abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
    List<String> result = new ArrayList<>();
    Deque<String> path = new ArrayDeque<>();
    char[] chars = digits.toCharArray();
    if(null == digits || digits.length() == 0){
        return result;
    }
    dfs(chars,0,result,path);
    return result;
}

private void dfs(char[] chars, int i, List<String> result, Deque<String> path) {
    if(i == chars.length){
        result.add(String.join("", path));
        return;
    }
    char aChar = chars[i];
    String mapStr = map.get(aChar);
    for (Character s : mapStr.toCharArray()) {
        path.addLast(s+"");
        dfs(chars,i+1,result,path);
        path.removeLast();
    }
}

39. 组合总和

image-20240205224606093

image-20240205224644462

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
/**
 * 回溯算法 + 剪枝
 * @param candidates
 * @param target
 * @return
 */
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(candidates,0,path,result,target);
    return result;
}

private boolean dfs(int[] candidates, int i, List<Integer> path, List<List<Integer>> result,int target) {
    if(target <= 0){
        if(target == 0){
            result.add(new ArrayList<>(path));
        }
        return true;
    }
    //j = i去除重复组合
    for (int j = i; j < candidates.length; j++) {
        int num = candidates[j];
        path.add(num);
        boolean breakFlag = dfs(candidates, j, path, result, target - num);
        path.remove(path.size()-1);
        if(breakFlag){
            break;
        }

    }
    return false;
}

22. 括号生成

image-20240207105648586

简单递归|回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
List<String> result = new ArrayList<>();
public List<String> generateParenthesis1(int n) {
    dfs2("",n,n);
    return result;
}

private void dfs2(String s, int leftN, int rightN) {
    if(leftN == 0 && rightN == 0){
        result.add(s);
    }
    if(leftN > 0){
        dfs2(s+"(",leftN-1,rightN);
    }
    if(leftN < rightN){
        dfs2(s+")",leftN,rightN-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
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    path.add("(");
    dfs(result,path,n-1,n);
    return result;
}

private void dfs(List<String> result,List<String> path,int leftN,int rightN){
    if(leftN == 0 && rightN == 0){
        result.add(String.join("",path));
        return;
    }

    if(leftN > 0){
        path.add("(");
        dfs(result,path,leftN-1,rightN);
        path.remove(path.size()-1);
    }
    if(rightN > 0 && leftN < rightN){
        path.add(")");;
        dfs(result,path,leftN,rightN-1);
        path.remove(path.size()-1);
    }
}

79. 单词搜索

image-20240207145336206

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
public boolean exist(char[][] board, String word) {
    boolean[][] used = new boolean[board.length][board[0].length];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if(dfs(board,i,j,word,0,used)){
                return true;
            }
        }
    }
    return false;
}

private boolean dfs(char[][] board, int row, int col, String word, int i,boolean[][] used) {
    if(i == word.length()){
        return true;
    }
    char c = word.charAt(i);
    if(0 <= row && row < board.length && 0 <= col && col < board[0].length
            && c == board[row][col] && !used[row][col] ){
        used[row][col] = true;
        System.out.println(row + "," + col + ":" +board[row][col]);
        boolean dfs1 = dfs(board, row + 1, col, word, i + 1, used);
        boolean dfs2 = dfs(board, row - 1, col, word, i + 1, used);
        boolean dfs3 = dfs(board, row, col + 1, word, i + 1, used);
        boolean dfs4 = dfs(board, row, col - 1, word, i + 1, used);
        used[row][col] = false;
        return dfs1 || dfs2 || dfs3 || dfs4;
    }
    return false;
}

131. 分割回文串

image-20240207163710805

解题思路：想象成树形截取，从截取1个字符，到全部截取，递归调用；截取时判断，截取的字符串是否回文，直至所有字符截取完毕，则收集一路上截取的字符串组合，即为某种结果；搜集所有结果

image-20240207164144797

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
public class A_6_131 {
    private boolean[][] flag;
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        flag = new boolean[s.length()][s.length()];
        //利用动态规划，回文的规则：左右两边相等 且左右边界各自-1也是回文串时，[j,i]也是回文
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || flag[j+1][i-1])){
                    flag[j][i] = true;
                }
            }
        }
        dfs(result,path,s,0);
        return result;
    }

    private void dfs(List<List<String>> result, Deque<String> path,String s, int i) {
        if(i == s.length()){
            result.add(new ArrayList<>(path));
        }
        for (int j = i; j < s.length(); j++) {
            String sub = s.substring(i,j+1);
            //  if(isPalindrome(sub)){
            if(flag[i][j]){
                path.addLast(sub);
                dfs(result,path,s,j+1);
                path.removeLast();
            }
        }
    }

    private boolean isPalindrome(String str) {
        for (int i = 0,j = str.length()-1; i <= j; i++,j--) {
            if(str.charAt(i) != str.charAt(j)){
                return false;
            }
        }
        return true;
    }

}

51. N 皇后

image-20240209151752517

题解：

​ 递归回溯思路，假设每次递归处理一行节点，从第一行开始处理到最后一行。递归下钻时，记录已经失效的节点，通过观察col[]记录皇后列，其中斜向下x-y+n固定的数组sub[]，斜向上x+y固定的数组sum[]来标记皇后斜向的情况。

image-20240209152330375

image-20240209152344361

二叉搜索

35. 搜索插入位置

image-20240214131356086

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 int searchInsert(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l <= r){
        int mid = (l+r) >> 1;
        if(nums[mid] == target){
            return mid;
        }
        if(nums[mid] > target){
            r = mid - 1;

        }else{
            l = mid + 1;
        }
    }
    return l;
    //        return binarySearch(nums,target,0,nums.length-1);
}

private int binarySearch(int[] nums, int target, int left, int right) {
    if(right < left){
        return left;
    }
    int mid = (left + right) >> 1;
    if(nums[mid] == target){
        return mid;
    }else if(nums[mid] < target){
        return binarySearch(nums,target,mid+1,right);
    }else{
        return binarySearch(nums,target,left,mid-1);
    }
}

74. 搜索二维矩阵

image-20240214214156606

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null){
        return false;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    int l = 0;
    int r = m*n-1;
    while(l <= r){
        int mid = (l+r) >> 1;
        int x = mid / n;
        int y = mid % n;
        if(matrix[x][y] == target){
            return true;
        }else if(matrix[x][y] > target){
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    return false;
}

34. 在排序数组中查找元素的第一个和最后一个位置

image-20240214214641674

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
/**
 * 1、找出=target的任意下标
 * 2、根据这个下标向左右扩展
 * @param nums
 * @param target
 * @return
 */
public int[] searchRange2(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l <= r){
        int mid = (l+r) >> 1;
        if(nums[mid] == target){
            l = r = mid;
            while(l > 0 && nums[l-1] == target){
                l--;
            }
            while(r < nums.length-1 && nums[r+1] == target){
                r++;
            }
            return new int[]{l,r};
        }
        if(nums[mid] > target){
            r = mid - 1;

        }else{
            l = mid + 1;
        }
    }
    return new int[]{-1,-1};
}

34. 在排序数组中查找元素的第一个和最后一个位置

image-20240217102733977

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
/**
 * 1、找出=target的任意下标
 * 2、根据这个下标向左右扩展
 * @param nums
 * @param target
 * @return
 */
public int[] searchRange2(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l <= r){
        int mid = (l+r) >> 1;
        if(nums[mid] == target){
            l = r = mid;
            while(l > 0 && nums[l-1] == target){
                l--;
            }
            while(r < nums.length-1 && nums[r+1] == target){
                r++;
            }
            return new int[]{l,r};
        }
        if(nums[mid] > target){
            r = mid - 1;

        }else{
            l = mid + 1;
        }
    }
    return new int[]{-1,-1};
}

33. 搜索旋转排序数组

image-20240217104118616

解题思路：

​ 中点mid的取值有2种可能，midValue >= lValue，或者mid < lValue，每种场景都存在某种场景：target落在单调递增的那一段，比如图一的 left < target < mid，图二的mid < target < right，这2种场景时，直接取区间内的那一半范围即可，否则取另一半。

image-20240217104340009

image-20240217104638071

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 int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l <= r){
        if(nums[l] == target){
            return l;
        }
        if(nums[r] == target){
            return r;
        }
        int mid = (l+r) >> 1;
        if(nums[mid] == target){
            return mid;
        }

        if(nums[mid] >= nums[l]){
            if(nums[l] < target && target < nums[mid]){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }else{
            if(target > nums[mid] && target < nums[r]){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
    }
    return -1;
}

153. 寻找旋转排序数组中的最小值

image-20240217110923239

解题思路：最小值初始为左右值的较小值，取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
public class A5_153 {
    public int findMin(int[] nums) {
        int min = -1;
        int l = 0;
        int r = nums.length-1;
        if(nums.length==0){
            return min;
        }
        if(nums.length == 1){
            return nums[0];
        }
        min = Math.min(nums[l],nums[r]);
        while(l <= r){
            int mid = (l+r) >> 1;
            if(nums[mid] >= nums[0]){
                //0,mid还是递增的,最小值一定出现在非递增区间，所以只需查找非递增区间
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            min = Math.min(nums[mid],min);
        }
        return min;
    }
}

4. 寻找两个正序数组的中位数

image-20240217114207215

解题思路：转化成查找整个m+n数组中第k个数的问题，分别比较查找数组m、n的第k/2个数，排除k/2个数后重复这个过程

image-20240217114850201

image-20240217114923550

image-20240217114944802

image-20240217115018598

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
/**
 * 利用寻找第k小的数原理
 * num1,num2分别比较第k/2的数,排除前k/2个数
 * @param nums1
 * @param nums2
 * @return
 */
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k
    int left = (m + n + 1) >> 1;
    int right = (m + n + 2) >> 1;
    
    return 0.5 * (getKthMin(nums1,0,m-1,nums2,0,n-1,left) +  getKthMin(nums1,0,m-1,nums2,0,n-1,right));

}

private double getKthMin(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;
    //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
    if(len1 > len2){
        return getKthMin(nums2,start2,end2,nums1,start1,end1,k);
    }
    if(len1 == 0){
        return nums2[start2+k-1];
    }
    if(k == 1){
        return Math.min(nums1[start1],nums2[start2]);
    }
    int kStep1 = Math.min(len1, k / 2);
    int kStep2 = Math.min(len2, k / 2);
    int i = start1 + kStep1 - 1;
    int j = start2 + kStep2 - 1;
    if(nums1[i] <= nums2[j]){
        return getKthMin(nums1,i+1,end1, nums2,start2,end2,k- kStep1);
    }else{
        return getKthMin(nums1,start1,end1, nums2,j+1,end2,k- kStep2);
    }
}

栈

20. 有效的括号

image-20240220185219528

思路：利用map保存对应{}的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isValid(String s) {
    if(s == null || s.length() < 2){
        return false;
    }
    Map<Character,Character> map = new HashMap<>();
    map.put('(',')');
    map.put('{','}');
    map.put('[',']');
    Deque<Character> stack = new ArrayDeque<>();
    char[] chars = s.toCharArray();
    for(char aChar : chars){
        Character before = stack.peek();
        if(map.containsKey(aChar)){
            stack.push(aChar);
        }else if(null != map.get(before) && aChar == map.get(before)){
            stack.pop();
        }else{
            return false;
        }

    }
    return stack.isEmpty();
}

155. 最小栈

image-20240220192431193

解法一：利用链表+链表元素插入时设置当前链表的最小值

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 A2_155 {
    public class Node{
        Integer val;
        Integer min;
        Node next;
        public Node(Integer val) {
            this.val = val;
        }
        public Node(Integer val, Integer min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
    private Node head;
    public void push(int val) {
        if(null == head){
            head = new Node(val,val,null);
        }else {
            head = new Node(val,Math.min(val, head.min), head);
        }
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.min;
    }
}

解法二：利用辅助栈，存储最小值

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 A2_155_2 {
    private Deque<Integer> oriQueue = new ArrayDeque();
    private Deque<Integer> minQueue = new ArrayDeque();
    public void push(int val) {
        oriQueue.push(val);
        if(minQueue.isEmpty()){
            minQueue.push(val);
        }else if(minQueue.peek() >= val){
            minQueue.push(val);
        }
    }
    public void pop() {
        Integer pop = oriQueue.pop();
        if(minQueue.peek().equals(pop)){
            minQueue.pop();
        }
    }

    public int top() {
        return oriQueue.peek();
    }

    public int getMin() {
        return minQueue.peek();
    }
}

394. 字符串解码

image-20240220194453163

解题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
public String decodeString(String s) {
    String result = "";
    String left = "[";
    String right = "]";
    Deque<String> stack = new ArrayDeque<>();
    char[] chars = s.toCharArray();
    for(char aChar : chars){
        if(!right.equals(aChar+"")){
            stack.push(aChar+"");
        }else{
            //step 1: 取出[] 内的字符串
            String copy = "";
            while(!left.equals(stack.peek())){
                copy = stack.pop() + copy;
            }
            //弹出[
            stack.pop();
            //step 2: 获取倍数数字
            String numStr = "";
            //弹出数字
            while(null != stack.peek() && stack.peek().length()==1 && '0' <= stack.peek().charAt(0) && stack.peek().charAt(0) <=
                    '9' ){
                numStr = stack.pop() + numStr;
            }
            int count = Integer.parseInt(numStr);
            String resultCopy = "";
            for (int i = 0; i < count; i++) {
                resultCopy += copy;
            }
            stack.push(resultCopy);
        }
    }
    while(!stack.isEmpty()){
        result = stack.pop() + result;
    }
   return result;
}

解题2：利用递归：解析字符串，先解析数字，遇到[下标begin，使用应用计数法往右找对应的]end，递归解析原字符串的subString(begin+1,end)

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 String decodeString1(String str) {
    if (!str.contains("[")) {
        return str;
    }
    StringBuilder sb = new StringBuilder();
    int index = 0;
    while (index < str.length()) {
        char c = str.charAt(index);
        index++;
        if (Character.isLetter(c)) {
            sb.append(c);
        } else if (Character.isDigit(c)) {
            // 提取完整的数字(可能会有多位)
            int num = c - '0';
            while (Character.isDigit(str.charAt(index))) { // 前面已经++过了
                num = num * 10 + str.charAt(index) - '0';
                index++;
            }
            // 数字之后必是左括号
            int leftNum = 0; // 使用引用计数的方式，匹配左右括号，0即表示匹配完毕
            int startIndex = index; // 记录左括号的位置
            do {
                if (str.charAt(index) == '[') leftNum++;
                else if (str.charAt(index) == ']') leftNum--;
                index++;
            } while (leftNum != 0);
            // 括号内部的字符串递归调用计算
            String resStr = decodeString(str.substring(startIndex + 1, index - 1));
            // 计算结果重复n次
            for (int i = 0; i < num; i++) {
                sb.append(resStr);
            }
        }
    }
    return sb.toString();
}

739. 每日温度

image-20240221192915747

解题1：单调递减栈

1
2
3
4
5
6
7
8
9
10
11
12
public int[] dailyTemperatures2(int[] temperatures) {
    Deque<Integer> stack = new ArrayDeque<>();
    int[] result = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        int temperature = temperatures[i];
        while(!stack.isEmpty() && temperature > temperatures[stack.peek()]){
            result[stack.peek()] = i - stack.pop();
        }
        stack.push(i);
    }
    return result;
}

题解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
/**
 * 从右到左
 * 暴力破解，时间复杂度O(n*n)
 * @param T
 * @return
 */
public int[] dailyTemperatures(int[] T) {
    int length = T.length;
    int[] result = new int[length];

    for (int i = length-2; i >= 0; i--) {
        // j = j + result[j],跳过重复比对
        for (int j = i+1; j < length; j = j + result[j]) {
            if(T[j] > T[i]){
                result[i] = j-i;
                break;
            }else if(result[j] == 0){
                //T[j] <= T[i],j后面都没有比i大的数了
                result[i] = 0;
                break;
            }
            //其他场景，继续遍历
        }
    }

    return result;
}

84. 柱状图中最大的矩形

image-20240221194745083

题解一：暴力破解

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
/**
 * 暴力破解
 * @param heights
 * @return
 */
public int largestRectangleArea1(int[] heights) {
    if(heights.length == 1){
        return heights[0];
    }
    int area = 0;
    int length = heights.length;
    for (int i = 0; i < length; i++) {
        int height = heights[i];
        int width = 1;
        int left = i;
        int right = i;
        while(left-1 >= 0 && heights[left-1] >= height){
            left--;
        }
        while(right+1 <length && heights[right+1] >= height){
            right++;
        }
        width = right - left + 1;
        area = Math.max(area,width * height);
    }
    return area;
}

题解二：单调栈 + 哨兵：从暴力破解中发现规律，需要寻找当前下边往左和往右第一个小于自己的值，单调递增栈能保证栈顶的下一个元素为左边第一个小于自己的元素，

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
/**
     * 单调栈 + 哨兵
     * @param heights
     * @return
     */
public int largestRectangleArea(int[] heights) {
    int area = 0;
    int length = heights.length;
    if(length == 0){
        return area;
    }
    if(length == 1){
        return heights[0];
    }
    int[] newHeights = new int[length + 2];
    for (int i = 0; i < length; i++) {
        newHeights[i+1] = heights[i];
    }
    heights = newHeights;
    length = length + 2;
    //单调递增栈
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    //加入哨兵后，循环无需判空
    for (int i = 1; i < length; i++) {
        while (heights[i] < heights[stack.peek()]){
            Integer currentIndex = stack.pop();
            //向左过程中也没必要判断是否相等，因为宽= i - index - 1;已经包含该场景
            //                while(heights[currentIndex] == heights[stack.peek()]){
            //                    //向左找，与当前一样大时，也左移，否则必然比当前值小
            //                    stack.pop();
            //                }
            int currentHeight = heights[currentIndex];
            int width = i - stack.peek() - 1;
            area = Math.max(area,width * currentHeight);
        }
        stack.push(i);
    }
    return area;
}

堆

215. 数组中的第K个最大元素

image-20240222082944791

题解一：提到了O（n）的时间复杂度，且限制-1w<= nums[i] <= 1w，可以使用桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] buckets = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            k = k - buckets[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
}

题解二：维护大小为K的小顶堆，一旦对容量超过K，移除堆顶元素，最终的堆顶元素即为第K大元素。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 利用小顶堆
 * 时间复杂度 O(nlogK)
 * 空间复杂度:O(k)
 * 调整堆时间复杂度:O(logK)
 * @param nums
 * @param k
 * @return
 */
public int findKthLargest1(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<Integer>();
    for (int num : nums) {
        heap.add(num);
        if(heap.size() > k){
            heap.poll();
        }
    }
    return heap.peek();
}

347. 前 K 个高频元素

image-20240223081713904

解题一：利用小顶堆，维护大小为k的高频元素堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * hash + priorityQueue
 * @param nums
 * @param k
 * @return
 */
public int[] topKFrequent1(int[] nums,int k) {
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
    }
    PriorityQueue<int[]> queue = new PriorityQueue<>((e1,e2) -> e1[1] - e2[1]);
    for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        queue.add(new int[]{entry.getKey(),entry.getValue()});
        if(queue.size() > k){
            queue.poll();
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
       result[i] = queue.poll()[0];
    }
    return result;
}

题解二：桶排序

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 int[] topKFrequent2(int[] nums, int k) {
    List<Integer> res = new ArrayList();
    // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
    HashMap<Integer,Integer> map = new HashMap();
    for(int num : nums){
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }

    //桶排序
    //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
    List<Integer>[] list = new List[nums.length+1];
    for(int key : map.keySet()){
        // 获取出现的次数作为下标
        int i = map.get(key);
        if(list[i] == null){
            list[i] = new ArrayList();
        }
        list[i].add(key);
    }

    // 倒序遍历数组获取出现顺序从大到小的排列
    for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
        if(list[i] == null) continue;
        res.addAll(list[i]);
    }
    return res.stream().mapToInt(Integer::intValue).toArray();
}

295. 数据流的中位数

image-20240223091145464

题解：维护大+小顶堆，小顶堆数量 >= 大顶堆，2个堆数量的绝对值 < 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
PriorityQueue<Integer> queMin;
PriorityQueue<Integer> queMax;
public MedianFinder() {
    //大顶堆  小于等于中位数的数
    queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
    //小顶堆  记录大于中位数的数
    queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
}

public void addNum(int num) {
    if(queMin.isEmpty()){
        queMin.add(num);

    }else if(queMin.peek() <= num){
        queMax.add(num);
        //重平衡
        if(queMax.size() > queMin.size()){
            queMin.add(queMax.poll());
        }
    }else{
        queMin.add(num);
        //重平衡
        if(queMin.size() > queMax.size() + 1){
            queMax.add(queMin.poll());
        }

    }
}

public double findMedian() {
    //小顶堆数量 > 大顶堆数量：元素个数为奇数，取小顶堆堆顶
    //小顶堆数量 = 大顶堆数量：元素个数为偶数，取大小顶堆堆顶 / 2
    if(queMin.size() > queMax.size()){
        return queMin.peek();
    }else{
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}
}

贪心算法

121. 买卖股票的最佳时机

image-20240224165649724

题解：在遍历过程中，记录最低的股票买入价格，一遍遍历计算出max（当前价格-当前最底价格）

1
2
3
4
5
6
7
8
9
10
11
public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int profit = 0;
    for (int i = 0; i < prices.length; i++) {
        int price = prices[i];
        minPrice = Math.min(minPrice, price);
        profit = Math.max(price-minPrice,profit);

    }
    return profit;
}

55. 跳跃游戏

image-20240224202723250

题解：遍历时，维护一个当前可走至的最远下标，直到latestIndex >= nums.length - 1，表示可达最后一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 可达最远的地方
 * @param nums
 * @return
 */
public boolean canJump(int[] nums) {
    if(nums.length == 0 || nums.length == 1){
        return true;
    }
    int reach = 0;
    int size = nums.length;
    //i 达不到 >reache 的位置，,提前结束
    //reach >= size -1 ,提前结束
    for (int i = 0; i <= reach && reach < size -1; i++) {
        reach = Math.max(i + nums[i],reach);
    }
    return reach >= nums.length -1;
}

45. 跳跃游戏 II

image-20240224205522507

题解：在当前位置i，可走arr[i] = step步，贪心的走[1，step]中第j步可走最远，则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
/**
 * 如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
 * 例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。
 * 从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4
 *
 * @param nums
 * @return
 */
public int jump(int[] nums) {
    int length = nums.length;
    //目前右边可达最大范围
    int rightIndex = 0;
    int nextIndex = 0;
    int jump= 0;
    for (int i = 0; i < length - 1;) {
        //step 本步可以行走的范围
        int step = nums[i];
        if(i + step >= length-1){
            return jump + 1;
        }
        for (int j = i + 1; j <= i + step; j++) {
            // nextStep 在本步范围内，每一步的下一步步长
            int nextStep = nums[j];
            //j + nextStep 用来比较走到从i 走到 j时，j能走到的最远距离
            if(j + nextStep > rightIndex){
                rightIndex = j + nextStep;
                nextIndex = j;
            }
        }
        //跳到能够到达最远的下标
        i = nextIndex;
        jump++;

    }
    return jump;
}

763. 划分字母区间

image-20240224211122841

题解：维护一个int[26]，存储每个字母最后出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> partitionLabels(String s) {
    List<Integer> result = new ArrayList<>();
    char[] chars = s.toCharArray();
    int[] endData = new int[26];
    for (int i = 0; i < chars.length; i++) {
        char c = chars[i];
        endData[c - 'a'] = i;
    }

    int begin,end;
    begin = end = 0;
    for (int i = 0; i < chars.length; i++) {
        end = Math.max(end,endData[chars[i] - 'a']);
        //关键的一步，i走到end时，表示到达某一段的终点
        if(i == end){
            result.add(end - begin + 1);
            begin = end + 1;

        }
    }
    return result;
}

动态规划

70. 爬楼梯

image-20240413222738977

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 int climbStairs(int n) {
    int pre = 1;
    int ppre = 1;
    if(n == 0 || n == 1){
        return 1;
    }
    int cur = 1;
    for (int i = 2; i <= n; i++) {
        ppre = pre;
        pre = cur;
        cur = ppre + pre;
    }
    return cur;

}

Map<Integer,Integer> dataMap = new HashMap<>();
public int climbStairs1(int n) {
    return f(n);

}
//动态规划+记忆化搜索
private int f(int n) {
    if(n == 1 || n == 0){
        return 1;
    }
    if(dataMap.containsKey(n)){
        return dataMap.get(n);
    }
    int result = f(n - 1) + f(n - 2);
    dataMap.put(n,result);
    return result;
}

118. 杨辉三角

image-20240413223600193

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
/**
     * 递归公式 result[i][j] = result[i-1][j-1] + result[i-1][j]
     * 边界：i==0时，输出[1],j==0或者j==i时,值=1
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if(numRows <= 0){
            return result;
        }
        for (int i = 0; i < numRows; i++) {
            List<Integer> data = new ArrayList<>(i+1);
            for (int j = 0; j <= i; j++) {
                if(j==0 || j==i){
                    data.add(1);
                    continue;
                }
                List<Integer> preRowData = result.get(i-1);
                data.add(preRowData.get(j-1) + preRowData.get(j));
            }
            result.add(data);
        }
        return result;
    }

279. 完全平方数

image-20240418195305821

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 递归转化公式:f[i] = min(f[i-j*j] + 1)
 * 边界条件：f[0] = 0,当 j = 根号i;
 * @param n
 * @return
 */
public int numSquares(int n) {
    int[] result = new int[n+1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        for (int j = 1; j*j <= i; j++) {
            min = Math.min(min,result[i-j*j]);
        }
        result[i] = min + 1;
    }
    return result[n];
}

322. 零钱兑换

image-20240423195720003

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 转化方程：dp[i] = dp[i-coins[j]] + 1, 0 <= j <= coins.length
 * @param coins 
 * @param amount
 * @return
 */
public int coinChange(int[] coins, int amount) {
    if(amount == 0){
        return 0;
    }
    int[] data = new int[amount+1];
    for (int i = 1; i <= amount; i++) {
        data[i] = Integer.MAX_VALUE;;
    }
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if(coins[j] <= i && data[i-coins[j]] != Integer.MAX_VALUE){
                data[i] = Math.min(data[i],data[i-coins[j]]+1);
            }

        }
    }
    return data[amount] == Integer.MAX_VALUE?-1:data[amount];
}

139. 单词拆分

image-20240804224541360

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 动态规划 + 记忆化搜索：内循环取决于i的长度
 * 转移方程:dp[i] = dp[j] && wordDict.contains(s.subString(j,i))
 * @param s
 * @param wordDict
 * @return
 */
public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<String> wordDictSet = new HashSet<>(wordDict);
    boolean[] result = new boolean[s.length()+1];
    result[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (result[j] && wordDictSet.contains(s.substring(j, i))) {
                result[i] = true;
                break;
            }
        }
    }
    return result[s.length()];
}

152. 乘积最大子数组

image-20240423210509222

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 整理区分正数负数
 * dpMax[i],dpMin[i]分别表示以第i位为结尾的连续子序列的最大和最小乘机
 * nums[i]是正数时，我们期望前积最大，是负数时，我们期望前积最小，负负得正
 * dpMax[i] = Math.max(nums[i],dpMax[i-1]*nums[i],dpMin[i-1]*nums[i])
 * dpMin[i] = Math.max(nums[i],dpMax[i-1]*nums[i],dpMin[i-1]*nums[i])
 * result = max dpMax[i];
 * @param nums
 * @return
 */
public int maxProduct(int[] nums) {
    int[] maxData = new int[nums.length];
    int[] minData = new int[nums.length];
    maxData[0] = nums[0];
    minData[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxData[i] = Math.max(nums[i],Math.max(nums[i] * maxData[i-1],nums[i] * minData[i-1]));
        minData[i] = Math.min(nums[i],Math.min(nums[i] * maxData[i-1],nums[i] * minData[i-1]));
        max = Math.max(maxData[i],max);
    }
    return max;
}

416. 分割等和子集

image-20240424205325881

1
2
3
4
背包问题：转化问题为：给定一个只包含正整数的非空数组 nums，判断是否可以从数组中选出一些数字，
使得这些数字的和等于整个数组的元素和的一半
boolean [][]的dp[i][j] 表示在nums数组0-i的范围内，能否选出和为j的数字集合
则dp[i][j] = dp[i-1][j] 或者 dp[i-1][j-nums[i]]，即对于当前数字nums[i]选或者不选的结果，其中dp[i][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
public boolean canPartition1(int[] nums) {
       int len = nums.length;
       int sum = 0;
       for (int i = 0; i < len; i++) {
           sum+=nums[i];
       }
       if((sum & 1) == 1 ){
           return false;
       }
       int target = sum / 2;
       boolean[][] dp = new boolean[len][target+1];
       //初始化第一行，第一列
       for (int i = 0; i < len; i++) {
           dp[i][0] = true;
       }
       if(nums[0] <= target){
           dp[0][nums[0]] = true;
       }
       for (int i = 1; i < len; i++) {
           for (int j = 1; j <= target; j++) {
               dp[i][j] = dp[i-1][j];
               if(nums[i] <= j){
                   dp[i][j] = dp[i][j] || dp[i-1][j-nums[i]];
               }
           }
           if(dp[i][target]){
               return true;
           }
       }
       return dp[len-1][target];
   }

32. 最长有效括号

image-20240425202747943

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
/**
 * int[i] 表示以第i为为结尾的最长有效括号的长度
 * 只有当s.charAt(i)==')'时,字符才有效，此时
 * 1、s.charAt(i-1)=='(',[i-1,i]凑成一对，dp[i] = dp[i-2] + 2
 * 2、s.charAt(i-1)==')',如果s.charAt(i-1-dp[i-1])=='(',则[i-1-dp[i-1],i]有效，dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]]
 * 3、其他场景，默认dp[i] = 0;
 * @param s
 * @return
 */
public int longestValidParentheses(String s) {
    if(s.length() < 2){
        return 0;
    }
    int length = s.length();
    int[] dp = new int[length];
    int max = 0;
    for (int i = 1; i < length; i++) {
        if(s.charAt(i) == ')'){
            if(s.charAt(i-1) == '('){
                dp[i] = 2 + (i>=2?dp[i-2]:0);
            }
            if(s.charAt(i-1) == ')'){
                if(i-1-dp[i-1] >= 0 && s.charAt(i-1-dp[i-1]) == '('){
                    dp[i] = 2 + dp[i-1] + ((i-2-dp[i-1]>=0)?dp[i-2-dp[i-1]]:0);
                }
            }
            max = Math.max(max,dp[i]);
        }
    }
    return max;
}

多维动态规划

62. 不同路径

image-20240425205817866

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 int uniquePaths1(int m,int n){
    int[][] data = new int[m][n];
    data[0][0] = 1;
    for(int i = 0;i < m;i++){
        data[i][0] = 1;
    }
    for(int i = 0;i < n;i++){
        data[0][i] = 1;
    }

    for(int i = 1;i < m;i++){
        for(int j = 1;j < n;j++){
            data[i][j] = data[i][j - 1] + data[i - 1][j];
        }

    }
    return  data[m-1][n-1];
}

/**
 * M * N 从[0，0]到 [m-1,n-1]需要走m-1+n-1=m+n-2步，在其中选n-1向右走，转化为排列组合C(m+n-2,n-1)
 * @param m
 * @param n
 * @return
 */
public int uniquePaths(int m, int n) {
    long ans = 1;
    for (int x = n, y = 1; y < m; ++x, ++y) {
        ans = ans * x / y;
    }
    return (int) ans;
}

64. 最小路径和

image-20240428000233033

1
2
3
4
5
6
7
8
9
10
11
12
5. 最长回文子串public int minPathSum(int[][] grid) {
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if(i == 0 && j == 0) continue;
            else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
            else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
            else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
        }

    }
    return grid[grid.length-1][grid[0].length-1];
}

5. 最长回文子串

image-20240428000348203

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
/**
 * 暴力破解
 * @param s
 * @return
 */
public String longestPalindrome(String s) {
    String cut = "";
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        String temp = s.substring(i,i+1);
        for (int j = chars.length; j >= i ; j--) {
            String substring = s.substring(i, j);
            if(isLongestPalindrome(substring)){
                temp = substring;
                if(temp.length() > cut.length()){
                    cut = temp;
                }
                break;
            }
        }
    }
    return cut;
}

private boolean isLongestPalindrome(String str) {
    for (int i = 0,j = str.length()-1; i <= j; i++,j--) {
        if(str.charAt(i) != str.charAt(j)){
            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
45
46
47
48
49
/**
 * 动态规划
 * boolean[][]dp,dp[j][i]表示字符s中，下标j到i的子串是否是回文字符串
 * dp[j][i] == {
 *     if j == i,true
 *     if Sj == Si,{
 *         if(i-j==1){
 *             true,相邻
 *         }
 *         if(dp[j+1][i-1]){
 *             true;
 *         }
 *     }
 *
 * }
 * @param s
 * @return
 */
public String longestPalindrome1(String s) {
    String result = "";
    int length = s.length();
    boolean [][] dp = new boolean[length][length];
    for (int i = 0; i < length; i++) {
        char charI = s.charAt(i);
        for (int j = i; j >= 0 ; j--) {
            if(i-j == 0){
                dp[j][i] = true;
            }else{
                if(charI == s.charAt(j)){
                    if(i-j==1){
                        //j,i相邻
                        dp[j][i] = true;

                    }else{
                        //状态转移
                        dp[j][i] = dp[j+1][i-1];
                    }

                }

            }

            if(dp[j][i]){
                result = i-j+1 > result.length()?s.substring(j,i+1):result;
            }
        }
    }
    return result;
}

1143. 最长公共子序列

image-20240428001134941

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    //dp[i][j] 表示text1[0,i],text2[0,j]范围内的最长公共子序列长度
    int[][] dp = new int[m + 1][n + 1];
    //从1开始，默认dp[0][j],dp[i][0]=0
    for (int i = 1; i <= m; i++) {
        char c1 = text1.charAt(i - 1);
        for (int j = 1; j <= n; j++) {
            char c2 = text2.charAt(j - 1);
            //转化方程
            if (c1 == c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

72. 编辑距离

image-20240430091704621

编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法

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[i][j]表示word1[0,i],word2[0,j]的转化最少操作数
 * 1、word1.charAt(i) == word2.charAt[j]时,无需交换dp[i][j] = dp[i-1][j-1]
 * 2、否则,以word1[i]为基准，新增、删除、替换操作后得到word2[j],dp[i][j] = min(dp[i-1][j] 或 dp[i][j-1] 或 dp[i-1][j-1]) + 1
  * @param word1
 * @param word2
 * @return
 */
public int minDistance1(String word1, String word2) {
    int length1 = word1.length();
    int length2 = word2.length();
    int[][] dp = new int[length1+1][length2+1];
    for (int i = 1; i <= length1; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= length2; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= length1; i++) {
        for (int j = 1; j <= length2; j++) {
            if(word1.charAt(i-1) == word2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1];
            }else {
                dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j])) + 1;
            }

        }

    }
    return dp[length1][length2];
}

技巧

136. 只出现一次的数字

image-20240430220847183

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 int singleNumber1(int[] nums) {
    boolean[] dataArr = new boolean[60000];
    for (int i = 0; i < nums.length; i++) {
        dataArr[30000+nums[i]] = !dataArr[30000+nums[i]];
    }
    for (int i = 0; i < dataArr.length; i++) {
        if(dataArr[i]){
            return i - 30000;
        }
    }

    return 0;

}

/**
 * 方法二
 * a ^ a = 0,a ^ 0 = a => a^b^b^c^c = a ^ 0 ^0 = a
 * @param nums
 * @return
 */
public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        result ^= nums[i];
    }



    return result;

}

169. 多数元素

image-20240430221013146

1
2
3
4
5
6
7
8
9
10
11
12
public int majorityElement(int[] nums) {
    Map<Integer,Integer> data = new HashMap<>();
    int length = nums.length;
    for (int i = 0; i < length; i++) {
        int times = data.getOrDefault(nums[i], 0) + 1;
        data.put(nums[i], times);
        if(times > length / 2){
            return nums[i];
        }
    }
    return 0;
}

摩尔投票法： 核心理念为票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1)，为本题的最佳解法。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 1、遍历数组时，假设vote=0时，认为下一个读到的数X是众数，如果接下来遍历时遇到=x的，则投票加一，否则减1
 * 2、当vote重新等于0时，重复第一步，前面的结果打平，不影响后面的投票。就能及时修正x值，全部遍历完后，x=值肯定是真正的众数。
 */
public int majorityElement1(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
}

75. 颜色分类

image-20240522192824037

经典的荷兰国旗问题

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
public void sortColors(int[] nums) {
    //小于target的最右下标
    int less = -1;
    //大于target的最左下标
    int length = nums.length;
    int large = length;
    int target = 1;
    for (int i = 0; i < large; ) {
        int num = nums[i];
        if(num < target){
            ++less;
            swap(nums,less,i);
            i++;
        }else if(num > target){
            --large;
            swap(nums,i,large);
        }else{
            i++;
        }
    }
}

public void swap(int[]nums,int i,int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

31. 下一个排列

image-20240522193454237

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
/**
 * 首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i]<a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。
 * 如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i]<a[j]。这样「较大数」即为 a[j]。
 * 交换 a[i] 与 a[j]，此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
 *
 * 注意
 * 如果在步骤 1 找不到顺序对，说明当前序列已经是一个降序序列，即最大的序列，
 * 我们直接跳过步骤 2 执行步骤 3，即可得到最小的升序序列
 *
 * @param nums
 */
public void nextPermutation(int[] nums) {
    if(nums.length < 2){
        return;
    }
    int i = nums.length - 2;
    //找到不符合单调递减的起点，待交换的左数
    while(i >= 0 && nums[i] >= nums[i+1]){
        i--;
    }
    if(i >= 0){
        //从右往左找，找到第一个比左数大的右数
        int j = nums.length-1;
        while (j > i && nums[j] <= nums[i]){
            j--;
        }
        //交换左右数
        swap(nums,i,j);
    }
    reverse(nums,i+1);
}

287. 寻找重复数

image-20240522202613342

转化为有换问题->快慢指针->找入环口

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
public int findDuplicate1(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            if(nums[i] == nums[j]){
                return nums[i];
            }
        }
    }
    return 0;
}

   /**
     * 我们对 nums数组建图，每个位置 i 连一条 i→nums[i]的边。由于存在的重复的数字 target，
     * 因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 target 就是这个环的入口
     * @param nums 
     * @return
     */
    public int findDuplicate(int[] nums) {
        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while (fast != slow);
        slow = 0;
        while (fast != slow){
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }