讨论/题目交流/🏆 迎国庆,力扣第 156 场周赛 🇨🇳/
🏆 迎国庆,力扣第 156 场周赛 🇨🇳

祖国 image.png 周年盛世华诞,这是国庆前的一场激烈竞赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验,祝大家国庆假期快乐。

image.png前往竞赛本周周赛题目:

独一无二的出现次数
尽可能使字符串相等
删除字符串中的所有相邻重复项 II
穿过迷宫的最少移动次数 —— 小蛇移动

展开讨论

1, 暴力遍历

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) { 
        unordered_map<int, int> freq, cnt;
        for (int a : arr) freq[a]++;
        for (auto& ir : freq) 
            if (++cnt[ir.second] > 1) return false;
        return true;
    }
};

2, 滑动窗口

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int ls = s.size();
        int sum = 0, ans = 0;
        for (int i = 0, j = 0; i < ls; i++) {
            sum += abs(s[i]-t[i]);
            while (sum > maxCost) {
                sum -= abs(s[j]-t[j]);
                j++;
            }
            ans = max(ans, i-j+1);
        }
        return ans;
    }
};

3, 栈模拟

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> sk;
        
        for (char c : s) {
            if (sk.empty() || sk.back().first != c) {
                sk.push_back({c, 1});
            } else if (++sk.back().second == k) {
                sk.pop_back();
            }
        }
        string ans;
        for (auto& r : sk) {
            ans.append(r.second, r.first);
        }
        return ans;
    }
};

4, BFS

class Solution {
public:
    int minimumMoves(vector<vector<int>>& g) {
        queue<array<int, 4>> q; // 两个小块的坐标
        int n = g.size();
        
        int dest = (n-1) + (n-2)*100 + (n-1)*10000 + (n-1)*1000000;
        q.push({0, 0, 0, 1});
        unordered_map<int, int> visited;
        int step = 0;
        while (!q.empty()) {
            
            for (int s = q.size(); s > 0; s--) {
                auto r = q.front(); q.pop();
                
                int y1 = r[0], x1 = r[1];
                int y2 = r[2], x2 = r[3];
                
                int key = y1 + x1*100 + y2*10000 + x2*1000000; 
                
                if (++visited[key] > 1) continue;
                if (key == dest) return step;
              
                
                if (y1==y2) { // 横
                    if (x2 < n-1 && g[y2][x2+1] == 0) { // 向右
                        q.push({y1, x1+1, y2, x2+1});
                    }
                    if (y1 < n-1 && g[y1+1][x1] == 0 && g[y2+1][x2] == 0) { 
                        q.push({y1+1, x1, y2+1, x2});// 整体向下
                        q.push({y1, x1, y2+1, x2-1});//顺时针
                    } 
                } else { // 竖
                    if (y2 < n-1 && g[y2+1][x2] == 0) {
                        q.push({y1+1, x1, y2+1, x2}); // 向下
                    }
                    if (x2 < n-1 && g[y1][x1+1] == 0 && g[y2][x2+1] == 0) {
                        q.push({y1, x1+1, y2, x2+1}); // 整体向右
                        q.push({y1, x1, y2-1, x2+1}); // 逆时针
                    }
                }
            }
            step++;
        }
        return -1;
    }
};
展开全部 21 讨论