代码随想录第三十一天

Posted on In

回溯总结

77 组合

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

    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return result;
    }

    private void backTracking(int n, int k, int start){
        if (k == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n - k + 1; i++){
            k--;
            path.add(i);
            backTracking(n, k, i + 1);
            k++;
            path.removeLast();
        }
    }
}

17 电话号码的字母组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backTracking(digits, 0);
        return result;
    }
    private void backTracking(String digits, int start){
        if (sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(start) - '0'];
        for (int i = 0; i < str.length(); i++){
            sb.append(str.charAt(i));
            backTracking(digits, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

216 组合总和III

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 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return result;
    }

    private void backTracking(int k, int n, int start){
        if (n < 0) return;
        if (k == 0 && n == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= 9 - k + 1; i++){
            k--;
            n -= i;
            path.add(i);
            backTracking(k, n, i + 1);
            path.removeLast();
            n += i;
            k++;
        }
    }
}

39 组合总和

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 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            target -= candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, i);
            path.removeLast();
            target += candidates[i];
        }

        
    }
}

40 组合总和II

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 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return result;
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int start){
        if (target < 0) return;
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.add(candidates[i]);
            target -= candidates[i];
            backTracking(candidates, target, i + 1);
            target += candidates[i];
            path.removeLast();
            used[i] = false;
        }
    }
}

131 分割回文串

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

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) return result;
        backTracking(s, 0);

        return result;
    }

    private void backTracking(String s, int start){
        if (start == s.length()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++){
            if (isPalindrome(s, start, i)){
                path.add(s.substring(start, i + 1));
                backTracking(s, i + 1);
                path.removeLast();
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end){
        while (start <= end){
            if (s.charAt(start++) != s.charAt(end--)) return false;
        }

        return true;
    }
}

93 复原ip地址

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
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0 || s.length() > 12) return result;
        backTracking(s, 0, 0);
        return result;
    }

    private void backTracking(String s, int start, int pointsNum){
        if (pointsNum == 3) {
            if (isValid(s, start, s.length() - 1)){
                result.add(s);
                return;
            }
        }

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                s = s.substring(0, i + 1) + '.' + s.substring(i + 1); 
                pointsNum++;
                backTracking(s, i + 2, pointsNum);
                pointsNum--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            }
        }
    }
    private boolean isValid(String s, int start, int end){
        if (start > end) return false;

        if (s.charAt(start) - '0' == 0 && start != end) return false;

        int num = 0;
        for (int i = start; i <= end; i++){
            if (s.charAt(i) - '0' < 0 || s.charAt(i) - '0' > 9) return false;
            
            num = num * 10 + s.charAt(i) - '0';

            if (num > 255) return false;
        }

        return true;
    }
}

78 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList<>(path));

        for (int i = start; i< nums.length; i++){
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

90 子集II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        Arrays.sort(nums);
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        result.add(new ArrayList(path));

        for (int i = start; i < nums.length; i++){
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

491 递增子序列

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 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length == 0 || nums == null) return result;
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int start){
        if (path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++){
            if (set.contains(nums[i]) || !path.isEmpty() && nums[i] < path.get(path.size() - 1)) continue;
            set.add(nums[i]);
            path.add(nums[i]);

            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46 全排列

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 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) return result;
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (path.contains(nums[i])) continue;
            path.add(nums[i]);
            backTracking(nums);
            path.removeLast();
        }
    }
}

47 全排列II

需要判断指定元素是否在枝上

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 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0) return result;
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;    
    }

    private void backTracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;
            if (used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums);
                used[i] = false;
                path.removeLast();
            }
            
        }
    }
}

