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

目录

力扣每日一题2141-同时运行N台电脑的最长时间

日期：2025-12-01

题意

给定正整数 n 与正整数数组 batteries 分别表示电脑数量与各电池的电量。每个电池同一时间可以供给一台电脑，每一单位电量可以供给一单位时间。求问最多可以同时开启所有电脑多长时间。

思路

咱们先想想，要求所有电脑开启 x 时间如何判断是否可行。若一个电池电量大于等于 x ，显然其全程只能供给一个，因为同一电池同一时间仅能供给一台电脑。而剩余的电池总电量仅需大于等于剩余电脑与总时之积即可。

由此我们可以想到对答案进行一个二分即可。

实现

class Solution {
using ll = long long;
public:
    ll maxRunTime(int n, vector<int>& batteries) {
        int m = batteries.size();

        auto check = [&](ll x) -> bool {
            int t = n;
            ll sum = 0;
            for (auto& b : batteries) {
                if (b >= x) t--;
                else sum += b;
            }
            return t <= 0 || sum / t >= x;
        };
        
        ll lo = 0, hi = accumulate(batteries.begin(), batteries.end(), 0ll) / n;
        while (lo < hi) {
            ll mid = (lo + hi + 1) / 2;
            if (check(mid)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    }
};

力扣每日一题3623-统计梯形的数目I

日期：2025-12-02

题意

给定二维坐标点集，求可从点集中组成多少个有一对边平行 x 轴的水平梯形。

思路

用哈希记录各纵坐标的点数，同纵坐标的点可以两两组成条边，而各不同纵坐标的边可两两组成一个水平梯形。

实现

using ll = long long;
static constexpr ll mod = 1e9 + 7;

ll powMod(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        unordered_map<int, int> cnt;
        for (const auto& vec : points) {
            int x = vec[0], y = vec[1];
            cnt[y]++;
        }
        ll ans = 0;
        vector<ll> tmp;
        ll inv2 = powMod(2, mod - 2);
        for (const auto& [y, t] : cnt) {
            if (t < 2) continue;
            // ans = ans * t % mod * (t - 1) % mod * powMod(2, mod - 2) % mod;
            tmp.push_back(1ll * t * (t - 1) % mod * inv2 % mod);
        }
        if (tmp.size() < 2) return 0;
        ll pre = 0;
        for (const auto& x : tmp) {
            ans = (ans + x * pre % mod) % mod;
            pre = (pre + x) % mod; 
        }
        return ans;
    }
};

力扣每日一题3625-统计梯形的数目II

日期：2025-12-03

题意

给定二维点集 points ，求可以组成多少梯形。

思路

和昨天的题很类似，只是没有了含一对边平行于 x 轴的限制。同时数据范围也小了很多 4 <= points.size() <= 500 。

那我们其实可以暴力去求点两两之间组成线段的斜率与截距，任意两斜率相同且截距不同的线段均可组成一个梯形。但需要注意，这样判断会将平行四边形计算两次，需对平行四边形进行去重，具体的，平行四边形两对角线中点重合，可借此进行去重处理。

实现

class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        int ans = 0;
        unordered_map<double, unordered_map<double, int>> line;
        unordered_map<int, unordered_map<double, int>> cnt;

        int n = points.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                double a = dx != 0 ? 1.0 * dy / dx : DBL_MAX;
                double b = dx != 0 ? 1.0 * (points[i][1] * dx - points[i][0] * dy) / dx : points[i][0];
                line[a][b]++;
                cnt[((points[i][0] + points[j][0] + 2000) << 16) | (points[i][1] + points[j][1] + 2000)][a]++;
            }
        }

        for (auto& [_, l] : line) {
            int pre = 0;
            for (auto& [__, t] : l) {
                ans += pre * t;
                pre += t;
            }
        }
        for (auto& [_, l] : cnt) {
            int pre = 0;
            for (auto& [__, t] : l) {
                ans -= pre * t;
                pre += t;
            }
        }
        return ans;
    }
};

力扣每日一题2211-统计道路上的碰撞次数

日期：2025-12-04

题意

给定字符串 directions 表示一排车的初始方向。若两辆车以相反的方向相撞则碰撞次数加 2 ；若移动车辆撞上静止车辆则移动次数加 1 。两车相撞后均保持停止在相撞位置。问最终总相撞次数。

思路

若从左往右遍历，显然只有向右与静止的车辆需要记录，进行一个模拟即可。

实现

class Solution {
public:
    int countCollisions(string directions) {
        int ans = 0;
        int t = 0;
        char last = '#';
        for (const auto& ch : directions) {
            if (ch == 'L') {
                if (last == 'R') {
                    ans += t + 1;
                    t = 0;
                    last = 'S';
                    continue;
                } else if (last == 'S') {
                    ans++;
                    last = 'S';
                    continue;
                }
            } else if (ch == 'S') {
                if (last == 'R') {
                    ans += t;
                    t = 0;
                    last = 'S';
                    continue;
                }
            } else {
                t++;
            }
            last = ch;
        }
        return ans;
    }
};

