力扣每月题解汇总-2025年09月

目录

力扣每日一题1792-最大平均通过率

日期：2025-09-01

题意

给定每个班级的总人数以及通过考试的人数，同时给定 extraStudents 个保证可以通过考试的人数，需将这 extraStudents 个学生分配到各个班级，使得各班级的平均通过率最大。求最大班级平均通过率。

思路

可以发现给不同的班级分配必过学生对通过率的影响是不同的，那直接根据这个影响进行排序开贪即可。由于有多个额外学生，使用优先队列进行维护就好。

实现

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto cmp = [&](const auto& x, const auto& y) {
            return 1ll * (x[1] - x[0]) * (y[1] + 1) * y[1] < 1ll * (y[1] - y[0]) * (x[1] + 1) * x[1];
        };
        priority_queue<array<int, 2>, vector<array<int, 2>>, decltype(cmp)> pq(cmp);

        for (const auto& vec : classes) {
            pq.push({vec[0], vec[1]});
        }

        while (extraStudents--) {
            auto [x, y] = pq.top();
            pq.pop();
            pq.push({x + 1, y + 1});
        }

        double s = 0;
        int n = classes.size();
        while (!pq.empty()) {
            auto [x, y] = pq.top();
            pq.pop();
            s += 1.0 * x / y;
        }
        return s / n;
    }
};
class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        pq = [(-((a + 1) / (b + 1) - a / b), a, b) for a, b in classes]
        heapify(pq)

        for _ in range(extraStudents):
            _, a, b = pq[0]
            a += 1
            b += 1
            heapreplace(pq, (-((a + 1) / (b + 1) - a / b), a, b))

        return sum(a / b for _, a, b in pq) / len(pq)

力扣每日一题3025-人员站位的方案数I

日期：2025-09-02

题意

给定 n 个点，求有多少点对 (A, B) 满足 A 在 B 的左上角且以 AB 为对角线的矩形内无其他点。

思路

注意到数据范围很小 1 <= n <= 50 所以可以直接暴力判断（见python）实现。

也可以对点的坐标进行排序判断（见cpp实现）。

实现

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        ans = 0
        for x0, y0 in points:
            for x1, y1 in points:
                if (x1 == x0 and y1 == y0) or (x1 < x0 or y1 > y0):
                    continue
                ans += 1
                for x2, y2 in points:
                    if (x0 == x2 and y0 == y2) or (x1 == x2 and y1 == y2):
                        continue
                    if x0 <= x2 <= x1 and y1 <= y2 <= y0:
                        ans -= 1
                        break
        return ans
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        ranges::sort(points, [&](const auto& x, const auto& y) {
            if (x[0] == y[0]) return x[1] > y[1];
            return x[0] < y[0];
        });
        int ans = 0;
        const int n = points.size();
        for (int i = 0; i < n; i++) {
            int my = INT_MIN;
            for (int j = i + 1; j < n && my < points[i][1]; j++) {
                if (points[j][1] <= points[i][1] && points[j][1] > my) {
                    my = points[j][1];
                    ans++;
                }
            }
        }
        return ans;
    }
};

力扣每日一题3027-人员站位的方案数II

日期：2025-09-03

题意

给定 n 个点，求有多少点对 (A, B) 满足 A 在 B 的左上角且以 AB 为对角线的矩形内无其他点。

思路

那和昨天的题是完全一样的，只是数据范围进行了增强 1 <= n <= 1000 ，那就没办法继续暴力了，使用昨日的cpp实现方法：按坐标进行排序即可。

实现

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda p: (p[0], -p[1]))
        ans = 0
        for i, (x0, y0) in enumerate(points):
            my = -inf
            for (x1, y1) in points[i + 1 : ]:
                if y1 <= y0 and y1 > my:
                    my = y1
                    ans += 1
                if my >= y0:
                    break
        return ans
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        ranges::sort(points, [&](const auto& x, const auto& y) {
            if (x[0] == y[0]) return x[1] > y[1];
            return x[0] < y[0];
        });
        int ans = 0;
        const int n = points.size();
        for (int i = 0; i < n; i++) {
            int my = INT_MIN;
            for (int j = i + 1; j < n && my < points[i][1]; j++) {
                if (points[j][1] <= points[i][1] && points[j][1] > my) {
                    my = points[j][1];
                    ans++;
                }
            }
        }
        return ans;
    }
};

力扣每日一题3516-找到最近的人

日期：2025-09-04

题意

给定三个整数表示三个人的位置，第一第二人均向第三人以相同速度走去而第三人不动，求谁先碰上第三人。

思路

没什么特别的，两人相遇时间显然可以用距离表示，比较第一第二人与第三人的距离即可。

实现

