单词搜索(中等题) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。


示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

采用回溯的思想，每匹配一个字母，在周围（上下左右）找一个接下来的字母，如果不匹配返回上层重新查找

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
79
80
81

public class FindWordInBoard {
    public static void main(String[] args) {

//        char board[][] = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        String word = "SEE";
//        char board[][]={{'a','a'}};
//        String word="a";
//        char board[][]={{'a','a','a','a'},
//                        {'a','a','a','a'},
//                        {'a','a','a','a'},
//                        {'a','a','a','a'},
//                        {'a','a','a','b'}};
//        String word="aaaaaaaaaaaaaaaaaaaa";

        char board[][]={{'A','B','C','E'},
                        {'S','F','E','S'},
                        {'A','D','E','E'}};
        String word="ABCESEEEFS";

        boolean flag = exist(board, word);
        System.out.println(flag);
    }

    public static boolean exist(char[][] board, String word) {

        int road[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        if(word.length()>board.length*board[0].length){//如果字符的长度大于棋盘中所有元素的数量，那么一定不匹配
            return false;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if(word.length()==1){//如果单词只有一个字母，并且存在一个匹配，那么匹配
                        return true;
                    }
                    boolean[][] flags = new boolean[board.length][board[0].length];
                    flags[i][j]=true;//设置棋盘i,j位置已经遍历过
                    boolean flag = findPath(board, word, i, j, road, 1, flags);
                    if (flag) {//下层都匹配，本层也匹配，那么完全匹配
                        return true;
                    }

                }
            }
        }

        return false;
    }

    public static boolean findPath(char[][] board, String word, int i, int j, int[][] road, int cur, boolean[][] flags) {
        int max_i = board.length;
        int max_j = board[0].length;
        if(cur>=word.length()){//如果超出了单词的长度，直接终止
            return false;
        }
        for (int r = 0; r < 4; r++) {//向上下左右四个方向查找匹配的字母
            int x = i + road[r][0];
            int y = j + road[r][1];
            if (x < max_i && y < max_j && x >= 0 && y >= 0 && flags[x][y] == false) {//如果坐标有效并且没被占用

                if (board[x][y] == word.charAt(cur)) {//如果匹配
                    flags[x][y] = true;
                    if (cur == word.length() - 1) {//如果当前匹配已经是最后一个字母匹配，那么已经完全匹配字符串
                        return true;
                    }
                    boolean flag = findPath(board, word, x, y, road, cur + 1, flags);
                    if (flag) {
                        return true;
                    } else {
                        flags[x][y]=false;//如果当前的坐标没有匹配成功，清空已经占用的字母
                    }
                }
            }
        }
        return 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
class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}


评论区效率比较高的一种写法

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

class Solution {

    private char[][] mat;

    private int n, m;

    private int[] dx = new int[]{-1, 0, 1, 0};

    private int[] dy = new int[]{0, 1, 0, -1};

    private boolean[][] used;

    public boolean exist(char[][] board, String word) {
        n = board.length;
        m = board[0].length;
        mat = board;
        used = new boolean[n][m];
        char[] chars = word.toCharArray();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                boolean ans = dfs(chars, 0, i, j);
                if (ans) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[] word, int index, int i, int j) {
        if (index >= word.length) return true;
        if (!isOK(i, j) || used[i][j] || mat[i][j] != word[index]) return false;
        used[i][j] = true;
        boolean ans = false;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            ans |= dfs(word, index + 1, x, y);
            if (ans) break;
        }
        used[i][j] = false;
        return ans;
    }

    private boolean isOK(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < m;
    }
}

展开全文 >>

二叉树的深度和广度遍历 

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

import java.util.ArrayDeque;


class BinaryTree {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    TreeNode root;

    public BinaryTree(int[] array) {
        root = makeBinaryTreeByArray(array, 1);
    }

    /**
     * 采用递归的方式创建一颗二叉树
     * 传入的是二叉树的数组表示法
     * 构造后是二叉树的二叉链表表示法
     */
    public static TreeNode makeBinaryTreeByArray(int[] array, int index) {
        if (index < array.length) {
            int value = array[index];
            if (value != 0) {
                TreeNode t = new TreeNode(value);
                array[index] = 0;
                t.left = makeBinaryTreeByArray(array, index * 2);
                t.right = makeBinaryTreeByArray(array, index * 2 + 1);
                return t;
            }
        }
        return null;
    }

