回溯

发表于

Leetcode

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

1
2
3
4
2 - abc
3 - def
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Although the above answer is in lexicographical order, your answer could be in any order you want.

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
class Solution {
    
    private String []letterMap = new String[]{
        " ",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    
    private List<String> res = new ArrayList<String>();
    
    private void helper(String digits, int index, String s){
        if(index == digits.length()){
            res.add(s);
            return;
        }
        char c = digits.charAt(index);
        String letter = letterMap[c - '0'];
        for(int i = 0; i < letter.length(); ++i){
            helper(digits, index + 1, s + String.valueOf(letter.charAt(i)));
        }
    }
    
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.equals("")){
            return res;
        }        
        
        helper(digits, 0, "");
        
        return res;
    }
}

93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

1
2
3
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
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
class Solution {
    
    private Set<String> set = new HashSet<>();
    private boolean isValid(String str){
        String []S = str.split("\\.");
        int []A = new int[4];
        for(int i = 0; i < S.length; ++i){
            A[i] = Integer.valueOf(S[i]);
            if(A[i] > 255 || A[i] < 0 || (S[i].charAt(0) == '0' && S[i].length() != 1)){
                return;
            }
            S[i] = String.valueOf(A[i]);
        }
        set.add(String.join(".", S));
    }
    private void helper(char []chars, int index, StringBuilder sb){
        if(sb.length() == chars.length + 3){
            isValid(sb.toString());
            return;
        }
        for(int i = index; i < sb.length()-1; ++i){
            StringBuilder sb2 = new StringBuilder(sb);
            sb2.insert(i+1, '.');
            helper(chars, i+2, sb2);
        }
    }
    public List<String> restoreIpAddresses(String s) {
        if(s == null || s.length() == 0 || s.length() >= 13){
            return new ArrayList<>();
        }
        helper(s.toCharArray(), 0, new StringBuilder(s));
        return new ArrayList<>(set);
    }
}

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

given s = “aab”, return

1
2
3
4
 [
  ["aa","b"],
  ["a","a","b"]
]
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 {
    private  List<List<String>> list2;
    private boolean isPalindrome(String s, int lo, int hi){
        if(lo == hi){
            return true;
        }
        while(lo < hi ) {
            if(s.charAt(lo++) != s.charAt(hi--)){
                return false;
            }
        }
        return true;
    }
    private void helper(String s, int index, Stack<String> stack){
        if(!stack.isEmpty() && index == s.length()){
            list2.add(new ArrayList<>(stack));
            return ;
        }
        for(int i = index; i < s.length(); ++i){
            if(isPalindrome(s, index, i)){
                stack.push(s.substring(index, i+1));
                helper(s, i+1, stack);
                stack.pop();
            }
        }
    }
    public List<List<String>> partition(String s) {
        list2 = new ArrayList<List<String>>();
        if(s == null || s.length() == 0){
            return list2;
        }
        helper(s, 0, new Stack<String>());
        return list2;
    }
}

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

Example:

[1,2,3] have the following permutations:

1
2
3
4
5
6
7
8
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,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
class Solution {
    private List<List<Integer>> list2;
    private boolean []visited;
    
    private void helper(int []A, int index, Stack<Integer> stack){
        if(index == A.length){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }        
        
        for(int i = 0; i < A.length; ++i){
            if(!visited[i]){
                visited[i] = true;
                stack.push(A[i]);
                
                helper(A, index+1, stack);
                
                stack.pop();
                visited[i] = false;
            }
        }
        
    } 
    
    public List<List<Integer>> permute(int[] nums) {
        list2 = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0 ){
            return list2;
        }
        
        visited = new boolean[nums.length];
        
        helper(nums, 0, new Stack<Integer>());
        
        return list2;
    }
}

47. Permutations II

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

Example:

[1,1,2] have the following unique permutations:

1
2
3
4
5
[
  [1,1,2],
  [1,2,1],
  [2,1,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
40
41
class Solution {
    private List<List<Integer>> list2 = new ArrayList<List<Integer>>();
    private boolean []visited;
    
    private void helper(int []A, int cnt, Stack<Integer> stack){
        if(cnt == A.length){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }
        
        for(int i = 0; i < A.length; ++i){
            //元素X只能在某次递归中使用一次
            if(i != 0 && A[i-1] == A[i] && visited[i-1]){
                continue;
            }
            
            if(!visited[i]){
                visited[i] = true;
                stack.push(A[i]);
                
                helper(A, cnt+1, stack);
                
                stack.pop();
                visited[i] = false;
            }
        }
    }
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null || nums.length == 0){
            return list2;
        }
        
        Arrays.sort(nums);
        visited = new boolean[nums.length];
            
        helper(nums, 0, new Stack<Integer>());
        
        return list2;
    }
}

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