力扣每日一题3432-统计元素和差值为偶数的分区方案

日期：2025-12-05

题意

给定整数数组 nums ，将整个数组分为两个非空的子数组，求两子数组元素和之差为偶数的分割方案数。

思路

使用前缀和优化求两段子数组和的过程，然后枚举所分割的点即可。

实现

class Solution {
public:
    int countPartitions(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        vector<int> pre(n);
        for (int i = 0; i < n; i++) {
            if (i) pre[i] += pre[i - 1];
            pre[i] += nums[i];
        }
        for (int i = 0; i < n - 1; i++) {
            if (!((pre[i] << 1) - pre.back() & 1)) ans++;
        }
        return ans;
    }
};

力扣每日一题3578-统计极差最大为K的分割方式数

日期：2025-12-06

题意

给定整数数组 nums 与一个整数 k 。求该数组有多少种划分方法，使得每个子数组极差不超过 k 。

思路

显然是进行一个 dp，不过我们需要维护一个区间的方案数以及最大最小值。这几个技巧我们先前都有联系过，就不过多赘述了。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int countPartitions(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n + 1);
        f[0] = 1;
        deque<int> mn, mx;
        
        for (int i = 0, l = 0, pre = 0; i < n; i++) {
            pre += f[i];
            if (pre >= mod) pre -= mod;
            for ( ; !mn.empty() && nums[mn.back()] >= nums[i]; mn.pop_back());
            mn.push_back(i);
            for ( ; !mx.empty() && nums[mx.back()] <= nums[i]; mx.pop_back());
            mx.push_back(i);

            for ( ; nums[mx.front()] - nums[mn.front()] > k; ) {
                pre = (pre - f[l] + mod) % mod;
                l++;
                for ( ; !mn.empty() && mn.front() < l; mn.pop_front());
                for ( ; !mx.empty() && mx.front() < l; mx.pop_front());
            }
            f[i + 1] = pre;
        }
        return f[n];
    }
};

力扣每日一题1523-在区间范围内统计奇数数目

日期：2025-12-07

题意

给定非负整数 low 和 high ，求 [low, high] 之间的奇数个数。

思路

可以想到求一个数 x 及其之前的所有非负奇数的个数有 (x + 1) / 2 个。只需要分别求出 low 与 high 之前的奇数个数然后做差即可。

实现

class Solution {
public:
    int countOdds(int low, int high) {
        return (high + 1 >> 1) - (low >> 1);
    }
};

力扣每日一题1925-统计平方和三元组的数目

日期：2025-12-08

题意

给定正整数 n ，求满足 1 <= a, b, c <= n && a^2 + b^2 == c^2 的三元组 (a, b, c) 的个数。

思路

勾股数是有很多有意思的数学上的性质，但这里数据范围实在不大 1 <= n <= 250 咱们就简单问题简单做，进行一个暴力模拟即可。

实现

class Solution {
public:
    int countTriples(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int k = i * i + j * j;
                int sk = sqrt(k);
                if (sk <= n && sk * sk == k) ans += 2;
            }
        }
        return ans;
    }
};

力扣每日一题3583-统计特殊三元组

日期：2025-12-09

题意

给定整数数组 nums ，返回满足以下条件的三元组 (i, j, k) 个数:

  • 0 <= i < j < k < nums.size
  • nums[i] == nums[j] * 2 == nums[k]

思路

比较容易想到的实现思路是使用哈希维护各个数出现的个数，前后扫一趟得出前后缀为当前数两倍的数的个数，然后枚举中间值求解。

但我们需要求的仅为三元组个数，可以通过类似 dp 的思想维护一下 元组 i 的个数 与 元组 (i, j) && nums[i] == 2 * nums[j] 的个数，由此即可推出 (i, j, k) 的个数，相较而言可以少扫描一次，常数级别上稍稍快些。

实现

class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;
public:
    int specialTriplets(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, ll> f0, f1;
        ll ans = 0;
        for (int x : nums) {
            if (x % 2 == 0) ans += f1[x >> 1];
            f1[x] += f0[x << 1];
            f0[x]++;
        }
        return ans % mod;
    }
};

力扣每日一题3577-统计计算机解锁顺序排列数

日期：2025-12-10

题意

给定数组 complexity 表示多台上锁的计算机的密码复杂度。若要解锁编号为 i 的计算机需用已解锁的计算机 j 解锁且要求 j < i && complexity[j] < complexity[i] 。初始编号为 0 的计算机已解锁。问有多少种 [0, 1, 2..., n - 1] 的排列解锁顺序能将所有计算机解锁。

思路

