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

目录

力扣每日一题3217-从链表中移除在数组中存在的节点

日期：2025-11-01

题意

给定数组 nums 以及一个链表头节点 head，删除链表中在 nums 中出现过的数。

思路

开一个哈希记录那些数存在过，然后进行一个遍历链表删除操作即可。

实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        unordered_set<int> t(nums.begin(), nums.end());
        for (auto it = head; it != nullptr && t.count(it->val); ) {
            head = it->next;
            it = head;
        }
        if (head == nullptr || head->next == nullptr) return head;
        for (auto it = head, itt = head->next; itt != nullptr; ) {
            if (t.count(itt->val)) {
                it->next = itt->next;
                itt = it->next;
            } else {
                it = itt;
                itt = itt->next;
            }
        }
        return head;
    }
};

力扣每日一题2257-统计网格图中没有被保卫的格子数

日期：2025-11-02

题意

给定 m * n 的网格图，以及数组 guards 和 walls 表示其中守卫和墙的位置，每个守卫可保卫其上下左右不被其他守卫或墙所遮挡的格子。求有多少格子未被保卫。

思路

数据范围实在不大 1 <= n * m <= 1e5 ，那也就是说 O(n * m) 是完全可以接受的。我们直接就以每个警卫为始，一直往上下左右直到出界或遇到其他警卫/墙停下，去掉被守卫的格子就好。

实现

class Solution {
static constexpr array<int, 2> nxt[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        int ans = n * m - guards.size() - walls.size();
        vector mp(m, vector<int> (n));
        for (auto g : guards) {
            mp[g[0]][g[1]] = 2;
        }
        for (auto w : walls) {
            mp[w[0]][w[1]] = 2;
        }

        for (auto g : guards) {
            for (auto [tx, ty] : nxt) {
                int nx = g[0] + tx;
                int ny = g[1] + ty;
                for ( ; ; nx += tx, ny += ty) {
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || mp[nx][ny] == 2) break;
                    if (mp[nx][ny] == 1) continue;
                    mp[nx][ny] = 1;
                    ans--;
                }
            }
        }
        return ans;
    }
};

力扣每日一题1578-使绳子变成彩色的最短时间

日期：2025-11-03

题意

给定字符串 color 与数组 neededTime 表示 n 个气球的颜色以及移除它们所需时间。希望无相邻气球同色，求最小花费时间。

思路

无相邻同色气球，那么贪心地同色区间仅保留耗时最大的气球即可。

实现

class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        int ans = 0;
        int n = colors.size();
        for (int i = 0; i < n; ) {
            int j = i, mx = 0, sum = 0;
            for ( ; j < n && colors[j] == colors[i]; j++) {
                mx = max(mx, neededTime[j]);
                sum += neededTime[j];
            }
            ans += sum - mx;
            i = j;
        }
        return ans;
    }
};

力扣每日一题3318-计算子数组的x-sumI

日期：2025-11-04

题意

给定整数数组 nums 与两个整数 k 和 x ，返回大小为 n - k + 1 的整数数组 ans，其中 ans[i] 表示子数组 nums[i : i + k] 仅保留出现频次前 x 大的元素的和。

思路

感觉是一个有点复杂的数据结构题，需要维护子区间出现频次前 x 大的元素并且可以右扩左缩，想想就挺复杂。

但是注意到这题是简单版本，数据范围很小 1 <= n <= 50 ，那咱们简单问题简单做，遍历每个子区间求出各数出现频次再进行一个排序求和即可。

实现

class Solution {
public:
    vector<int> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<int> ans(n - k + 1);
        array<int, 51> cnt;
        vector<int> p(51);
        ranges::iota(p, 0);
        for (int i = 0; i < n - k + 1; i++) {
            cnt.fill(0);
            for (int j = 0; j < k; j++) cnt[nums[i + j]]++;
            ranges::sort(p, [&](const int& x, const int& y) {
                if (cnt[x] == cnt[y]) return x > y;
                return cnt[x] > cnt[y];
            });
            for (int j = 0; j < x && cnt[p[j]]; j++) ans[i] += p[j] * cnt[p[j]];
        }
        return ans;
    }
};

力扣每日一题3321-计算子数组的x-sumII

日期：2025-11-05

题意

给定整数数组 nums 与两个整数 k 和 x ，返回大小为 n - k + 1 的整数数组 ans，其中 ans[i] 表示子数组 nums[i : i + k] 仅保留出现频次前 x 大的元素的和。