class Solution {
public:
    int findClosest(int x, int y, int z) {
        int t = abs(x - z) - abs(y - z);
        if (t < 0) return 1;
        else if (t == 0) return 0;
        return 2;
    }
};
class Solution:
    def findClosest(self, x: int, y: int, z: int) -> int:
        t = abs(x - z) - abs(y - z)
        if t < 0:
            return 1
        elif t == 0:
            return 0
        return 2

力扣每日一题2749-得到整数零需要执行的最少操作数

日期：2025-09-05

题意

给定两个整数 num1 与 num2 ，每一次操作可任选 令 。判断是否可以将 num1 减为 0 并求出最少操作次数。

思路

注意到 1 <= num1 <= 1e9 -1e9 <= num2 <= 1e9，显然最多的操作次数不会超过 40 次。对操作次数进行枚举即可。

显然在操作 k 次后，剩余数转为二进制的 1 数量必须小于 k 且 剩余的数大于等于 k

实现

class Solution {
using ll = long long;
using ull = unsigned long long;
public:
    int makeTheIntegerZero(int num1, int num2) {
        for (int k = 1; k <= 40; k++) {
            ll t = num1 - 1ll * num2 * k;
            if (t <= 0) break;
            if (popcount(ull(t)) <= k && t >= k) return k;
        }
        return -1;
    }
};
class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in range(1, 40):
            t = num1 - k * num2
            if t <= 0:
                break
            if t.bit_count() <= k and t >= k:
                return k
        return -1

力扣每日一题3495-使数组元素都变为零的最少操作次数

日期：2025-09-06

题意

给定一组询问 queries 每个询问给定两数 l, r 表示给出连续的整数数组 [l, r]，对于每个询问的每次操作，可以任选同一数组中的两个数 a, b 令 a = floor(a / 4), b = floor(b / 4) 。求将所有询问的数组中都变为 0 的最小操作次数之和。

思路

a = floor(a / 4) 等价于 a >>= 2 那么将 a 变为 0 的操作次数就是其二进制表示下的长度比二向上取整即 (a.bit_length() + 1) // 2 == a.bit_length() + 1 >> 1。

但 [l, r] 的范围可能较大，不太好枚举，进行一个式子的推即可。

实现

def cal(x):
    t = x.bit_length()
    res = (t + 1 >> 1) * (x + 1 - (1 << t >> 1))
    res += sum((i + 1 >> 1) * (1 << i >> 1) for i in range(1, t))
    return res

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
       return sum(cal(r) - cal(l - 1) + 1 >> 1 for l, r in queries) 
class Solution {
using ll = long long;
public:
    long long minOperations(vector<vector<int>>& queries) {
        auto cal = [&](int x) -> ll {
            int t = bit_width(unsigned(x));
            ll res = 1ll * ((t + 1) >> 1) * (x + 1 - (1 << t >> 1));
            for (int i = 1; i < t; i++) {
                res += 1ll * ((i + 1) >> 1) * (1 << i >> 1);
            }
            return res;
        };

        ll ans = 0;
        for (const auto& q : queries) {
            ans += (cal(q[1]) - cal(q[0] - 1) + 1) >> 1;
        }
        return ans;
    }
};

力扣每日一题1304-和为零的 N 个不同整数

日期：2025-09-07

题意

给定整数 n 返回任意大小为 n 由不同整数组成且和为 0 的数组。

思路

比较简单的构造题，随便写写满足题意就可以了。

实现

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ans(n);
        for (int i = 0, t = 1; i < n; i++) {
            if (i & 1) {
                ans[i] = -(t++);
            } else {
                ans[i] = t;
            }
        }
        if (n & 1) ans[n - 1] = 0;
        return ans;
    }
};
class Solution:
    def sumZero(self, n: int) -> List[int]:
        ans = [0] * n
        t = 1
        for i in range(n):
            if i & 1:
                ans[i] = -t
                t += 1
            else:
                ans[i] = t
        if n & 1:
            ans[-1] = 0
        return ans

力扣每日一题1317-将整数转换为两个无零整数的和

日期：2025-09-08

题意

给定一个正整数 n 将其拆分为两个十进制下不含 0 的数的和。

思路

注意到数据范围并不大， 2 <= n <= 1e4 ，那咱们简单问题简单做进行一个枚举即可。

实现

class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
        auto check = [](int x) -> bool {
            string s = to_string(x);
            for (char ch : s) {
                if (ch == '0') return false;
            }
            return true;
        };
        for (int i = 1; i < n; i++) {
            if (check(i) && check(n - i)) return {i, n - i};
        }
        return {-1};
    }
};
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        def check(x):
            for ch in str(x):
                if ch == '0':
                    return False
            return True

        for i in range(1, n):
            if check(i) and check(n - i):
                return [i, n - i]
        return -1

力扣每日一题2327-知道秘密的人数

日期：2025-09-09

题意

第 1 天有 1 个人知道了一个秘密，一个人在知道秘密的 forget 天后会遗忘这个秘密，同时一个人在知道秘密的 delay 天后未遗忘前会每天告诉一个新人这个秘密。求第 n 天后有多少人知道这个秘密。

