算法

回溯深搜广搜题目总结

回溯深搜广搜

Posted by WenlSun" on June 19, 2020

电话号码的字母组合(中等)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。电话号码的字母组合

参考代码

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

vector<string> res;
vector<string> letterCombinations(string digits) {
    if (digits.empty()) return res;
    string path;
    dfs(digits, 0, path);
    return res;
}

void dfs(string& digits, int idx, string& path) {
    if (idx == digits.size()) {
        res.push_back(path);
        return ;
    }
    string s = m[digits[idx]];
    for (auto c : s) {
        path.push_back(c);
        dfs(digits, idx + 1, path);
        path.pop_back();
    }
}

括号生成(中等)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。括号生成

参考代码

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

vector<string> res;
vector<string> generateParenthesis(int n) {
    string path;
    dfs(n, n, path); // 做减法
    return res;
}

void dfs(int l, int r, string& path) {
    if (l == 0 && r == 0) {
        res.push_back(path);
        return;
    }
    if (l > 0) {
        path.push_back('(');
        dfs(l - 1, r, path);
        path.pop_back();
    }
    if (l < r && r > 0) { // 右侧的剩余数量要大于左侧
        path.push_back(')');
        dfs(l, r - 1, path);
        path.pop_back();
    }
}

解数独(困难)

编写一个程序，通过已填充的空格来解决数独问题。解数独

参考代码

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

void solveSudoku(vector<vector<char>>& board) { dfs(board, 0, 0); }

bool dfs(vector<vector<char>>& board, int x, int y) {
    int n = 9, m = 9;
    if (y == m) return dfs(board, x + 1, 0); // 当前行结束，转下一行
    if (x == n) return true; // 到最后一行，完成
    if (board[x][y] != '.') return dfs(board, x, y + 1); // 已有数字，跳到下一个位置
    for (char i = '1'; i <= '9'; i++) { // 依次尝试每一个数字
        if (isValid(board, x, y, i)) {
            board[x][y] = i;
            if (dfs(board, x, y + 1)) return true;
            board[x][y] = '.';
        }
    }
    return false;
}

/**
 * 判断当前数字是否合法
 */
bool isValid(vector<vector<char>>& board, int x, int y, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[x][i] == c) return false;
        if (board[i][y] == c) return false;
        if (board[(x / 3) * 3 + i / 3][(y / 3) * 3 + i % 3] == c)
            return false;
    }
    return true;
}

组合总和(中等)

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

参考代码

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

vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    if (!candidates.size()) return res;
    vector<int> path;
    dfs(candidates, target, 0, path); // 这儿必须要有起始位置
    return res;
}

void dfs(vector<int>& candidates, int target, int idx, vector<int>& path) {
    if (target == 0) {
        res.push_back(path);
        return;
    }
    // 从起始位置开始，前面的数字不能再用了！！！
    for (int i = idx; i < candidates.size(); i++) {
        if (candidates[i] <= target) {
            path.push_back(candidates[i]);
            dfs(candidates, target - candidates[i], i, path);
            path.pop_back();
        }
    }
}

组合总和II(中等)

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。组合总和II

参考代码

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

vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<int> path;
    sort(candidates.begin(), candidates.end()); // 先排序，目的是将相同的数字放在一起方便去重
    dfs(candidates, target, 0, path); // 做减法
    return res;
}

void dfs(vector<int>& candidates, int target, int idx, vector<int>& path) {
    if (target == 0) {
        res.push_back(path);
        return;
    }
    for (int i = idx; i < candidates.size(); i++) {
        if (i > idx && candidates[i] == candidates[i - 1]) continue; // 去重
        if (candidates[i] <= target) { // 如果当前值大于剩余值，则直接剪枝
            path.push_back(candidates[i]);
            dfs(candidates, target - candidates[i], i + 1, path);
            path.pop_back();
        }
    }
}

组合总和III(中等)

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。说明：所有数字都是正整数。 解集不能包含重复的组合。组合总和III

参考代码

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

vector<vector<int>> res;
vector<vector<int>> combinationSum3(int k, int n) {
    vector<int> path;
    dfs(k, n, 1, path); // 做减法
    return res;
}

void dfs(int k, int n, int idx, vector<int>& path) {
    if (k == 0) { // 先判断数字的个数是否满足
        if (n == 0) res.push_back(path); // 如果能凑成就记录答案
        return;
    }
    for (int i = idx; i < 10; i++) {
        if (i <= n) { // 如果当前数字比剩余数字大则剪枝
            path.push_back(i);
            dfs(k - 1, n - i, i + 1, path);
            path.pop_back();
        }
    }
}

全排列(中等)

给定一个 没有重复 数字的序列，返回其所有可能的全排列。全排列

参考代码

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

vector<bool> st; // 需要一个标记数组
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
    st = vector<bool>(nums.size());
    vector<int> path;
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    if (idx == nums.size()) {
        res.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (!st[i]) {
            path.push_back(nums[i]);
            st[i] = true;
            dfs(nums, idx + 1, path);
            path.pop_back();
            st[i] = false;
        }
    }
}

全排列II(中等)

给定一个可包含重复数字的序列，返回所有不重复的全排列。全排列II