思路

是的，题目与昨天完全一致，只是数据范围 n 从 50 扩大到了 1e5 ，那显然是不能再暴力了。

我们需要维护一个区间出现频次前 x 大的元素的出现频次与元素大小的和，同时这个区间还可以右扩左缩。首先我们可以想到使用一个 set 来进行维护区间出现元素与其出现频次，这样已经是排好序状态，仅需求出前 x 大元素的和即可。 可若暴力求出前 x 大元素还是太暴了，考虑如何优化这个和。

这时我们可以想到，可以使用两个 set 进行维护，一个仅维护前 x 大的元素，另一个维护剩余的元素，当需要加入一个元素时，首先删除旧有元素，将新元素插入小集合，判断小集合最大是否比大集合最小大，再据此进行移动元素并更新和即可。删除元素的逻辑类似，每次仅需进行比较小集合最大与大集合最小即可。

因为今天比较忙开始的比较晚，赶工之下没想明白，写了一大坨东西还望见谅（

实现

class Solution {
using ll = long long;
public:
    vector<ll> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<ll> ans(n - k + 1);
        set<array<int, 2>> small;
        set<array<int, 2>> big;
        unordered_map<int, int> cnt;
        ll sum = 0;
        for (int l = 0, r = 0, cur = 0; r < n; r++) {
            array<int, 2> tr = {cnt[nums[r]], nums[r]};
            if (cnt[nums[r]]) {
                if (big.count(tr)) {
                    big.erase(tr);
                    tr[0]++;
                    cnt[nums[r]]++;
                    sum += tr[1];
                    big.insert(tr);
                } else {
                    small.erase(tr);
                    tr[0]++;
                    cnt[nums[r]]++;
                    if (tr > *big.begin()) {
                        small.insert(*big.begin());
                        sum -= 1ll * (*big.begin())[0] * (*big.begin())[1];
                        big.erase(big.begin());
                        sum += 1ll * tr[0] * tr[1];
                        big.insert(tr);
                    } else {
                        small.insert(tr);
                    }
                }
            } else {
                tr[0]++;
                cnt[nums[r]]++;
                if (big.size() < x) {
                    big.insert(tr);
                    sum += 1ll * tr[0] * tr[1];
                } else {
                    if (tr > *big.begin()) {
                        small.insert(*big.begin());
                        sum -= 1ll * (*big.begin())[0] * (*big.begin())[1];
                        big.erase(big.begin());
                        sum += 1ll * tr[0] * tr[1];
                        big.insert(tr);
                    } else {
                        small.insert(tr);
                    }
                }
            }
            
            if (r - l + 1 > k) {
                array<int, 2> tl = {cnt[nums[l]], nums[l]};
                if (big.count(tl)) {
                    big.erase(tl);
                    sum -= 1ll * tl[0] * tl[1];
                    tl[0]--;
                    cnt[nums[l]]--;
                    if (!small.empty() && *small.rbegin() > tl) {
                        sum += 1ll * (*small.rbegin())[0] * (*small.rbegin())[1];
                        big.insert(*small.rbegin());
                        small.erase(*small.rbegin());
                        small.insert(tl);
                    } else {
                        sum += 1ll * tl[0] * tl[1];
                        big.insert(tl);
                    }
                } else {
                    small.erase(tl);
                    tl[0]--;
                    cnt[nums[l]]--;
                    if (tl[0]) small.insert(tl);
                }
                l++;
            }
            if (r - l + 1 == k) {
                ans[cur++] = sum;
            }
            // cout << "!!" << l << " " << r << "\n";
            // for (auto [num, p] : small) cout << "s " << num << " " << p << "\n";
            // for (auto [num, p] : big) cout << "b " << num << " " << p << "\n";
            // cout << "\n";
        }
        return ans;
    }
};

稍微清醒点后重写版本

class Solution {
using ll = long long;
public:
    vector<long long> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<ll> ans(n - k + 1);