思路

数据范围并不大 1 <= n <= 1000 那显然不是什么数学题不用推什么公式的。

维护当前知道的人数、当前会每天告诉新人秘密的人数，以及每天新知道秘密的人数进行模拟即可。当前知道的人数 与 每天新知道秘密的人数 可以用 当前会每天告诉新人秘密的人数 更新，而 当前会每天告诉新人秘密的人数 可以通过 forget 天前与 delay 天前 新知道的人数更新。进行一个模拟即可。

实现

mod = 1000000007
class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        f = [1] + [0] * (n - 1)
        ans = 1
        p = 0
        for i in range(n):
            if i >= delay:
                p += f[i - delay]
            if i >= forget:
                p -= f[i - forget]
                ans -= f[i - forget]
            f[i] += p
            ans += p
        return (ans + mod) % mod
class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<int> f(n);
        int ans = 1, p = 0;
        f[0] = 1;
        for (int i = 0; i < n; i++) {
            if (i >= delay) {
                p += f[i - delay];
                if (p >= mod) p -= mod;
            }
            if (i >= forget) {
                p -= f[i - forget];
                p += mod;
                if (p >= mod) p -= mod;
                ans -= f[i - forget];
                ans += mod;
                if (ans >= mod) ans -= mod;
            }
            f[i] += p;
            ans += p;
            if (ans >= mod) ans -= mod;
        }
        return (ans + mod) % mod;
    }
};

力扣每日一题1733-需要教语言的最少人数

日期：2025-09-10

题意

有 n 种语言， m 个人，其中已知所有人已会的语言，同时知道某些人之间存在朋友关系。两两之间需要会任意同种语言才可交流。现欲教某些人同一种语言，使得所有朋友之间可以互相交流，求最少教几人。

思路

n 和 m 的范围都不是很大，均在 500 以内，那其实可以随便乱搞的。

这里我是先找到所有存在无法交流朋友的人，枚举所教的语言，所需教的人即为 存在无法交流朋友的人 - 存在无法交流朋友且会该语言的人

实现

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        know = list(map(set, languages))
        
        p = set()
        for u, v in friendships:
            if know[u - 1].isdisjoint(know[v - 1]):
                p.add(u - 1)
                p.add(v - 1)

        ans = len(languages)
        for i in range(1, n + 1):
            ans = min(ans, len(p) - sum(i in know[x] for x in p))
        return ans
class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        const int m = languages.size();
        vector know(m, vector<bool> (n));
        for (int i = 0; i < m; i++) {
            for (const auto& x : languages[i]) {
                know[i][x - 1] = true;
            }
        }

        unordered_set<int> p;
        for (const auto& f : friendships) {
            int u = f[0], v = f[1];
            u--; v--;
            bool need = true;
            for (const auto& x : languages[u]) {
                if (know[v][x - 1]) {
                    need = false;
                    break;
                }
            }
            if (need) {
                p.insert(u);
                p.insert(v);
            }
        }

        int ans = m;
        for (int i = 0; i < n; i++) {
            int t = 0;
            for (const auto& x : p) {
                if (know[x][i]) t++;
            }
            ans = min(ans, int(p.size()) - t);
        }
        return ans;
    }
};

力扣每日一题2785-将字符串中的元音字母排序

日期：2025-09-11

题意

给定英文字符串，将其中辅音字母保持不动，元音字母按ASCII序进行排序。

思路

将其中元音字母及对应位置记录下来，排序后填回即可。

实现

class Solution {
unordered_set<char> ust{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
public:
    string sortVowels(string s) {
        const int n = s.size();
        vector<int> p;
        vector<char> ch;
        for (int i = 0; i < n; i++) {
            if (ust.count(s[i])) {
                ch.push_back(s[i]);
                p.push_back(i);
            }
        }
        ranges::sort(ch);
        for (int i = 0; i < p.size(); i++) {
            s[p[i]] = ch[i];
        }
        return s;
    }
};
class Solution:
    def sortVowels(self, s: str) -> str:
        t = list(s)
        vowels = "aeiouAEIOU"
        p = []
        ch = []
        for i, c in enumerate(s):
            if c in vowels:
                p.append(i)
                ch.append(c)
        ch.sort()
        for i, c in enumerate(ch):
            t[p[i]] = c
        return ''.join(t)

力扣每日一题3227-字符串元音游戏

日期：2025-09-12

题意

给定已字符串 s ，小明小红轮流进行游戏，小红先手：