参考代码

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

vector<bool> st;
vector<vector<int>> res;
vector<vector<int>> permuteUnique(vector<int>& nums) {
    st = vector<bool>(nums.size());
    sort(nums.begin(), nums.end()); // 先排序，将相同的数字放在一起方便去重
    vector<int> path;
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    if (idx == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        // 去重，这儿！可有可无，有的话剪枝更彻底，因为是按顺序添加进去的
        if (st[i] || (i > 0 && nums[i] == nums[i - 1] && !st[i - 1]))
            continue;
        path.push_back(nums[i]);
        st[i] = true;
        dfs(nums, idx + 1, path);
        path.pop_back();
        st[i] = false;
    }
}

第k个排列(中等)

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。给定 n 和 k，返回第 k 个排列。第k个排列

参考代码

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

int cnt = 0;
string res;
vector<bool> st;
// 回溯效率不高
string getPermutation(int n, int k) {
    st = vector<bool>(n);
    string path;
    string num;
    for (int i = 1; i <= n; i++) num += to_string(i);
    dfs(num, k, 0, path);
    return res;
}

void dfs(string& num, int k, int idx, string& path) {
    if (idx == num.size()) {
        cnt++;
        if (cnt == k) res = path;
        return;
    }
    for (int i = 0; i < num.size(); i++) {
        if (!st[i] && cnt < k) {
            path.push_back(num[i]);
            st[i] = true;
            dfs(num, k, idx + 1, path);
            path.pop_back();
            st[i] = false;
        }
    }
}

// 这个方法高效 双百算法
string getPermutation(int n, int k) {
    vector<int> t;
    for (int i = 1; i <= n; i++) t.push_back(i);
    string ans;
    while (t.size() > 0) {
        int tn = t.size();
        int count = jie(tn - 1);
        tn = (k - 1) / count;
        ans += to_string(t[tn]);
        k = k - count * tn;
        t.erase(t.begin() + tn);
    }
    return ans;
}

int jie(int n) {
    int ans = 1;
    while (n) ans *= n--;
    return ans;
}

// 直接调用库函数
string getPermutation(int n, int k) {
    string nums;
    for (int i = 1; i <= n; i++) nums += to_string(i);
    for (int i = 0; i < k - 1; i++) next_permutation(nums.begin(), nums.end());
    return nums;
}

N皇后(困难)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。N皇后

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
   public:
    /**
     * 依次枚举每一行皇后的位置
     * 1. 每一列只能有一个皇后 col[N]
     * 2. 每条斜线上只能有一个皇后 d[2N] ud[2N] 有2N-1条斜线
     * x+y 表示反向斜线  x-y+n 表示正向斜线  这个很秀！！！
     */
    vector<vector<string>> res;  // 记录所有答案
    vector<string> tmp;          // 记录当前方案
    vector<bool> col, d, ud;     // 列， 正斜线， 反斜线

    vector<vector<string>> solveNQueens(int n) {
        string line(n, '.');  // 当前行
        col = vector<bool>(n);
        d = vector<bool>(2 * n);
        ud = vector<bool>(2 * n);
        dfs(line, 0, n);  // dfs 每一行
        return res;
    }

    void dfs(string& line, int u, int n) {
        // 如果到达最后一行，则记录答案
        if (u == n) {
            res.push_back(tmp);
            return;
        }
        // 遍历每一列
        for (int i = 0; i < n; i++) {
            // 判断当前行能否放置皇后
            if (!col[i] && !d[u + i] && !ud[u - i + n]) {
                line[i] = 'Q';        // 放置皇后
                tmp.push_back(line);  // 添加当前行
                line[i] = '.';        // 新的一行
                col[i] = true, d[u + i] = true, ud[u - i + n] = true;
                dfs(line, u + 1, n);
                col[i] = false, d[u + i] = false, ud[u - i + n] = false;
                tmp.pop_back();
            }
        }
    }
};

N皇后II(困难)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回 n 皇后不同的解决方案的数量。N皇后II

参考代码

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

vector<bool> col, d, ud; // 列，对角线，反对角线
int res = 0;
int totalNQueens(int n) {
    col = vector<bool>(n);
    d = vector<bool>(2 * n);
    ud = vector<bool>(2 * n);
    dfs(n, 0);
    return res;
}

void dfs(int n, int idx) {
    if (idx == n) {
        res++;
        return;
    }
    // 遍历每一列
    for (int i = 0; i < n; i++) {
        // 判断是否符合
        if (!col[i] && !d[idx + i] && !ud[idx - i + n]) {
            col[i] = true, d[idx + i] = true, ud[idx - i + n] = true;
            dfs(n, idx + 1); // dfs下一行
            col[i] = false, d[idx + i] = false, ud[idx - i + n] = false;
        }
    }
}

组合(中等)

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。组合

参考代码

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

vector<vector<int>> res;
vector<vector<int>> combine(int n, int k) {
    vector<int> path;
    dfs(n, k, 1, path);
    return res;
}

