1457. Pseudo-Palindromic Paths in a Binary Tree
Posted Updated LeetCode / Mediuma minute read (About 221 words)

1457. Pseudo-Palindromic Paths in a Binary Tree

Question

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Solution

用数组bin[]记录一个树枝上的节点。

回溯，遇到根节点则判断数组bin[]中是否只有0个或1个奇数的数字。

Code

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res;
    int[] bin;
    public int pseudoPalindromicPaths (TreeNode root) {
        res = 0;
        bin = new int[10];
        backtrack(root);
        return res;
    }
    
    private void backtrack(TreeNode root){
        if(root.left == null && root.right == null){
            bin[root.val]++;
            boolean flag = false;
            for(int i = 0; i < bin.length; i++){
                if(flag && (bin[i] & 1) == 1){
                    bin[root.val]--;
                    return;
                }
                else if((bin[i] & 1) == 1) flag = true;
            }
            res++;
            bin[root.val]--;
            return;
        }
        bin[root.val]++;
        if(root.left != null) backtrack(root.left);
        if(root.right != null) backtrack(root.right);
        bin[root.val]--;
    }
}
967. Numbers With Same Consecutive Differences
Posted Updated LeetCode / Medium2 minutes read (About 228 words)

967. Numbers With Same Consecutive Differences

Question

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

Solution

回溯，每次传入上一个数字和剩余的位数。
全局变量sum记录加和。
DFS搜索，每次计算下一位的可行数字并递归。
用回溯维护sum的值。
如果剩余位数为1，则将当前的sum加入结果，并清零sum。

Code

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<Integer> res;
    int sum;
    public int[] numsSameConsecDiff(int n, int k) {
        res = new ArrayList<>();
        for(int i = 1; i < 10; i++){
            sum = 0;
            dfs(i, n, k);
        }
        
        int[] ret = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ret[i] = res.get(i);
        }
        return ret;
    }
    
    private void dfs(int prev, int n, int k){
        sum += prev;
        if(n == 1){
            res.add(sum);
            return;
        }
        
        if(k == 0){
            sum *= 10;
            dfs(prev + k, n-1, k);
            sum /= 10;
            return;
        }
        if(prev + k < 10){
            sum *= 10;
            dfs(prev + k, n-1, k);
            sum /= 10;
        }
        if(prev >= k){
            sum *= 10;
            dfs(prev - k, n-1, k);
            sum /= 10;
        }
    }
}

869. Reordered Power of 2
Posted Updated LeetCode / Medium / 复习3 minutes read (About 411 words)

869. Reordered Power of 2

Question

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Solution

打表，将所有二的指数全部计算出来，并用数组统计各个数字出现的频率。
然后同样统计n中各个数字出现的频率。

如果两者中有频率完全相同的情况，则返回true，反之返回false。

Code

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 boolean reorderedPowerOf2(int n) {
        int[] reorders = new int[10];
        int m = 1, digits = 0;
        for(int i = n; i > 0; i/=10){
            reorders[i % 10]++;
            digits++;
        }
        
        int size = 0;
        List<Integer[]> powerOfTwo = new ArrayList<>();
        
        while(m > 0 && size <= digits){
            size = 0;
            Integer[] bin = new Integer[10];
            Arrays.fill(bin, 0);
            for(int i = m; i > 0; i/=10){
                size++;
                bin[i % 10]++;
            }
            if(size == digits) powerOfTwo.add(bin);
            m *= 2;
        }
        
        for(Integer[] bin : powerOfTwo) if(check(bin, reorders)) return true;
        return false;
    }
    
    private boolean check(Integer[] bin, int[] reorders){
        for(int i = 0; i < bin.length; i++) if(bin[i] != reorders[i]) return false;
        return true;        
    }
}

Solution 2

回溯，遍历计算可以组成的所有数字。
打表记录所有二的指数并记录在哈希表内，如果所有组成数字中有哈希表内的数字则返回true，反之返回false。