If n = 4 and k = 2, a solution is:

1
2
3
4
5
6
7
8
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
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 {
    private List<List<Integer>> list2;
    
    private void helper(int n, int k, int index, List<Integer> list){
        if(k == list.size()){
            list2.add(list.clone());
            return;
        }
        
        for(int i = index; i <= n; ++i){
            list.add(i);
            helper(n, k, i+1, list);
            list.remove(list.size()-1);
        }
    }
    
    public List<List<Integer>> combine(int n, int k) {
        list2 = new ArrayList<List<Integer>>();
        
        if(n <= 0 || k <= 0 || n < k){
            return list2;
        }
        
        helper(n, k, 1, new ArrayList<Integer>());
        
        return list2;
    }
}

回溯剪枝

1
2
3
4
//list还需求 k - list.size()个元素
//[i, n]中至少要有 k - list.size()个元素
//i最多为为 n - (k-list.size()) + 1 个元素
for(int i = index; i <= n-(k-list.size())+1; ++i)

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example:

given candidate set [2, 3, 6, 7] and target 7,
A solution set is: 

1
2
3
4
[
  [7],
  [2, 2, 3]
]
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 {
    private List<List<Integer>> list2;
    private boolean []visited;
    
    private void helper(int []A, int target, int sum, Stack<Integer> stack, int index){
        if(target == sum){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }
        else if(target < sum){
            return;
        }
        
        // [2, 2, 3] , [2, 3, 2] 是不行的
        for(int i = index; i < A.length; ++i){
            if(!stack.isEmpty() && stack.peek() > A[i]){
                continue;
            }
            sum += A[i];
            stack.push(A[i]);
            
            helper(A, target, sum, stack, index);
            
            stack.pop();
            sum -= A[i];
        }
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        list2 = new ArrayList<List<Integer>>();
        
        if(candidates == null){
            return list2;
        }
        
        visited = new boolean[candidates.length];
        
        Arrays.sort(candidates);
        
        helper(candidates, target, 0, new Stack<Integer>(), 0);
        
        return list2;
    }
}

剪枝

1
2
3
4
5
for(int i = index; i < A.length && target >= sum + A[i]; ++i){
	...
	helper(A, target, sum, stack, i);
	...
}

40. Combination Sum II

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

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

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example:

given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: 