void dfs(int n, int k, int idx, vector<int>& path) {
    if (k == path.size()) {
        res.push_back(path);
        return;
    }
     // 这儿构建树的时候前面用过就不再使用
    for (int i = idx; i <= n; i++) {
        path.push_back(i);
        dfs(n, k, i + 1, path);
        path.pop_back();
    }
}

子集(中等)

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。子集

参考代码

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

vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> path;
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    res.push_back(path);
    for (int i = idx; i < nums.size(); i++) {
        path.push_back(nums[i]);
        dfs(nums, i + 1, path);
        path.pop_back();
    }
}

子集II(中等)

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。子集II

参考代码

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

vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // 要去重，先排序
    vector<int> path;
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    res.push_back(path);
    for (int i = idx; i < nums.size(); i++) {
        if (i > idx && nums[i] == nums[i - 1]) continue; // 去重
        path.push_back(nums[i]);
        dfs(nums, i + 1, path);
        path.pop_back();
    }
}

单词搜索(中等)

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。单词搜索

参考代码

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

int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
bool exist(vector<vector<char>>& board, string word) {
    if (!board.size() || !board[0].size()) return false;
    m = board.size(), n = board[0].size();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (board[i][j] == word[0] && dfs(board, i, j, 0, word))
                return true;
    return false;
}

bool dfs(vector<vector<char>>& board, int x, int y, int idx, string& word) {
    if (board[x][y] != word[idx]) return false;
    if (idx == word.size() - 1) return true;
    board[x][y] = '.';
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n) {
            if (dfs(board, a, b, idx + 1, word)) return true;
        }
    }
    board[x][y] = word[idx];
    return false;
}

单词搜索II(中等)

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。单词搜索II

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
vector<vector<bool>> st;
// 回溯法会超时 考虑新的数据结构 前缀树或者叫字典树
vector<string> findWords(vector<vector<char>>& board,
                            vector<string>& words) {
    vector<string> res;
    if (!board.size() || !board[0].size()) return res;
    m = board.size(), n = board[0].size();
    for (auto w : words) {
        st = vector<vector<bool>>(m, vector<bool>(n));
        bool flag = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == w[0] && dfs(board, i, j, 0, w))
                    flag = true;
            }
        }
        if (flag) res.push_back(w);
    }
    return res;
}

bool dfs(vector<vector<char>>& board, int x, int y, int idx,
            string& words) {
    if (board[x][y] != words[idx] || st[x][y]) return false;
    if (idx == words.size() - 1) return true;
    st[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n) {
            if (dfs(board, a, b, idx + 1, words)) return true;
        }
    }
    st[x][y] = false;
    return false;
}

// 使用前缀树结构
// 待完善。。。。

复原IP地址(中等)

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。复原IP地址

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

vector<string> res;
vector<string> restoreIpAddresses(string s) {
    string path;
    dfs(s, 0, 4, path);
    return res;
}

void dfs(string& s, int idx, int nums, string path) {
    if (idx == s.size()) {
        if (nums == 0) {
            path.pop_back(); // 删除最后一个点
            res.push_back(path);
        }
        return;
    }
    // 计算当前块
    for (int i = idx; i < idx + 3; i++) {
        if (i > s.size()) break; // 如果超出界线 剪枝
        if (nums * 3 < s.size() - i) continue; // 如果剩余的超出可能的范围，则为当前块继续添加
        if (isValid(s.substr(idx, i - idx + 1))) { // 如果这个块的地址是合法的，则递归  否则剪枝
            dfs(s, i + 1, nums - 1,
                path + s.substr(idx, i - idx + 1) + '.');
        }
    }
}

bool isValid(string s) {
    if (s.empty() || (s[0] == '0' && s.size() > 1)) return false;
    int val = stoi(s);
    if (val >= 0 && val <= 255) return true;
    return false;
}

累加数(中等)

累加数是一个字符串，组成它的数字可以形成累加序列。一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。给定一个只包含数字 ’0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 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

bool isAdditiveNumber(string num) { return dfs(num, 0, "", "", 0); }

/**
 * idx: 字符串中的位置
 * pre：前一个数字
 * sum: 前面两个数字的和
 * k：第k个数字
 */
bool dfs(string& num, int idx, string sum, string pre, int k) {
    // 如果到字符串末尾，则判断k是否符合条件，即k>2
    if (idx == num.size()) return k > 2;
    // 从当前位置向后遍历，寻找与前两个数字和相等的数字
    for (int i = idx; i < num.size(); i++) {
        string cur = num.substr(idx, i - idx + 1);  // 获取当前数字
        if (idx < i && cur[0] == '0') continue;  // 判断数字是否合法
        // 当前数字与前两个数字和不相等，则剪枝
        if (k >= 2 && cur != sum) continue;
        if (dfs(num, i + 1, add(pre, cur), cur, k + 1)) return true;
    }
    return false;
}

/**
 * 大数相加
 */