        set<array<int, 2>> small, big;
        unordered_map<int, int> cnt;
        ll sum = 0;
        auto apply = [&]() -> void {
            while (!small.empty()) {
                if (big.size() < x) {
                    auto tmp = *small.rbegin();
                    sum += 1ll * tmp[0] * tmp[1];
                    small.erase(tmp);
                    big.insert(tmp);
                } else if (*small.rbegin() > *big.begin()) {
                    auto tl = *small.rbegin();
                    auto tr = *big.begin();
                    sum += 1ll * tl[0] * tl[1] - 1ll * tr[0] * tr[1];
                    small.erase(tl); small.insert(tr);
                    big.erase(tr); big.insert(tl);
                } else {
                    break;
                }
            }
        };
        auto add = [&](int x) -> void {
            array<int, 2> tmp = {cnt[x], x};
            if (tmp[0]) {
                if (small.count(tmp)) small.erase(tmp);
                else {big.erase(tmp); sum -= 1ll * tmp[0] * tmp[1];}
            }
            tmp[0]++;
            cnt[x]++;
            small.insert(tmp);
            apply();
        };
        auto del = [&](int x) -> void {
            array<int, 2> tmp = {cnt[x], x};
            if (small.count(tmp)) small.erase(tmp);
            else {big.erase(tmp); sum -= 1ll * tmp[0] * tmp[1];}
            tmp[0]--;
            cnt[x]--;
            if (tmp[0]) small.insert(tmp);
            apply();
        };

        for (int l = 0, r = 0, cur = 0; r < n; r++) {
            add(nums[r]);
            if (r - l + 1 > k) del(nums[l++]);
            if (r - l + 1 == k) ans[cur++] = sum;
        }

        return ans;
    }
};

力扣每日一题3607-电网维护

日期：2025-11-06

题意

有 c 个初始为开启的电站，标志从 1~c 编号。给定数组 connections 表示某些电站之间两两双向连接。可互达的电站称为一个电网。同时有询问数组 queries ：

  • 若 queries_i == [1, x] 表示对 x 进行检查，若 x 仍在线则返回 x ，否则返回其所在电网中编号最小的在线电站，若无在线电站返回 -1
  • 若 queries_i == [2, x] 表示将 x 关停

返回所有 [1, x] 的查询结果。

思路

所有连接都是双向的，那直接使用并查集进行处理，同一个连通块的为同一电网，记录当前所在电网的所有电站并维护最小在线电站即可。

实现

struct DSU {
    int n;
    vector<int> fa;
    DSU(int x) {
        n = x;
        fa.resize(x);
        ranges::iota(fa, 0);
    }
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (x > y) swap(x, y);
        fa[y] = x;
        return true;
    }
};

class Solution {
public:
    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        DSU dsu(c);
        vector<bool> online(c, true);

        for (const auto& e : connections) {
            int u = e[0] - 1, v = e[1] - 1;
            dsu.merge(u, v);
        }
        unordered_map<int, vector<int>> ump;
        unordered_map<int, int> index;
        for (int i = 0; i < c; i++) {
            int f = dsu.find(i);
            ump[f].push_back(i);
        }

        vector<int> ans;
        for (const auto& q : queries) {
            int op = q[0], x = q[1] - 1;
            if (op == 1) {
                if (online[x]) ans.push_back(x + 1);
                else {
                    int f = dsu.fa[x];
                    if (index[f] >= ump[f].size()) ans.push_back(-1);
                    else ans.push_back(ump[f][index[f]] + 1);
                }
            } else {
                online[x] = false;
                int f = dsu.fa[x];
                while (index[f] < ump[f].size() && !online[ump[f][index[f]]]) index[f]++;
            }
        }
        return ans;
    }
};

力扣每日一题2528-最大化城市的最小电量

日期：2025-11-07

题意

给定数组 stations 表示 n 个城市的供电站个数。以及两个整数 r 和 k ，其中 r 表示每个供电站的供电范围，具体的城市 i 的供电站可供 |j - i| <= r 的城市 j ；还可以额外在任意城市再建造 k 个供电站。求所有城市中最小电量的最大值。

思路

求最小值的最大，那很显然应该是一个二分，我们二分答案，进行一个 check 。

如何检查一个答案 x 是否可行呢。我们这里也别将电站视作建在某点覆盖某个半径为 r 的区域了，我们简化为建在某点覆盖其后的 2 * r 的区域。由此贪心地，若当前城市供电数不足 x 时就在此处建立对应额外的电站，若最终新建的个数小于等于 k 即表明答案 x 可行。

如何表示一个城市被覆盖的数量呢，比较自然是可以想到使用拆分与前缀和的。

实现