332 重新安排行程

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 {
    List<String> result = new LinkedList<>();
    Map<String, Map<String, Integer>> map = new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets){
            Map<String, Integer> temp;
            if (map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }

            map.put(t.get(0), temp);
        }

        result.add("JFK");
        backTracking(tickets.size());
        return new ArrayList<>(result);
    }

    private boolean backTracking(int ticketSize){
        if (result.size() == ticketSize + 1){
            return true;
        }

        String last = result.getLast();
        if (map.containsKey(last)){
            for (Map.Entry<String, Integer> entry : map.get(last).entrySet()){
                int count = entry.getValue();
                if (count > 0){
                    result.add(entry.getKey());
                    entry.setValue(count - 1);
                    if (backTracking(ticketSize)) return true;
                    result.removeLast();
                    entry.setValue(count);
                }
                
            }
        }
        return false;

    }
}

也可利用priority queue，做排序

51 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
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
class Solution {
    List<List<String>> result = new ArrayList<>();
    char[][] board;
    public List<List<String>> solveNQueens(int n) {
        board = new char[n][n];
        for (char[] i : board){
            Arrays.fill(i, '.');
        }
        backTracking(n, 0);
        return result;
    }

    private void backTracking(int n, int row){
        if (row == n){
            result.add(board2List(board));
            return;
        }
        for (int i = 0; i < n; i++){
            if (isValid(n, row, i)){
                board[row][i] = 'Q';
                backTracking(n, row + 1);
                board[row][i] = '.';
            }
        }
    }

    private List<String> board2List(char[][] board){
        List<String> result = new ArrayList<>();
        for (char[] i : board){
            result.add(String.copyValueOf(i));
        }

        return result;
    }


    private boolean isValid(int n, int row, int col){
        for (int i = row - 1; i >= 0; i--){
            if (board[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if (board[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if (board[i][j] == 'Q') return false;
        }

        return true;
    }
}

37 解数独

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 {
    public void solveSudoku(char[][] board) {
        solver(board);
    }

    private boolean solver(char[][] board){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++){
                    if (isValid(board, i, j, k)){
                        board[i][j] = k;
                        if (solver(board)) return true;
                        board[i][j] = '.';
                    }
                }

                return false;
            }
        }

        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char k){
        for (int i = 0; i < 9; i++){
            if (board[i][col] == k) return false; 
        }
        for (int i = 0; i < 9; i++){
            if (board[row][i] == k) return false;
        }

        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;

        for (int i = startRow; i < startRow + 3 ; i++){
            for (int j = startCol; j< startCol + 3; j++){
                if (board[i][j] == k) return false;
            }
        }

        return true;
    }
}

贪心算法

理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优
贪心没有套路
最好的策略就是反例，举不了反例就是用贪心，有反例考虑动态规划

贪心算法分四步

  1. 问题分解成若干子问题
  2. 找出适合的贪心策略
  3. 求解每一个子问题的最优解
  4. 将局部最优解堆叠成全局最优解

455 分发饼干

小饼干喂小胃口
或者大饼干先满足大胃口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int index = 0;
        int count = 0;
        for (int i : g){
            while (index < s.length && i > s[index]) index++;
            if (index == s.length) break;
            count++;
            index++;
        }

        return count;
    }
}

376 摆动序列

局部最优是删除单调坡度上的点
整体就是求整个序列有几个局部峰值

不用删除，只需要就长度，即统计峰值数量

考虑情况：

  1. 上下坡中有中坡， 这里可以删除左边的或者右边的
  2. 数组首位两端，可以写死，或者添加dummy在数组中
  3. 单调坡度上有平坡
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 wiggleMaxLength(int[] nums) {
        if (nums.length < 1){
            return nums.length;
        }

        int curDiff = 0;
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i - 1];
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){
                count++;
                preDiff = curDiff;
            }

        }

        return count;

        
    }
}

53 最大子序和

局部：如果连续和为负数时，放弃，从下一个计算连续和
全局：最大连续和

如果 count 小于0， 把coun归位
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1) return nums[0];

    int sum = Integer.MIN_VALUE;
    int count = 0;

    for (int i = 0; i < nums.length; i++){
        count += nums[i];
        sum = Math.max(count, sum);
        if (count <= 0){
            count = 0;
        }
    }

    return sum;

}

}