Code

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 {
    HashSet<Integer> visited, set, numbers;
    List<Integer> arr, res;
    public boolean reorderedPowerOf2(int n) {
        int m = 1;
        set = new HashSet<>();
        visited = new HashSet<>();
        numbers = new HashSet<>();
        res = new ArrayList<Integer>();
        while(m > 0){
            set.add(m);
            m *= 2;
        }
        
        arr = new ArrayList<>();
        
        while(n > 0){
            arr.add(n % 10);
            n /= 10;
        }
        
        for(int i = 0; i< arr.size(); i++){
            if(arr.get(i) == 0) continue;
            visited.add(i);
            reorder(arr.get(i));
            visited.remove(i);
        }
        
        
        for(int num : res) if(set.contains(num)) return true;
        return false;
    }
    
    private void reorder(int num){
        if(visited.size() == arr.size()){
            res.add(num);
            return;
        };
        
        if(numbers.contains(num)) return;
        numbers.add(num);

        for(int i = 0; i < arr.size(); i++){
            if(visited.contains(i)) continue;
            int next = num * 10 + arr.get(i);
            visited.add(i);
            reorder(next);
            visited.remove(i);
        }
    }
}
473. Matchsticks to Square
Posted Updated LeetCode / Medium / 复习2 minutes read (About 279 words)

473. Matchsticks to Square

Question

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Solution

回溯，用int[] edges记录边长。

先计算所有火柴棍的长度之和是否能被4整除，如果不能则返回false。
将所有火柴排序，以减少回溯时的计算量。

Backtracking 回溯

当遍历越界时（传入index为-1），则返回true。

每次将当前火柴matchsticks[index]添加到一个edges[i]中。
当edges[i] <= sum / 4，且向前回溯前一个位置index-1返回结果为真，则返回true。
然后将当前火柴从edges[i]中取出。

Code

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 {
    int[] edges;
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int i = 0; i < matchsticks.length; i++) sum += matchsticks[i];
        if(sum % 4 != 0) return false;
        
        edges = new int[4];
        Arrays.sort(matchsticks);
        return backtracking(matchsticks, matchsticks.length-1, sum/4);
    }
    
    public boolean backtracking(int[] matchsticks, int index, int len){
        if(index == -1) return true;

        for(int i = 0; i < 4; i++){
            edges[i] += matchsticks[index];
            if(edges[i] <= len && backtracking(matchsticks, index - 1, len)) return true;
            edges[i] -= matchsticks[index];
        }
        return false;
    }
}
52. N-Queens II
Posted Updated LeetCode / Harda minute read (About 188 words)

52. N-Queens II

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Solution

和昨天的题目51. N-Queens一样。
只是不需要转换并记录字符串了，递归结束时直接将res+1即可。

Code

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 {
    int target;
    int res;
    int[][] operations;
    public int totalNQueens(int n) {
        target = n;
        res = 0;
        operations = new int[][]{{-1,0},{-1,1},{-1,-1}};
        backtracking(new int[n][n], 0, 0);
        return res;
    }
    
    private void backtracking(int[][] board, int i, int n){
        if(n == target){
            res++;
            return;
        }
        for(int j = 0; j < target; j++){
            if(isValid(board, i, j)){
                board[i][j] = 1;
                backtracking(board, i+1, n+1);
                board[i][j] = 0;
            }
        }
    }
    
    private boolean isValid(int[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0], q = j + operation[1];
            while(p >= 0 && p < target && q >= 0 && q < target){
                if(board[p][q] == 1) return false;
                p += operation[0];
                q += operation[1];                
            }
        }
        return true;
    }
}
51. N-Queens
Posted Updated LeetCode / Hard / 复习5 minutes read (About 749 words)

51. N-Queens

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Solution

话说今天出这道题真的不是搞事情嘛？