class Solution {
using ll = long long;
static constexpr int N = 1e5;
public:
    ll maxPower(vector<int>& stations, int r, int k) {
        const int n = stations.size();
        vector<ll> f(n + 1);
        for (int i = 0; i < n; i++) {
            int left = max(0, i - r);
            int right = min(n, i + r + 1);
            f[left] += stations[i];
            f[right] -= stations[i];
        }

        auto check = [&](ll x) -> bool {
            auto tf = f;
            int t = k;
            for (int i = 0; i < n; i++) {
                if (i) tf[i] += tf[i - 1];
                ll dif = x - tf[i];
                if (dif > 0) {
                    t -= dif;
                    if (t < 0) return false;
                    tf[i] += dif;
                    tf[min(n, i + 2 * r + 1)] -= dif;
                }
            }
            return true;
        };
        
        ll lo = 0, hi = 1ll * N * n + k;
        while (lo < hi) {
            ll mid = lo + hi + 1 >> 1;
            if (check(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
};

力扣每日一题1611-使整数变为 0 的最少操作次数

日期：2025-11-08

题意

给定非负整数 n ，每次操作可任选以下其一进行

  • 翻转 n 二进制下的最低位
  • 若 n 二进制下第 i - 1 为 1 且剩余低位均为 0 ，则翻转第 i 位

问将 n 变为 0 的最小操作数。

思路

想想怎么让 00100 变成 0 呢

首先若想 100 第3位变为0仅能使用操作二，换言而之需要第2位为1剩余低位为0
即需变为 110
而需使第2位变为1同样仅能使用操作二，即需先使第1位为1
最低位为1则仅需一次操作一即可
故而有操作
100->101->111->110->010->011->001->000

可以发现，若想使得第 i 位翻转，需先使得 i - 1 位为 1 且其余低位为 0 。可以想到是一个递归的问题。

实现

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n) {
            ans = ((n & -n) << 1) - 1 - ans;
            n ^= n & -n;
        }
        return ans;
    }
};

力扣每日一题2169-得到0的操作数

日期：2025-11-09

题意

给定两个非负整数 num1 和 num2 。在每次操作中若 num1 >= num2 则 num1 -= num2，反之若 num1 < num2 则 num2 -= num1 。直到 num1 或 num2 为 0，求总操作数。

思路

数据范围并不是很大，均不大于 1e5，直接暴力模拟是可以接受的。

但这个过程我们很容易联想到辗转相减法，那实际上的过程和辗转相除法是非常类似的，进行一个加速优化。

实现

class Solution {
public:
    int countOperations(int num1, int num2) {
        int ans = 0;
        while (num2) {
            ans += num1 / num2;
            num1 %= num2;
            swap(num1, num2);
        }
        return ans;
    }
};s

力扣每日一题3542-将所有元素变为0的最少操作次数

日期：2025-11-10

题意

给定非负整数数组 nums，每次操作可任选子数组将其中所有最小非负整数设为 0。求将 nums 变为全零数组的最小操作次数。

思路

贪心地想，我们每次操作会希望尽可能多地改变数组，会希望每次操作尽可能长地包含非 0 数，多次这样的操作后当前数组的最小非零数就都变为零了，就会把数组分割为更多的小块即更多的子问题。由此我们可以想到分治。

一个较小的数会将数组分割为多个子数组，同时多个同一块的相同数可以仅一次操作全部处理，由此可以想到使用单调栈对上述分割操作进行模拟即可。

实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        vector<int> stk;
        int ans = 0;
        for (const auto& x : nums) {
            while (!stk.empty() && stk.back() > x) {
                stk.pop_back();
            }
            if (!stk.empty() && stk.back() == x) continue;
            stk.push_back(x);
            if (x) ans++;
        }
        return ans;
    }
};

力扣每日一题474-一和零

日期：2025-11-11

题意

给定二进制字符串数组 strs 以及两个正整数 n 和 m。返回 strs 的最大子集的大小，满足该子集中最多有 n 个 1 和 m 个 0

思路

数据范围都并不是很大，其中 1 <= n, m <= 100 1 <= strs.size() <= 600，那也就是说 1 <= n * m * strs.size() <= 6e6

那还是比较自然的可以想到 背包dp，枚举每个字符串以及在当前有几个零几个一下选择该字符串即可。

记当前所举字符串为 s ，其中含一个数为 含零个数为 ，同时当前子集含有 i 个一 j 个零，有递推公式

实现

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(n + 1, vector<int> (m + 1, -1));
        f[0][0] = 0;
        for (const auto& s : strs) {
            int o = count(s.begin(), s.end(), '1');
            int z = s.size() - o;
            for (int i = n - o; i >= 0; i--)
                for (int j = m - z; j >= 0; j--) {
                    if (f[i][j] == -1) continue;
                    f[i + o][j + z] = max(f[i + o][j + z], f[i][j] + 1);
                }
        }
        int ans = 0;
        for (int i = 0; i <= n; i++) ans = max(ans, ranges::max(f[i]));
        return ans;
    }
};