string add(string s1, string s2) {
    int carry = 0;
    string res;
    for (int i = s1.size() - 1, j = s2.size() - 1;
            i >= 0 || j >= 0 || carry; i--, j--) {
        int n1 = i < 0 ? 0 : s1[i] - '0';
        int n2 = j < 0 ? 0 : s2[j] - '0';
        int sum = (n1 + n2 + carry) % 10;
        res += to_string(sum);
        carry = (n1 + n2 + carry) / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

计算各个位数不同的数字个数(中等)

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^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

int countNumbersWithUniqueDigits(int n) {
    if (!n) return 1;
    st = vector<bool>(10);
    dfs(n, 0);
    return res;
}

void dfs(int n, int idx) {
    res++;
    if (idx == n) return;
    for (int i = 0; i < 10; i++) {
        if (i == 0 && idx < 1) continue; // 多位时，第一个位置不能为0
        if (!st[i]) {
            st[i] = true;
            dfs(n, idx + 1);
            st[i] = false;
        }
    }
}

/**
 * 找规律
 */
int countNumbersWithUniqueDigits(int n) {
    if (!n) return 1;
    int a = 10, b = 9 * 9;
    for (int i = 2; i <= n; i++) {
        a += b;
        b *= 10 - i;
    }
    return a;
}

二进制手表(简单)

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。二进制手表

参考代码

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

vector<bool> st;
vector<string> res;
typedef pair<int, int> PII;
int m[10] = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
vector<string> readBinaryWatch1(int num) {
    PII t(0, 0);
    dfs(num, t, 0);
    return res;
}

/**
 * 回溯法
 */
void dfs(int num, PII& time, int idx) {
    if (num == 0) {
        if (time.first < 12 && time.second < 60) {
            res.push_back(to_string(time.first) + ":" +
                            (time.second < 10 ? "0" + to_string(time.second)
                                            : to_string(time.second)));
        }
        return;
    }
    for (int i = idx; i < 10; i++) {
        // 剪枝
        if (time.first > 11 || time.second > 59) continue;
        PII t = time; // 记录之前的时刻，以便回溯
        if (i < 4)
            time.first += m[i]; // 计算小时
        else
            time.second += m[i]; // 计算分钟
        dfs(num - 1, time, i + 1);
        time = t;
    }
}

/**
 * 换一种思考方式！！！
 * 直接遍历，然后统计出符合要求的即可  利用统计二进制表示中1的个数的代码模板
 */
vector<string> readBinaryWatch(int num) {
    vector<string> res;
    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 60; j++)
            if (count1(i) + count1(j) == num)
                res.push_back(to_string(i) + ":" +
                                (j < 10 ? "0" + to_string(j) : to_string(j)));

    return res;
}

int count1(int num) {
    int res = 0;
    while (num) {
        res++;
        num = num & (num - 1);
    }
    return res;
}

优美的排列(中等)

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：第 i 位的数字能被 i 整除。i 能被第 i 位上的数字整除。现在给定一个整数 N，请问可以构造多少个优美的排列？优美的排列

参考代码

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

int res = 0;
vector<bool> st; // 用于标记数字是否使用过
int countArrangement(int N) {
    st = vector<bool>(N + 1);
    dfs(N, 1);
    return res;
}

void dfs(int n, int idx) {
    if (idx > n) { // 数字是从1到n的，所以这儿需要大于n
        res++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (i % idx && idx % i) continue; // 如果两个条件都不满足，则剪枝
        if (!st[i]) {
            st[i] = true;
            dfs(n, idx + 1);
            st[i] = false;
        }
    }
}

字母大小写全排列(简单)

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。字母大小写全排列

参考代码

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

vector<string> res;
vector<string> letterCasePermutation(string S) {
    dfs(S, 0);
    return res;
}

void dfs(string& s, int idx) {
    res.push_back(s); // 记录答案
    if (idx == s.size()) return; // 终止条件
    for (int i = idx; i < s.size(); i++) {
        if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
            s[i] = s[i] ^ ' '; // 大小写互换
            dfs(s, i + 1);
            s[i] = s[i] ^ ' ';
        }
    }
}

将数组拆分成斐波拉契数列(中等)

给定一个数字字符串 S，比如 S = “123456579”，我们可以将它分成斐波那契式的序列 [123, 456, 579]。形式上，斐波那契式序列是一个非负整数列表 F，且满足：0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；F.length >= 3；对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回空。将数组拆分成斐波那契序列

参考代码

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

vector<int> res;
typedef long long LL;
vector<int> splitIntoFibonacci(string s) {
    vector<int> path;
    dfs(s, 0, path);
    return res;
}

void dfs(string& s, int idx, vector<int>& path) {
    if (idx == s.size()) {
        // 如果数字大于2 说明符合条件
        if (path.size() > 2) res = path;
        return;
    }
    for (int i = idx; i < s.size(); i++) {
        int n = path.size(); // 当前拆分的数组长度
        string st = s.substr(idx, i - idx + 1); // 获取当前数字对应的字符串
        if (i > idx && st[0] == '0') continue; // 剪枝不合法的，即第一个位置是0的情况
        LL t = stoll(st); // 转数字
        if (t > INT_MAX) break; // 如果当前数字大于 INT_MAX 剪枝
        // 如果前两项的和大于 INT_MAX 剪枝
        if (n > 2 && (LL)path[n - 1] + path[n - 2] > INT_MAX) break;
        // 如果满足条件  则dfs
        if (n < 2 || t == (LL)path[n - 1] + path[n - 2]) {
            path.push_back(t);
            dfs(s, i + 1, path);
            path.pop_back();
        }
    }
}