1
2
3
4
5
6
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
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 {
    private List<List<Integer>> list2;
    
    private void helper(int []A, int remain, Stack<Integer> stack, int index){
        if(remain == 0){
            list2.add(new ArrayList<Integer>(stack));
            return;
        }
        else if(remain < 0){
            return;
        }
        
        for(int i = index; i < A.length; ++i){
            if(i > index && A[i] == A[i-1]){
                continue;
            }
            stack.push(A[i]);
            helper(A, remain-A[i], stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        list2 = new ArrayList<List<Integer>>();
        if(candidates == null){
            return list2;
        }
        Arrays.sort(candidates);
        
        helper(candidates, target, new Stack<Integer>(), 0);
        
        return list2;
    }
}

剪枝

1
for(int i = index; i < A.length && A[i] <= remain; ++i)

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example:

1
2
3
4
5
Input: k = 3, n = 7
Output:
[[1,2,4]]
1
2
3
4
5
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
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
class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int k, int remain, Stack<Integer> stack, int index){
        if(k == stack.size()){
            if(remain == 0){
                list2.add(new ArrayList<Integer>(stack));
            }
            return;
        }
        
        for(int i = index; i <= 9; ++i){
            stack.push(i);
            helper(k, remain-i, stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        list2 = new ArrayList<List<Integer>>();
        if(k <= 0 || n <= 0 || n <= k){
            return list2;
        }
        helper(k, n, new Stack<Integer>(), 1);
        
        return list2;
    }
}

剪枝

1
2
3
4
//stack还需要 k-stack.size()个元素
//[i, 9]中至少还需要有 k-stack.size()个元素
//i最多可以是 9 - (k-stack.size()) + 1 
for(int i = index; i <= 10 -k + stack.size() && i <= remain; ++i)

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note:

The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
If nums = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,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
28
class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int []A, Stack<Integer> stack, int index){
        if(stack.size() <= A.length){
            list2.add(new ArrayList<Integer>(stack));
            //这里不能return,因为每一次递归调用都有stack要加入list2
        }
        
        for(int i = index; i < A.length; ++i){
            stack.push(A[i]);
            helper(A, stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> subsets(int[] nums) {
        list2 = new ArrayList<List<Integer>>();
        
        if(nums == null){
            return list2;
        }
        
        helper(nums, new Stack<Integer>(), 0);
        
        return list2;
    }
}

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note:

The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
If nums = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,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
28
29
30
31
32
33
class Solution {
    private List<List<Integer>> list2;
    
    private void helper(int []A, Stack<Integer> stack, int index){
        if(stack.size() <= A.length){
            list2.add(new ArrayList<Integer>(stack));
        }
        
        //每一轮递归中的for循环，相同元素只能被用一次
        //例如 [2, 2]  第一个2和第二个2的组只能有 [] [2] [2, 2]
        //或者 [1, 2, 2] 对于元素1来说，和前后两个元素2的组合策略是一样的
        for(int i = index; i < A.length; ++i){
            if(index < i && A[i] == A[i-1]){
                continue;
            }
            stack.push(A[i]);
            helper(A, stack, i+1);
            stack.pop();
        }
    }
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        list2 = new ArrayList<List<Integer>>();
        
        if(nums == null){
            return list2;
        }
        Arrays.sort(nums);
        helper(nums, new Stack<Integer>(), 0);
        
        return list2;
    }
}

401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

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
private List<String> list;
private boolean visited[];
// visited[10]
// 1 2 4 8 1 2 4 8 16 32
private String caculateTime(){
    int min = 0;
    int sec = 0;
    
    for(int i = 0; i < 10; ++i){
        if(i < 4 && visited[i]){
            min += Math.pow(2, i);
        }
        else if(visited[i]){
            sec += Math.pow(2, i-4);
        }
    }
    String m = min + ":";
    String s = sec < 10 ? "0"+sec : String.valueOf(sec);
    return m+s;
}
private void helper(int remain, int index){
    if(remain == 0){
        list.add(caculateTime());
        return;
    }
    for(int i = index; i < 10; ++i){
        visited[i] = true;
        
        //不满足 min(4,8) 或者 sec(32, 16, 8, 4)的情况下
        //才递归
        if(!(visited[2] && visited[3] ||
                visited[9] && visited[8] && visited[7] && visited[6])){
            helper(remain-1, i+1);
        }
        visited[i] = false;
    }
}
public List<String> readBinaryWatch(int num) {
    list = new ArrayList<String>();
    visited = new boolean[10];
    helper(num, 0);
    return list;
}

Given a 2D board and a word, find if the word exists in the grid.

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

example:

1
2
3
4
5
6
7
8
9
Given board  =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    private boolean [][]visited;
    private int [][]d;
    private int m;
    private int n;
    
    private boolean isValidPos(int x, int y){
        return x >= 0 && x < m && y >=0 && y < n;
    }
    
    private boolean helper(char [][]board, String word, int index, int x, int y){
        if(index == word.length()-1){
            return word.charAt(index) == board[x][y];
        }
        
       
        if(board[x][y] == word.charAt(index)){
            visited[x][y] = true;
            
            for(int i = 0; i < 4; ++i){
                int newX = x + d[i][0];
                int newY = y + d[i][1];
                if(isValidPos(newX, newY) && !visited[newX][newY] && 
                        helper(board, word, index+1, newX, newY)){
                    
                    return true;
                }
            }
            
            visited[x][y] = false;
        }
        
        
        return false;
    }
    
    
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(helper(board, word, 0, i, j)){
                    return true;
                }
            }
        }
        
        return false;
    }
}

200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

1
2
3
4
5
11110
11010
11000
00000
Answer: 1

Example 2:

1
2
3
4
5
11000
11000
00100
00011
Answer: 3
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
class Solution {
    private boolean [][]visited;
    private int [][]d;
    private int m;
    private int n;
    
    private boolean inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    private void dfs(char [][]grid, int x, int y){
        //不需要递归终止条件
        //dfs一直搜索直到(x, y)四周都被搜索了
        
        if(!visited[x][y]){
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i){
                int newX = d[i][0] + x;
                int newY = d[i][1] + y;
                if(inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]){
                    dfs(grid, newX, newY);
                }
            }
        }
    }
    
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0){
            return 0;
        }
        
        int cnt = 0;
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j] && grid[i][j] == '1' ){
                    ++cnt;
                    dfs(grid, i, j);
                }
            }
        }
        
        return cnt;
    }
}

