算法学习笔记-回溯

//这就是一个单纯的排列问题，不要求前面的数必须在前面，要求就是每个数只能出现一次：无重复数字
class Solution {
    private:
        vector <int> tmp;
        vector <vector <int>> res;
        int vis[10] = {0};
    public:

        void dfs (vector<int>&nums, vector<int>& tmp, int k, int len){
            if (k >= len){
                res.push_back(tmp);
                return;
            }
            for (int i = 0; i < len; i ++){//不要求后面的数必须在后面，每次循环从0开始
                if (vis[i] == 0){ //每个数只能出现一次
                    tmp.push_back(nums[i]);
                    vis[i] = 1;
                    dfs(nums, tmp, k + 1, len);
                    vis[i] = 0;
                    tmp.pop_back();
                }
            }
        }

        vector<vector<int>> permute(vector<int>& nums) {
            decltype (nums.size()) len = nums.size();
            dfs(nums, tmp, 0, len);
            return res;
        }
    };

//这个是有重复数字，也就是说，按照上面的算法，，肯定有重复
//只需要先排序，然后剪枝
   class Solution {
    private:
        vector <int> tmp;
        vector <vector <int>> res;
        int vis[10] = {0};
    public:

        void dfs (vector<int>&nums, vector<int>& tmp, int k, int len){
            if (k >= len){
//                auto isNull = find(res.begin(), res.end(), tmp);
//                if (isNull == res.end()){
                    res.push_back(tmp);
               // }
                return;
            }
            for (int i = 0; i < len; i ++){
                if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])continue; //防重复都可以这样写
                if (vis[i] == 0){
                    tmp.push_back(nums[i]);
                    vis[i] = 1;
                    dfs(nums, tmp, k + 1, len);
                    vis[i] = 0;
                    tmp.pop_back();
                }
            }
        }

        vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            decltype (nums.size()) len = nums.size();
            dfs(nums, tmp, 0, len);
            return res;
        }
    };

   //跟第46题思想一模一样
     class Solution {
    public:
        vector <int> nums;
        int vis[10] = {0}, cnt = 0, flag = 0;
        string str = "";
        void getStr(){
            for (auto c : nums){
                str += to_string(c);
            }
        }
        void dfs (vector <int>& nums, int n, int k, int sum){
             if (sum >= n){
                 cnt ++;
                 if (cnt == k){
                     flag = 1;
                     getStr();
                 }
                 return;
             }
             for (int i = 1; i <= n; i ++){
                 if (vis[i] == 0 && flag == 0){
                     nums.push_back(i);
                     vis[i] = 1;
                     dfs (nums, n, k, sum + 1);
                     nums.pop_back();
                     vis[i] = 0;
                 }
             }
        }
        string getPermutation(int n, int k) {
           dfs (nums, n, k, 0);
           return str;
        }
    };

  //这题跟46题一模一样
  class Solution {
    private:
        int nums[16] = {0};
        int ans = 0;
    public:
        void dfs(int n, int cnt){
            if (cnt > n){
                ans ++;
                return;
            }
            for (int i = 1; i <= n; i ++){
                if ((i % cnt == 0 || cnt % i == 0) && nums[i] == 0){
                    nums[i] = 1;
                    dfs (n, cnt + 1);
                    nums[i] = 0;
                }
            }
        }
        int countArrangement(int n) {
            dfs(n, 1);
            return ans;
        }
    };