不同路径III(困难)

在二维网格 grid 上，有 4 种类型的方格：

  • 1 表示起始方格。且只有一个起始方格。
  • 2 表示结束方格，且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。不同路径III

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

int res = 0, m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
/**
 * 回溯法：首先统计0的数量（把1的位置也需要加进去），然后利用零的数量来做dfs
 * 因为每一个零的位置都要走一遍！！！
 */
int uniquePathsIII(vector<vector<int>>& grid) {
    if (!grid.size() || !grid[0].size()) return 0;
    m = grid.size(), n = grid[0].size();
    int cnt = 0, x, y; // 记录0的数量和1的位置
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == 1) //记录1的位置
                cnt++, x = i, y = j;
            else if (grid[i][j] == 0) // 统计0的数量
                cnt++;
    dfs(grid, x, y, cnt); // 从1的位置开始dfs
    return res;
}

void dfs(vector<vector<int>>& grid, int x, int y, int cnt) {
    if (cnt == 0) {
        if (grid[x][y] == 2) res++; // 如果结束位置是2，则说明可以到达，记录答案
        return;
    }
    int t = grid[x][y];
    grid[x][y] = -1;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] != -1)
            dfs(grid, a, b, cnt - 1);
    }
    grid[x][y] = t;
}

正方形数组的数目(困难)

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。正方形数组的数目

参考代码

1

// 待填。。。

活字印刷(中等)

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。注意：本题中，每个活字字模只能使用一次。活字印刷

参考代码

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

int res = 0;
vector<bool> st;
int numTilePossibilities(string tiles) {
    st = vector<bool>(tiles.size());
    sort(tiles.begin(), tiles.end());
    dfs(tiles);
    return res;
}

void dfs(string& tiles) {
    for (int i = 0; i < tiles.size(); i++) {
        if (i > 0 && tiles[i] == tiles[i - 1] && !st[i - 1]) continue; // 去重
        if (!st[i]) {
            st[i] = true;
            res++;
            dfs(tiles);
            st[i] = false;
        }
    }
}

黄金矿工(中等)

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。为了使收益最大化，矿工需要按以下规则来开采黄金： 每当矿工进入一个单元，就会收集该单元格中的所有黄金。矿工每次可以从当前位置向上下左右四个方向走。每个单元格只能被开采（进入）一次。 不得开采（进入）黄金数目为 0 的单元格。矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。黄金矿工

参考代码

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

int res = 0, sum, m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int getMaximumGold(vector<vector<int>>& grid) {
    if (!grid.size() || !grid[0].size()) return 0;
    m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j]) { // 遍历每一个非0的位置开始dfs
                sum = 0;
                dfs(grid, i, j);
            }
    return res;
}

void dfs(vector<vector<int>>& grid, int x, int y) {
    int t = grid[x][y];
    sum += t; // 当前累加和
    res = max(res, sum); // 更新答案
    grid[x][y] = 0;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b])
            dfs(grid, a, b);
    }
    grid[x][y] = t; // 回溯
    sum -= t; // 回溯
}

串联字符串的最大长度(中等)

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。请返回所有可行解 s 中最长长度。串联字符串的最大长度

参考代码

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

int maxLength(vector<string>& arr) { return dfs(arr, 0, 0); }

/**
 * 回溯 + 位压缩
 * idx: 数组中的当前索引
 * m: 表示已经拼接的字符串的字符状态
 */
int dfs(vector<string>& arr, int idx, int m) {
    if (idx == arr.size()) return 0;
    int t = m;  // 记录状态
    // 判断当前字符串中是否有重复字符
    for (auto c : arr[idx]) {
        // 如果有重复字符，则跳过当前字符串，状态使用之前记录的状态
        if (m & (1 << (c - 'a'))) return dfs(arr, idx + 1, t);
        m |= 1 << c - 'a';
    }
    int len = arr[idx].size();  // 当前字符串的长度
    // 对于当前字符串可以选择用，也可选择不用，取两者之间的最大值
    return max(len + dfs(arr, idx + 1, m), dfs(arr, idx + 1, t));
}

铺瓷砖(困难)

被围绕的区域(中等)

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。被围绕的区域

思路：转换为寻找以边界上O开始的连通区域并设置为#

参考代码

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

int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
void solve(vector<vector<char>>& board) {
    if (!board.size() || !board[0].size()) return;
    m = board.size(), n = board[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            bool isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1; // 判断是否是边界
            if (isEdge && board[i][j] == 'O') { // 如果是边界并且是O则dfs
                dfs(board, i, j);
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X'; // 将O换成X
            if (board[i][j] == '#') board[i][j] = 'O'; // 将#换成O
        }
    }
}

void dfs(vector<vector<char>>& board, int x, int y) {
    board[x][y] = '#';
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'O')
            dfs(board, a, b);
    }
}

岛屿数量(中等)

给你一个由 ’1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。岛屿数量

参考代码

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

