1.深度优先搜索

37. 解数独

| Hard |

一、 排列类题目

46. 全排列

题解

class Solution {
public:
    vector<vector<int>> res;
    vector<bool> visited;
    vector<int> path;
    vector<vector<int>> permute(vector<int> nums) {
        for (int i = 0; i < nums.size(); ++i) {
            visited.push_back(false);
        }
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int> &nums, int deep) {
        if (deep == nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (!visited[i]) {
                visited[i] = true;
                path.push_back(nums[i]);
                dfs(nums, deep + 1);
                visited[i] = false;
                path.pop_back();// 弹出来 以便 其余数字排列时加入进去;
            }
        }
    }
};

47.全排列 II

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> visited;
public:
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        if (nums.empty()) {
            return ans;
        }
        for (int i = 0; i < nums.size(); i++) {
            visited.push_back(false);
        }
        // 排序是去重的首要操作，方便下面 nums[i-1]==nums[i]的判断
        // 如果不排序，[2,1,2] 这样的数据无法判断出来
        sort(nums.begin(), nums.end(), greater<int>());
        dfs(nums, 0);
        return ans;
    }
    void dfs(vector<int> &nums, int deep) {
        if (deep == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!visited[i]) {
                if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                    continue;
                }
                visited[i] = true;
                path.push_back(nums[i]);
                dfs(nums, deep + 1);
                visited[i] = false;
                path.pop_back();
            }
        }
    }
};

面试题 08.07 无重复字符串的排列组合

class Solution {
public:
    vector<string> ans;
    vector<char> path;
    vector<bool> visited;
    vector<string> permutation(string S) {
        for (int i = 0; i < S.length(); i++) {
            visited.push_back(false);
        }
        dfs(S, 0);
        return ans;
    }
    void dfs(string s, int deep) {
        if (deep == s.length()) {
            // char 与 string 转换
            string ss(path.begin(), path.end());
            ans.push_back(ss);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.push_back(s[i]);
                dfs(s, deep + 1);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};

面试题 08.08 有重复字符串的排列组合

class Solution {
public:
    vector<string> ans;
    vector<char> path;
    vector<bool> visited;
    vector<string> permutation(string S) {
        for (int i = 0; i < S.length(); i++) {
            visited.push_back(false);
        }
        sort(S.begin(), S.end());
        dfs(S, 0);
        return ans;
    }
    void dfs(string s, int deep) {
        if (deep == s.length()) {
            string ss(path.begin(), path.end());
            ans.push_back(ss);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (!visited[i]) {
                // 剪枝;
                if (i > 0 && s[i - 1] == s[i] && !visited[i - 1]) {
                    continue;
                }
                visited[i] = true;
                path.push_back(s[i]);
                dfs(s, deep + 1);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};

60. 排列序列

题解：题解

class Solution {
public:
    vector<bool> visited;
    int n, k;
    vector<int> factorial;
    string getPermutation(int n, int k) {
        this->n = n;
        this->k = k;
        calcFactorial();
        visited = vector<bool>(n + 1, false);
        string str;
        dfs(0, str);
        return str;
    }
    void dfs(int index, string &str) {
        if (index == n) { return; }
        int cnt = factorial[n - index - 1];
        for (int i = 1; i <= n; ++i) {
            if (visited[i]) { continue; }
            if (cnt < k) {
                k -= cnt;
                continue;
            }
            visited[i] = 1;
            string tmp;
            stringstream ss;
            ss << i;
            ss >> tmp;
            str.append(tmp);
            dfs(index + 1, str);
            return;
        }
    }
    void calcFactorial() {
        factorial = vector<int>(n, 0);
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }
};

二、组合类题目

77.组合

题解

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> nums;
    vector<vector<int>> combine(int n, int k) {
        if( k<=0 || k>n ){
            return res;
        }
        for (int i = 1; i <= n; ++i) {
            nums.push_back(i);
        }
        dfs(nums, 0, k, 1);
        return res;
    }
    void dfs(vector<int> &nums, int deep, int k, int start) {
        if (deep == k) {
            res.push_back(path);
            return;
        }
        for (int i = start; i <= nums.size(); ++i) {
                path.push_back(i);
                dfs(nums, deep + 1, k, i + 1);
                path.pop_back();
        }
    }
};

17. 电话号码的字母组合

class Solution {
public:
    unordered_map<char, string> map = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
    };
    vector<string> ans;
    string current;
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return ans;
        }
        dfs(0, digits);
        return ans;
    }
    void dfs(int index, string &digits) {
        if (index == digits.size()) {
            ans.push_back(current);
            return;
        }
        for (int i = 0; i < map[digits[index]].size(); i++) {
            current.push_back(map[digits[index]][i]);
            dfs(index + 1, digits);
            current.pop_back();
        }
    }
};

三、子集类

78. 子集

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> visited;
    int N;
    vector<vector<int>> subsets(vector<int> &nums) {
        N = nums.size();
        if (N == 0) {
            return ans;
        }
        visited = vector<bool>(N, 0);
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return ans;
    }
    void dfs(int index, vector<int> &nums) {
        ans.push_back(path);
        for (int i = index; i < nums.size(); i++) {
            path.push_back(nums[i]);
            visited[i] = 1;
            dfs(i + 1, nums);
            path.pop_back();
            visited[i] = 0;
        }
    }
};