咋一看有点复杂，但实际难点全在读懂题目上了。我们要按排列的方式一个一个去解锁所有的计算机，初始仅有 0 是解锁了的，所以 0 是固定好在首位的。若之后存在复杂度小于等于首个复杂度的必定无法解锁，这是可由解锁条件直接推出的。若之后所有数均严格 大于首个复杂度，那显然排序方式是不影响的，因为每台均可由首台解锁，则答案为 (n - 1)!

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int countPermutations(vector<int>& complexity) {
        int ans = 1;
        int n = complexity.size();
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) return 0;
            ans = 1ll * ans * i % mod;
        }
        return ans;
    }
};

力扣每日一题3531-统计被覆盖的建筑

日期：2025-12-11

题意

给定 n * n 大小的城市，以及所有建筑位置 buildings 。若某建筑上下左右方向上都至少存在一个建筑则称其被覆盖，求该城市被覆盖建筑个数。

思路

使用哈希记录每个横纵轴最大最小位置的建筑，对于某建筑若其不为所在横纵轴最大/最小建筑则其被覆盖。

实现

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        vector<int> xmn(n + 1, n), ymn(n + 1, n), xmx(n + 1, 0), ymx(n + 1, 0);
        for (const auto& b : buildings) {
            int x = b[0], y = b[1];
            xmn[y] = min(xmn[y], x);
            xmx[y] = max(xmx[y], x);
            ymn[x] = min(ymn[x], y);
            ymx[x] = max(ymx[x], y);
        }
        int ans = 0;
        for (const auto& b : buildings) {
            int x = b[0], y = b[1];
            ans += (xmn[y] < x && xmx[y] > x && ymn[x] < y && ymx[x] > y);
        }
        return ans;
    }
};

力扣每日一题3433-统计用户被提及情况

日期：2025-12-12

题意

给定数组 events 表示一堆消息，具体的 events[i] = [type_i, time_i, mentions_i] 。

  • 若 type_i 为 MESSAGE 表示在 time_i 时一组用户被消息提及。
    • 其中若 mentions_i 为 ALL 表示给所有用户发送消息，包括离线用户
    • 若 mentions_i 为 HERE 表示给所有在线用户发送消息
    • 若为多个由空格分隔的 id<numer> 表示给对应 numer 的用户发送消息，即使对方离线
  • 若 type_i 为 OFFLINE 表示 mentions_i 表示的用户在 time_i 开始离线 60 个单位时间，并会在 time_i + 60 时自动再次上线。

求所有用户被提及到的总次数。

思路

没什么特别的算法，就是根据题意进行模拟即可。只是这里需要注意给出来的事件并非是按时间顺序排好的，需要先排序一下，同时相同时间下优先处理下线逻辑。

实现

class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        ranges::sort(events, [&](const auto& x, const auto& y) {
            int xt = stoi(x[1]), yt = stoi(y[1]);
            if (xt == yt) return x[0] == "OFFLINE";
            return xt < yt;
        });
        vector<int> ans(numberOfUsers);
        vector<int> onlineT(numberOfUsers);
        int curT = 0;
        for (const auto& e : events) {
            auto message = e[0], ti = e[1], mentions = e[2];
            int t = stoi(ti);
            if (message == "MESSAGE") {
                if (mentions == "ALL") {
                    for (auto& x : ans) x++;
                } else if (mentions == "HERE") {
                    for (int i = 0; i < numberOfUsers; i++) {
                        if (onlineT[i] <= t) ans[i]++;
                    }
                } else {
                    int m = mentions.size();
                    for (int i = 0; i < m; i++) {
                        if (!isdigit(mentions[i])) continue;
                        int j = i + 1;
                        for ( ; j < m && isdigit(mentions[j]); j++);
                        int id = stoi(mentions.substr(i, j - i));
                        ans[id]++;
                        i = j;
                    }
                }
            } else {
                int id = stoi(mentions);
                onlineT[id] = t + 60;
            }
        }
        return ans;
    }
};

力扣每日一题3606-优惠券校验器

日期：2025-12-13

题意

给定三个等长数组 code、businessLine 和 isActive 分别表示多个优惠券的标识符、业务类别以及有效状态。若一个优惠券的标识符仅由字母数字与下划线组成，且业务类别属于 electronics /grocery/pharmacy/restaurant 之一，同时处于有效状态则称该优惠券有效。返回所有有效优惠券的标识符，以业务类型进行排序，相同业务类型的优惠券按标识符字典序升序排序。

思路

也没什么特别的做法，就是遍历优惠券，按题设条件判断其是否有效，分组排序后合并即可。

实现

unordered_map<string, int> s2i = {
    {"electronics", 0}, {"grocery", 1}, {"pharmacy", 2}, {"restaurant", 3}
};