八皇后问题，回溯+剪枝。按顺序搜索可以减少情况的重复计算。
由于棋盘的大小为n * n，要放n个皇后，因此每一行（列）上都有且只有一位皇后。
我们可以依顺序逐行回溯，对逐行的每一列进行回溯。
由于每一行的可选位置都减少1，因此时间复杂度为O(N!)。

回溯

通过一个char数组board[][]记录棋子状态。将board[][]初始化为’.’。
遍历这一行的所有列，如果该位置有效，则board[i][j]改为’Q’，将这个点设置为有棋子，并递归下一行。
回溯，将board[i][j]重新设置为’.’。

当递归次数达到n时，将char[]数组转换为字符串加入答案。

辅助方法 isValid

检测该位置是否有效。即该位置的路径上是否已经有棋子，或该位置已经有棋子。
由于我们的回溯方法是逐行确定棋子位置，因此不需要查看全部八个方向，而是查看之前已经遍历过的行即可。

Code

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
class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{-1,-1},{-1,1},{-1,0}};
        char[][] board = new char[n][n];
        for(char[] s : board){
            Arrays.fill(s,'.');
        }
        backtracking(board,0,0);
        return ret;
    }
    
    private void backtracking(char[][] board, int n, int i){
        if(n == size){
            List<String> ans = new ArrayList<>();
            for(char[] s : board) ans.add(new String(s));
            ret.add(ans);
            return;
        }

        for(int j = 0; j < size; j++){
            if(isValid(board, i, j)){
                board[i][j] = 'Q';
                backtracking(board, n+1, i+1);
                board[i][j] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0];
            int q = j + operation[1];
            while(p >= 0 && p < size && q >= 0 && q < size){
                if(board[p][q] == 'Q') return false;
                p += operation[0];
                q += operation[1];
            }
        }
        return true;
    }
}

Solution 2

简单回溯。
在回溯时搜索二维位置，因此增加了时间复杂度，正常是过不了的。
通过按顺序进行搜索（只搜索当前行之后的位置）进行剪枝。

Code

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 {
    List<List<String>> ret;
    int size;
    int[][] operations;
    HashSet<String> set;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{1,1},{1,-1},{1,0},{0,1},{0,-1}};
        backtracking(new int[n][n],0,0);
        return ret;
    }
    
    private void backtracking(int[][] border, int n, int start){
        if(n == size){
            //print(border);
            List<String> ans = new ArrayList<>();
            for(int i = 0; i < size; i++){
                StringBuffer sb = new StringBuffer();
                for(int j = 0; j < size; j++){
                    if(border[i][j] == 1){
                        sb.append("Q");
                    }
                    else{
                        sb.append(".");
                    }
                }
                ans.add(sb.toString());
            }
            ret.add(ans);
            return;
        }
        
        for(int i = start; i < size; i++){
            for(int j = 0; j < size; j++){
                if(border[i][j] == 0){
                    border[i][j] = 1;
                    List<int[]> temp = new ArrayList<>();
                    for(int[] operation : operations){
                        int p = i, q = j;
                        while(p >= 0 && p < size && q >= 0 && q < size){
                            if(border[p][q] == 0){
                                border[p][q] = 2;
                                temp.add(new int[]{p,q});
                            }
                            p += operation[0];
                            q += operation[1];
                        }
                    }
                    backtracking(border, n+1, i+1);
                    for(int[] t : temp){
                        border[t[0]][t[1]] = 0;
                    }
                    border[i][j] = 0;
                }
            }
        }
    }
}
216. Combination Sum III
Posted Updated LeetCode / Medium2 minutes read (About 260 words)

216. Combination Sum III

Question

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Solution

回溯，创建一个成员变量visited[]记录访问情况。

剪枝优化，遍历所有可选择的数字，将其加和，如果加和大于target则返回。
剪枝优化，每层级遍历的范围大于传入列表中的最后一个元素。
回溯，向下递归。

如果k等于0并且sum等于target则添加arr到列表ret中。