//本题其实严格意义上来说，跟47题是一样的，因为除去要判断每对相邻的和为完全平方数，其他的就是47题，
//所以只要加一个这样的判断即可，比如记录前缀，
 class Solution {
        int ans = 0;
    public:
        int numSquarefulPerms(vector<int>& A) {
            vector<bool> vis(A.size(), false);
            sort(A.begin(), A.end());
            dfs(A, 0, -1, vis);
            return ans;
        }
        void dfs(vector<int>& A, int count, int prev, vector<bool>& vis)
        {
            if(count == A.size())
            {
                ans++;
                return;
            }
            for(int i = 0; i < A.size(); ++i)
            {
                if(i > 0 && !vis[i-1] && A[i-1]==A[i])//用这个前提，要把初始序列排序
                    continue;// 剪枝
                if(!vis[i] && (prev == -1 || ok(prev, A[i])))//判断是否相邻和为完全平方数。
                {
                    vis[i] = true;
                    dfs(A, count+1, A[i], vis);
                    vis[i] = false;
                }
            }
        }
        bool ok(int a, int b)
        {
            int num = sqrt(a+b);
            return num*num == a+b;
        }
    };

//组合问题就是在一个序列中，选出一个或多个能重复或者不能重复的值，然后让其满足一个条件，即为组合问题
//本题就是一个选出一个或多个可重复的值，然后让其结果等于target
//因为前面数的序号，不能大于后面数的序号，所以每次循环不能从0开始，要从上一次开始的地方开始。
class Solution {
    private:
        vector <vector<int>> res;
        vector <int> cnt;
    public:
        void dfs(vector <int>& candidates, int sum, int target, int s){
            if (sum > target)return ;
            if (sum == target){
                res.push_back(cnt);
                return;
            }
            for (int i = s; i < candidates.size(); i ++){//要从上一次开始的地方开始
                cnt.push_back(candidates[i]);
                dfs (candidates, sum + candidates[i],target, i);
                cnt.pop_back();
            }
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            dfs(candidates, 0, target, 0);
            return res;
        }
    };

//这一题与上一题不同的地方是一个数字只能用一次，加一个vis就好了
 class Solution {
    private:
        vector <vector <int>> res;
        vector <int> cnt;
    public:
        void dfs(vector<int>& candidates, int target, int sum, vector <int>& vis, int s){
            if (sum > target)return;
            if (sum == target){
//                auto iter = find(res.begin(), res.end(), cnt);
//                if (iter == res.end())
                res.push_back(cnt);
                return;
            }
            for (int i = s; i < candidates.size(); i ++){
                if (i > 0 && vis[i - 1] == 0 && candidates[i] == candidates[i - 1])continue; //剪枝
                if (vis[i] == 0){//加上这个就好了。
                    vis[i] = 1;
                    cnt.push_back(candidates[i]);
                    dfs(candidates, target, sum + candidates[i], vis, i);
                    vis[i] = 0;
                    cnt.pop_back();
                }
            }
        }
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector <int> vis(candidates.size(), 0);
            dfs (candidates, target, 0, vis, 0);
            return res;
        }
    };

