头像

dade68




离线:2天前



dade68
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

bfs

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> S;
        for (auto str : bank) S.insert(str);
        unordered_map<string, int> dist;
        dist[start] = 0;

        char gene[4] = {'A', 'C', 'G', 'T'};
        queue<string> q;
        q.push(start);
        while (q.size()) {
            auto t = q.front();
            q.pop();
            for (int i = 0; i < t.size(); i ++) {
                string a = t;
                for (int j = 0; j < 4; j ++) {
                    a[i] = gene[j];
                    if (S.count(a) && dist.count(a) == 0) {
                        dist[a] = dist[t] + 1;
                        if (a == end) return dist[a];
                        q.push(a);
                    }
                }
            }
        }
        return -1;
    }
};



dade68
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

双指针

class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i ++) {
            if (s[i] == ' ') continue;
            int j = i + 1;
            while (j < s.size() && s[j] != ' ') j ++;
            res ++;
            i = j;
        }
        return res;
    }
};


活动打卡代码 LeetCode 435. 无重叠区间

dade68
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

贪心选区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& q) {
        if (q.empty()) return 0;
        sort(q.begin(), q.end(), [](vector<int> a, vector<int> b){
            return a[1] < b[1];
        });

        int res = 1, right = q[0][1];
        for (int i = 1; i < q.size(); i ++)
            if (q[i][0] >= right) {
                res ++, right = q[i][1];
            }
        return q.size() - res;
    }
};



dade68
3天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

各个击破

class Solution {
public:
    string originalDigits(string s) {
        vector<char> letter = {'z', 'g', 'h', 'w', 'r', 'f', 'x', 's', 'o', 'i'};
        vector<char> number = {'0', '8', '3', '2', '4', '5', '6', '7', '1', '9'};
        vector<string> word = {"zero", "eight", "three", "two", "four", "five", "six", "seven", "one", "nine"};

        unordered_map<char, int> cnt;
        for (auto c : s) cnt[c] ++;

        string res;
        for (int i = 0; i < 10; i ++) {
            int t = cnt[letter[i]];
            for (int j = 0; j < t; j ++) res += number[i];
            for (auto c : word[i]) {
                cnt[c] -= t;
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};


活动打卡代码 LeetCode 407. 接雨水 II

dade68
3天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

每个点到所有边界的路径中最大值的最小值, 小根堆

class Solution {
public:
    struct Cell{
        int h, x, y;
        bool operator< (const Cell& t) const{
            return h > t.h;
        }
    };

    int trapRainWater(vector<vector<int>>& h) { //小根堆
        if (h.empty() || h[0].empty()) return 0;
        int n = h.size(), m = h[0].size();
        priority_queue<Cell> q;
        vector<vector<bool>> st(n, vector<bool>(m));
        for (int i = 0; i < n; i ++) {
            q.push({h[i][0], i, 0});
            q.push({h[i][m - 1], i, m - 1});
            st[i][0] = st[i][m - 1] = true;
        }
        for (int i = 0; i < m; i ++) {
            q.push({h[0][i], 0, i});
            q.push({h[n - 1][i], n - 1, i});
            st[0][i] = st[n - 1][i] = true;
        }

        int res = 0;
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        while (q.size()) {
            auto t = q.top();
            q.pop();
            res += t.h - h[t.x][t.y];

            for (int i = 0; i < 4; i ++) {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) {
                    q.push({max(h[a][b], t.h), a, b});
                    st[a][b] = true;
                }
            }
        }
        return res;
    }
};



dade68
3天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

bfs

class Solution {
public:

    string findLexSmallestString(string s, int a, int b) {
        unordered_set<string> S;
        S.insert(s);
        string minv = s;
        queue<string> q;
        q.push(s);

        while (q.size()) {
            auto t = q.front();
            q.pop();
            // cout << t << endl;
            if (t < minv) minv = t;
            auto t1 = t, t2 = t;
            for (int i = 1; i < t.size(); i += 2) t1[i] = (t[i] - '0' + a) % 10 + '0';
            if (!S.count(t1)) q.push(t1), S.insert(t1);
            t2 = t.substr(t.size() - b) + t.substr(0, t.size() - b);
            if (!S.count(t2)) q.push(t2), S.insert(t2);            
        }
        return minv;

    }
};



dade68
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

枚举

class Solution {
public:

    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        vector<int> res(n - 1);
        vector<vector<int>> di(n + 1, vector<int>(n + 1, 1e8));
        for (auto &e : edges) {
            auto a = e[0], b = e[1];
            di[a][b] = di[b][a] = 1;
        }
        auto link = di;
        for (int k = 1; k <= n; k ++)
            for (int i = 1; i <= n; i ++)
                for (int j = 1; j <= n; j ++)
                    di[i][j] = min(di[i][j], di[i][k] + di[k][j]);

        for (int p = 0; p < 1 << n; p ++) {
            vector<int> s;
            for (int i = 0; i < n; i ++)
                if ((p >> i) & 1) s.push_back(i + 1);
            if (s.size() < 2) continue;

            int cnt = 0;
            for (int i = 0; i < s.size(); i ++)
                for (int j = i + 1; j < s.size(); j ++) {
                    if (link[s[i]][s[j]] == 1) cnt ++;
                }
            if (cnt < s.size() - 1) continue;
            int dist = 0;
            for (int i = 0; i < s.size(); i ++)
                for (int j = i + 1; j < s.size(); j ++)
                    dist = max(dist, di[s[i]][s[j]]);
            res[dist - 1] ++;

        }
        return res;
    }
};



dade68
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    int n, m;
    vector<vector<int>> w, st;
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        w = matrix;
        if (w.empty() || w[0].empty()) return {};
        n = w.size(), m = w[0].size();
        st.resize(n, vector<int>(m));

