LeetCode 八周 - 搜索专题 - 《算法学习笔记》

搜索

单词搜索 https://leetcode-cn.com/problems/word-search/

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int mm[4][2] = {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
        };
        function<bool (int, int, int)> f = [&](int row, int col, int pos) {
            if (board[row][col] != word[pos]) return false;
            if (pos == word.size() - 1) return true;
            board[row][col] = '#';
            for (int i = 0; i < 4; i++) {
                int new_row = row + mm[i][0];
                int new_col = col + mm[i][1];
                if (new_row >= 0 && new_row < board.size() && new_col >= 0 && new_col < board[0].size() && f(new_row, new_col, pos + 1)) return true;
            }
            board[row][col] = word[pos];
            return false;
        };
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[i].size(); j++)
                if (f(i, j, 0)) return true; 
        return false;
    }
};

普通的搜索

全排列 https://leetcode-cn.com/problems/permutations/

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<bool> vis(nums.size(), false);
        // 定义为 void (vector<int> & vec, int cnt)
        function<void (vector<int>&)> dfs = [&](vector<int> & vec) {
            if (vec.size() == nums.size()) {
                ans.push_back(vec);
                return;
            }
            for (int i = 0; i < nums.size(); i++) {
                if (!vis[i]) {
                    vis[i] = true;
                    vec.push_back(nums[i]);
                    dfs(vec);
                    vec.pop_back();
                    vis[i] = false;
                }
            }
        };
        vector<int> tmp;
        dfs(tmp);
        return ans;
    }
};

对于每个位置，枚举数字

全排列 II https://leetcode-cn.com/problems/permutations-ii/

class Solution {
public:
    int n;
    vector<bool> vis;
    vector<int> path;
    vector<vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        sort(nums.begin(), nums.end());
        vis = decltype(vis)(n, false);
        path = decltype(path)(n);
        dfs(nums, 0, 0);
        return ans;
    }
    void dfs(vector<int>& nums, int num_pos, int start_pos) {
        if (num_pos == n) {
            ans.push_back(path);
            return;
        }
        for (int i = start_pos; i < n; i++) {
            if (!vis[i]) {
                vis[i] = true;
                path[i] = nums[num_pos];
                dfs(nums, num_pos + 1, num_pos + 1 < n && nums[num_pos] == nums[num_pos + 1] ? i + 1 : 0);
                vis[i] = false;
            }
        }
    }
};

对于每个数字，枚举位置
去重：对于相等的元素，如 x y z，保证相同元素的相对大小不发生变化
排序 + 多穿个变量 start_pos

下一个排列 https://leetcode-cn.com/problems/next-permutation/

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int pos = n - 1;
        for (; pos && nums[pos] <= nums[pos - 1]; pos--);
        reverse(nums.begin() + pos, nums.end());
        if (pos) {
            int i = pos;
            for (; i < n && nums[i] <= nums[pos - 1]; i++);
            swap(nums[i], nums[pos - 1]);
        }
    }
};

递增，让后面枚举的，大于前面的
每次都增加的尽可能少
从后往前找到一个小的值 a[pos - 1]，即第一个破坏从后往前升序的值
将 pos, end 反转，让其变成从 pos + 1 到 end 的升序
从 pos, end 找一个值 a[i]，然后 swap(a[pos], a[i])，这样就保证了每次尽可能少

需要注意，pos 要大于0，如果 pos = 0，即该序列已经是最大序列，直接反转即可

子集 https://leetcode-cn.com/problems/subsets/

class Solution {
public:
    vector<vector<int>> ans;
    bitset<32> b;
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>>ans;
        for (int i = 0; i < 1 << n; i++) {
            b = i;
            vector<int> vec;
            for (int i = 0; i < n; i++) if (b[i]) vec.push_back(nums[i]);
            ans.push_back(vec);
        }
        return ans;
    }
    vector<vector<int>> f2(vector<int> & nums) {
        int n = nums.size();
        vector<vector<int>>ans;
        for (int val = 0; val < 1 << n; val++) {
            vector<int> vec;
            for (int j = 0; j < n; j++)
                if (val >> j & 1) vec.push_back(nums[j]);
            ans.push_back(vec);
        }
        return ans;
    }
    void dfs(vector<int> & nums, int pos, vector<int> & vec) {
        if (pos == nums.size()) {
            ans.push_back(vec);
            return;
        }
        dfs(nums, pos + 1, vec);
        vec.push_back(nums[pos]);
        dfs(nums, pos + 1, vec);
        vec.pop_back();
    }
};

递归做法比较容易
非递归做法可以做个常数优化，即每个值只有选或不选两种状态，利用二进制枚举，然后根据二进制值构造序列

子集 II https://leetcode-cn.com/problems/subsets-ii/

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ans;
    }
    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }

        int k = 0;
        while (u + k < nums.size() && nums[u + k] == nums[u]) k++;
        for (int i = 0; i <= k; i++) {
            dfs(nums, u + k);
            path.push_back(nums[u]);
        }
        for (int i = 0; i <= k; i++) path.pop_back();
    }
};

枚举每个元素的出现次数
和全排列二类似，先进行排序，然后对整个序列进行枚举
但因为排过序了，所以相同值挤在一起，算出相同值个数 k 后，在[0, k] 之间枚举