  • 小红每次可以删除 s 中任意包含奇数个元音字符的子字符串
  • 小明每次可以删除 s 中任意包含偶数个元音字符的子字符串

谁先无法行动则失败。

判断小红是否必胜。

思路

简单手玩一下：

若开局无元音字母，显然小明必胜。

若开局有奇数个元音字母，小红可以直接删除整个字符串，小红胜。

若开局有偶数个元音字母，小红可以将字符串删至仅含单元音字母，若此时无其他辅音字母则小红胜；若含其他字母小明仅可删除辅音字母，再到小红时小红可将剩余字符全删除，仍是小红胜。

故而若字符串含元音字母则小红必胜。

实现

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        for ch in s:
            if ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u':
                return True
        return False
class Solution {
unordered_set<char> ust = {'a', 'e', 'i', 'o', 'u'};
public:
    bool doesAliceWin(string s) {
        int n = 0;
        for (const auto& ch : s) {
            if (ust.count(ch)) n++;
        }
        return n != 0;
    }
};

力扣每日一题3541-找到频率最高的元音和辅音

日期：2025-09-13

题意

给定小写英文字符串，返回其中出现频次最高的元音字母和辅音字母的频次和。

思路

没什么特别的，只需记录每个字母的出现次数，然后找出现次数最多的元音辅音即可。

实现

class Solution:
    def maxFreqSum(self, s: str) -> int:
        cnt = Counter(s)
        u = v = 0
        for i in range(26):
            ch = chr(ord('a') + i)
            if ch in "aeiou":
                u = max(u, cnt[ch])
            else:
                v = max(v, cnt[ch])
        return u + v
class Solution {
public:
    int maxFreqSum(string s) {
        array<int, 26> cnt;
        cnt.fill(0);
        for (const auto& ch : s) cnt[ch - 'a']++;
        int u = 0, v = 0;
        for (int i = 0; i < 26; i++) {
            char ch = i + 'a';
            if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
                u = max(u, cnt[i]);
            } else {
                v = max(v, cnt[i]);
            }
        }
        return u + v;
    }
};

力扣每日一题966-元音拼写检查器

日期：2025-09-14

题意

给定单词表 wordlist 以及询问若干个 queries ，对于每个询问给出一个字符串 query

  • 若字符串 query 可以再 wordlist 中找到，则返回对应单词表中单词
  • 若字符串 query 忽视大小写差异后可在 wordlist 中找到，则返回单词表中第一个符合的单词w
  • 若字符串 query 忽视大小写且各元音字母可以任意替换为其他元音字母后可在 wordlist 中找到，则返回单词表中第一个符合的单词。

思路

维护三个哈希表即可：

  • 原单词表的哈希表
  • 将所有单词转为小写字母的对应单词表
  • 将所有单词转为小写且元音字母均替换为 '*' 后的对应单词表

然后对询问做同样的处理并进行查询是否存在即可。

实现

class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> ori(wordlist.begin(), wordlist.end());
        unordered_map<string, vector<string>> bigSmall;
        unordered_map<string, vector<string>> vowel;

        for (const auto& s : wordlist) {
            auto t = s;
            for (auto& ch : t) {
                if (isupper(ch)) ch = char(ch - 'A' + 'a');
            }
            bigSmall[t].push_back(s);
            for (auto& ch : t) {
                if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') ch = '*';
            }
            vowel[t].push_back(s);
        }

        vector<string> ans;
        for (auto& s : queries) {
            if (ori.count(s)) {
                ans.push_back(s);
                continue;
            }
            for (auto& ch : s) if (isupper(ch)) ch = char(ch - 'A' + 'a');
            if (bigSmall.count(s)) {
                ans.push_back(bigSmall[s].front());
                continue;
            }
            for (auto& ch : s) if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') ch = '*';
            if (vowel.count(s)) {
                ans.push_back(vowel[s].front());
                continue;
            }
            ans.push_back("");
        }
        return ans;
    }
};

力扣每日一题1935-可以输入的最大单词数

日期：2025-09-15

题意

给定字符串 brokenLetters 表示键盘破损的键位，以及多个由空格分隔的单词组成的字符串 text ，返回 text 中可以完整打出的单词数量。

思路

简单问题简单做，使用哈希记录破损键盘或直接遍历 brokenLetters 都是可以的，然后遍历每个单词判断其是否含破损键位即可。

实现

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        array<int, 26> a;
        a.fill(0);
        for (const auto& ch : brokenLetters) a[ch - 'a'] = 1;

        int ans = 0, ok = 1;
        const int n = text.size();
        for (int i = 0; i < n; i++) {
            if (text[i] == ' ') {
                ans += ok;
                ok = 1;
            }
            else if (a[text[i] - 'a']) ok = 0;
        }
        return ans + ok;
    }
};
class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        ans = 0
        for word in text.split():
            if all(ch not in brokenLetters for ch in word):
                ans += 1
        return ans

力扣每日一题2197-替换数组中的非互质数

日期：2025-09-16

题意

给定数组 nums ，当 nums 中存在任意两相邻数不互质时将这两数替换为这两数的 lcm， 返回不会再发生合并后的结果。

思路