class Solution {
public:
    vector<string> validateCoupons(vector<string>& code, vector<string>& businessLine, vector<bool>& isActive) {
        vector<vector<string>> s(4);
        int n = code.size();
        for (int i = 0; i < n; i++) {
            if (isActive[i] && s2i.count(businessLine[i])) {
                bool ok = !code[i].empty();
                for (auto& ch : code[i]) {
                    if (!isalpha(ch) && !isdigit(ch) && ch != '_') {
                        ok = false;
                        break;
                    }
                }
                if (ok) s[s2i[businessLine[i]]].emplace_back(move(code[i]));
            }
        }
        vector<string> ans;
        for (auto& vec : s) {
            ranges::sort(vec);
            ans.insert(ans.end(), vec.begin(), vec.end());
        }
        return ans;
    }
};

力扣每日一题2147-分隔长廊的方案数

日期：2025-12-14

题意

给定一条由座位与植物组成的长廊，需往其间空隙上放屏风使得长廊被分割为若干个恰有两座位的子段。求有多少种不同放置方案。

思路

假如我们先把所有的植物移除，那么放置方案显然是确定且唯一的。那不同的放置方案实际上就是，将座位按连续的两两分组，不同组之间的空隙数量之积。简单模拟计算即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int numberOfWays(string corridor) {
        int n = corridor.size();
        int ans = 1, t = 0, last = -1;
        for (int i = 0; i < n; i++) {
            if (corridor[i] == 'S') {
                t++;
                if (t > 2 && (t & 1)) {
                    ans = 1ll * ans * (i - last) % mod;
                }
                last = i;
            }
        }
        if ((t & 1) || t == 0) return 0;
        return ans;
    }
};

力扣每日一题2110-股票平滑下跌阶段的数目

日期：2025-12-15

题意

给定正整数数组 prices 表示某支股票的历史股价。若连续一天或多天每日股价比前一日股价恰好少 1 则称该阶段为平滑下降阶段。求所有平滑下降阶段的数目。

思路

那好像是有写过几次很类似的题目了。咱们直接进行一个滑动窗口求出当前最长平滑下降阶段，再用等差数列求和公式求出该段总贡献即可。

实现

class Solution {
using ll = long long;
public:
    ll getDescentPeriods(vector<int>& prices) {
        ll ans = 0;
        int n = prices.size();
        for (int i = 0; i < n; ) {
            int j = i + 1;
            for ( ; j < n && prices[j] == prices[j - 1] - 1; j++);
            ans += 1ll * (j - i + 1) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
};

力扣每日一题3562-折扣价交易股票的最大利润

日期：2025-12-16

题意

给定长度为 n 的数组 present 与 future 表示这 n 个员工当天购买股票的价格与明天可以卖出的价格。同时给出二维数组 hierarchy 表示员工之间直接的上下属关系。若某员工的直系上司购买了股票，则该员工可半价购买。在给定预算 budget 下，该公司的最大利润是多少。

思路

员工间的上下属关系可以转换为一棵树。那在不用考虑预算的情况下，显然是进行一个树形dp即可：递归处理每个结点，根据当前结点是否可以半价购买进行状态转移。

但加上预算要求应该怎么做呢，首先想到增加一个维度用来处理预算。记当前结点为 u 购买价格为 c 还剩预算 x ，若购买当前结点则所有子树剩余预算为 c - x 且直接的子节点可以半价购买；若不购买当前结点则剩余预算为 c 且直接的子节点只能原价购买。若所有子节点已经处理完毕，显然是要做一个树上背包的操作处理得到当前结点的最大价值。

实现

class Solution {
public:
    int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
        vector<vector<int>> e(n);
        for (const auto& h : hierarchy) {
            int u = h[0], v = h[1];
            u--; v--;
            e[u].push_back(v);
        }

        vector f(n, vector<array<int, 2>> (budget + 1));
        vector g(n, vector<array<int, 2>> (budget + 1));
        auto dfs = [&](this auto&& self, int u) -> void {
            for (auto v : e[u]) {
                self(v);
                for (int i = budget; i >= 0; i--) {
                    for (int j = 0; j <= i; j++) {
                        for (int k = 0; k < 2; k++) {
                            f[u][i][k] = max(f[u][i][k], f[u][i - j][k] + g[v][j][k]);
                        }
                    }
                }
            }
            for (int i = 0; i <= budget; i++) {
                for (int k = 0; k < 2; k++) {
                    int c = k ? present[u] / 2 : present[u];
                    if (i >= c) {
                        g[u][i][k] = max(f[u][i][0], f[u][i - c][1] + future[u] - c);
                    } else {
                        g[u][i][k] = f[u][i][0];
                    }
                }
            }
        };
        dfs(0);
        return g[0][budget][0];
    }
};

力扣每日一题3573-买卖股票的最佳时机V

日期：2025-12-17

题意

给定正整数数组 prices 表示每天的股票价格，同时我们仅能进行 k 笔交易，可进行如下类型的交易：

