代码随想录第三十天

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
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++){
            path.add(i);
            k--;
            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
23
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);
            k++;
            n += i;
            path.removeLast();
        }
    }
}

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
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.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;
            target -= candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, i + 1);
            used[i] = false;
            path.removeLast();
            target += candidates[i];

        }
    }
}

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
class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if (s.length() == 0 || s == null) 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;
            start++;
            end--;
        }

        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.length() == 0 || s == null || s.length() > 12) return result;

        backtracking(s, 0, 0);
        return result;
    }

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

        for (int i = start; i < s.length(); i++){
            if (isValid(s, start, i)){
                points++;
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                backtracking(s, i + 2, points);
                points--;
                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' > 9 || s.charAt(i) - '0' < 0) return false;
            num = num * 10 + s.charAt(i) - '0';
            if (num > 255) return false;
        }

        return true;
    }
}

78 子集

注意result添加地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] 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++){
            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
22
23
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length];
        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 > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            backTracking(nums, i + 1);
            used[i] = false;
            path.removeLast();
        }
    }
}

491 递增子序列

这里在result结果输出时不返回
利用set判断结果
判断path里面的重复数组

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>> 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 (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || set.contains(nums[i])) 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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0 || nums == null) 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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if (nums.length == path.size()){
            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){
                path.add(nums[i]);
                used[i] = true;
                backTracking(nums);
                used[i] = false;
                path.removeLast();
            }
        }
    } 
}

332 重新安排行程

难点：

  1. 一个行程可能有圆
  2. 有多种解法时，字母排序问题
  3. 回溯法的终止条件
  4. 搜索过程中遍历机场对应的所有机场

建立Map<String, Map<String, Integer>> 记录每个飞机场对应的下一个飞机场的map

注意因为有字母排序问题，生成map<String,Integer>时要用Treemap直接进行排序

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
class Solution {
    LinkedList<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;
    }
}

优化就是把Map<String, Integer> 调整成为链表的形式
添加节点不需要利用treemap

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
class Solution {
    Map<String, LinkedList<String>> ticketMap = new HashMap<>();
    LinkedList<String> result = new LinkedList<>();
    int total;

    public List<String> findItinerary(List<List<String>> tickets) {
        total = tickets.size() + 1;
        for (List<String> ticket : tickets) {
            addNew(ticket.get(0), ticket.get(1));
        }
        result.add("JFK");
        deal();
        return result;
    }

    boolean deal() {
        if (result.size() == total) {
            return true;
        }

        String last = result.getLast();
        if (ticketMap.containsKey(last)){
            String cur;
            LinkedList<String> list = ticketMap.get(last);
            for (int i = 0; i < list.size(); i++){
                cur = list.get(i);
                list.remove(i);
                result.add(cur);
                if (deal()) return true;
                result.removeLast();
                list.add(i, cur);
            }
        }
        return false;
    }

    void addNew(String start, String end) {
        LinkedList<String> startAllEnd = ticketMap.getOrDefault(start, new LinkedList<>());
        if (!startAllEnd.isEmpty()) {
            for (int i = 0; i < startAllEnd.size(); i++) {
                if (end.compareTo(startAllEnd.get(i)) < 0) {
                    startAllEnd.add(i, end);
                    return;
                }
            }
            startAllEnd.add(startAllEnd.size(), end);
        } else {
            startAllEnd.add(end);
            ticketMap.put(start, startAllEnd);
        }
    }
}

51 N皇后

本题难点就是怎样找到valid的格子，也就是Q的位置
要检查列，45度角，135度；

将此问题抽象成树形式

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

        backtracking(n, 0);
        return result;
    }

    private void backtracking(int n, int row){
        if (row == n){
            result.add(Board2List());
            return;
        }

        for (int i = 0; i < n; i++){
            if (isValid(n, row, i)){
                chessboard[row][i] = 'Q';
                backtracking(n, row + 1);
                chessboard[row][i] = '.';
            }
        }
    }

    private List<String> Board2List(){
        List<String> list = new ArrayList<>();

        for (char[] i : chessboard){
            list.add(String.copyValueOf(i));
        }

        return list;
    }

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

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

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

        return true;
    }
}

37 解数独

二维递归
思路类似n皇后
只是比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
class Solution {
    public void solveSudoku(char[][] board) {
        sudoSolver(board);
    }

    private boolean sudoSolver(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(i, j, k, board)){
                        board[i][j] = k;
                        if (sudoSolver(board)) return true;
                        board[i][j] = '.'; 
                    }
                }

                return false;
            }
        }

        return true;
    }

    private boolean isValid(int row, int col, char val, char[][] board){
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val) return false;
        }
        for (int i = 0; i < 9; i++){
            if (board[i][col] == val) 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] == val) return false;
            }
        }

        return true;
    }
}