    /**
     * 深度优先遍历，相当于先根遍历
     * 采用非递归实现
     * 需要辅助数据结构：栈
     */
    public void depthOrderTraversal() {
        if (root == null) {
            System.out.println("empty tree");
            return;
        }
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        stack.push(root);
        while (stack.isEmpty() == false) {
            TreeNode node = stack.pop();
            System.out.print(node.value + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.print("\n");
    }

    /**
     * 广度优先遍历
     * 采用非递归实现
     * 需要辅助数据结构：队列
     */
    public void levelOrderTraversal() {
        if (root == null) {
            System.out.println("empty tree");
            return;
        }
        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.add(root);
        while (queue.isEmpty() == false) {
            TreeNode node = queue.remove();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        System.out.print("\n");
    }

    /**
     * 13
     * / \
     * 65 5
     * / \ \
     * 97 25 37
     * / /\ /
     * 22 4 28 32
     */
    public static void main(String[] args) {
        int[] arr = {0, 13, 65, 5, 97, 25, 0, 37, 22, 0, 4, 28, 0, 0, 32, 0};
        BinaryTree tree = new BinaryTree(arr);
        tree.depthOrderTraversal();
        tree.levelOrderTraversal();
    }
}


参考文献

DFS（深度优先搜索）和BFS(广度优先搜索)

展开全文 >>

二叉树的层平均值（简单） 

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
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

 

示例 1：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 

提示：

节点值的范围在32位有符号整数范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        
        List<Double> ans = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> oneLevel = new ArrayList<>();
            int count = queue.size();

            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                oneLevel.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            double sum = 0;
            for (Integer val : oneLevel) {
                sum += val;
            }
            double avg = sum / oneLevel.size();
            ans.add(avg);
        }
        return ans;

    }



}


评论区高效一点的解法

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (list.size() != 0){
            int len = list.size();
            double sum = 0;
            for (int i = 0; i < len; i++){
                TreeNode node = list.poll();
                sum += node.val;
                if (node.left != null) list.add(node.left);
                if (node.right != null) list.add(node.right);
            }
            res.add(sum/len);
        }
        return res;
    }
}

展开全文 >>

组合总和3(中等题)

216. 组合总和 III

难度中等275

找出所有相加之和为 n 的 k\ 个数的组合。\组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

1
2
输入: k = 3, n = 9
输出: [[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
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
class Solution {
    private List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {

        int maxCyc=n>9?9:n;
        int[] candidates=new int[maxCyc+1];
        boolean[] flags=new boolean[maxCyc+1];
        List<Integer> tempList=new ArrayList<>();//临时列表
        List<Integer> indexList=new ArrayList<>();//每个数字只能使用一次

        for(int i=0;i<maxCyc;i++){
            candidates[i]=i+1;
        }
        calc(candidates,k,n,flags,tempList,indexList,0,0);

        return ans;
    }

     public Integer calc(int[] candidates,int k, int target,boolean[] flags, List<Integer> tempList,
                               List<Integer> indexList,int start,int layer){

        if(layer>k){//超出层数，终止
            return target+1;
        }

        int sum=0;
        for(Integer val:tempList){
            sum+=val;
        }

        if(sum<target&& layer==k){//已经满足层数了，但是和还是小于，直接终止，换掉最后一个数字
            return target+1;
        }

        if(sum>=target){//无需继续算
            return sum;
        }
        for(int i=start;i<candidates.length;i++) {
            if (!flags[i]) {
                tempList.add(candidates[i]);
                flags[i] = true;
                indexList.add(i);
            } else {
                continue;
            }

            Integer val = calc(candidates, k,target, flags, tempList, indexList, i,layer+1);
            if (val == target) {
                List<Integer> tempAns = new ArrayList<>(tempList);//容器复制
                if(layer+1==k&&!ans.contains(tempAns)){//因为和是layer+1层的，判断layer+1是否满足k层，并且没有重复
                    ans.add(tempAns);
                }
            }

            tempList.remove(tempList.size() - 1);//移除上个轮次用的数字
            flags[indexList.get(indexList.size() - 1)] = false;//移除上个占用的数字
            indexList.remove(indexList.size() - 1);//坐标也移除，与上面对应
        }
        return target+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

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> list = new ArrayList<>();
        dfs(k,1,n,list);
        return lists;
    }
    
    public void dfs(int k,int index,int target,List<Integer> list){
        if(target == 0 && k == 0){
            lists.add(new ArrayList<Integer>(list));
            return;
        }
        if(target < index || k <= 0){
            return;
        }
        for(int i = index;i <= 9;i++){
            list.add(i);
            dfs(k-1,i+1,target-i,list);
            list.remove(list.size()-1);
        }
    }
}

组合枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, 9, k, n);
        return ans;
    }

    public void dfs(int cur, int n, int k, int sum) {
        if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
            return;
        }
        if (temp.size() == k) {
            int tempSum = 0;
            for (int num : temp) {
                tempSum += num;
            }
            if (tempSum == sum) {
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
        }
        temp.add(cur);
        dfs(cur + 1, n, k, sum);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k, sum);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/combination-sum-iii/solution/zu-he-zong-he-iii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