  • 普通交易：第 i 天买入，第 j 天卖出，获利 prices[j] - prices[i]
  • 做空交易：第 i 天卖出，第 j 天买入，获利 prices[i] - prices[j]

必须在当前交易结束后才可进行下一笔交易，求可获最大总利润。

思路

数据范围比较合适，同时状态间的转移关系也比较明显，还是可以比较自然想到使用dp的。

我们最多可以进行 k 笔交易，即最多可以买入 k 次卖出 k 次，因此我们可以将 k 次交易拆分为 2 * k 次操作，这样方便进行状态的转移。

同时我们有两种交易方式，那么我们其实仅有 3 种不同状态：1. 上一交易已完成可以任意开始下一交易； 2. 正在进行普通交易，已买入股票等待卖出； 3. 正在进行做空交易，已卖出股票等待买入。状态1通过开始对应交易进入对应交易状态，状态23通过完成当前交易回到状态1。最终答案显然是取状态1的最大值即可。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
public:
    ll maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        vector<array<ll, 3>> f(2 * k + 1, {-inf, -inf, -inf});
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = min(2 * k, i + 1); j > 0; j--) {
                f[j][0] = max({f[j][0], f[j - 1][1] + prices[i], f[j - 1][2] - prices[i]});
                f[j][1] = max(f[j][1], f[j - 1][0] - prices[i]);
                f[j][2] = max(f[j][2], f[j - 1][0] + prices[i]);
            }
        }
        ll ans = -inf;
        for (int i = 0; i <= 2 * k; i++) {
            ans = max(ans, f[i][0]);
        }
        return ans;
    }
};

力扣每日一题3652-按策略买卖股票的最佳时机

日期：2025-12-18

题意

给定整数数组 prices 和 strategy 分别表示每日股价与每日操作策略，其中每日策略有买入/卖出/持有三种。同时给定偶数 k ，可以对 strategy 进行最多一次修改：选择连续 k 天的策略，将前 k / 2 天操作均修改为持有，将后 k / 2 天操作均改为卖出。假定没有预算与持股等限制，求可获最大利润。

思路

修改某个子区间的操作，可以想到使用前缀和处理记录当前位置之前均改为持有以及均改为卖出对最终利润的影响。再通过枚举修改区间的左右边界进行求利润最大即可。

实现

class Solution {
using ll = long long;
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        const int n = prices.size();
        ll ans = 0;
        vector<ll> hold(n + 1), sole(n + 1);
        for (int i = 0; i < n; i++) {
            if (strategy[i] == 1) {
                ans += prices[i];
                hold[i + 1] = hold[i] - prices[i];
                sole[i + 1] = sole[i];
            } else if (strategy[i] == 0) {
                sole[i + 1] = sole[i] + prices[i];
                hold[i + 1] = hold[i];
            } else {
                ans -= prices[i];
                hold[i + 1] = hold[i] + prices[i];
                sole[i + 1] = sole[i] + prices[i] * 2; 
            }
        }

        ll mx = 0;
        for (int l = 0, m = k / 2 - 1, r = k - 1; r < n; l++, m++, r++) {
            mx = max(mx, hold[m + 1] - hold[l] + sole[r + 1] - sole[m + 1]);
        }
        return ans + mx;
    }
};

力扣每日一题2092-找出知晓秘密的所有专家

日期：2025-12-19

题意

给定数组 meetings 表示多个会议，其中 meeting[i] = [x_i, y_i, time_i] 表示在 time_i 时 x_i 与 y_i 处于同一个会议。每人可以同时参与多个会议，若会议中有人知道秘密则所有参会者均会知道秘密，同时秘密的传播是瞬时的，所有人均可在知道秘密的瞬间向其他人分享秘密。初始有 0 与 firstPerson 知道秘密，求开完所有会后所有知道秘密的人。

思路

参加同一个会议就可以知道秘密，由此我们可以比较自然的想到使用并查集处理每个会议，将所有参与同一个会议的人合并起来，最终与 0 同处一个并查集即表示其知道秘密。

但仔细一想，是有些疏漏的，并查集不具备时间的属性，而会议是有的。比如：甲乙开会时无人知晓秘密，但会将其合入同一并查集，之后乙与指导秘密的丙开会，则使得甲乙丙同处一个并查集但实际应仅有乙丙知道秘密。所以我们需要使用到撤销合并的操作，此处相对比较简单，我们仅关心每人是否知道了秘密，所以不用上太高级的内容，只需合并过后检查其是否会知晓秘密即是否与 0 同集即可，若不知晓则撤销该操作即将其父节点设为自己即可。同时我们需要将会议按时间进行排序，顺序的去处理每个会议，同时因秘密可以瞬时传播，所以我们需一起处理同时发生的所有会议。

