头像

sep

hhh联盟




离线:17小时前


最近来访(57)
用户头像
AcWing2AK
用户头像
一万小时定律
用户头像
退站.AC_Boy
用户头像
WangJY
用户头像
cyz3209
用户头像
Gzm1317
用户头像
Justice
用户头像
LJ24PengHR
用户头像
猫公爵
用户头像
盖上被被睡觉觉
用户头像
ZDC
用户头像
xkf
用户头像
Lurrick
用户头像
ustc-lj
用户头像
不拿NOI金牌不改名
用户头像
DPH
用户头像
诺亚方舟.
用户头像
RyanMoriarty
用户头像
M4LLKN0W
用户头像
Kafuu_Chino

活动打卡代码 LeetCode 1282. 用户分组

sep
5天前
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& g) {
        vector<vector<int>> res;
        unordered_map<int, vector<int>> hash;
        for (int i = 0; i < g.size(); i ++ ) {
            hash[g[i]].push_back(i);
            if (hash[g[i]].size() == g[i]) {
                res.push_back(hash[g[i]]);
                hash[g[i]] = {};
            }
        }
        return res;
    }
};



sep
1个月前
class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size();
        vector<vector<int>> f(n + 1, vector<int>(3, INT_MIN));
        f[0][1] = 0;
        for (int i = 1; i <= n; i ++ ) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] - p[i - 1]);
            f[i][1] = max(f[i - 1][1], f[i - 1][2]);
            f[i][2] = f[i - 1][0] + p[i - 1];
        }
        return max(f[n][1], f[n][2]);
    }
};


活动打卡代码 LeetCode 677. 键值映射

sep
1个月前
const int N = 2510;
int son[N][26], idx, w[N];
class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        memset(son, 0, sizeof son);
        memset(w, 0, sizeof w);
        idx = 0;
    }

    void insert(string key, int val) {
        int p = 0;
        for (auto c: key) {
            int u = c - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        w[p] = val;
    }

    int sum(string prefix) {
        int p = 0, res = 0;
        for (auto c: prefix) {
            int u = c - 'a';
            if (son[p][u]) p = son[p][u];
            else return 0;
        }
        return dfs(p);
    }
    int dfs(int p) {
        int res = w[p];
        for (int i = 0; i < 26; i ++ )
            if (son[p][i])
                res += dfs(son[p][i]);
        return res;
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */



sep
1个月前
class MagicDictionary {
public:
    /** Initialize your data structure here. */
    struct Node {
        bool is_end;
        Node* son[26];
        Node() {
            is_end = false;
            memset(son, 0, sizeof son);
        }
    }*root;

    void insert(string w) {
        auto p = root;
        for (int i = 0; i < w.size(); i ++ ) {
            int idx = w[i] - 'a';
            if (!p->son[idx]) p->son[idx] = new Node();
            p = p->son[idx];
        }
        p->is_end = true;
    }

    MagicDictionary() {

    }

    void buildDict(vector<string> dictionary) {
        root = new Node();
        for (auto& w : dictionary) {
            insert(w);
        }
    }

    bool search(string w) {
        return dfs(w, 0, 1, root);
    }

    bool dfs(string w, int u, int t, Node* p) {
        if (u == w.size()) {
            if (t == 0 && p->is_end) return true;
            return false;
        }
        if (t < 0) return false;
        int idx = w[u] - 'a';
        for (int i = 0; i < 26; i ++ ) {
            if (p->son[i]) {
                if (dfs(w, u + 1, t - (i != idx), p->son[i]))
                    return true;
            }
        }
        return false;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */


活动打卡代码 LeetCode 684. 冗余连接

sep
1个月前
class Solution {
public:
    vector<int> p;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for (int i = 0; i < 2 * n; i ++ ) p.push_back(i);
        for (auto e : edges) {
            int a = e[0], b = e[1];
            int pa = find(a), pb = find(b);
            if (pa == pb) return {a, b};
            else p[pa] = pb;
        }
        return edges[n - 1];
    }
};



sep
1个月前
class Solution {
public:
    vector<int> p;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool check(string& a, string& b) {
        if (a == b) return true;
        vector<int> q;
        for (int k = 0; k < a.size(); k ++ ) {
            if (a[k] != b[k]) {
                q.push_back(k);
            }
        }
        if (q.size() != 2) return false;
        int x = q[0], y = q[1];
        return a[x] == b[y] && a[y] == b[x];
    }
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        for (int i = 0; i < n; i ++ ) {
            p.push_back(i);
        }
        for (int i = 0; i < n; i ++ )
            for (int j = i + 1; j < n; j ++ ) {
                string a = strs[i], b = strs[j];
                if (check(a, b)) {
                    p[find(i)] = find(j);
                }
            }
        int ans = 0;
        for (int i = 0; i < n; i ++ )
            if (find(i) == i)
                ans ++;
        return ans;
    }
};


活动打卡代码 LeetCode 547. 朋友圈

sep
1个月前
const int N = 210;
int p[N];
class Solution {
public:
    int n;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        for (int i = 1; i <= n; i ++ ) {
            p[i] = i;
        }
        for (int i = 1; i <= n; i ++ )
            for (int j = i + 1; j <= n; j ++ ) {
                int a = i, b = j;
                if (isConnected[i - 1][j - 1] == 1) {
                    a = find(a), b = find(b);
                    if (a != b) {
                        p[a] = b;
                    }
                }
            }
        int ans = 0;
        for (int i = 1; i <= n; i ++ )
            if (find(i) == i) ans ++;
        return ans;
    }
};


活动打卡代码 LeetCode 210. 课程表 II

sep
1个月前
const int N = 2010;
class Solution {
public:
    vector<int> g[N];
    int d[N];
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
        memset(d, 0, sizeof d);
        for (auto p : prerequisites) {
            int a = p[0], b = p[1];
            g[b].push_back(a);
            d[a] ++;
        }
        queue<int> q;
        for (int i = 0; i < n; i ++ )
            if (!d[i])
                q.push(i);

        vector<int> res;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            res.push_back(t);
            for (auto v : g[t]) {
                if (--d[v] == 0)
                    q.push(v);
            }
        }
        if (res.size() != n) return {};
        return res;
    }
};