力扣每日一题2654-使数组所有元素变成1的最少操作次数

日期：2025-11-12

题意

给定正整数数组 nums，每次操作可任选 0 <= i < n - 1 使得 nums[i] = gcd(nums[i], nums[i + 1]) ，求将 nums 全变为 1 需要操作多少次。

思路

首先我们想想如果整个数组 gcd 不为 1 ，显然此时题目无解。

若数组初始含 1 ，显然所需操作次数为不为 1 的数的个数，因为1和任意数gcd均为1.

若数组不含 1 ，我们首先需要用最少的次数将数组变出一个 1， 再结合上一行思路得到答案。而变出一个 1 显然就是找到最小 gcd 为 1 的子数组的长度减一。此处数据范围较小 1 <= nums.size() 因此可以直接暴力地去做；也可以利用一个数组 gcd 变换次数最多是 log 级别地简化这个过程。

实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int g = 0, t = 0;
        for (auto x : nums) {
            t += x == 1;
            g = gcd(g, x);
        }
        if (g != 1) return -1;
        if (t) return n - t;

        int mn = n;
        vector<array<int, 2>> f;
        for (int i = 0; i < n; i++) {
            f.push_back({nums[i], i});
            vector<array<int, 2>> nf;
            for (const auto& x : f) {
                t = gcd(x[0], nums[i]);
                if (!nf.empty() && nf.back()[0] == t) nf.back()[1] = x[1];
                else nf.push_back({t, x[1]});
            }
            swap(f, nf);
            if (f[0][0] == 1) mn = min(mn, i - f[0][1]);
        }
        return mn + n - 1;
    }
};

力扣每日一题3228-将1移动到末尾的最大操作次数

日期：2025-11-13

题意

给定二进制字符串数组 s 。每次可任选满足 0 < i < s.size() - 1 && s[i] == '1' && s[i + 1] == '0' 的 i 使得 s[i] 向后移动到字符串末尾或下一个 1 。求最多可以操作多少次。

思路

手玩一下可以发现，每次选择最前面的可操作 i 可以得到最大操作数。具体地每有一个 10 前面的所有 1 均可以添加到答案中。

实现

class Solution {
public:
    int maxOperations(string s) {
        int n = s.size();
        int ans = 0;
        for (int i = 0, t = 0; i < n - 1; i++) {
            if (s[i] == '1') {
                t++;
                if (s[i + 1] == '0') {
                    ans += t;
                }
            }
        }
        return ans;
    }
};

力扣每日一题2536-子矩阵元素加1

日期：2025-11-14

题意

给定一个正整数 n ，表示一个 n * n 初始全为 0 的整数矩阵 mat。以及一个询问数组 query ，其中每个询问形如 query[i] = [row1, col1, row2, col2] 表示给左上角为 (row1, col1) 右下角为 (row2, col2) 的子矩阵所有元素加 1。返回所有询问操作后的矩阵。

思路

那就是一个非常经典的二维差分与前缀和的题目。

不太熟悉可以先想想一维的情况：给定一维数组，多次询问表示给一个区间所有元素加减某个数，仅需返回所有操作后的结果，处理每个操作复杂度需为 O(1)。

然后就是一个升维的操作，觉得比较复杂可以先简单画个图辅助一下思考。

实现

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector ans(n, vector<int> (n));
        for (const auto& q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            ans[r1][c1]++;
            if (c2 + 1 < n && r2 + 1 < n) ans[r2 + 1][c2 + 1]++;
            if (c2 + 1 < n) ans[r1][c2 + 1]--;
            if (r2 + 1 < n) ans[r2 + 1][c1]--;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (i && j) ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
                else if (i) ans[i][j] += ans[i - 1][j];
                else if (j) ans[i][j] += ans[i][j - 1];
            }
        return ans;
    }
};

力扣每日一题3234-统计1显著的字符串的数量

日期：2025-11-15

题意

给定二进制字符串，返回满足 1 个数大于等于 0 个数的平方的子字符串个数。

思路

第一反应是进行一个前缀和加树状数组，但细想这是不对的，因为平方是没有前缀和性质的。

应该进行一个滑动窗口枚举 0 的数量。

实现