实现

struct DSU {
	vector<int> fa, sz;

	DSU() {}
	DSU(int n) {
		init(n);
	}

	void init(int n) {
		fa.resize(n);
		iota(fa.begin(), fa.end(), 0);
		sz.assign(n, 1);
	}

	int find(int x) {
		while(x != fa[x]) {
			x = fa[x] = fa[fa[x]];
		}
		return x;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	bool merge(int x, int y) {
		x = find(x); y = find(y);
		if(x == y) return false;
		sz[x] += sz[y];
		fa[y] = x;
		return true;
	}

	int size(int x) {
		return sz[find(x)];
	}
};

class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        DSU dsu(n);
        int m = meetings.size();
        ranges::sort(meetings, [&](const auto& x, const auto& y) {
            return x[2] < y[2];
        });

        dsu.merge(0, firstPerson);
        for (int i = 0; i < m; ) {
            int j = i;
            for ( ; j < m && meetings[j][2] == meetings[i][2]; j++) {
                int x = meetings[j][0], y = meetings[j][1];
                dsu.merge(x, y);
            }
            for (int k = i; k < j; k++) {
                int x = meetings[k][0], y = meetings[k][1];
                if (!dsu.same(x, 0)) {
                    dsu.fa[x] = x;
                    dsu.fa[y] = y;
                }
            }
            i = j;
        }

        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (dsu.same(i, 0)) ans.push_back(i);
        }
        return ans;
    }
};

力扣每日一题944-删列造序

日期：2025-12-20

题意

给定由等长字符串组成的数组 strs ，将这些字符串排成列，删除其中不是非严格递增的列，求总共需要删除多少列。

思路

遍历检查每个列是否为递增的即可。

实现

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size(), m = strs.back().size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (strs[j][i] < strs[j - 1][i]) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
};

力扣每日一题955-删列造序II

日期：2025-12-21

题意

给定多个等长字符串组成的数组 strs ，将这些字符串排成列，每次操作可以任意删除所有字符串某一列的字母，若想使所有字符串按字典序升序排序，最少需要多少次操作。

思路

和昨天的题目还是非常类似的，只是昨天要求为每列均升序，今天要求为整个字符串升序。那只需维护每个字符串剩余的部分进行遍历检查即可。

实现

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int ans = 0;
        int n = strs.size(), m = strs.back().size();
        vector<string> pre(n);
        for (int i = 0; i < m; i++) {
            bool del = false;
            for (int j = 1; j < n; j++) {
                if (pre[j] + strs[j][i] < pre[j - 1] + strs[j - 1][i]) {
                    ans++;
                    del = true;
                    break;
                }
            }
            if (!del) {
                for (int j = 0; j < n; j++) pre[j] += strs[j][i];
            }
        }
        return ans;
    }
};

力扣每日一题960-删列造序III

日期：2025-12-22

题意

给定多个等长字符串组成的数组 strs ，将这些字符串排成列，每次操作可以任意删除所有字符串某一列的字母。若想使得操作后所有的字符串中所有剩余字母按升序排序，即每行字符升序排序，最少需要多少次操作。

思路

乍一看好难，细一想确实好难，想不到什么特别棒的方法。但仔细一看数据范围 1 <= strs.size() <= 100 1 <= strs[i].size() <= 100 ，那其实就很好做了。将其视作一个最长递增子序列，只是比较函数需要重载一下即可，用 dp 的方式去写， 1 <= strs.size() * strs.size() * strs[i].size() <= 1e6 显然是可以接受的。

实现

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size(), m = strs.back().size();
        vector<int> f(m, 1);

        auto x_leq_y = [&](int x, int y) -> bool {
            for (int i = 0; i < n; i++) {
                if (strs[i][x] > strs[i][y]) return false;
            }
            return true;
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < i; j++) {
                if (x_leq_y(j, i)) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }

        return m - ranges::max(f);
    }
};

力扣每日一题2054-两个最好的不重叠活动

日期：2025-12-23

题意

给定多个活动的开始结束时间及其价值用数组 envents 表示，最多同时参加两个时间不重叠的活动，求可参加活动的价值最大和。

思路

有蛮多实现方法的，比如按结束时间排序后维护已结束活动然后进行二分。这里我选择对时间离散化后进行一个后缀max，维护每个时间点之后开始的活动可得的最大价值，然后枚举结束时间，求最大即可。

实现

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        vector<int> t;
        for (auto& e : events) {
            t.push_back(e[0]);
            t.push_back(e[1]);
        }
        ranges::sort(t);
        int m = t.erase(unique(t.begin(), t.end()), t.end()) - t.begin();
        vector<int> f(m + 1);
        for (auto& e : events) {
            int it = ranges::lower_bound(t, e[0]) - t.begin();
            f[it] = max(f[it], e[2]);
        }
        for (int i = m - 1; i >= 0; i--) f[i] = max(f[i], f[i + 1]);

        int ans = 0;
        for (auto& e : events) {
            int it = ranges::lower_bound(t, e[1]) - t.begin();
            ans = max(ans, f[it + 1] + e[2]);
        }
        return ans;
    }
};

