头像

wyf

山西大学




离线:11天前


最近来访(4)
用户头像
Rezarc
用户头像
KONNG
用户头像
努力至死不渝
用户头像
Michael.


wyf
2个月前
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int n = A.size();
        for (int i = 1; i < n - 1; i++)
            if (A[i - 1] < A[i] && A[i] > A[i + 1])
                return i;
        return -1;
    }
};


活动打卡代码 LeetCode 851. 喧闹和富有

wyf
2个月前
class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> edges(n);
        vector<int> deg(n, 0);

        for (auto &e : richer) {
            edges[e[0]].push_back(e[1]);
            deg[e[1]]++;
        }

        queue<int> q;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = i;
            if (deg[i] == 0)
                q.push(i);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &v : edges[u]) {
                deg[v]--;
                if (quiet[ans[v]] > quiet[ans[u]])
                    ans[v] = ans[u];
                if (deg[v] == 0)
                    q.push(v);
            }
        }
        return ans;
    }
};



wyf
2个月前
/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Master {
 *   public:
 *     int guess(string word);
 * };
 */
class Solution {
public:
    int get(vector<int>& g, vector<bool>& st, int u) {
        int res = 0;
        for (int i = 0; i < g.size(); i ++ )
            if (g[i] == u && st[i])
                res ++ ;
        return res;
    }

    void findSecretWord(vector<string>& wordlist, Master& master) {
        int n = wordlist.size();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                for (int k = 0; k < 6; k ++ )
                    if (wordlist[i][k] == wordlist[j][k])
                        f[i][j] ++ ;

        vector<bool> st(n, true);
        for (int i = 0; i < 10; i ++ ) {
            int k = -1, t = INT_MAX;
            for (int j = 0; j < n; j ++ ) {
                if (!st[j]) continue;
                int s = 0;
                for (int u = 0; u <= 6; u ++ )
                    s = max(s, get(f[j], st, u));
                if (t > s) {
                    k = j;
                    t = s;
                }
            }
            int res = master.guess(wordlist[k]);
            if (res == 6) break;
            st[k] = false;
            for (int j = 0; j < n; j ++ )
                if (f[k][j] != res)
                    st[j] = false;
        }
    }
};


活动打卡代码 LeetCode 837. 新21点

wyf
2个月前
class Solution {
public:
    double new21Game(int N, int K, int W) {
        if (K == 0) return 1.0;

        vector<double> f(N + 1, 0), s(N + 1, 0);
        f[0] = s[0] = 1;

        for (int i = 1; i <= N; i++) {
            int l = max(0, i - W), r = min(K - 1, i - 1);

            if (l <= r) {
                if (l == 0) f[i] = s[r] / W;
                else f[i] = (s[r] - s[l - 1]) / W;
            }

            s[i] = s[i - 1] + f[i];
        }

        return s[N] - s[K - 1];
    }
};


活动打卡代码 LeetCode 850. 矩形面积 II

wyf
2个月前
typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

class Solution {
public:
    const int MOD = 1e9 + 7;
    vector<vector<int>> rects;

    int calc(int a, int b) {
        vector<PII> q;
        for (auto& r: rects)
            if (a >= r[0] && b <= r[2])
                q.push_back({r[1], r[3]});
        sort(q.begin(), q.end());

        int res = 0, st = -1, ed = -1;
        for (auto& t: q)
            if (t.x > ed) {
                res = (res + ed - st) % MOD;
                st = t.x, ed = t.y;
            } else {
                ed = max(ed, t.y);
            }
        res = (res + ed - st) % MOD;
        return res * (LL)(b - a) % MOD;
    }

    int rectangleArea(vector<vector<int>>& rectangles) {
        rects = rectangles;
        vector<int> xs;
        for (auto& r: rects) {
            xs.push_back(r[0]);
            xs.push_back(r[2]);
        }
        sort(xs.begin(), xs.end());
        int res = 0;
        for (int i = 1; i < xs.size(); i ++ )
            res = (res + calc(xs[i - 1], xs[i])) % MOD;
        return res;
    }
};



wyf
2个月前
class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int res = 0;
        for (int i = 0; i < seats.size(); i ++ ) {
            if (seats[i]) continue;
            int j = i + 1;
            while (j < seats.size() && !seats[j]) j ++ ;
            if (!i) res = max(res, j - i);
            if (j == seats.size()) res = max(res, j - i);
            res = max(res, (j - i + 1) / 2);
            i = j;
        }
        return res;
    }
};


活动打卡代码 LeetCode 848. 字母移位

wyf
2个月前
class Solution {
public:
    #define LL long long
    string shiftingLetters(string S, vector<int>& shifts) {
        int n = S.length();
        LL tot = 0;
        for (int i = n - 1; i >= 0; i--) {
            tot += shifts[i];
            S[i] = (S[i] - 'a' + tot) % 26 + 'a';
        }
        return S;
    }
};



wyf
2个月前
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> map(n, vector<int>(n, n * n));
        vector<vector<int>> f(1 << n, vector<int>(n, n * n));

        for (int i = 0; i < n; i++)
            for (auto j : graph[i])
                map[i][j] = map[j][i] = 1;


        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

        for (int i = 0; i < n; i++)
            f[1 << i][i] = 0;

        for (int S = 0; S < (1 << n); S++)
            for (int i = 0; i < n; i++)
                if (S & 1 << i)
                    for (int j = 0; j < n; j++)
                        if (! (S & (1 << j)))
                            f[S | (1 << j)][j] = min(f[S | (1 << j)][j], f[S][i] + map[i][j]);

        int ans = n * n;
        for (int i = 0; i < n; i++)
            ans = min(ans, f[(1 << n) - 1][i]);
        return ans;
    }
};


活动打卡代码 LeetCode 846. 一手顺子

wyf
2个月前
class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        int n = hand.size();
        if (n % W != 0)
            return false;
        multiset<int> s(hand.begin(), hand.end());
        multiset<int>::iterator it;
        for (int i = 0; i < n / W; i++) {
            int st = *s.begin();
            for (int j = st; j < st + W; j++) {
                it = s.find(j);
                if (it == s.end())
                    return false;
                s.erase(it);
            }
        }
        return true;
    }
};



wyf
2个月前
class Solution {
public:
    int longestMountain(vector<int>& A) {
        int n = A.size(), ans = 0;
        int last = 0;
        bool up = false, down = false;
        for (int i = 1; i < n; i++) {
            if (A[i] == A[i - 1]) {
                last = i;
                up = down = false;
            }
            else if (A[i] > A[i - 1]) { // up
                if (down) {
                    down = false;
                    last = i - 1;
                }
                up = true;
            }
            else {  // down
                if (!up) {
                    last = i;
                    down = false;
                }
                else {
                    down = true;
                }
            }
            if (up && down)
                ans = max(ans, i - last + 1);
        }
        return ans;
    }
};