sep
1个月前
const int N = 210;
class Solution {
public:
    int f[N][N];
    int ans = 1, n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    vector<vector<int>> g;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        memset(f, -1, sizeof f);
        g = matrix;
        n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                ans = max(ans, dfs(i, j));
        return ans;
    }
    int dfs(int x, int y) {
        int& v = f[x][y];
        if (v != -1) return v;
        int res = 1;
        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 && g[a][b] < g[x][y])
                res = max(res, dfs(a, b) + 1);
        }
        return v = res;
    }
};


活动打卡代码 LeetCode 399. 除法求值

sep
1个月前
class Solution {
public:
    int n = 0;
    double temp;
    double g[30][30];
    bool vis[30];
    unordered_map<string, int> hash;
    int getID(string a) {
        if (!hash.count(a)) hash[a] = n ++;
        return hash[a];
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); i ++ ) {
            int a = getID(equations[i][0]), b = getID(equations[i][1]);
            g[a][b] = values[i], g[b][a] = 1 / values[i];
        }
        vector<double> res;
        for (auto& t : queries) {
            string a = t[0], b = t[1];
            if (!hash.count(a) || !hash.count(b)) res.push_back(-1);
            else {
                memset(vis, 0, sizeof vis);
                if (dfs(getID(a), getID(b), 1)) res.push_back(temp);
                else res.push_back(-1);
            }
        }
        return res;
    }
    bool dfs(int u, int b, double m) {
        if (u == b) {
            temp = m;
            return true;
        }
        vis[u] = true;
        for (int i = 0; i < n; i ++ ) {
            if (g[u][i] != 0 && !vis[i])
                if (dfs(i, b, m * g[u][i]))
                    return true;
        }
        return false;
    }
};