组合总和 III https://leetcode-cn.com/problems/combination-sum-iii/

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> vec;
    int n, k;
    vector<vector<int>> combinationSum3(int k, int n) {
        this->n = n;
        this->k = k;
        dfs(0, 0, 1);
        return ans;
    }
    void dfs(int sum, int cnt, int startpos) {
        if (cnt == k) {
            if (sum == n) ans.push_back(vec);
            return;
        }
        for (int i = startpos; i <= 10 - k + cnt; i++) {
            vec.push_back(i);
            dfs(sum + i, cnt + 1, i + 1);
            vec.pop_back();
        }
    }
};

枚举每个位置的每个数，记录总和
去重：保证后面的数比前面大

N皇后 II https://leetcode-cn.com/problems/n-queens-ii/

class Solution {
public:
    int ans;
    int n;
    vector<bool> cols, d, rd;
    int totalNQueens(int _n) {
        n = _n;
        cols = vector<bool>(n);
        d = rd = vector<bool>(2 * n);
        dfs(0);
        return ans;
    }
    void dfs(int u) {
        if (u == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!cols[i] && !d[u + i] && !rd[u - i + n]) {
                cols[i] = d[u + i] = rd[u - i + n] = true;
                dfs(u + 1);
                cols[i] = d[u + i] = rd[u - i + n] = false;
            }
        }
    }
};

因为每一行，每一列，每一个正反对角线只能有 1 个皇后
枚举 n 行的每一列（压缩成一维的），然后再利用三个数组，col, d, rd 记录每一列，每一个正对角线，每一个反对角线的使用情况
d[u + i] 和 rd[u - i + n] 怎么得来的？
正对角线是 y = x + b，b = y - x
反对角线是 y = -x + b, b = y + x
然后为了防止负数，将值域右移 n

N皇后 https://leetcode-cn.com/problems/n-queens/

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> vec;
    vector<bool> d, rd, cols;
    int n;
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        string tmp;
        for (int i = 0; i < n; i++) tmp.push_back('.');
        for (int i = 0; i < n; i++) vec.push_back(tmp);
        d = rd = vector<bool>(2 * n);
        cols = vector<bool>(n);
        dfs(0);
        return ans;
    }
    void dfs(int row) {
        if (row == n) {
            ans.push_back(vec);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!cols[i] && !d[row + i] && !rd[row - i + n]) {
                cols[i] = d[row + i] = rd[row - i + n] = true;
                vec[row][i] = 'Q';
                dfs(row + 1);
                vec[row][i] = '.';
                cols[i] = d[row + i] = rd[row - i + n] = false;
            }
        }
    }
};

一样，只是改个地图而已

解数独 https://leetcode-cn.com/problems/sudoku-solver/

class Solution {
public:
    int row[9][9] = {}, col[9][9] = {}, cell[3][3][9] = {};
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] != '.') {
                    int val = board[i][j] - '1';
                    row[i][val] = 1;
                    col[j][val] = 1;
                    cell[i / 3][j / 3][val] = 1;
                }
        dfs(board, 0, 0);
    }
    bool dfs(vector<vector<char>> & board, int x, int y) {
        if (y == 9) x++, y = 0;
        if (x == 9) return true;

        if (board[x][y] != '.') return dfs(board, x, y + 1);
        for (int i = 0; i < 9; i++) {
            if (!row[x][i] && !col[y][i] && !cell[x/3][y/3][i]) {
                row[x][i] = col[y][i] = cell[x/3][y/3][i] = 1;
                board[x][y] = i + '1';
                if (dfs(board, x, y + 1)) return true;
                row[x][i] = col[y][i] = cell[x/3][y/3][i] = 0;
                board[x][y] = '.';
            }
        }
        return false;
    }
};

记录一下每行每列每个小方格的，各个数字的使用情况
数据比较弱，用不着二进制优化

火柴拼正方形 https://leetcode-cn.com/problems/matchsticks-to-square/

class Solution {
public:
    vector<bool> vis;
    int n;
    long long target;
    bool makesquare(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        vis = vector<bool>(nums.size());
        n = nums.size();
        long long sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 4 != 0) return false;
        target = sum / 4;
        return dfs(nums, 0, 0);
    }
    bool dfs(vector<int> & nums, int cnt, long long val) {
        if (val > target) return false;
        else if (val == target) cnt++, val = 0;
        if (cnt == 4) return true;
        for (int i = 0; i < nums.size(); i++)
            if (!vis[i]) {
                vis[i] = true;
                if (dfs(nums, cnt, val + nums[i])) return true;
                vis[i] = false;
                for (; i + 1 < nums.size() && nums[i] == nums[i + 1]; i++);
                if (val == 0 || val + nums[i] == target) return false;
            }
        return false;
    }
};

剪枝策略：

从大到小枚举每根木棒，因为大的木棒组合的比较少，剪枝效果就比较优异（可以剪掉更多小木棒的组合）
木棒内部保证也是从大到小枚举
组合过程中，如果长度为 k 的木棒组合失败，跳过接下来所有长度为 k 的木棒
如果组合的过程中，第一根就失败，那么直接返回 false
如果组合过程中，最后一根返回失败，直接返回 false