130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

解题思路:

这道题使用DFS

Example:

1
2
3
4
X X X X
X O O X
X X O X
X O X X
1
2
3
4
5
6
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

StackOverflow做法

当测试数量大，并且包含大量的’O’，递归调用breakSurrounded太深，爆

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 {
    private int m;
    private int n;
    private boolean [][]visited;
    private int [][]d;
    private boolean outOfArea(int x, int y){
        return x < 0 || x >= m || y < 0 || y >= n; 
    }
    private boolean breakSurrounded(char [][]board, int x, int y){
        if(board[x][y] == 'X'){
            return false;
        }
        
        if(!visited[x][y]){
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i){
                int newX = x + d[i][0];
                int newY = y + d[i][1];
                if(outOfArea(newX, newY) ||
                        !visited[newX][newY] && board[newX][newY] == 'O' &&
                         breakSurrounded(board, newX, newY)){
                    visited[x][y] = false;
                    return true;
                }
            }
            visited[x][y] = false;
        }
        return false;
    }
    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int i = 1; i < board.length - 1; ++i){
            for(int j = 1; j < board[0].length - 1; ++j){
                if(board[i][j] == 'O' && !breakSurrounded(board, i, j)){
                    board[i][j] = 'X';
                }
            }
        }
    }
}

优化做法

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
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    private boolean[][] visited;
    private int [][]d;
    private int m;
    private int n;
    
    private boolean inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    private void digChannel(char [][]board, int x, int y){
        if(board[x][y] == 'X'){
            visited[x][y] = true;
            return;
        }
        else if(board[x][y] == 'O'){
            board[x][y] = '*';
        }
        
        if(!visited[x][y]){
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i){
                int newX = x + d[i][0];
                int newY = y + d[i][1];
                if(inArea(newX, newY) && !visited[newX][newY]){
                    digChannel(board, newX, newY);
                }
            }
        }
    }
    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        d = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        
        for(int i = 0; i < n; ++i){
            if(board[0][i] == 'O'){
                digChannel(board, 0, i);
            }
            if(board[m-1][i] == 'O'){
                digChannel(board, m-1, i);
            }
        }
        
        for(int i = 0; i < m; ++i){
            if(board[i][0] == 'O'){
                digChannel(board, i, 0);
            }
            if(board[i][n-1] == 'O'){
                digChannel(board, i, n-1);
            }
        }
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(board[i][j] == 'X'){
                    continue;
                }
                else{
                    board[i][j] = board[i][j] == '*' ? 'O' : 'X';
                }
            }
        }
    }
}

417. Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

  • he order of returned grid coordinates does not matter.
  • Both m and n are less than 150.
1
2
3
4
5
6
7
8
9
10
11
12
13
Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

解题思路:

东南方向和西北方向的深度优先搜索

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
private List<int[]> intArrayList;
private int m;
private int n;
private int [][]direction;
private boolean[][] visited;
private boolean inPacific(int x, int y){
    return x < 0 || y < 0;
}
private boolean inAtlantic(int x, int y){
    return x >= m || y >= n;
}
private boolean inArea(int x, int y){
    return x >= 0 && x < m && y >= 0 && y < n;
}
private boolean flowToPacific(int [][]matrix, int x, int y){
    visited[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int newX = direction[i][0] + x;
        int newY = direction[i][1] + y;
        if(inPacific(newX, newY) ||
               inArea(newX, newY)&& !visited[newX][newY] && matrix[newX][newY] <= matrix[x][y] && flowToPacific(matrix, newX, newY)){
		
            //回溯的时候访问过的点要置为false
            //否则会影响以后的点
            visited[x][y] = false;
            return true;
        }
    }
    visited[x][y] = false;
    return false;
}
private boolean flowToAtlantic(int [][]matrix, int x, int y){
    visited[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int newX = direction[i][0] + x;
        int newY = direction[i][1] + y;
        if(inAtlantic(newX, newY) ||
                inArea(newX, newY)&& !visited[newX][newY] && matrix[newX][newY] <= matrix[x][y] && flowToAtlantic(matrix, newX, newY)){
            visited[x][y] = false;
            return true;
        }
    }
    visited[x][y] = false;
    return false;
}
public List<int[]> pacificAtlantic(int[][] matrix) {
    intArrayList = new ArrayList<int[]>();
    if(matrix == null ||matrix.length == 0){
        return intArrayList;
    }
    direction = new int[][]{{-1, 0}, { 0, -1}, {1, 0}, {0, 1}};
    m = matrix.length;
    n = matrix[0].length;
    visited = new boolean[m][n];
    for(int i = 0; i < matrix.length; ++i){
        for(int j = 0; j < matrix[0].length; ++j){
            if(flowToPacific(matrix, i, j) && flowToAtlantic(matrix, i, j)){
               intArrayList.add(new int[]{i, j});
            }
        }
    }
    return intArrayList;
}