Code

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 {
    int[] visited;
    List<List<Integer>> ret;

    public List<List<Integer>> combinationSum3(int k, int n) {
        visited = new int[9];
        ret = new ArrayList<>();
        backTracking(k, n, new ArrayList<>(), 0);
        return ret;
    }
    
    private void backTracking(int k, int target, List<Integer> arr, int sum){
        if(k == 0 && sum == target) ret.add(new ArrayList<>(arr));
        int start = 1;
        if(arr.size() != 0) start =  arr.get(arr.size()-1)+1;
        for(int i = start ; i <= 9; i++){
            if(visited[i-1] == 1) continue;
            sum+=i;
            if(sum > target) return;
            visited[i-1] = 1;
            arr.add(i);
            
            backTracking(k-1, target, arr, sum);
            sum-=i;
            arr.remove(new Integer(i));
            visited[i-1] = 0;
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 294 words)

113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

回溯，每次将root的值添加到list中。并计算新的sum值。分别向左右子节点进行递归，然后回溯。
当节点没有左右子节点，且sum等于targetSum则将新建的list添加到结果中。
（注意这一步内也需要进行回溯操作。）

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        if(root == null) return ret;
        target = targetSum;
        backTrack(root, 0, new ArrayList<>());
        return ret;
    }
    
    private void backTrack(TreeNode root, int sum, List<Integer> nodes){
        if(root.left == null && root.right == null){
            sum += root.val;
            if(sum == target){
                nodes.add(root.val);
                ret.add(new ArrayList<Integer>(nodes));
                nodes.remove(nodes.size()-1);
            }
            return;
        }
        nodes.add(root.val);
        sum += root.val;
        if(root.left != null) backTrack(root.left, sum, nodes);
        if(root.right != null) backTrack(root.right, sum, nodes);
        nodes.remove(nodes.size()-1);
        sum -= root.val;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 301 words)

79. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

回溯，遍历所有初始元素。
当寻找的字符与当前matrix里的字符相同时，将当前位置记录在visited里，并向下递归搜索四个方向，回溯visited。
当越界或者字符已经visited时返回false。
当寻找到单词的最后一位时，如果当前matrix里的字符与搜索的字符相等，则返回true。反之返回false。

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 {
    char[][] bd;
    String wd;
    int[][] visited;
    public boolean exist(char[][] board, String word) {
        boolean ans = false;
        visited = new int[board.length][board[0].length];
        bd = board;
        wd = word;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                ans = ans || backtracking(i, j, 0);
            }
        }
        return ans;
    }
    
    private boolean backtracking(int i, int j, int n){
        
        if(i < 0 || j < 0 || i >= bd.length || j >= bd[0].length || n >= wd.length()) return false;
        if(visited[i][j] == 1) return false;
        if(n == wd.length()-1) return bd[i][j] == wd.charAt(n); 
        if( bd[i][j] == wd.charAt(n) ){
            n++;
            visited[i][j] = 1;
            boolean a = backtracking(i+1, j, n);
            boolean b = backtracking(i-1, j, n);
            boolean c = backtracking(i, j+1, n);
            boolean d = backtracking(i, j-1, n);
            visited[i][j] = 0;
            return a || b || c || d;
        }
        return false;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 166 words)

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

回溯，记录左右括号的出现次数。
每次递归都添加左侧括号。
左侧括号的数量大于右侧括号时递归下一级才可以添加右侧括号。
当左侧括号和右侧括号达到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
class Solution {
    int N;
    List<String> ret;
    StringBuffer sb;
    
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        sb = new StringBuffer();
        N = n;
        backtracking(0, 0);
        return ret;
    }
    
    private void backtracking(int left, int right){
        if(left > N || right > N){
            return;
        }
        if(left == N && right == N){
            ret.add(sb.toString());
            return;
        }
        if(left > right){
            sb.append(')');
            backtracking(left, right+1);
            sb.delete(sb.length()-1, sb.length());        
        }
        sb.append('(');
        backtracking(left+1, right);
        sb.delete(sb.length()-1, sb.length());        
    }
}
Posted Updated LeetCode / Mediuma minute read (About 189 words)

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