//这题就是单纯的取一定数目的数字了，不能重复用vis，前面的数不能大于后面的数，从上一次结束的地方开始。
 class Solution {
    private:
        vector <int> cnt;
        vector <vector<int>> res;

    public:
        void dfs (int n, int k, int ans, int s, vector <int>& vis){
            if (ans >= k){
                res.push_back(cnt);
                return ;
            }
            for (int i = s; i <= n; i ++){
                if (vis[i] == 0){
                    cnt.push_back(i);
                    vis[i] = 1;
                    dfs (n, k, ans + 1, i, vis);
                    vis[i] = 0;
                    cnt.pop_back();

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

//跟上面一题一模一样
class Solution {
    private:
        vector <int> cnt;
        vector <vector<int>> res;

    public:
        void dfs (int n, int k, int ans, int s, vector <int>& vis, int sum){
            if (ans == k && n == sum){
                res.push_back(cnt);
                return ;
            }
            if (ans > k) return;
            if (sum > n) return;

            for (int i = s; i <= 9; i ++){
                if (vis[i] == 0){
                    cnt.push_back(i);
                    vis[i] = 1;
                    dfs (n, k, ans + 1, i, vis, sum + i);
                    vis[i] = 0;
                    cnt.pop_back();

                }
            }
        }
        vector<vector<int>> combinationSum3(int k, int n) {
            vector <int> vis(10, 0);
            dfs (n, k, 0, 1, vis, 0);
            return res;
        }
    };

//按照数组顺序遍历数组，如果碰到与单词第一个字母一样的，，继续，并且记录；
class Solution {
    private:
        int flag = 0;
    public:
        void backTrack(vector<vector<char>>& board, vector<vector<int>>& vis, int i, int j, int index, string& word){
            if (index == word.size() - 1 && board[i][j] == word[index]){
                flag = 1;
                return;
            }
            if (board[i][j] != word[index])return;
            vector<pair<int, int>> directions{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
            for (const auto& dir : directions){
                int newi = dir.first + i, newj = dir.second + j;
                if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size() && !vis[newi][newj]){
                    vis[newi][newj] = 1;
                    backTrack(board, vis, newi, newj, index + 1, word);
                    vis[newi][newj] = 0;
                    if (flag == 1)return;
                }
            }
        }
        bool exist(vector<vector<char>>& board, string word) {
            int n = board.size(), m = board[0].size();
            vector<vector<int>> vis(n, vector<int>(m));
            for (int i = 0; i < n; i ++){
                for (int j = 0; j < m; j ++){
                    vis[i][j] = 1;
                    backTrack(board, vis, i, j, 0, word);
                    vis[i][j] = 0;
                    if(flag)return true;
                }
            }
            return false;
        }
    };

//用字典树来存储单词数组，然后每次遍历与字典树进行比对
   struct node{
        int id;     //记录该node是否为某个单词的结尾字符
        int cnt;    //记录有几个单词经过该node
        node* children[26];
        node(){
            cnt = 0;
            id = -1;
            memset(children, 0, sizeof(children));
        }
        ~node(){
            for(node* child : children)
                delete child;
        }
    };
    int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int backtrace(vector<vector<char>>& board, vector<string>& words, node* cur, int i, int j, vector<string>& res){
        node* child = cur->children[board[i][j]-'a'];
        if(!child) return 0;
        int ans = 0;    //计算经过该node匹配到的单词数量
        if(child->id != -1){
            res.push_back(words[child->id]);
            child->id = -1;
            ans++;
        }
        char c = board[i][j];
        board[i][j] = '#';
        for(int k = 0; k < 4; k++){
            int x = i + dirs[k][0], y = j + dirs[k][1];
            if(x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] != '#'){
                ans += backtrace(board, words, child, x, y, res);
            }
        }
        board[i][j] = c;
        child->cnt -= ans;
        if(child->cnt == 0){  //经过该节点的所有单词都匹配到了，回溯回来的路上将其删除
            delete child;
            cur->children[board[i][j]-'a'] = nullptr;
        }
        return ans;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words){
        vector<string> res;
        node* root = new node();
        for(int i = 0; i < words.size(); i++){
            node* cur = root;
            for(char c : words[i]){
                if(!cur->children[c - 'a']) cur->children[c - 'a'] = new node();
                cur = cur->children[c - 'a'];
                cur->cnt++;
            }
            cur->id = i;
        }
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                backtrace(board, words, root, i, j, res); 
            }
        }
        return res;
    }

 class Trie {
        private:
        bool is_string = false;
        Trie* next[26] = {nullptr};
        public:
            /** Initialize your data structure here. */
            Trie() {
            }

            /** Inserts a word into the trie. */
            void insert(string word) {
                Trie* root = this;
                for (const auto& u : word){
                    if (!root->next[u - 'a'])root->next[u - 'a'] = new Trie();
                    root = root->next[u - 'a'];
                }
                root->is_string = true;
            }

            /** Returns if the word is in the trie. */
            bool search(string word) {
                Trie* root = this;
                for (const auto& u : word){
                    if (!root->next[u - 'a'])return false;
                    root = root->next[u - 'a'];
                }
                return root->is_string;
            }
            /** Returns if there is any word in the trie that starts with the given prefix. */
            bool startsWith(string prefix) {
                Trie* root = this;
                for (const auto& u : prefix){
                    if (!root->next[u - 'a'])return false;
                    root = root->next[u - 'a'];
                }
                return true;
            }
        };

 class WordDictionary {
    private:
        WordDictionary* next[27] = {nullptr};
        bool is_string = false;
    public:
        /** Initialize your data structure here. */
        WordDictionary() {

        }

        void addWord(string word) {
            WordDictionary* root = this;
            for (const auto& u : word){
                if (!root->next[u - 'a'])root->next[u - 'a'] = new WordDictionary();
                root = root->next[u - 'a'];
            }
            root->is_string = true;
        }

        bool findWord(WordDictionary* root, const string& word, int index){
            if (index == word.size())return root->is_string;
            if (word[index] == '.'){
                for (int i = 0; i < 26; i ++){
                    if (root->next[i] && findWord(root->next[i], word, index + 1)){
                        return true;
                    }
                }
            }else{
                int u = word[index] - 'a';
                if (root->next[u]){
                    return findWord(root->next[u], word, index + 1);
                }else{
                    return false;
                }
            }
            return false;
        }

        bool search(string word) {
            WordDictionary* root = this;
            return findWord(root, word, 0);
        }
    };

//n皇后一般进行逐行判断，也就是说第n行要不要放这个问题，需要判断每一列，每一正负对角线符不符合
//正对角线的数的下标满足：i - j + n;副对角线满足i + j;
class Solution {
    private:
        int cols[10], primary[20], deputy[20];
        vector <vector<string>> res;
        vector <string> cnt;
    public:
        void dfs(int n, int ans){
            if (ans >= n){
                res.push_back(cnt);
                return;
            }
            for (int i = 0; i < n; i ++){
                cnt[ans][i] = 'Q';
                if (!cols[i] && !primary[ans - i + n] && !deputy[i + ans]){
                    cols[i] = primary[ans - i + n] = deputy[i + ans] = 1;
                    dfs(n, ans + 1);
                    cols[i] = primary[ans - i + n] = deputy[i + ans] = 0;
                }
                cnt[ans][i] = '.';
            }
        }
        vector<vector<string>> solveNQueens(int n) {
           string str = "";
            for (int i = 0; i < n; i ++){
                str += '.';
            }
           for (int i = 0; i < n; i ++){
               cnt.push_back(str);
           }
           dfs (n, 0);
           return res;
        }
    };

 class Solution {
    private:
        int cols[10], primary[20], deputy[20];
        int num = 0;
    public:
        void dfs(int n, int ans){
            if (ans >= n){
                num ++;
                return;
            }
            for (int i = 0; i < n; i ++){
                if (!cols[i] && !primary[ans - i + n] && !deputy[i + ans]){
                    cols[i] = primary[ans - i + n] = deputy[i + ans] = 1;
                    dfs(n, ans + 1);
                    cols[i] = primary[ans - i + n] = deputy[i + ans] = 0;
                }
            }
        }
        int totalNQueens(int n) {
            dfs (n, 0);
            return num;
        }
    };

 class Solution {
    private:
        vector <string> res;
    public:
        void dfs (const string& tiles, vector <int>& vis, string& str, int sum){
            if (sum < tiles.size() && str != ""){
                res.push_back(str);
            }
            if (sum >= tiles.size()){
                res.push_back(str);
                return ;
            }
            for (int i = 0; i < tiles.size(); i ++){
                if (i > 0 && !vis[i - 1] && tiles[i] == tiles[i - 1])continue;
                if (!vis[i]){
                    vis[i] = 1;
                    str += tiles[i];
                    dfs(tiles, vis, str, sum + 1);
                    str.erase(--str.end());
                    vis[i] = 0;
                }
            }
        }
        int numTilePossibilities(string tiles) {
            string str = "";
            sort(tiles.begin(), tiles.end());
            vector <int> vis(tiles.size(), 0);
            dfs (tiles, vis, str, 0);
            return res.size();
        }
    };

//这种题目就是建立一个层次树，以beginword为根结点，每一次取出每一层的最后一个单词看看能不能扩充
//直到最后一个单词与endword一样即可：
 class Solution {
        vector <vector<string>> res;
    public:
        vector<vector<string>> BFS(vector<string>& wordList, string beginWord, string endWord){
            unordered_set<string> searchWord(wordList.begin(), wordList.end());
            deque <vector<string>> level;
            level.push_back({beginWord});
            while (!level.empty()){
                unordered_set <string> visited;
                for (int i = level.size(); i > 0; i --){
                    vector<string> tmp = level.front();
                    level.pop_front();
                    string tail = tmp.back();
                    if (endWord == tail){
                        res.push_back(tmp);
                        continue;
                    }
                    for (int j = 0; j < tail.size(); j ++){
                        char temp = tail[j];
                        for (char c = 'a'; c <= 'z'; c ++){
                            if (temp == c)continue;
                            tail[j] = c;
                            if (searchWord.count(tail) == 0)continue;
                            tmp.push_back(tail);
                            visited.insert(tail);
                            level.push_back(tmp);
                            tmp.pop_back();
                        }
                        tail[j] = temp;
                    }

                }
                if (res.size())return res;
                for (auto& vis : visited)searchWord.erase(vis);
            }
            return {};
        }
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())return {};
            return BFS(wordList, beginWord, endWord);

        }
    };