组合总和2（中等题）

40. 组合总和 II

难度中等516收藏分享切换为英文接收动态反馈

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

暴力解法

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
class Solution {
    private List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> tempList=new ArrayList<>();
        List<Integer> indexList=new ArrayList<>();//保存的下标去重的临时下标
        Arrays.sort(candidates);
        boolean[] flags=new boolean[candidates.length];//去重标识
        calc(candidates, target,flags,tempList,indexList,0);
        return ans;
    }

    public Integer calc(int[] candidates, int target,boolean[] flags, List<Integer> tempList,List<Integer> indexList,int start){

        int sum=0;
        for(Integer val:tempList){
            sum+=val;
        }

        if(sum>=target){//如果和已经大于或等于，没必要继续添加其他数字进来
            return sum;
        }

        for(int i=start;i<candidates.length;i++) {//继续添加数字进来
            if (!flags[i]) {
                tempList.add(candidates[i]);
                flags[i] = true;
                indexList.add(i);
            } else {
                continue;
            }

            Integer val = calc(candidates, target, flags, tempList, indexList, i);
            if (val == target) {
                List<Integer> tempAns = new ArrayList<>(tempList);
                if(!ans.contains(tempAns)){//如果与以前的没有重复，继续添加，如果出现重复，则不再添加
                    ans.add(tempAns);
                }
            }

            //本层完成后，移除上个轮次用到的数字
            tempList.remove(tempList.size() - 1);
            flags[indexList.get(indexList.size() - 1)] = false;
            indexList.remove(indexList.size() - 1);
        }
        return target+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
class Solution {

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, new ArrayList<>(), 0, target);
        return res;
    }

    private void dfs(int[] candidates, List<Integer> path, int index, int target) {
        if(target < 0) return;

        if(target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i-1]) continue;
            path.add(candidates[i]);
            dfs(candidates, path, i+1, target-candidates[i]);
            path.remove(path.size()-1);
        }
    }
}

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/zu-he-zong-he-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

组合总和（中等题）

39. 组合总和

难度中等1200

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

1
2
3
4
5
6
7
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

自己做的暴力算法

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>> ans=new ArrayList<>(); //存储答案列表

    public  List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> tempList=new ArrayList<>();
        calc(candidates, target,tempList,0);
        return ans;
    }

    public Integer calc(int[] candidates, int target, List<Integer> tempList,int start){

        int sum=0;
        for(Integer val:tempList){//计算当前已经加入的和
            sum+=val;
        }

        if(sum>=target){//如果和已经大于目标了，返回
            return sum;
        }

        for(int i=start;i<candidates.length;i++){
            tempList.add(candidates[i]);
            Integer val=test(candidates,target,tempList,i);

            if(val==target){
                List<Integer> tempAns=new ArrayList<>(tempList);
                ans.add(tempAns);
            }
            tempList.remove(tempList.size()-1);
        }


        return target+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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> listAll=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<Integer>();
        //排序
        Arrays.sort(candidates);
        find(listAll,list,candidates,target,0);
        return listAll;
    }
    public void find(List<List<Integer>> listAll,List<Integer> tmp,int[] candidates, int target,int num){
        //递归的终点
        if(target==0){
            listAll.add(tmp);
            return;
        } 
        if(target<candidates[0]) return;
        for(int i=num;i<candidates.length&&candidates[i]<=target;i++){
            //拷贝一份，不影响下次递归
            List<Integer> list=new ArrayList<>(tmp);
            list.add(candidates[i]);
            //递归运算，将i传递至下一次运算是为了避免结果重复。
            find(listAll,list,candidates,target-candidates[i],i);
        }   
    } 
}


展开全文 >>

组合问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

学习评论区大佬的解法

根据排列组合的性质$C_{m}^{n}=C_{m-1}^{n}+C_{m-1}^{n-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

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if(k>n){
            return null;
        }
        if(k==1){//k等于1时直接返回每个数字
            List<List<Integer>> answer=new ArrayList<>();
            for(int i=1;i<=n;i++){
                List<Integer> tList=new ArrayList<>();
                tList.add(i);
                answer.add(tList);
            }
            return answer;
        }
        if(k==n){//k等于n时直接返回所有数字
            List<List<Integer>> answer=new ArrayList<>();
            List<Integer> tList=new ArrayList<>();
            for(int i=1;i<=n;i++){
                tList.add(i);
            }
            answer.add(tList);
            return answer;
        }
        // 根据排列组合的性质
        List<List<Integer>> answer = combine(n-1,k);
        List<List<Integer>> answer1 = combine(n-1,k-1);

        for(List<Integer> list:answer1){
            list.add(n);
            answer.add(list);
        }
    return answer;
    }


}