class Solution {
public:
    int numberOfSubstrings(string s) {
        int ans = 0;
        vector<int> pos{-1};
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') pos.push_back(i);
            else {
                ans += i - pos.back();
            }

            int m = pos.size();
            for (int j = m - 1; j > 0; j--) {
                int z = m - j;
                int o = i - pos[j] + 1 - z;
                if (z * z >= n) break;
                ans += max(0, pos[j] - max(z * z - o, 0) - pos[j - 1]);
            }
        }
        return ans;
    }
};

力扣每日一题1513-仅含1的子串数

日期：2025-11-16

题意

给定二进制字符串 s， 返回仅有 1 的子串个数，答案模 1e9 + 7

思路

可以先想想给定一个全 1 的字符串，其有多少个子串，显然应该是一个等差数列求和：设其长度为 n 则有 n 个长度为 1 的子串，有 n - 1 个长度为 2 的子串….有 1 个长度为 n 的子串。

那问题就转换为了有多少个全 1 的子串且它们长度各为多少，简单模拟一下即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int numSub(string s) {
        int n = s.size();
        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (s[i] == '0') continue;
            for (j = i + 1; j < n && s[j] == '1'; j++);
            ans += (1ll * (j - i + 1) * (j - i) >> 1) % mod;
            if (ans >= mod) ans -= mod;
            i = j - 1;
        }
        return ans;
    }
};

力扣每日一题1437-是否所有1都至少相隔k个元素

日期：2025-11-17

题意

给定 0/1 数组 nums 以及一个整数 k 。判断数组内所有 1 之间是否至少相隔 k 个元素。

思路

显然仅需判断相邻 1 之间是否满足条件即可，那么只需记录上一个 1 出现的位置，遍历一躺进行判断即可。

实现

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i = 0, last = -k - 1; i < n; i++) {
            if (nums[i]) {
                if (i - last <= k) return false;
                last = i;
            }
        }
        return true;
    }
};

力扣每日一题717-1比特与2比特字符

日期：2025-11-18

题意

给定以 0 结尾的 01 数组 bits。其中有两种特殊字符，一种用一个 0 表示，一种以 10 或 11 表示。求问给定数组 bits 是否以第一种字符结尾。

思路

注意到以 1 开头的字符一定需要两个字母，以 0 开头的一定仅需一个字母，从头进行一个模拟即可。

实现

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int n = bits.size();
        bool ans = false;
        for (int i = 0; i < n; i++) {
            ans = bits[i] == 0;
            if (!ans) i++;
        }
        return ans;
    }
};

力扣每日一题2154-将找到的值乘以2

日期：2025-11-19

题意

给定整数数组 nums 和一个整数 original 。重复以下步骤：

  • 若 nums 中存在 original 则令 original 乘以二
  • 如 nums 中不存在 original 则停止操作

返回最终的 original

思路

比较简单的做法就是将数组排序后遍历/二分。

但仔细观察可以发现一个复杂度低一些的做法：一个数不断乘以二，那么就是原数的 2,4,8... 倍，即原数的二的幂次倍，由此遍历一遍记录出现过的二的幂次倍，找出第一个未出现的即可。利用位运算的性质还可以把空间复杂度也降低。

实现

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        ranges::sort(nums);
        int l = 0;
        for (auto it = lower_bound(nums.begin(), nums.end(), original); it != nums.end() && *it == original; it = lower_bound(nums.begin() + l, nums.end(), original)) {
            l = it - nums.begin();
            original <<= 1;
        }
        return original;
    }
};
class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        int mask = 0;
        for (auto& x : nums) {
            if (x % original) continue;
            int k = x / original;
            if ((k & -k) == k) mask |= k;
        }
        mask = ~mask;
        return original * (mask & -mask);
    }
};

力扣每日一题757-设置交集大小至少为2

日期：2025-11-20

题意

给定一堆区间的左右端点用二维数组 intervals 表示。需要满足每个区间都至少有两个点在答案集合中，求问答案集合的最小大小。

思路

咱们不妨先简化一下问题：假如每个区间只需要一个点在答案集合中，这应该怎么做呢。可以想到将区间按右端点进行排序从小到大进行遍历，只需维护最后一个加入答案集合的点以及尚无点在答案集合内的区间，若某个区间即将移除仍无点在集合中则将其右端点加入至集合即可。

那么问题扩展至每个区间需要两个点，很自然就可以想到维护最后两个加入的点即可，当区间移出时则就有三种情况：区间内无点、有一点、有两点，进行一个分类讨论即可。

