T O P

[资源分享]     C++ 算法

  • By - 楼主

  • 2020-10-29 21:40:25
  • /*******************************************************************************
    避免洪水泛滥
    https://leetcode-cn.com/problems/avoid-flood-in-the-city/solution/avoid-flood-in-the-city-by-ikaruga/
    rains : 1 0 2 0 2 1 
    *******************************************************************************/
    class Solution {
    public:
      vector<int> avoidFlood(vector<int> &rains) {
        vector<int> ans(rains.size(), 1);
        unordered_map<int, int> water; //记录每个湖泊上一次下雨的日期
        set<int> zero;
    
        for (int i = 0; i < rains.size(); i++) {
          int r = rains[i];
    
          if (r == 0) {
            //将晴天的日期记录到zero中,遇到晴天时,先不用管抽哪个湖
            zero.insert(i);
            continue;
          }
          if (water.count(r) != 0) { //当下雨时,湖泊已经水满时,可以查询上次下雨的日期
            auto it = zero.lower_bound(water[r]); //通过上次下雨的日期,查找对应的晴天日期
            if (it == zero.end()) { //如果没有找到,则无法使用那天抽水,发生洪水
              return {};
            }
            ans[*it] = r; // 如果在晴天*it找到了对应的下雨日期,则记录抽干的湖泊
            zero.erase(it); //删除当前的晴天记录
          }
    
          // water记录每个湖泊上一次下雨的日期
          water[r] = i; //更新当前湖的下雨日期
          ans[i] = -1;  
        }
        return ans;
      }
    };
    
    /*******************************************************************************
    并查集
    *******************************************************************************/
    void join(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return;
        }
        //将两棵树合并为一棵
        parent[rootP] = rootQ;
        return;
    }
    int find(int p){
        while(p != parent[p]){  //如果P的父亲指针指向不是自己,说明P不是根元素
            //在find查询中嵌入一个路径压缩 此处不懂,参考这里https://blog.csdn.net/qq_19782019/article/details/78919990
            parent[p] = parent[parent[p]];
            //p元素不再选择原来的父亲节点,而是选择父亲节点的父亲节点作为自己的新的一个父亲节点
            p = parent[p];        
        }
        //经过while循环后,p = parent[p], 一定是一个根节点,且不能够再进行压缩
        return p;
    }
    /*******************************************************************************
    1319. 连通网络的操作次数
    https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
    两种方法:并查集 和 深度优先探索
    *******************************************************************************/
    /*并查集*/
    class Solution {
    public:
        int* parent;
        int find(int p){
            while(p != parent[p]){
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }
        void join(int x, int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return;
            }
            parent[rootX] = rootY;
            return;
        }
        int makeConnected(int n, vector<vector<int>>& connections) {
            if(connections.size()<n-1) //不满足线缆数量
                return -1;
            parent = new int[n];  //申请n个空间
            for(int i =0;i<n;i++){
                parent[i] = i;   //初始化
            }
            for(int i =0;i<connections.size();i++){
                join(connections[i][0],connections[i][1]);  //连接
            }
            set<int> pars;
            for(int i =0;i<n;i++){                //计算连通分量数
                pars.insert(find(i));  //每个节点的根节点插入pars,每个键都是唯一的,可以插入或删除但不能更改
            }
            return pars.size()-1;
        }
    };
    
    class Solution {
        private:
            vector<int> fa;
        public:
            int find(int x){
                return x == fa[x] ? x : fa[x] = find(fa[x]);  //  这种是未压缩路径  
                // return x == fa[x] ? x : x = find(fa[x]);
            }
            int makeConnected(int n, vector<vector<int>>& connections){
                if(connections.size() < n-1){
                    return -1;
                }
                fa.resize(n);  //初始化
                iota(fa.begin(), fa.end(), 0);
                
                int part = n; //初始化共有n个连通分量数
                for(auto&& c : connections){                //连接
                    int p = find(c[0]), q = find(c[1]);
                    if(p != q){
                        --part;
                        fa[p] = q;
                    }
                }
                return part - 1;
            }
    };
    /*
    邻接矩阵深度优先探索算法
    */
    class Solution{
        private:
            vector<vector<int>> edges;
            vector<bool> used;
        
        public:
            void dfs(int u){
                used[u] = true;  //将已访问的定点标记true
                for(int v : edges[u]){  //对于顶点u的其他相邻的节点,进行继续深度优先探索
                    if(!used[v]){
                        dfs(v);
                    }
                }
            }
            int makeConnected(int n, vector<vector<int>> & connections){
                if(connections.size() < n-1){
                    return -1;
                }
                edges.resize(n);
                for(auto&& c: connections){   //组合无向图
                    edges[c[0]].push_back(c[1]);
                    edges[c[1]].push_back(c[0]);
                }
                used.resize(n);
    
                int part = 0;
                for(int i = 0; i < n; i++){   //遍历所有顶点,计算连通数量
                    if(!used[i]){
                        ++part;
                        dfs(i);
                    }
                }
                return part-1;
            }
    };
    
    /*邻接矩阵的广度优先探索*/
    class Solution {
    public:
        int makeConnected(int n, vector<vector<int>>& connections) {
            if (connections.size() < (n-1)) {
                return -1;
            }
    
            //将相连接的组合成一个无向图
            unordered_map<int, unordered_set<int>> link_map;
            for (auto &conn : connections) {
                link_map[conn[0]].emplace(conn[1]);
                link_map[conn[1]].emplace(conn[0]);
            }
    
            vector<int> mark(n, 0);
            int num = 0;
            for (int i = 0; i < n; ++i) {
                if (mark[i]) continue;
                num++;
                queue<int> q;
                q.push(i);
                while (!q.empty()) {
                    int index = q.front();
                    q.pop();
                    if (link_map.count(index) == 0) {
                        continue;
                    }
                    for (auto mi : link_map[index]) {
                        if (mark[mi]) continue;
                        q.push(mi);
                        mark[mi] = 1;
                    }
                }
            }
    
            return num-1;
        }
    };
    
    /*******************************************************************************
    邻接矩阵:深度优先遍历,广度优先遍历
    深度优先遍历:不断地沿着顶点的深度方向遍历;顶点的深度方向:它的邻接点方向。
                 用visited[i]表示顶点i的访问情况。
    广度优先遍历:先访问当前顶点的所有邻接点;先访问顶点的邻接点先于后访问顶点的邻接点被访问
    *******************************************************************************/
    //访问标志数组
    int visited[MAX] = {0};
    void DFS(M G, int v){
        visited[v] = 1;
    
    }
    /*******************************************************************************
    朋友圈
    https://leetcode-cn.com/problems/friend-circles/
    *******************************************************************************/
    
    class Solution {
    public:
        vector<int> fa;
        int find(int p){
            while(p != fa[p]){
                fa[p] = fa[fa[p]];
                p = fa[p];
            }
            return p;
        }
        void Union(int p, int q){
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP != rootQ){
                fa[rootP] = rootQ;
            }
            return;
        }
        int findCircleNum(vector<vector<int>>& M) {
            int n = M.size();
            fa.resize(n);      //申请n个空间
            for(int i = 0; i < n; i++){  //初始化
                fa[i] = i;
            }
            //连接
            for(int i=0;i<n;++i){
                for(int j=0;j<n;++j){
                    if(M[i][j]==1 && i!=j)
                        Union(fa[i], fa[j]);
                }
            }
            //计算有多少个连通分量数
            int count = 0;
            for(int i = 0; i < n; i++){
                if(fa[i] == i){
                    ++count;
                }
            }
            return count;
            //计算有多少个连通分量数
            // set<int> pars;
            // for(int i =0;i<n;i++){
            //     pars.insert(find(i));  //每个节点的根节点插入pars,每个键都是唯一的,可以插入或删除但不能更改
            // }
            // return pars.size();
        }
    };
    
    /*深度优先探索*/
    //把矩阵 M 看成是图的邻接矩阵,则问题转化为求图的连通块数
    class Solution {
        private:
            vector<bool> vis;
        public:
            int findCircleNum(vector<vector<int>>& M){
                int n = M.size();
                vis.resize(n);
                int ans = 0;
                for(int i = 0; i < n; i++){
                    if(vis[i] == false){
                        dfs(M, i);
                        ans++;
                    }
                }
                return ans;
            }
            void dfs(vector<vector<int>> M, int i){
                int n = M.size();
                for(int j = 0; j < n; j++){
                    if(M[i][j] == 1 && vis[j] == false){
                        vis[j] = true;
                        dfs(M, j);
                    }
                }
            }
    
    };
    
    /*广度优先探索*/
    class Solution {
        public:
            int findCircleNum(vector<vector<int>>& M){
                int n = M.size();
                vector<int> visit(n, 0);
                int count = 0, tmp;
                queue<int> que;
                for(int i = 0; i < n; i++){
                    if(!visit[i]){
                        count++;
                        que.push(i);
                        while(!que.empty()){
                            tmp = que.front();
                            que.pop();
                            visit[tmp] = 1;
                            for(int j = 0; j < n; j++){
                                if(M[tmp][j] == 1 && !visit[j]){
                                    que.push(j);
                                }
                            }
                        }
                    }
                }
                return count;
            }
    };
    
    
    /*******************************************************************************
    820. 单词的压缩编码
    https://leetcode-cn.com/problems/short-encoding-of-words/
    *******************************************************************************/
    class Solution {
    public:
        int minimumLengthEncoding(vector<string>& words) {
            //unordered_set<string> good(words.begin(), words.end());
            unordered_set<string> origin;
            for(auto& word : words){
                origin.insert(word);
            }
            for (const string& word: words) {
                for (int k = 1; k < word.size(); ++k) {
                    origin.erase(word.substr(k));
                }
            }
    
            int ans = 0;
            for (const string& word: origin) {
                ans += word.size() + 1;
            }
            return ans;
        }
    };
    
    
    /*******************************************************************************
    LCP 08. 剧情触发时间
    https://leetcode-cn.com/problems/ju-qing-hong-fa-shi-jian/
    *******************************************************************************/
    
    #define col 3
    class Solution {
    public:
        vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
            vector<int> res;
            int row = increase.size();
            cout << row << endl;
            vector<vector<int>> sum(row+1, vector<int>(col,0));
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    sum[i+1][j] = sum[i][j] + increase[i][j];
                }
            }
    
            for(auto v : requirements){
                int l = 0, r = row;
                while(l < r){
                    int m = (l + r) / 2;
                    if(sum[m][0] >= v[0] && sum[m][1] >= v[1] && sum[m][2] >= v[2]){
                        r = m;
                    } else {
                        l = m + 1;
                    }
                }
                if(sum[l][0] >= v[0] && sum[l][1] >= v[1] && sum[l][2] >= v[2]){
                    res.push_back(l);
                } else {
                    res.push_back(-1);
                }
            }
            return res;
        }
    };
    class Solution{
        public:
            vector<int> getTriggerTime(vector<vector<int>>& increase, vectoro<vector<int>>& requirements){
                vector<int> C(increase.size()+1, 0);
                vector<int> R(increase.size()+1, 0);
                vector<int> H(increase.size()+1, 0);
    
                for(int i = 0; i < inrease.size(); ++i){
                    C[i+1] = C[i] + increase[i][0];
                    R[i+1] = R[i] + increase[i][1];
                    H[i+1] = H[i] + increase[i][2];
                }
                vector<int> res;
                int maxLen = C.size();
                for(int i = 0; i < requirements.size(); i++){
                    int lc = lower_bound(C.begin(), C.end(), requirements[i][0]) - C.begin();
                    int lr = lower_bound(R.begin(), R.end(), requirements[i][1]) - R.begin();
                    int lh = lower_bound(H.begin(), H.end(), requirements[i][2]) - H.begin();
                    if(lc == maxLen || lr == maxLen || lh == maxLen){
                        res.push_back(-1);
                    } else {
                        res.push_back(max(max(lc,lr),lh));
                    }
                }
                return res;
            }
    };
    
    /*******************************************************************************
    76. 最小覆盖子串
    https://leetcode-cn.com/problems/minimum-window-substring/
    *******************************************************************************/
    class Solution {
    public:
        string minWindow(string s, string t) {
            unordered_map<char, int> need;
            unordered_map<char, int> windows;
            int len = s.size() + 1;
            int start = 0;
            //先计算need
            for(auto w : t){  
                ++need[w];
            }
            int left =  0, right = 0, valid = 0; //初始化
            while(right < s.size()){
                char chr = s[right];
                ++right;
                if(need.count(chr)){
                    ++windows[chr];
                    if(windows[chr] == need[chr]){
                        valid++;
                    }
                }
                while(valid == need.size()){
                    if(right - left < len){
                        start = left;
                        len = right - left;
                    }
                    char chl = s[left];
                    ++left;
                    if(need.count(chl)){
                        if(windows[chl] == need[chl]){
                            --valid;
                        }
                        --windows[chl];
                    }
                }
            }
            return len == s.size()+1 ? "" : s.substr(start, len);
        }
    };
    /*******************************************************************************
    438. 找到字符串中所有字母异位词
    https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
    *******************************************************************************/
    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            unordered_map<char, int> window;
            unordered_map<char, int> need;
            
            for(auto c : p){
                need[c]++;
            }
            int left = 0, right = 0, valid = 0;
            vector<int> res;
            while(right < s.size()){
                char c = s[right];
                right++;
                if(need.count(c)){
                    window[c]++;
                    if(window[c] == need[c]){
                        valid++;
                    }
                }
                //判断左侧端口是否要收缩
                while(right - left >= p.size()){
                    if(valid == need.size()){
                        res.push_back(left);
                    }
                    char d = s[left];
                    left++;
                    if(need.count(d)){
                        if(window[d] == need[d]){
                            valid--;
                        }
                        window[d]--;
                    }
                }
            }
            return res;
        }
    };
    /*******************************************************************************
    567. 字符串的排列
    https://leetcode-cn.com/problems/permutation-in-string/
    *******************************************************************************/
    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            unordered_map<char, int> need, window;
            for(auto c : s1){
                need[c]++;
            }
            int left = 0, right = 0;
            int valid = 0;
            while(right < s2.size()){
                char c = s2[right];
                right++;
                if(need.count(c)){
                    window[c]++;
                    if(window[c] == need[c]){
                        valid++;
                    }
                }
    
                while(right - left >= s1.size()){
                    if(valid == need.size()){
                        return true;
                    }
                    char d = s2[left];
                    left++;
                    if(need.count(d)){
                        if(window[d] == need[d]){
                            valid--;
                        }
                        window[d]--;
                    }
                }
            }
            return false;
        }
    };
    /*******************************************************************************
    3. 无重复字符的最长子串
    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
    *******************************************************************************/
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            unordered_map<char, int> window;
            int left = 0, right = 0;
            int res = 0;
            while(right  < s.size()){
                char c = s[right];
                right++;
                //进行窗口数据更新
                window[c]++;
                //判断窗口是否要收缩
                while(window[c] > 1){
                    char d = s[left];
                    left++;
                    window[d]--;
                }
                res = max(res, right-left);
            }
            return res;
        }
    };
    
    /*******************************************************************************
    II. 左旋转字符串
    https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
    *******************************************************************************/
    class Solution {
    public:
        string reverseLeftWords(string s, int n) {
            reverse(s.begin(), s.begin()+n);
            reverse(s.begin()+n, s.end());
            reverse(s.begin(), s.end());
            return s;
        }
    };
    
    /*******************************************************************************
    N皇后
    https://leetcode-cn.com/problems/n-queens/
    *******************************************************************************/
    class Solution {
    public:
        vector<vector<string>> res;
        vector<vector<string>> solveNQueens(int n) {
            vector<string> board(n, string(n, '.'));
            backtrack(board, 0);
            return res;
        }
        void backtrack(vector<string>& board, int row){
            //触发条件
            if(row == board.size()){
                res.push_back(board);
                return;
            }
            int n = board[row].size();
            for(int col = 0; col < n; col++){
                if(!isValid(board ,row, col)){
                    continue;
                }
                //做选择
                board[row][col] = 'Q';
                // 进行下一步策略
                backtrack(board, row+1);
                //撤回选择
                board[row][col] = '.';
    
            }
        }
        bool isValid(vector<string>& board, int row, int col){
            int n = board.size();
            //检查列是否有皇后冲突
            for(int i = 0; i < n; i++){
                if(board[i][col] == 'Q'){
                    return false;
                }
            }
            //检查右上方是否有皇后互相冲突
            for(int i = row-1, j = col + 1; i>=0 && j < n; i--, j++){
                if(board[i][j] == 'Q'){
                    return false;
                }
            }
            //检查左上方是否有皇后互相冲突
            for(int i = row-1, j = col - 1; i>=0 && j >= 0; i--, j--){
                if(board[i][j] == 'Q'){
                    return false;
                }
            }
            return true;
        }
    };
    
    /*******************************************************************************
    980. 不同路径 III
    https://leetcode-cn.com/problems/unique-paths-iii/
    *******************************************************************************/
    class Solution {
    public:
        int uniquePathsIII(vector<vector<int>>& grid) {
            int startX = 0, startY = 0, stepNum = 1;
            //遍历获取起始位置和统计总步数
            for(int i = 0; i < grid.size(); i++){
                for(int j = 0; j < grid[0].size(); j++){
                    if(grid[i][j] == 1){
                        startX = j;
                        startY = i;
                        continue;
                    }
                    if(grid[i][j] == 0){
                        stepNum++;
                    }
                }
            }
            return dfs(startX, startY, stepNum, grid);
        }
        int dfs(int x, int y, int stepSur, vector<vector<int>>& grid){
            if(x < 0 || x >= grid[0].size() || y < 0 || y >= grid.size() || grid[y][x] == -1){
                return 0;
            }
            if (grid[y][x] == 2) return stepSur == 0 ? 1 : 0;
            grid[y][x] = -1;
            int res = 0;
            res += dfs(x-1, y, stepSur -1 ,grid);
            res += dfs(x + 1, y, stepSur - 1, grid);
            res += dfs(x, y - 1, stepSur - 1, grid);
            res += dfs(x, y + 1, stepSur - 1, grid);
            grid[y][x] = 0;
            return res;
    
        }
    };
    
    /*******************************************************************************
    833. 字符串中的查找与替换
    https://leetcode-cn.com/problems/find-and-replace-in-string/
    *******************************************************************************/
    class Solution {
    public:
        string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
            int n = S.size();
            vector<string> vec(n, "");
            string res = "";
            for (int i = 0; i < S.size(); ++i) vec[i] += S[i];
            for (int i = 0; i < indexes.size(); ++i) {
                int size = sources[i].size();
                if (S.substr(indexes[i], size) == sources[i]) {
                    vec[indexes[i]] = targets[i];
                    for (int j = indexes[i] + 1; j < indexes[i] + size; ++j)
                        vec[j] = "";
                }
            }
            for (auto str : vec) {
                res += str;
            }
            return res;
        }
    };
    
    /*******************************************************************************
    84. 柱状图中最大的矩形
    https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
    *******************************************************************************/
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights)
        {
            int ans = 0;
            vector<int> st;
            heights.insert(heights.begin(), 0);
            heights.push_back(0);
            for (int i = 0; i < heights.size(); i++)
            {
                while (!st.empty() && heights[st.back()] > heights[i])
                {
                    int cur = st.back();
                    st.pop_back();
                    int left = st.back() + 1;
                    int right = i - 1;
                    ans = max(ans, (right - left + 1) * heights[cur]);
                }
                st.push_back(i);
            }
            return ans;
        }
    };
    
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights){
            int res = 0;
            stack<int> tack;
            heights.insert(heights.begin(), 0);
            heights.push_back(0);
            for(int i = 0; i < heights.size(); i++){
                while(!tack.empty() && heights[tack.top()] > heights[i]){
                    int cur = tack.top();
                    tack.pop();
                    int left = tack.top() + 1;
                    int right = i - 1;
                    //heights[cur] 是 离heights[i] 最远的那个且大于heights[i],right-left 是递增的宽度
                    res = max(res, (right - left + 1) * heights[cur]);
                }
                tack.push(i);
            }
            return res;
        }
    };
    
    
    /*******************************************************************************
    735. 行星碰撞
    https://leetcode-cn.com/problems/asteroid-collision/
    *******************************************************************************/
    class Solution {
    public:
        vector<int> asteroidCollision(vector<int>& asteroids) {
            vector<int> res;
            for(auto v : asteroids){
                bool flag = true;
                while(!res.empty() && v < 0 && res.back() > 0){
                    int sum = res.back() + v;
                    if(sum <= 0){
                        res.pop_back();
                    } 
                    if(sum >= 0) {
                        flag = false;
                        break;
                    }
    
                }
                if(flag){
                    res.push_back(v);
                }
            }
            return res;
        }
    };
    
    /*******************************************************************************
    2. 两数相加
    https://leetcode-cn.com/problems/add-two-numbers/
    *******************************************************************************/
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode* head = nullptr;
            ListNode* tail = nullptr;
            int carry = 0;
            if(l1 == nullptr){
                return l2;
            }
            if(l2 == nullptr){
                return l1;
            }
            while(l1 || l2){
                int n1 = l1 ? l1->val : 0;
                int n2 = l2 ? l2->val : 0;
                int sum = n1 + n2 + carry;
                if(!head){
                    head = tail = new ListNode(sum % 10);
                } else {
                    tail->next = new ListNode(sum % 10);
                    tail = tail->next;
                }
                carry = sum / 10;
                if(l1){
                    l1 = l1->next;
                }
                if(l2){
                    l2 = l2->next;
                }
            }
            if(carry > 0){
                tail->next = new ListNode(carry);
            }
            return head;
        }
    };
    
    /*******************************************************************************
    15. 三数之和---左右指针
    https://leetcode-cn.com/problems/3sum/
    *******************************************************************************/
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> res;
            sort(nums.begin(), nums.end());
            int target;
            for(int i = 0; i < nums.size(); i++){
                if(i > 0 && nums[i] == nums[i-1]){
                    continue;
                }
                if((target = nums[i]) > 0){
                    break;
                }
                int l = i + 1;
                int r = nums.size()-1;
                while(l < r){
                    if(nums[l] + target + nums[r] < 0){
                        ++l;
                    } else if(nums[l] + target + nums[r] > 0){
                        --r;
                    } else {
                        res.push_back({nums[l], target, nums[r]});
                        ++l;
                        --r;
                        while(l < r && nums[l] == nums[l-1]){
                            l++;
                        }
                        while(l < r && nums[r] == nums[r+1]){
                            r--;
                        }
                    }
                }
            }
            return res;
            
        }
    };
    
    /*******************************************************************************
    面试题 08.12. 八皇后---回溯法
    https://leetcode-cn.com/problems/eight-queens-lcci/
    *******************************************************************************/
    class Solution1 {
    public:
        vector<vector<string>> res;
    
        vector<vector<string>> solveNQueens(int n) {
            vector<string> board(n, string(n, '.'));
            backtrack(board ,0);
            return res;
        }
        void backtrack(vector<string>& board, int row){
            if(row == board.size()){
                res.push_back(board);
                return;
            }
            int n = board[row].size();
            for(int col = 0; col < n; col++){
                if(!isValid(board, row, col)){
                    continue;
                }
                board[row][col] = 'Q';
                backtrack(board, row+1);
                board[row][col] = '.';
            }
        }
        bool isValid(vector<string>& board, int row, int col){
            int n = board.size();
            //检查列是否有冲突
            for(int i = 0; i < n; i++){
                if(board[i][col] == 'Q'){
                    return false;
                }
            }
            //检查右上方对角线
            for(int i = row-1, j= col+1; i >= 0 && j < n; i--, j++){
                if(board[i][j] == 'Q'){
                    return false;
                }
            }
            //检查左上方对角线
            for(int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--){
                if(board[i][j] == 'Q'){
                    return false;
                }
            }
            return true;
    
        }
    };
    /*******************************************************************************
    980. 不同路径 III---回溯法
    https://leetcode-cn.com/problems/unique-paths-iii/
    *******************************************************************************/
    class Solution3{
    public:
        int uniquePathsIII(vector<vector<int>>& grid){
            int res = 0;
            int startX = 0, startY = 0;
            int step = 0;
            for(int i = 0; i < grid.size(); i++){
                for(int j = 0; j < grid[0].size(); j++){
                    if(grid[i][j] == 1){
                        startX = i;
                        startY = j;
                        continue;
                    }
                    if(grid[i][j] == 0){
                        step++;
                    }
                }
            }
            //step + 1 针对step != 0 时,则直接返回res = 0
            trackBack(grid, startX, startY, step+1, res);
            return  res;
        }
        void trackBack(vector<vector<int>>& grid, int startX, int startY, int step, int &res){
            if(startX < 0 || startX >= grid.size() || startY < 0 || startY >= grid[startX].size() || grid[startX][startY] == -1){
                return;
            }
            if(grid[startX][startY] == 2){
                if(step == 0){
                    res++;
                }
                return;
            }
            grid[startX][startY] = -1;
            trackBack(grid, startX-1, startY, step-1, res);
            trackBack(grid, startX+1, startY, step-1, res);
            trackBack(grid, startX, startY-1, step-1, res);
            trackBack(grid, startX, startY+1, step-1, res);
            grid[startX][startY] = 0;
    
        }
    };

     

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册