回溯，每个回溯层级添加数字对应的字符。

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 List<String> letterCombinations(String digits) {

        
        List<String> ret = new ArrayList<>();
        if(digits.equals("")) return ret;
        
        char[][] bin = new char[8][0];
        bin[0] = new char[]{'a', 'b', 'c'}; 
        bin[1] = new char[]{'d', 'e', 'f'};
        bin[2] = new char[]{'g', 'h', 'i'};
        bin[3] = new char[]{'j', 'k', 'l'};
        bin[4] = new char[]{'m', 'n', 'o'};
        bin[5] = new char[]{'p', 'q', 'r', 's'};
        bin[6] = new char[]{'t', 'u', 'v'};
        bin[7] = new char[]{'w', 'x', 'y', 'z'};
        
        backtracking(ret, new StringBuffer(), bin, digits, 0);
        return ret;
    }
    
    private void backtracking(List<String> ret, StringBuffer sb, char[][] bin, String digits, int i){
        if(sb.length() == digits.length() ){
            ret.add(sb.toString());
            return;
        }
        
        for(char c : bin[digits.charAt(i)-'2']){
            sb.append(c);
            backtracking(ret, sb, bin, digits, i+1);
            sb.delete(sb.length()-1, sb.length());
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 229 words)

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

由于有重复性元素，因此先将数组排序。
储存一个数组，记录元素是否被选择。
回溯，遍历选择元素，并计算加和，并记录选择的元素。当选择的元素与上一个元素重复时，则跳过。

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 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, ret, new ArrayList<>(), new int[candidates.length], target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int[] visited, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i-1] && visited[i-1] == 0) continue;
            visited[i] = 1;
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, visited, target, sum, i+1);
            visited[i] = 0;
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 240 words)

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

回溯，记录当前加和。
遍历所有数组元素，当sum大于target时返回，等于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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(candidates, ret, new ArrayList<>(), target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, target, sum, i);
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 255 words)

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

首先排序，对于有重复数据的数组，排序可以方便剪枝。
回溯，每次遍历数组内的元素。
创建一个数组记录元素是否已被遍历。
遍历时如果数组已经被记录，或者当前元素与数组中的上一个元素相等，且上一个数组未被选择，则跳过。
（如果上一个同样的数字没被选择，则放弃这个排列。即在元素相同时，优先选择前面的元素进行排列）

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 List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int[] visited = new int[nums.length];
        backtracking(ret, new ArrayList<>(), visited , nums);
 
        return ret;
    }

    private void backtracking(List<List<Integer>> ret, List<Integer> arr, int[] visited, int[] nums){
        if(arr.size() == nums.length){
            ret.add(new LinkedList<>(arr));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){
            if(visited[i] == 1) continue;
            if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue;
            arr.add(nums[i]);
            visited[i] = 1;
            backtracking(ret, arr, visited, nums);
            visited[i] = 0;
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 214 words)

90. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

首先对数组进行排序，这样重复的元素将排列在一起。
接下来对每一个层级进行回溯。
进入每一个层级都根据上一级传递来的列表创建新列表。
然后对层级下的所有元素进行回溯。
剪枝，当遍历节点和上一个节点相等时，则跳过。
回溯，从列表中去掉最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        backtrack(ret, new LinkedList<Integer>(), nums, 0);
        return ret;
    }
    
    private void backtrack(List<List<Integer>> ret, List<Integer> arr, int[] nums, int level){
        ret.add(new LinkedList<>(arr));
        
        for(int i = level; i < nums.length; i++){
            if(i != level && nums[i] == nums[i-1]) continue;
            arr.add(nums[i]);
            backtrack(ret, arr, nums, i+1);
            arr.remove(arr.size()-1);
        }
    }
}
Follow

Recents

Archives

Links

×