显然合并的顺序是不会影响最终结果的：x, y 不互质意味着 gcd(x, y) > 1 而两数的 lcm 实际上为两数的质因数分解后取各质因子的最高次幂，也就是说任意一个数 z 若可与 x 或 y 不互质，则其一定与 lcm(x, y) 不互质即 gcd(z, lcm(x, y)) > 1。

所以仅需一个栈进行维护即可。

实现

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> ans;
        for (auto x : nums) {
            while (!ans.empty() && gcd(ans.back(), x) != 1) {
                x = lcm(ans.back(), x);
                ans.pop_back();
            }
            ans.push_back(x);
        }
        return ans;
    }
};
class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        ans = []
        for x in nums:
            while len(ans) > 0 and gcd(x, ans[-1]) > 1:
                x = lcm(x, ans[-1])
                ans.pop()
            ans.append(x)
        return ans

力扣每日一题2349-设计数字容器系统

日期：2025-09-17

题意

实现一个数字容器系统，包含以功能

  • 在定下标处插入或替换一个数字
  • 返回给定数字的最小下标

思路

下标范围很大有 1 <= index <= 1e9 故而是不能直接数组模拟的，但是题目也明确了各个功能的调用总次数不超过 1e5 因此也无需太在意空间，直接使用哈希进行模拟即可。

实现

class NumberContainers {
private:
    unordered_map<int, int> loc;
    unordered_map<int, set<int>> ump;
public:
    NumberContainers() {
        loc.clear();
        ump.clear();
    }
    
    void change(int index, int number) {
        if (!loc.count(index)) {
            loc[index] = number;
            ump[number].insert(index);
        } else {
            ump[loc[index]].erase(index);
            if (ump[loc[index]].empty()) ump.erase(loc[index]);
            ump[number].insert(index);
            loc[index] = number;
        }
    }
    
