力扣记录：Hot100（3）——46-72

46 全排列

• 回溯，之前做过，定义used数组判断该位置是否选择过，若选择过则跳过。
  • 时间复杂度O(n * n!)，空间复杂度O(n)

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        //回溯
        backtracking(nums, result, path, used);
        return result;
    }
    //回溯函数
    private void backtracking(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used){
        //终止条件
        if(path.size() == nums.length){
            result.add(new ArrayList(path));
            return;
        }
        //循环
        for(int i = 0; i < nums.length; i++){
            if(used[i] == true) continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, result, path, used); //递归
            //回溯
            used[i] = false;
            path.remove(path.size() - 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

48 旋转图像

• 对称覆盖，注意交换的下标关系。另：水平翻转再对角翻转
  • 时间复杂度O(n^2)，空间复杂度O(1)

class Solution {
    public void rotate(int[][] matrix) {
        //对称覆盖
        int m = matrix.length;
        int temp = 0;
        for(int i = 0; i < m / 2; i++){
            for(int j = 0; j < (m + 1) / 2; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[m - j - 1][i];
                matrix[m - j - 1][i] = matrix[m - i - 1][m - j - 1];
                matrix[m - i - 1][m - j - 1] = matrix[j][m - i - 1];
                matrix[j][m - i - 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

49 字母异位词分组

• 哈希表，之前做过，键为排序后的字符串，值为字母异位词数组。字符串排序：先转为字符数组然后排序再转为字符串。优化：可以使用字符串中各个字母出现次数作为键
  • 时间复杂度O(nklogk)，空间复杂度O(nk)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //哈希表，键为排序后的字符串，值为字母异位词数组
        Map<String, List<String>> map = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        for(String str : strs){
            //字符串排序
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String strNew = Arrays.toString(ch);
            if(!map.containsKey(strNew)){
                map.put(strNew, new ArrayList<>());
            }
            map.get(strNew).add(str);   //直接添加
        }
        for(List<String> value : map.values()){
            result.add(value);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

53 最大子数组和

• 贪心，之前做过，初始化当前和为0，最大值为数组第一位，遍历数组，先求和，然后更新最大值，最后当和小于0时修改当前和为0，从下一位重新求和。
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        //贪心
        int sum = 0;
        int max = nums[0];
        for(int num : nums){
            sum += num;
            max = Math.max(sum, max);
            if(sum < 0) sum = 0;
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

55 跳跃游戏

• 贪心，之前做过，遍历当前最远跳跃的范围，不断更新这个范围，直到到达数组最后一位或遍历结束。
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public boolean canJump(int[] nums) {
        //贪心
        //遍历时不断更新最远跳跃的位置
        int maxJump = nums[0];
        for(int i = 0; i <= maxJump; i++){
            maxJump = Math.max(maxJump, nums[i] + i);
            if(maxJump >= nums.length - 1) return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

56 合并区间

• 贪心，之前做过
  • 时间复杂度O(nlogn)，空间复杂度O(logn)

class Solution {
    public int[][] merge(int[][] intervals) {
        //贪心
        List<int[]> result = new ArrayList<>();
        //先对数组进行排序（按左边界）
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        //定义左右边界
        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] <= right){
                right = Math.max(right, intervals[i][1]);   //更新右边界
            }else{
                result.add(new int[]{left, right});
                //更新左右边界
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        //数组最后一个需要手动加入
        result.add(new int[]{left, right});
        return result.toArray(new int[result.size()][]);
        // int[][] resultArr = new int[result.size()][];
        // int count = 0;
        // for(int[] res : result){
        //     resultArr[count++] = res;
        // }
        // return resultArr;
    }
}
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

62 不同路径

• 动态规划，之前做过，当前位置的路径数量为上面一格路径数量加左边一格路径数量。使用滚动数组。
  • 时间复杂度O(mn)，空间复杂度O(n)
• 补充：可以直接使用数学方法计算，总共移动m+n-2次，其中m-1次向下移动，n-1次向右移动，因此，组合数为：

  • 

  • 时间复杂度O(m)，空间复杂度O(1)

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

64 最小路径和

• 动态规划，当前位置的最小路径和等于上一格和左一格较小的最小路径和加上当前位置权重。使用滚动数组。
  • 时间复杂度O(mn)，空间复杂度O(n)

class Solution {
    public int minPathSum(int[][] grid) {
        //动态规划
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];  //表示当前位置最小路径和
        //初始化
        dp[0] = grid[0][0];
        for(int i = 1; i < n; i++){
            dp[i] = dp[i - 1] + grid[0][i];
        }
        for(int i = 1; i < m; i++){
            dp[0] += grid[i][0];
            for(int j = 1; j < n; j++){
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

70 爬楼梯

• 动态规划，之前做过，斐波那契数列，当前爬楼梯方法数为上一格爬楼梯方法数加上两格爬楼梯方法数。使用两个常数。
  • 时间复杂度O(n)，空间复杂度O(1)
• 补充：直接使用斐波那契数列通项公式：
• 

class Solution {
    public int climbStairs(int n) {
        //动态规划，斐波那契数列
        if(n < 3) return n;
        int a = 1;
        int b = 2;
        int c = 0;
        for(int i = 3; i <= n; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

72 编辑距离

• 动态规划，之前做过，插入和删除操作实际是一样的，替换对两个字符串实际是一样的，因此，实际有三种操作：插入A、插入B、替换A。当前位置的字符相等，则最短编辑距离为上一位置的编辑距离；当前位置的字符不相等，则最短编辑距离为插入A、插入B、替换A三种操作中最短的加1。
  • 时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
    public int minDistance(String word1, String word2) {
        //动态规划
        int leng1 = word1.length();
        int leng2 = word2.length();
        int[][] dp = new int[leng1 + 1][leng2 + 1];
        //初始化
        for(int i = 0; i <= leng1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= leng2; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= leng1; i++){
            for(int j = 1; j <= leng2; 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[leng1][leng2];
    }
}
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