另一个评论区大佬的解法

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>> lss = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combine(int n, int k) {
        if(n < 1 || k == 0) return lss;
        dfs(n, k, 0);
        return lss;
    }

    private void dfs(int n, int k, int start){
        if(k == 0){//k==0时，所有的数都选完了
            lss.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = start + 1; i <= n; ++i){
            if(n - i < k-1) break;//如果当前的元素不能凑够k-1个值，直接跳出
            temp.add(i);
            dfs(n, k - 1, i);//从当前位置选，第k-1个元素
            temp.remove(temp.size() - 1);
        }
    }


}

官方解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

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

    public void dfs(int cur, int n, int k) {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.size() == k) {
            ans.add(new ArrayList<Integer>(temp));
            return;
        }
        // 考虑选择当前位置
        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/combinations/solution/zu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考
评论区

展开全文 >>

二叉树自底向上的层次遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

想出来的方法不太聪明的样子，2ms效率很低

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

public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();

    Map<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>(
            new Comparator<Integer>() {
                public int compare(Integer obj1, Integer obj2) {
                    // 降序排序
                    return obj2.compareTo(obj1);
                }
            });

    Integer val = layerTrace(root, 0, map);
    if (val != null) {
        if (map.containsKey(0)) {
            map.get(0).add(val);
        } else {

            map.put(0, Arrays.asList(val));
        }
    }


    for(Map.Entry set:map.entrySet()){
        list.add((List<Integer>) set.getValue());
    }


    return list;
}

public static Integer layerTrace(TreeNode root, int depth, Map<Integer, List<Integer>> map) {
    if (null != root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        depth=depth+1;
        Integer left = layerTrace(root.left, depth, map);
        Integer right = layerTrace(root.right, depth, map);

        if (left != null) {
            if (map.containsKey(depth)) {
                map.get(depth).add(left);
            } else {
                List<Integer> list=new ArrayList<>();
                list.add(left);
                map.put(depth, list);
            }
        }

        if (right != null) {
            if (map.containsKey(depth)) {
                map.get(depth).add(right);
            } else {
                List<Integer> list=new ArrayList<>();
                list.add(right);
                map.put(depth, list);
            }
        }

        return root.val;
    } else {
        return null;
    }
}


大佬的写法，1ms效率比较高

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

public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> result = new LinkedList<>();
    if (root == null)
        return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> oneLevel = new ArrayList<>();
        // 每次都取出一层的所有数据
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            TreeNode node = queue.poll();//每次把队列中最前面的拿出来
            oneLevel.add(node.val);
            if (node.left != null)
                queue.add(node.left);//将左子树入队
            if (node.right != null)
                queue.add(node.right);//将右子树入队
        }
        // 每次都往队头塞，最后添加进去的最先拿出来（有点像栈了）
        result.addFirst(oneLevel);
    }
    return result;
}

展开全文 >>

n皇后问题 

1
n 皇后问题研究的是如何将 n 个皇后放置在 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

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 
示例：

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
 

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

import java.util.*;

public class NQueue {
    public static void main(String[] args) {

        System.out.println(solveNQueens(4));
    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }
    // 回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。
    // 每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，
    // 并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。
    // 当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。

    public static void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {//每次结束时自动将结果存储
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) {                       //对列循环
                if (columns.contains(i)) {                      //列已经出现过了
                    continue;
                }
                //方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，
                // 例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。
                // 因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

                int diagonal1 = row - i;                        //同一斜线上行减列之差相同
                if (diagonals1.contains(diagonal1)) {           //斜线方向上已经出现了
                    continue;
                }
                //方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，
                // 例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。
                // 因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

                int diagonal2 = row + i;                        //同一条反斜线上行加列之和相同
                if (diagonals2.contains(diagonal2)) {           //反向斜线方向上已经出现了
                    continue;
                }

                queens[row] = i;                                //上述条件都满足，在第row行第i列放置皇后
                columns.add(i);                                 //本列不能再放置
                diagonals1.add(diagonal1);                      //这个斜线方向上不能再放置
                diagonals2.add(diagonal2);                      //反斜线方向上不能再放置
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);//递归下一行放置
                //已经完成了一次满足条件的放置，清空限制条件，开始下一轮
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public static List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';//放置皇后
            board.add(new String(row));
        }
        return board;
    }
}


展开全文 >>

刷题反思 

1
2
3
4
5
6
解题思路不够清晰，疲于应付检测点的测试样例，导致代码混乱，最后解题思路步明确，
问题难以解决。

刷题前考虑清楚解题的思路，思路清晰了再去做题，否则难以有进步。


展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走