    int find(int number) {
        if (!ump.count(number)) return -1;
        return *ump[number].begin();
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

力扣每日一题3408-设计任务管理器

日期：2025-09-18

题意

实现一个任务管理器系统，有如下功能：

  • 初始化，给定三维数组 tasks 其内 [userId, taskId, priority] 分别表示该任务的用户id 任务id 优先级
  • 添加一个 userId, taskId, priority 的任务
  • 将任务id为 taskId 的任务优先级修改为 newPriority
  • 删除任务id为 taskId 的任务
  • 返回优先级最高，若有多任务优先级等高则返回任务id最高的任务的用户id

思路

那没什么特别的，就是按照题意模拟即可。

实现

class TaskManager {
private:
    unordered_map<int, int> id2prio;
    unordered_map<int, int> id2uid;
    priority_queue<array<int, 3>> pq;
public:
    TaskManager(vector<vector<int>>& tasks) {
        for (const auto& t : tasks) {
            int uid = t[0], tid = t[1], pri = t[2];
            pq.push({pri, tid, uid});
            id2prio[tid] = pri;
            id2uid[tid] = uid;
        }
    }
    
    void add(int userId, int taskId, int priority) {
        pq.push({priority, taskId, userId});
        id2prio[taskId] = priority;
        id2uid[taskId] = userId;
    }
    
    void edit(int taskId, int newPriority) {
        id2prio[taskId] = newPriority;
        pq.push({newPriority, taskId, id2uid[taskId]});
    }
    
    void rmv(int taskId) {
        id2prio[taskId] = id2uid[taskId] = -1;
    }
    
    int execTop() {
        for ( ; !pq.empty(); pq.pop()) {
            auto [pri, tid, uid] = pq.top();
            if (pri == id2prio[tid]) {
                pq.pop();
                id2prio[tid] = -1;
                return uid;
            }
        }
        return -1;
    }
};

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager* obj = new TaskManager(tasks);
 * obj->add(userId,taskId,priority);
 * obj->edit(taskId,newPriority);
 * obj->rmv(taskId);
 * int param_4 = obj->execTop();
 */

力扣每日一题3484-设计电子表格

日期：2025-09-19

题意

实现一个电子表格，包含以下功能：

  • Spereadsheet(int rows) 初始化一个有 26 列和 rows 行的表格，其中列编号为 A-Z 行编号为 1-rows
  • setCell(string cell, int value) 将格 cell 的值置为 value
  • resetCell(string cell) 将格 cell 的值置为 0
  • getValue(string formula) 给定格式形如 =X+Y 的公式，若 X 为单元格则取对应单元格的值，若为数字则取对应数字值，返回 X + Y 的结果

思路

同样是没有什么特别的，进行一个模拟即可。

实现

class Spreadsheet {
private:
    unordered_map<string, int> data;
public:
    Spreadsheet(int rows) {
        data.clear();
    }
    
    void setCell(string cell, int value) {
        data[cell] = value;
    }
    
    void resetCell(string cell) {
        data[cell] = 0;
    }
    
    int getValue(string formula) {
        int plusloc = formula.find('+');
        string x = formula.substr(1, plusloc - 1);
        string y = formula.substr(plusloc + 1);
        int a = isupper(x.front()) ? data[x] : stoi(x);
        int b = isupper(y.front()) ? data[y] : stoi(y);
        return a + b;
    }
};

/**
 * Your Spreadsheet object will be instantiated and called as such:
 * Spreadsheet* obj = new Spreadsheet(rows);
 * obj->setCell(cell,value);
 * obj->resetCell(cell);
 * int param_3 = obj->getValue(formula);
 */

力扣每日一题3508-设计路由器

日期：2025-09-20

题意

每个数据包包含以下内容 [source, destination, timestamp]

实现 Router 类有如下功能：

  • Router(int memoryLimit) : 初始化，并设置固定内存限制，若未转发包数大于 memoryLimit 则不断丢弃最久的数据包
  • bool addPacket(int source, int destination, int timestamp) 添加对应数据包，若已存在完全相同的数据包则添加失败，返回添加结果
  • vector<int> forwardPacket() 按先入先出规则返回下一个未被丢弃的数据包
  • int getCount(int destination, int startTime, int endTime) 返回尚未转发目的地为 destination 且 startTime <= timeStamp <= endTime 的数据包数量

思路

也同样没什么特别的，进行一个模拟就好。

实现

struct Ahash {
    size_t operator()(const array<int, 3>& arr) const noexcept {
        size_t h1 = hash<int>{}(arr[0]);
        size_t h2 = hash<int>{}(arr[1]);
        size_t h3 = hash<int>{}(arr[2]);
        size_t seed = h1;
        seed ^= h2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= h3 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};
struct Aequal {
    bool operator()(const array<int, 3>& x, const array<int, 3>& y) const noexcept {
        return x == y;
    }
};

class Router {
private:
    int limit;
    unordered_set<array<int, 3>, Ahash, Aequal> ust;
    unordered_map<int, vector<int>> dst2time;
    unordered_map<int, int> dst2sz;
    queue<array<int, 3>> q;
public:
    Router(int memoryLimit) {
        limit = memoryLimit;
        ust.clear();
        dst2time.clear();
        dst2sz.clear();
    }
    
    bool addPacket(int source, int destination, int timestamp) {
        auto [it, ok] = ust.insert({source, destination, timestamp});
        if (!ok) return ok;
        dst2time[destination].push_back(timestamp);
        q.push({source, destination, timestamp});
        for ( ; q.size() > limit; q.pop()) {
            auto [source, destination, timestamp] = q.front();
            ust.erase({source, destination, timestamp});
            dst2sz[destination]++;
        }
        return ok;
    }
    
    vector<int> forwardPacket() {
        if (q.empty()) return {};
        auto [source, destination, timestamp] = q.front();
        q.pop();
        ust.erase({source, destination, timestamp});
        dst2sz[destination]++;
        return {source, destination, timestamp};
    }
    
    int getCount(int destination, int startTime, int endTime) {
        if (!dst2time.count(destination)) return 0;
        const auto& vec = dst2time[destination];
        int t = dst2sz[destination];
        auto l = ranges::lower_bound(vec.begin() + t, vec.end(), startTime);
        auto r = ranges::upper_bound(vec.begin() + t, vec.end(), endTime);
        return r - l;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

力扣每日一题1912-设计电影租借系统

日期：2025-09-21

题意

所有电影用数组 entries 表示，其中 entries[i] = [shop, movie, price] 分别表示对应商店 shop 有一份价格为 price 的电影 movie

实现含如下功能的 MovieRentingSystem 类

  • MovieRentingSystem(int n, vector<vector<int>>& entries) 构造函数
  • vector<int> search(int movie) 返回指定电影的未借出且最便宜的 5 个商店，不足 5 则全返回。按价格升序，若价格相同按商店编号升序排序。
  • void rent(int shop, int movie) 将指定商店的指定电影借出
  • void drop(int shop, int movie) 将指定电影归还到指定商店
  • vector<vector<int>> report() 返回已借出的最便宜的 5 部电影，按 [shop, movie] 返回该借出电影的信息。不足 5 则全返回。按价格升序，若价格相同按商店编号升序，若商店编号相同按电影编号升序排序。

保证所有输入合法，所有商店同一电影最多有一份。

思路

进行一个稍复杂的模拟即可。

实现

class MovieRentingSystem {
using ll = long long;
unordered_map<ll, int> price;
unordered_map<int, set<array<int, 2>>> umovies;
set<array<int, 3>> movies;
public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (const auto& e : entries) {
            int shop = e[0], m = e[1], p = e[2];
            price[(1ll * shop) << 32 | m] = p;
            umovies[m].insert({p, shop});
        }
    }
    
    vector<int> search(int movie) {
        vector<int> ans;
        for (const auto& arr : umovies[movie]) {
            ans.push_back(arr[1]);
            if (ans.size() >= 5) break;
        }
        return ans;
    }
    
    void rent(int shop, int movie) {
        int p = price[(1ll * shop) << 32 | movie];
        umovies[movie].erase({p, shop});
        movies.insert({p, shop, movie});
    }
    
    void drop(int shop, int movie) {
        int p = price[(1ll * shop) << 32 | movie];
        movies.erase({p, shop, movie});
        umovies[movie].insert({p, shop});
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        for (const auto& [p, s, m] : movies) {
            ans.push_back({s, m});
            if (ans.size() >= 5) break;
        }
        return ans;
    }
};

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
 * vector<int> param_1 = obj->search(movie);
 * obj->rent(shop,movie);
 * obj->drop(shop,movie);
 * vector<vector<int>> param_4 = obj->report();
 */

力扣每日一题3005-最大频率元素计数

日期：2025-09-22

题意

给定数组 nums ，返回数组中具有最大频率的元素的总频率和。

思路

使用哈希记录每个数的出现频次，再找出最大频次及其和即可。

实现

class Solution {
public:
    int maxFrequencyElements(vector<int>& nums) {
        vector<int> cnt(101);
        for (auto x : nums) cnt[x]++;
        int mx = 0, ans = 0;
        for (int i = 0; i <= 100; i++) {
            if (cnt[i] > mx) {
                mx = cnt[i];
                ans = cnt[i];
            } else if (cnt[i] == mx) ans += cnt[i];
        }
        return ans;
    }
};
class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        cnt = [0] * 101
        ans = mx = 0
        for x in nums:
            cnt[x] += 1
            if cnt[x] > mx:
                mx = cnt[x]
                ans = cnt[x]
            elif cnt[x] == mx:
                ans += cnt[x]
        return ans

力扣每日一题165-比较版本号

日期：2025-09-23

题意

给定两个由 '.' 分割开的数字版本号，比较两个版本号的大小。

思路

将两个版本号每一部分转换为数字进行比较就好，只是这里需要注意题目给定的每个数字范围是 所有修订号都可以存储在 32 位整数 中 如果用cpp的话需要开 unsigned 或者 long long。

实现

class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<unsigned> x, y;
        unsigned t = 0;
        for (const auto& ch : version1) {
            if (ch == '.') {
                x.push_back(t);
                t = 0;
            }
            else {
                t += 10 * t + (ch - '0');
            }
        }
        x.push_back(t);
        t = 0;
        for (const auto& ch : version2) {
            if (ch == '.') {
                y.push_back(t);
                t = 0;
            }
            else {
                t += 10 * t + ch - '0';
            }
        }
        y.push_back(t);

        while (x.size() < y.size()) x.push_back(0);
        while (y.size() < x.size()) y.push_back(0);

        if (x > y) return 1;
        else if (x < y) return -1;
        return 0;
    }
};
class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        for i, j in zip_longest(version1.split('.'), version2.split('.'), fillvalue=0):
            x = int(i)
            y = int(j)
            if (x > y):
                return 1
            elif (x < y):
                return -1
        return 0

力扣每日一题166-分数到小数

日期：2025-09-24

题意

给定分子分母，返回其表示的小数，若其有循环则将其循环节用 "()" 括起。

思路

模拟手算除法的操作即可，循环节的寻找可以通过使用哈希记录该余数是否出现过。

实现

class Solution {
using ll = long long;
public:
    string fractionToDecimal(int numerator, int denominator) {
        ll x = abs(1ll * numerator), y = abs(1ll * denominator);
        string ans;
        if (1ll * numerator * denominator < 0) ans += '-';
        ans += to_string(x / y);

        if (x % y == 0) return ans;
        ans += '.';

        unordered_map<ll, int> rem;
        ll r = x % y;
        rem[r] = ans.size();
        while (r) {
            r *= 10;
            ans += to_string(r / y);
            r %= y;
            if (rem.count(r)) {
                int p = rem[r];
                return ans.substr(0, p) + '(' + ans.substr(p) + ')';
            }
            rem[r] = ans.size();
        }

        return ans;
    }
};

力扣每日一题120-三角形最小路径和

日期：2025-09-25

题意

给定一个数字三角形，初始位于最上层顶点，每一步可以向正下或右下走一格，求到达最底层的最小路径和。

思路

那这是一道非常经典的dp问题了，每一个格子仅可能从其上或其左上的格子得来，因此其最小代价为其值加上可达其的格子的最小代价。注意边界的处理即可。

实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        const int n = triangle.size();
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < i; j++) {
                triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
            }
            triangle[i][0] += triangle[i - 1][0];
            triangle[i][i] += triangle[i - 1][i - 1];
        }
        return ranges::min(triangle.back());
    }
};
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for i in range(1, len(triangle)):
            for j in range(1, i):
                triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j])
            triangle[i][0] += triangle[i - 1][0]
            triangle[i][i] += triangle[i - 1][i - 1]
        return min(triangle[-1])