90. 子集 II

class Solution {
public:
    int N;
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> visited;
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        N = nums.size();
        if (nums.size() == 0) {
            return ans;
        }
        visited = vector<bool>(N, 0);
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return ans;
    }
    void dfs(int index, vector<int> &nums) {
        ans.push_back(path);
        for (int i = index; i < nums.size(); i++) {
            //减枝
            if (i > 0 && !visited[i - 1] && nums[i] == nums[i - 1]) {
                continue;
            }
            visited[i] = 1;
            path.push_back(nums[i]);
            dfs(i + 1, nums);
            path.pop_back();
            visited[i] = 0;
        }
    }
};

面试题 08.04. 幂集

class Solution {
public:
    int N;
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> visited;
    vector<vector<int>> subsets(vector<int> &nums) {
        N = nums.size();
        if (nums.size() == 0) {
            return ans;
        }
        visited = vector<bool>(N, 0);
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return ans;
    }
    void dfs(int index, vector<int> &nums) {
        ans.push_back(path);
        for (int i = index; i < nums.size(); i++) {
            //减枝
            if (i > 0 && !visited[i - 1] && nums[i] == nums[i - 1]) {
                continue;
            }
            visited[i] = 1;
            path.push_back(nums[i]);
            dfs(i + 1, nums);
            path.pop_back();
            visited[i] = 0;
        }
    }
};

37. 解数独

题解：https://leetcode.cn/problems/sudoku-solver/solution/hui-su-fa-jie-shu-du-by-i_use_python/

    vector<vector<int>> rowUsed;
    vector<vector<int>> colUsed;
    vector<vector<vector<int>>> boxUsed;
    void solveSudoku(vector<vector<char>> &board) {
        rowUsed = vector<vector<int>>(9, vector<int>(10));
        colUsed = vector<vector<int>>(9, vector<int>(10));
        boxUsed = vector<vector<vector<int>>>(3, vector<vector<int>>(3, vector<int>(10)));
        for (int row = 0; row < board.size(); row++) {
            for (int col = 0; col < board[0].size(); col++) {
                int num = board[row][col] - '0';
                if (num >= 1 && num <= 9) {
                    rowUsed[row][num] = 1;
                    colUsed[col][num] = 1;
                    boxUsed[row / 3][col / 3][num] = 1;
                }
            }
        }
        recSolveSudoKu(board, rowUsed, colUsed, boxUsed, 0, 0);
    }
    bool recSolveSudoKu(vector<vector<char>> &board, vector<vector<int>> &rowUsed,
                        vector<vector<int>> &colUsed, vector<vector<vector<int>>> &boxUsed, int row, int col) {
        if (col == board[0].size()) {
            col = 0;
            row += 1;
            if (row == board.size()) {
                return true;
            }
        }
        if (board[row][col] == '.') {
            for (int num = 1; num <= 9; num++) {
                bool canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row / 3][col / 3][num]);
                if (canUsed) {
                    rowUsed[row][num] = 1;
                    colUsed[col][num] = 1;
                    boxUsed[row / 3][col / 3][num] = 1;
                    board[row][col] = char(num + '0');
                    if (recSolveSudoKu(board, rowUsed, colUsed, boxUsed, row, col + 1)) {
                        return true;
                    }
                    rowUsed[row][num] = 0;
                    colUsed[col][num] = 0;
                    boxUsed[row / 3][col / 3][num] = 0;
                    board[row][col] = '.';
                }
            }
        } else {
            return recSolveSudoKu(board, rowUsed, colUsed, boxUsed, row, col + 1);
        }
        return false;
    }