实现

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        ranges::sort(intervals, [&](const auto& x, const auto& y) {
            if (x[1] == y[1]) return x[0] > y[0];
            return x[1] < y[1];
        });
        int ans = 0;
        int f = -1, s = -1;
        for (const auto& q : intervals) {
            int l = q[0], r = q[1];
            if (l <= f) continue;
            else if (l <= s) f = s;
            else {
                f = r - 1;
                ans++;
            }
            s = r;
            ans++;
        }
        return ans;
    }
};

力扣每日一题1930-长度为3的不同回文子序列

日期：2025-11-21

题意

给定小写字母字符串 s， 返回其中长度为 3 的不同回文子序列个数。

思路

长度为 3 的回文串首尾相同而中间任意。故而可以考虑前后缀处理每个位置之前/之后出现了哪些字符，枚举中间字符，使用哈希去重即可。这里因为只有小写字母数据范围较小，所以我使用了位运算优化空间。

实现

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.size();
        vector<int> pre(n);
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] | (1 << (s[i - 1] - 'a'));
        }

        int suf = 0;
        int ans = 0;
        array<int, 26 * 26> vis; vis.fill(0);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if ((pre[i] >> j & 1) && (suf >> j & 1) && !vis[j * 26 + (s[i] - 'a')]) {
                    vis[j * 26 + (s[i] - 'a')] = 1;
                    ans++;
                }
            }
            suf |= 1 << (s[i] - 'a');
        }
        return ans;
    }
};

力扣每日一题3190-使所有元素都可以被3整除的最少操作数

日期：2025-11-22

题意

给定正整数数组 nums ，每次操作可以任选一个数加减一，求问将整个数组变为 3 的倍数最少需要多少次操作。

思路

换言而止需要每个数模 3 等于 0 ，而一个数模 3 仅有三种可能 0\1\2。显然为1时减为2时加即可，也就是非零情况均仅需一次操作。

实现

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int ans = 0;
        for (auto& x : nums) {
            if (x % 3) ans++;
        }
        return ans;
    }
};

力扣每日一题1262-可被三整除的最大和

日期：2025-11-23

题意

给定正整数数组 nums 返回能被三整除的元素最大和。

思路

那也是一个比较经典的dp了。

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f{0, -inf, -inf};
        for (auto& x : nums) {
            auto nf = f;
            for (int i = 0; i < 3; i++) {
                nf[(i + x) % 3] = max(nf[(i + x) % 3], f[i] + x);
            }
            swap(f, nf);
        }
        return f[0];
    }
};

力扣每日一题1018-可被5整除的二进制前缀

日期：2025-11-24

题意

给定二进制数组 nums ，定义 x_i 表示 nums[0 : i + 1] 表示的数，判断每个 x_i 是否为 5 的倍数。

思路

很容易就想到遍历数组将先前累计的数左移一位或上当前数进行模拟。但是注意到这里数组比较长有 1e5 ，就算是 python 直接模拟也是会爆范围的，所以需要优化一下。一个数什么情况下是 5 的倍数呢，显然是个位数为 0 或 5 时，因此我们仅需模拟记录当前数的个位数即可，即每次模 10 运算。

实现

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        int n = nums.size();
        vector<bool> ans(n);
        for (int i = 0, cur = 0; i < n; i++) {
            cur = (cur << 1) | nums[i];
            if (cur >= 10) cur -= 10;
            if (cur == 0 || cur == 5) ans[i] = true;
        }
        return ans;
    }
};

力扣每日一题1015-可被K整除的最小整数

日期：2025-11-25

题意

给定正整数 k， 找出可以被 k 整除且仅含数字 1 的最小正整数的长度。

思路

换而言之，找到最小全 1 且模 k 为 0 的数，显然我们仅需维护余数部分，每次乘十加一再取余即可。

实现

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (k % 2 == 0) return -1;

        int ans = 1;
        vector<bool> vis(k);
        for (int cur = 1 % k; cur != 0; cur = (10 * cur + 1) % k, ans++) {
            if (vis[cur]) return -1;
            vis[cur] = true;
        }
        return ans;
    }
};

力扣每日一题2435-矩阵中和能被K整除的路径

日期：2025-11-26

题意

给定 n * m 的矩阵 grid 与一个正整数 k，初始位于矩阵左上角 (0, 0) 目的地为右下角 (n - 1, m - 1) ，每步仅能往下或往右。求路径和能被 k 整除的路径数目。对 1e9 + 7 取余。