力扣每日一题611-有效三角形的个数

日期：2025-09-26

题意

给定一个非负整数数组 nums ， 返回其中可以组成三角形的三条边的三元组个数。

思路

数据范围 1 <= nums.size() <= 1000

可以考虑将边排序后，固定最短边，枚举次短边，最长边用一个指针维护，因为最短边固定 次短边按递增枚举 则其可以满足的最长边一定是递增的（三角形最短两边和大于最长边）

注意这里给定数是非负整数，即含有0即可。

实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        ranges::sort(nums);
        int ans = 0;
        int n = nums.size();
        for (int x = 0; x < n - 2; x++) {
            if (nums[x] == 0) continue;
            for (int y = x + 1, z = x + 2; y < n - 1; y++) {
                for ( ; z < n && nums[x] + nums[y] > nums[z]; z++);
                ans += z - y - 1;
            }
        }
        return ans;
    }
};
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        n = len(nums)
        for x in range(n - 2):
            if nums[x] == 0:
                continue
            z = x + 2
            for y in range(x + 1, n - 1):
                while z < n and nums[x] + nums[y] > nums[z]:
                    z += 1
                ans += z - y - 1
        return ans

力扣每日一题812-最大三角形面积

日期：2025-09-27

题意

给定二维平面点集 points 返回其中可组成面积最大的三角形的面积。