int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int numIslands(vector<vector<char>>& grid) {
    if (!grid.size() || !grid[0].size()) return 0;
    m = grid.size(), n = grid[0].size();
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') { // 寻找陆地
                res++;
                dfs(grid, i, j); // 将当前陆地区域置为0
            }
        }
    }
    return res;
}

void dfs(vector<vector<char>>& grid, int x, int y) {
    grid[x][y] = '0';
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == '1')
            dfs(grid, 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
44
45
46
47
48
49

vector<string> res;
vector<string> removeInvalidParentheses(string s) {
    int l = 0, r = 0; // 统计需要删除的左括号和右括号的数量
    for (auto c : s) {
        if (c == '(')
            l++;
        else if (c == ')') {
            if (l > 0)
                l--;
            else
                r++;
        }
    }
    dfs(s, 0, l, r);
    return res;
}

void dfs(string& s, int idx, int l, int r) {
    if (l == 0 && r == 0) { // 都删除完了，如果是有效的则记录答案
        if (isValid(s)) res.push_back(s);
        return;
    }
    for (int i = idx; i < s.size(); i++) {
        if (i != idx && s[i] == s[i - 1]) continue; // 去重
        if (s[i] == '(' && l > 0) { // 删除左括号
            string t = s;
            t.erase(i, 1);
            dfs(t, i, l - 1, r);
        }
        if (s[i] == ')' && r > 0) { // 删除右括号
            string t = s;
            t.erase(i, 1);
            dfs(t, i, l, r - 1);
        }
    }
}

// 判断括号是否有效
bool isValid(string s) {
    int cnt = 0;
    for (auto c : s) {
        if (c == '(')
            cnt++;
        else if (c == ')')
            cnt--;
        if (cnt < 0) return false;
    }
    return cnt == 0;
}

矩阵中的最长递增路径(困难)

给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。矩阵中的最长递增路径

参考代码

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

int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
vector<vector<int>> memo; // 使用备忘录的深搜，否则会超时
int longestIncreasingPath(vector<vector<int>>& matrix) {
    if (!matrix.size() || !matrix[0].size()) return 0;
    m = matrix.size(), n = matrix[0].size();
    memo = vector<vector<int>>(m, vector<int>(n));
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = max(res, dfs(matrix, i, j));
        }
    }
    return res;
}

int dfs(vector<vector<int>>& matrix, int x, int y) {
    if (memo[x][y]) return memo[x][y];
    int t = 0;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n &&
            matrix[a][b] > matrix[x][y])
            t = max(t, dfs(matrix, a, b));
    }
    t++;
    memo[x][y] = t;
    return t;
}

重新安排行程(中等)

参考代码

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

vector<string> res; // 记录答案
unordered_map<string, deque<string>> hash; // 键是起点，值是一个双向队列，里面存的是终点
/**
 * 欧拉路径问题 转换变形的成后序遍历
 */
vector<string> findItinerary(vector<vector<string>>& tickets) {
    for (auto t : tickets) hash[t[0]].push_back(t[1]);
    for (auto& item : hash) {
        auto& t = item.second;
        sort(t.begin(), t.end()); // 对队列进行排序
    }
    string st = "JFK";
    dfs(st); // 深搜 类似后序遍历
    reverse(res.begin(), res.end()); // 将遍历结果翻转就是答案
    return res;
}

void dfs(string& s) {
    auto& t = hash[s];
    while (t.size()) { // 先遍历当前结点的孩子
        auto child = t.front();
        t.pop_front(); // 每遍历一次就删除当前孩子结点的边
        dfs(child);
    }
    res.push_back(s); // 最后访问当前结点
}

太平洋大西洋水流问题(中等)

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。太平洋大西洋水流问题

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int m, n;
vector<vector<bool>> st1, st2; // 分别标记大西洋和太平洋逆向访问过的区域
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
/**
 * 逆向想，类似洪水灌溉，就可以从边向里面搜索可以到达的区域，分别从太平洋和大西洋的区域进行搜索，将搜索过的区域分别标记，
 * 如果一个区域同时被两次遍历标记，则该区域可以流向两个洋。
 */
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
    vector<vector<int>> res;
    if (!matrix.size() || !matrix[0].size()) return res;
    m = matrix.size(), n = matrix[0].size();
    st1 = vector<vector<bool>>(m, vector<bool>(n));
    st2 = vector<vector<bool>>(m, vector<bool>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            bool isEdge1 = i == 0 || j == 0; // 太平洋
            bool isEdge2 = i == m - 1 || j == n - 1; // 大西洋
            if (isEdge1) dfs(matrix, i, j, st1); // 从边界向里面逆向搜索
            if (isEdge2) dfs(matrix, i, j, st2); // 从边界向里面逆向搜索
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 同时被访问过位置记录答案
            if (st1[i][j] && st2[i][j]) res.push_back({i, j});
        }
    }
    return res;
}

void dfs(vector<vector<int>>& matrix, int x, int y,
            vector<vector<bool>>& st) {
    st[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n &&
            matrix[a][b] >= matrix[x][y] && !st[a][b])
            dfs(matrix, a, b, st);
    }
}

火柴拼正方形(中等)

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。火柴拼正方形

参考代码

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