思路

那很明显就是两个经典的dp问题组合起来，一个是合法路径数目，一个是和为某数倍数的方案数，没什么新的东西，将两者结合起来即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid.back().size();
        vector f(n, vector (m, vector<int> (k)));
        f[0][0][grid[0][0] % k] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                auto add = [&](vector<int>& x, vector<int>& y) {
                    for (int z = 0; z < k; z++) {
                        int& t = x[(z + grid[i][j]) % k];
                        t += y[z];
                        if (t >= mod) t -= mod;
                    }
                };
                if (i) add(f[i][j], f[i - 1][j]);
                if (j) add(f[i][j], f[i][j - 1]);
            }
        }
        return f.back().back()[0];
    }
};

力扣每日一题3381-长度可被K整除的子数组的最大元素和

日期：2025-11-27

题意

给定整数数组 nums 和一个正整数 k 。返回 nums 中一个非空子数组的最大和要求该子数组长度可以被 k 整除。

思路

比较自然想到使用前缀和处理子数组的和。那么子数组长度可被 k 整除应该怎么处理呢，类似于先前做过的最长子数组和问题（当且仅当前一数大于等于零时将其加入当前维护的子数组），只是这里步长从 1 变为了 k ，当且仅当前 k 数和大于等于零时将其加入当前维护的子数组。

实现

class Solution {
using ll = long long;
public:
    ll maxSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        ll ans = -1e18;
        vector<ll> pre(n + 1);
        for (int i = 0; i <= n; i++) {
            if (i < n) pre[i + 1] = pre[i] + nums[i];
            if (i >= k) {
                ans = max(ans, pre[i] - pre[i - k]);
                pre[i] = min(pre[i], pre[i - k]);
            }
        }
        return ans;
    }
};

力扣每日一题2872-可以被K整除连通块的最大数目

日期：2025-11-28

题意

给定一棵树，以及一正整数数组 value 表示各结点权值。可任意删除树的边，若最终各联通块的权值和可以被 k 整除，则称其为合法分割。求问合法分割最多有多少连通块。

思路

一个数是 k 的倍数，那么其减去另一个小于其的 k 的倍数则仍是 k 的倍数。因此我们这里开搜，若某点子树和为 k 的倍数则将其切割出去，由此得到的答案一定是最大的。

不过要注意数据范围，可能会超 int 的。

实现

class Solution {
using ll = long long;
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
        vector<vector<int>> adj(n);
        for (const auto& e : edges) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        int ans = 0;
        auto dfs = [&](this auto&& self, int u, int fa) -> ll {
            ll sum = values[u];
            for (auto v : adj[u]) {
                if (v == fa) continue;
                sum += self(v, u);
            }
            sum %= k;
            if (sum == 0) {
                ans++;
            }
            return sum;
        };
        dfs(0, -1);
        return ans;
    }
};

力扣每日一题3512-使数组和能被K整除的最少操作次数

日期：2025-11-29

题意

给定正整数数组 nums 与一个正整数 k ，每次操作可任选 nums 中一个数减一，求问令数组元素之和能被 k 整除所需最小操作次数。

思路

需要使得和为 k 的倍数，那对那个元素操作其实是没差的。同时仅有减操作，因此仅需操作数组和对 k 取余即可。

实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        return accumulate(nums.begin(), nums.end(), 0) % k;
    }
};

力扣每日一题1590-使数组和能被P整除

日期：2025-11-30

题意

给定正整数数组 nums 与一个正整数 p ，移除 nums 最短子数组使得其内剩余元素和能被 p 整除，不可将 nums 全部移除。求问最短移除的长度。

思路

移除某子数组使得剩余和如何如何，我们可以自然想到使用前缀和进行处理。需使得剩余元素和能被 p 整除即为 p 的倍数，那么所移除的子数组和应当与整个数组元素和同余于 p 。这里 p 的范围较大，故使用哈希处理上一个同余位置即可。

实现

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        unordered_map<int, int> ump;
        ump[0] = -1;
        int sum = accumulate(nums.begin(), nums.end(), 0ll) % p;
        if (sum == 0) return 0;
        int ans = n;
        for (int i = 0, pre = 0; i < n; i++) {
            pre = (pre + nums[i]) % p;
            if (ump.count((pre - sum + p) % p)) ans = min(ans, i - ump[(pre - sum + p) % p]);
            ump[pre] = i;
        }
        return ans == n ? -1 : ans;
    }
};