class Solution {
public:
    int BFS(vector<string>& wordList, string beginWord, string endWord){
        unordered_set<string> searchWord(wordList.begin(), wordList.end());
        deque <vector<string>> level;
        level.push_back({beginWord});
        while (!level.empty()){
            unordered_set <string> visited;
            for (int i = level.size(); i > 0; i --){
                vector<string> tmp = level.front();
                level.pop_front();
                string tail = tmp.back();
                if (endWord == tail){
                    return tmp.size();
                }
                for (int j = 0; j < tail.size(); j ++){
                    char temp = tail[j];
                    for (char c = 'a'; c <= 'z'; c ++){
                        if (temp == c)continue;
                        tail[j] = c;
                        if (searchWord.count(tail) == 0)continue;
                        tmp.push_back(tail);
                        visited.insert(tail);
                        level.push_back(tmp);
                        tmp.pop_back();
                    }
                    tail[j] = temp;
                }

            }
            for (auto& vis : visited)searchWord.erase(vis);
        }
        return 0;
    }
   int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())return {};
        return BFS(wordList, beginWord, endWord);

    }
};

class Solution {
    public:
        bool isVaild(vector<vector<char>>& board, int row, int col, char ch){
            for (int i = 0; i < 9; i ++){
                if (board[i][col] == ch)return false;
                if (board[row][i] == ch)return false;
                if(board[(row/3)*3 + i/3][(col/3)*3 + i%3] == ch) return false;
            }
            return true;
        }

        bool backTrack(vector<vector<char>>& board, int row, int col){
            if (col == 9){
                return backTrack(board, row + 1, 0);
            }
            if (row == 9){
                return true;
            }
            for (int i = row; i < 9; i ++){
                for (int j = col; j < 9; j ++){
                    if (board[i][j] != '.')return backTrack(board, i, j + 1);
                    for (char c = '1'; c <= '9'; c ++){
                        if (isVaild(board, i, j, c) == false)continue;
                        board[i][j] = c;
                        if (backTrack(board, i, j + 1)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                    return false;
                }
            }
            return false;
        }
        void solveSudoku(vector<vector<char>>& board) {
            backTrack(board, 0, 0);
        }
    };