力扣每日一题3074-重新分装苹果

日期：2025-12-24

题意

给定正整数数组 apple 和 capacity 分别表示多袋苹果的苹果个数与多个箱子可容纳苹果的个数。求最少需要多少个箱子可将所有苹果装完。

思路

每袋的苹果均可以拆分开来装入不同箱子，那显然就是简单的贪心操作，从大到小排序遍历箱子，第一个前缀和大于苹果数量的即为答案。

实现

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        int n = capacity.size();
        int sum = accumulate(apple.begin(), apple.end(), 0);
        ranges::sort(capacity, greater());
        for (int i = 0, cur = 0; i < n; i++) {
            cur += capacity[i];
            if (cur >= sum) return i + 1;
        }
        return -1;
    }
};

力扣每日一题3075-幸福值最大化的选择方案

日期：2025-12-25

题意

给定多个小孩的幸福值用非负整数数组 happiness 表示。用 k 轮筛选出 k 个孩子，每一轮中所有未被选中的孩子幸福值减一但不会降至负数。求可获得的最大幸福值之和。

思路

比较明显是进行一个从大到小贪 k 个孩子就好。

实现

class Solution {
using ll = long long;
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        ll ans = 0;
        int n = happiness.size();
        ranges::sort(happiness, greater());
        for (int i = 0; i < n && k; i++, k--) {
            happiness[i] -= i;
            if (happiness[i] <= 0) break;
            ans += happiness[i];
        }
        return ans;
    }
};

力扣每日一题2483-商店的最少代价

日期：2025-12-26

题意

给定字符串 customers 表示每时刻是否有顾客到来，在初始商店是营业的，可任选一个时刻关闭商店不再营业。若营业期间某时刻无客到来则代价加一，若歇业期间某时刻有客到来则代价加一。求代价最小的前提下最早的关门时间。

思路

某时刻关门的代价为：关门之前的无客数量与关门后的有客数量之和。进行一个前后缀处理前后信息即可。

实现

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();
        int ans = 0, mn = n;
        vector<int> suf(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] + (customers[i] == 'Y');
        }
        for (int i = 0, c = 0; i <= n; i++) {
            int cur = c + suf[i];
            if (cur < mn) {
                mn = cur;
                ans = i;
            }
            c += customers[i] == 'N';
        }
        return ans;
    }
};

力扣每日一题2402-会议室III

日期：2025-12-27

题意

有 n 个会议室，同时给出多个会议的开始与结束时间用数组 meetings 表示。每场会议会在未占用且编号最小的会议室举办；若当前无可用会议室则会议延期直到有空会议室，且会议时长不会改变；若有多个会议均处于延期状态会优先分配给原定开始时间最早的会议。求举办最多次会议的会议室编号。

思路

那么我们模拟一下会议分配的过程就好了，对于在开会议的会议室根据其结束时间进行排序，同时维护空闲的会议室，按开始时间的顺序给各个会议分配会议室，最终统计各个会议室开会次数即可。

实现

class Solution {
using ll = long long;
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        vector<int> cnt(n);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> busy;
        priority_queue<int, vector<int>, greater<>> free;
        for (int i = 0; i < n; i++) free.push(i);
        ranges::sort(meetings);
        for (auto& m : meetings) {
            ll s = m[0], e = m[1];
            while (!busy.empty() && busy.top().first <= s) {
                free.push(busy.top().second);
                busy.pop();
            }
            if (free.empty()) {
                auto [t, id] = busy.top();
                busy.pop();
                cnt[id]++;
                busy.push({t + e - s, id});
            } else {
                int id = free.top();
                free.pop();
                cnt[id]++;
                busy.push({e, id});
            }
        }
        int mx = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] > mx) {
                mx = cnt[i];
                ans = i;
            }
        }
        return ans;
    }
};

力扣每日一题1351-统计有序矩阵中的负数

日期：2025-12-28

题意

给定二维整数矩阵 grid，其中各行各列均以非严格递减的顺序排列。统计其中负数的数量。

思路

数据范围并不大，可以直接进行一个暴力遍历。

但题目已经保证了各行各列均递减排序，那么其实有着非常好的性质。比如一个数若是负数，则其所在列行数大于其的数均为负数；若一个数为正数，则其左上的元素一定为正数。由此优化一下遍历方式即可。

实现

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid.back().size();
        int ans = 0;
        for (int i = 0, j = m - 1; i < n && j >= 0; ) {
            if (grid[i][j] >= 0) {
                i++;
            } else {
                ans += n - i;
                j--;
            }
        }
        return ans;
    }
};