vector<bool> st;
bool makesquare(vector<int>& nums) {
    if (!nums.size()) return false;
    sort(nums.begin(), nums.end()), reverse(nums.begin(), nums.end());
    int sum = 0;
    for (auto n : nums) sum += n;
    if (sum % 4) return false;
    st = vector<bool>(nums.size()); // 用于标记边是否被用过
    for (int i = 0; i < 4; i++) { // dfs每条边。
        if (!dfs(nums, 0, sum / 4)) return false;
    }
    return true;
}

bool dfs(vector<int>& nums, int idx, int sum) {
    if (sum == 0) return true; // 如果构成了边，则返回true
    if (idx == nums.size()) return false; // 构不成，返回false
    for (int i = idx; i < nums.size(); i++) {
        if (nums[i] > sum || st[i]) continue; // 如果当前长度大于正方形边的剩余长度，就跳过
        st[i] = true;
        if (dfs(nums, i + 1, sum - nums[i])) return true;
        st[i] = false;
    }
    return false;
}

递增子序列(中等)

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。递增子序列

参考代码

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

vector<vector<int>> res;
vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<int> path;
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    if (path.size() > 1) res.push_back(path);
    unordered_set<int> hash; //用于去重
    for (int i = idx; i < nums.size(); i++) {
        if (hash.count(nums[i])) continue; // 去重
        if (!path.size() || path.back() <= nums[i]) {
            path.push_back(nums[i]);
            hash.insert(nums[i]); // 当前值插入到哈希表
            dfs(nums, i + 1, path);
            path.pop_back();
        }
    }
}

目标和(中等)

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。目标和

参考代码

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

int res = 0;
int findTargetSumWays(vector<int>& nums, int s) {
    int cur = 0;
    dfs(nums, 0, cur, s);
    return res;
}

void dfs(vector<int>& nums, int idx, int cur, int s) {
    if (idx == nums.size()) {
        if (s == cur) res++;
        return;
    }
    dfs(nums, idx + 1, cur + nums[idx], s);
    dfs(nums, idx + 1, cur - nums[idx], s);
}

/**
 * 动态规划 转换成0-1背包问题
 * 设正数的子集为P，负数的子集为N，所以要使sum(p)-sum(N)=S，两边同时加上sum(P)+sum(N)==>2sum(p)=S+sum(nums)
 * 所以sum(P) = (S+sum(nums))/2; 问题转换为寻找和为P的方案数
 */
int findTargetSumWays(vector<int>& nums, int s) {
    if (!nums.size()) return 0;
    int w = 0;
    for (auto n : nums) w += n;
    if (w < s || (s + w) % 2) return 0;
    int p = (s + w) / 2; // 相当于背包容量
    vector<int> dp(p + 1);
    dp[0] = 1;
    for (auto n : nums)
        for (int j = p; j >= n; j--) dp[j] += dp[j - n];
    return dp[p];
}

扫雷游戏(中等)

给定一个代表游戏板的二维字符矩阵。 ’M’ 代表一个未挖出的地雷，’E’ 代表一个未挖出的空方块，’B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（’1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，’X’ 则表示一个已挖出的地雷。现在给出在所有未挖出的方块中（’M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ’X’。如果一个没有相邻地雷的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的方块都应该被递归地揭露。如果一个至少与一个地雷相邻的空方块（’E’）被挖出，修改它为数字（’1’到’8’），表示相邻地雷的数量。如果在此次点击中，若无更多方块可被揭露，则返回面板。扫雷游戏

参考代码

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

int m, n;
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1},
    dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
vector<vector<char>> updateBoard(vector<vector<char>>& board,
                                    vector<int>& click) {
    m = board.size(), n = board[0].size();
    dfs(board, click[0], click[1]);
    return board;
}

void dfs(vector<vector<char>>& board, int x, int y) {
    if (board[x][y] == 'E') { //如果是E
        board[x][y] = 'B'; // 先标记为B
        int cnt = judge(board, x, y); // 统计当前位置相邻的雷的数量
        if (cnt == 0) { // 如果雷的数量为零，则dfs
            for (int i = 0; i < 8; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < m && b >= 0 && b < n) dfs(board, a, b);
            }
        } else // 否则标记当前位置为雷的数量
            board[x][y] = cnt + '0';
    } else if (board[x][y] == 'M') // 如果是雷M
        board[x][y] = 'X'; // 设置标记为X
}

// 统计当前位置相邻雷的数量
int judge(vector<vector<char>>& board, int x, int y) {
    int cnt = 0;
    for (int i = 0; i < 8; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'M') cnt++;
    }
    return cnt;
}

变身程序员-多源最短路径问题

公司的程序员不够用了，决定把产品经理都转变为程序员以解决开发时间长的问题。在给定的矩形网格中，每个单元格可以有以下三个值之一：值0代表空单元格;值1代表产品经理;值2代表程序员;每分钟，任何与程序员(在4个正方向上)相邻的产品经理都会变成程序员。返回直到单元格中没有产品经理为止所必须经过的最小分钟数。如果不可能，返回-1。

思路：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
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

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

typedef pair<int, int> PII;  // 存储位置

int n, m;
int g[N][N];     // 分布
int dist[N][N];  // 距离