思路

点集的大小不大 3 <= points.size() <= 50 故而之间枚举三个点即可。

实现

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        auto cal = [](vector<int>& x, vector<int>& y, vector<int>& z) -> double {
            return 0.5 * abs(x[0] * y[1] + y[0] * z[1] + z[0] * x[1] - x[0] * z[1] - y[0] * x[1] - z[0] * y[1]);
        };

        int n = points.size();
        double ans = 0;
        for (int i = 0; i < n - 2; i++)
            for (int j = i + 1; j < n - 1;j ++)
                for (int k = j + 1; k < n; k++)
                    ans = max(ans, cal(points[i], points[j], points[k]));
        return ans;
    }
};
class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        def cal(x, y, z):
            return abs(x[0] * y[1] + y[0] * z[1] + z[0] * x[1] - x[0] * z[1] - y[0] * x[1] - z[0] * y[1]) / 2
        return max(cal(x, y, z) for x, y, z in combinations(points, 3))

力扣每日一题976-三角形的最大周长

日期：2025-09-28

题意

给定正整数数组 nums ，返回其可以组成的最长周长的三角形的周长。

思路

根据三角形最短两边和大于第三边，显然排序过后最长周长的三条边是连续的，由此排序后枚举找到第一个满足构成三角形条件的三条连续边即可。

实现

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        int n = nums.size();
        ranges::sort(nums, greater());
        for (int i = 2; i < n; i++) {
            if (nums[i] + nums[i - 1] > nums[i - 2]) return nums[i] + nums[i - 1] + nums[i - 2];
        }
        return 0;
    }
};
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        for i in range(2, len(nums)):
            if nums[i] + nums[i - 1] > nums[i - 2]:
                return sum(nums[i - 2 : i + 1])
        return 0

力扣每日一题1039-多边形三角剖分的最低得分

日期：2025-09-29

题意

给定长度为 n 的正整数数组 values ，表示一个凸多边形顺时针下各顶点的值。欲将其分割为 n - 2 个三角形，分割值为各三角形顶点值的积之和，求分隔值的最小。

思路

分割出一个三角形可以看作是三个顶点的合并，这样就可以将问题转换为了经典的区间dp。

实现

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        const int n = values.size();
        vector f(n, vector<int> (n));
        for (int len = 2; len < n; len++) {
            for (int i = 0, j = len; j < n; i++, j++) {
                f[i][j] = 1e9;
                for (int k = i + 1; k < j; k++) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        return f[0][n - 1];
    }
};
class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        @cache
        def dfs(i, j):
            if i == j or i + 1 == j:
                return 0
            return min(dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k] for k in range(i + 1, j))
        return dfs(0, len(values) - 1)

力扣每日一题2221-数组的三角和

日期：2025-09-30

题意

给定非负个位数数组 nums ，每次操作将 nums[i] = (nums[i] + nums[i + 1]) % 10 并将最后一个元素删除，直到数组只剩最后一个元素。求最后元素是什么。

思路

这题的数据范围并不大 1 <= nums.size() <= 1000

所以虽然确实有更加高级的做法，但有点太耗费脑子与时间了，咱们简单问题简单做，直接进行一个模拟就好。

实现

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        const int n = nums.size();
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                nums[j] = nums[j] + nums[j + 1];
                if (nums[j] >= 10) nums[j] -= 10;
            }
        }
        return nums[0];
    }
};
class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i):
                nums[j] = nums[j] + nums[j + 1]
                if nums[j] >= 10:
                    nums[j] -= 10
        return nums[0]