力扣每日一题756-金字塔转换矩阵

日期：2025-12-29

题意

给定一堆长度为 3 的字符串 allowed 表示一些可选的字母三角形。同时给出一个字符串 bottom 表示一个金字塔底座。求问给定的 allowed 与 bottom 是否可以补全出一个完整的金字塔，使得该金字塔每一个小三角形均可在 allowed 中找到。

思路

数据范围实在很小，2 <= bottom.length() <= 6 && 0 <= allow.length() <= 216 && 所有字符来自 {'A', 'B', 'C', 'D', 'E', 'F'}

那咱们直接进行一个暴搜就好，根据底座一层层往上枚举可选的字符，直到到顶或无可选字符。

实现

class Solution {
static constexpr int N = 6;
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        int n = bottom.size();
        bool ans = false;
        vector<string> f(N, "######");
        vector allow(N, vector<string> (N));
        for (const auto& s : allowed) {
            allow[s[0] - 'A'][s[1] - 'A'] += s[2];
        }
        for (int i = 0; i < n; i++) f[0][i] = bottom[i];

        auto dfs = [&](this auto&& self, int i, int j) -> void {
            if (i == n - 1) {
                ans = true;
                return;
            }
            if (allow[f[i][j - 1] - 'A'][f[i][j] - 'A'].empty()) return;
            for (auto& ch : allow[f[i][j - 1] - 'A'][f[i][j] - 'A']) {
                f[i + 1][j - 1] = ch;
                if (j == n - i - 1) self(i + 1, 1);
                else self(i, j + 1);
                if (ans) return;
            }
        };
        dfs(0, 1);

        return ans;
    }
};

力扣每日一题840-矩阵中的幻方

日期：2025-12-30

题意

给定矩阵 grid ，求其内存在几个幻方。幻方定义为 3 * 3 的矩阵，同时每一行每一列每个对角线的和相同，同时数字 1 ~ 9 均出现且仅出现一次。

思路

也没什么好的办法，就进行一个求每行每列和进行检查的暴力就好。只是为了方便实现，可以数学推导一下，首先 1 ~ 9 均出现且仅出现一次则和为 45 ，每行列对角线和相同则均为 45 / 3 == 15，由此可以稍微简化一下实现的复杂度。

实现

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid.back().size();
        int ans = 0;

        auto check = [&](int i, int j) -> bool {
            if (grid[i - 1][j - 1] != 5) return false;
            int mask = 0;
            for (int x = 0; x < 3; x++) {
                int c = 0, r = 0;
                for (int y = 0; y < 3; y++) {
                    mask |= 1 << grid[i - x][j - y];
                    c += grid[i - x][j - y];
                    r += grid[i - y][j - x];
                }
                if (c != 15 || r != 15) return false;
            }
            return mask == 1022;
        };

        for (int i = 2; i < n; i++) 
            for (int j = 2; j < m; j++) 
                ans += check(i, j);

        return ans;
    }
};

力扣每日一题1970-你能穿过矩阵的最后一天

日期：2025-12-31

题意

给定 row * col 大小的陆地，每天都会有一个新的陆地变为水域用数组 cells 表示。可任选最上面一行的某个陆地位置出发，每次可以往上下左右任意相邻的陆地格子移动。问哪一天是可以从最上面一行陆地走到最下面一行陆地的最后一天。

思路

那方法还是有很多的，与时间相关最简单的方法还是想到使用二分，二分时间然后进行检查，检查就是一个很常规的联通性问题，bfs dfs都是可以的。

也可以换一个角度想，从最后一天往前推，即为全是水域的矩阵每天会多一块陆地。那么第一次使得最上最下两行联通的天数即为答案。联通性问题很自然可以想到使用并查集进行维护，每一块陆地可以使得其上下左右的陆地联通。

实现

class Solution {
static constexpr array<int, 2> nxt[] = {
    {0, 1}, {0, -1}, {1, 0}, {-1, 0}
};
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int n = cells.size();

        auto check = [&](int t) -> bool {
            vector mp(row, vector<int> (col));
            for (int i = 0; i <= t; i++) {
                mp[cells[i][0] - 1][cells[i][1] - 1] = 1;
            }
            queue<array<int, 2>> q;
            for (int i = 0; i < col; i++) {
                if (mp[0][i] == 0) q.push({0, i});
            }
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                if (mp[x][y] != 0) continue;
                if (x == row - 1) return true;
                mp[x][y] = 2;
                for (auto [tx, ty] : nxt) {
                    int nx = tx + x, ny = ty + y;
                    if (nx < 0 || nx >= row || ny < 0 || ny >= col || mp[nx][ny] != 0) continue;
                    q.push({nx, ny});
                }
            }
            return false;
        };

        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (check(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo + 1;
    }
};