        for (int i = 0; i < n; i ++) dfs(i, 0, 1), dfs(i, m - 1, 2);
        for (int i = 0; i < m; i ++) dfs(0, i, 1), dfs(n - 1, i, 2);

        vector<vector<int>> res;
        for (int i = 0; i < n; i ++)
            for (int j = 0;j < m; j ++) {
                if (st[i][j] == 3) res.push_back({i, j});
            }
        return res;
    }

    void dfs(int x, int y, int t) {
        if (st[x][y] & t) return;
        st[x][y] |= t;
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && w[a][b] >= w[x][y]) {
                dfs(a, b, t);
            }
        }
    }
};



dade68
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

分类讨论,y总牛逼

class Solution {
public:
    int strongPasswordChecker(string s) {
        int a = 0, b = 0, c = 0, n = s.size(), k = 0;
        for (int i = 0; i < n; i ++) {
            if (s[i] >= 'a' && s[i] <= 'z') a = 1;
            if (s[i] >= 'A' && s[i] <= 'Z') b = 1;
            if (s[i] >= '0' && s[i] <= '9') c = 1;
        }
        k = a + b + c;

        if (n < 6) return max(6 - n, 3 - k);
        int d[3] = {0}, p = 0, del = n - 20, res = del;
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && s[j] == s[i]) j ++;
            int t = j - i;
            p += t / 3;
            if (t >= 3) d[t % 3] ++;
            i = j;
        }
        if (n <= 20) return max(p, 3 - k);
        if (d[0] && del) {
            int t = min(d[0], del);
            del -= t;
            p -= t;
        }
        if (d[1] && del) {
            int t = min(d[1] * 2, del);
            del -= t;
            p -= t / 2;
        }
        if (p && del) {
            int t = min(p * 3, del);
            p -= t / 3;
        }
        return res + max(p, 3 - k);
    }
};



dade68
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

统计左上角的个数

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int res = 0, n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++) {
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;
                if (board[i][j] == 'X') res ++;
            }
        return res;
    }
};