int bfs() {
    queue<PII> que;
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 2) {
                dist[i][j] = 0;
                que.push({i, j}); // 所有源点入队
            }
        }
    }
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while (que.size()) {
        auto t = que.front();
        que.pop();
        int x = t.first, y = t.second;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 1 &&
                dist[a][b] == -1) {
                dist[a][b] = dist[x][y] + 1;
                que.push({a, b});
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 1) {
                if (dist[i][j] == -1) return -1;
                res = max(res, dist[i][j]);
            }
        }
    }
    return res;
}

int main() {
    // 不定长读取！！！
    string line;
    while (getline(cin, line)) {
        int k = 0;
        stringstream ssin(line);
        while (ssin >> g[n][k]) k++;
        m = k;
        n++;
    }
    cout << bfs() << endl;
}

01矩阵-多源最短路径问题(中等)

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。01矩阵

思路：首先把每个源点 0 入队，然后从各个 0 同时开始一圈一圈的向 1 扩散（每个 1 都是被离它最近的 0 扩散到的 ），扩散的时候可以设置int[][] dist 来记录距离（即扩散的层次）并同时标志是否访问过。对于本题是可以直接修改原数组 int[][] matrix 来记录距离和标志是否访问的，这里要注意先把 matrix 数组中 1 的位置设置成 -1 （设成INT_MAX啦，m * n啦，10000啦都行，只要是个无效的距离值来标志这个位置的 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

typedef pair<int, int> PII;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
// bfs 多源最短路径问题
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    queue<PII> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                q.push({i, j}); // 源点入队
            } else
                matrix[i][j] = -1; // 1的位置用-1来表示未访问
        }
    }
    while (q.size()) {
        auto t = q.front(); // 访问结点
        q.pop();
        int x = t.first, y = t.second;
        // 访问当前结点的周围一圈
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && matrix[a][b] == -1) {
                matrix[a][b] = matrix[x][y] + 1; // 更新距离
                q.push({a, b}); // 周围结点入队
            }
        }
    }
    return matrix;
}

地图分析-多源最短路径问题(中等)

你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。如果我们的地图上只有陆地或者海洋，请返回 -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

typedef pair<int, int> PII;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int maxDistance(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<PII> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) q.push({i, j});  // 所有陆地作为源点，入队
        }
    }
    if (q.empty() || q.size() == m * n) return -1; // 如果全是陆地或者海洋，返回-1
    PII t;
    while (q.size()) {
        t = q.front(); // 取出队列元素
        q.pop();
        int x = t.first, y = t.second;
        // 遍历四周的海洋
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 0) {
                grid[a][b] = grid[x][y] + 1; // 这里直接修改了原数组，因此就不需要额外的数组来标志是否访问
                q.push({a, b}); // 将四周的海洋入队
            }
        }
    }
    return grid[t.first][t.second] - 1; // 返回最后一次遍历到的海洋的距离。
}

员工的重要性(简单)

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。员工的重要性

参考代码

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

class Employee {
   public:
    int id;
    int importance;
    vector<int> subordinates;
};

class Solution {
   public:
    int getImportance(vector<Employee*> employees, int id) {
        int res = 0;
        for (int i = 0; i < employees.size(); i++) {
            if (employees[i]->id == id) {
                res += employees[i]->importance;
                for (auto nid : employees[i]->subordinates) {
                    res += getImportance(employees, nid);
                }
            }
        }
        return res;
    }
};

岛屿的最大面积(中等)

给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)岛屿的最大面积

参考代码

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

int m, n, cnt = 0;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int maxAreaOfIsland(vector<vector<int>>& grid) {
    if (!grid.size() || !grid[0].size()) return 0;
    m = grid.size(), n = grid[0].size();
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                cnt = 0;
                dfs(grid, i, j);
                res = max(res, cnt);
            }
        }
    }
    return res;
}

void dfs(vector<vector<int>>& grid, int x, int y) {
    cnt++;
    grid[x][y] = 0;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b])
            dfs(grid, a, b);
    }
}

网络延迟时间(中等)

有 N 个网络节点，标记为 1 到 N。给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -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

vector<vector<int>> g;
vector<int> dist;
vector<bool> st;
int INF = 100000000;
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    g = vector<vector<int>>(N + 1, vector<int>(N + 1, INF)); // 存储图
    dist = vector<int>(N + 1, INF); // 存储到起点的距离
    st = vector<bool>(N + 1); // 标记结点是否被访问
    for (auto t : times) {
        g[t[0]][t[1]] = t[2];
    }
    dijkstra(K, N);
    int res = 0;
    for (int i = 1; i <= N; i++) res = max(res, dist[i]);
    return res == INF ? -1 : res;
}
// dijsktra版本
void dijkstra(int k, int n) {
    dist[k] = 0;
    for (int i = 0; i < n; i++) {
        int idx = -1, mind = INF;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && dist[j] < mind) {
                idx = j, mind = dist[j];
            }
        }
        st[idx] = true;
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[idx] + g[idx][j]);
        }
    }
}
FEATURED TAGS
笔记 算法 Object Detection 算法模板 pytorch 笔经 动态规划 面经 面试题 C++ Vim
FRIENDS