51. N-Queens

Example:

1
2
3
4
5
6
7
8
9
10
11
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
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
60
61
62
63
64
65
class Solution {
    private List<List<String>> list2;
    private boolean []col;
    private boolean []dia1;
    private boolean []dia2;
    private List<String> generateBoard(Stack<Integer> rowLine, int n){
        List<String> list = new ArrayList<String>();
        for(int i = 0; i < rowLine.size(); ++i){
            StringBuilder sb = new StringBuilder();
            int y = rowLine.get(i);
            for(int j = 0; j < n; ++j){
                if(y == j){
                    sb.append('Q');
                }
                else{
                    sb.append('.');
                }
            }
            list.add(sb.toString());
        }
        return list;
    }
    private void putQueue(int n, int x, Stack<Integer> rowLine){
        if(n == x){
            list2.add(generateBoard(rowLine, n));
            return;
        }
        for(int y = 0; y < n; ++y){
            if(!col[y] && !dia1[x+y] && ! dia2[x-y+n-1]) {
                rowLine.push(y);
                col[y] = true;
                dia1[x+y] = true;
                dia2[x-y+n-1] = true;
                putQueue(n, x+1, rowLine);
                col[y] = false;
                dia1[x+y] = false;
                dia2[x-y+n-1] = false;
                rowLine.pop();
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        list2 = new ArrayList<List<String>>();
        col = new boolean[n];
        dia1 = new boolean[2*n-1];
        dia2 = new boolean[2*n-1];
        putQueue(n, 0, new Stack<Integer>());
        return list2;
    }
}

52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

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
class Solution {
    private boolean []col;
    private boolean []dia1;
    private boolean []dia2;
    private int res;
    private void putQueensSolutions(int n, int x, Stack<Integer> rowLine){
        if(n == x){
            res += 1;
        }
        
        for(int y = 0; y < n; ++y){
            if(!col[y] && !dia1[x+y] && !dia2[x-y+n-1]){
                col[y] = true;
                dia1[x+y] = true;
                dia2[x-y+n-1] = true;
                putQueensSolutions(n, x+1, rowLine);
                col[y] = false;
                dia1[x+y] = false;
                dia2[x-y+n-1] = false;
            }
        }
    }
    public int totalNQueens(int n){
        col = new boolean[n];
        dia1 = new boolean[2*n-1];
        dia2 = new boolean[2*n-1];
        res = 0;
        putQueensSolutions(n, 0, new Stack<Integer>());
        return res;
    }
}

37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

解题思路:

很脑瓜子疼的一道题目，
想不明白

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
private boolean isValid(char [][]board, int x, int y, char c){
    for(int i = 0; i < board[x].length; ++i){
        //行判断
        if(board[x][i] != '.' && c == board[x][i]){
            return false;
        }
        //列判断
        if(board[i][y] != '.' && c == board[i][y]){
            return false;
        }
        //9宫格判断
        if(board[3*(x/3)+i/3][3*(y/3)+i%3] !='.' &&
                board[3*(x/3)+i/3][3*(y/3)+i%3] == c){
            return false;
        }
    }
    return true;
}
public boolean putNumbers(char[][] board){
    for(int i = 0; i < board.length; ++i){
        for(int j = 0; j < board[0].length; ++j){
            if(board[i][j] == '.'){
                for(char ch = '1'; ch <= '9'; ++ch){
                    if(isValid(board, i, j, ch)){
                        board[i][j] = ch;
                        if(putNumbers(board)){
                            return true;
                        }
                        else{
                            board[i][j] = '.';
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}
public void solveSudoku(char[][] board) {
    if(board == null || board.length == 0){
        return;
    }
    putNumbers(board);
}