力扣每月题解汇总-2026年07月

目录

力扣每日一题2812-找出最安全路径

日期：2026-07-01

题意

给定一方阵 grid 表示一个含有若干小偷的地图. 图上路径的安全系数定义为路径上任一单元格到任一小偷的最小曼哈顿距离. 求问从左上角出发到达右下角, 安全系数最高的路径安全系数为多少.

思路

那先做个多源 bfs 求出每个位置离最近小偷的曼哈顿距离. 然后就可以做一个优先走安全系数大格子的 “最短路” 即可, 因为优先走安全系数高的格子答案一定不劣.

实现

class Solution {
static constexpr array<int, 2> nxt[] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        vector f(n, vector<int> (n, -1));
        queue<array<int, 3>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) q.push({i, j, 0});
            }
        }
        while (!q.empty()) {
            auto [x, y, d] = q.front();
            q.pop();
            if (f[x][y] != -1) continue;
            f[x][y] = d;
            for (auto [tx, ty] : nxt) {
                int nx = tx + x, ny = ty + y;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || f[nx][ny] != -1) continue;
                q.push({nx, ny, d + 1});
            }
        }

        priority_queue<array<int, 3>> pq;
        pq.push({f[0][0], 0, 0});
        vector vis(n, vector<bool> (n));
        while (!pq.empty()) {
            auto [d, x, y] = pq.top();
            pq.pop();
            if (vis[x][y]) continue;
            vis[x][y] = true;
            d = min(d, f[x][y]);
            if (x == n - 1 && y == n - 1) return d;
            for (auto [tx, ty] : nxt) {
                int nx = tx + x, ny = ty + y;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny]) continue;
                pq.push({d, nx, ny});
            }
        }
        return -1;
    }
};

力扣每日一题3286-穿越网格图的安全路径

日期：2026-07-02

题意

给定二维矩阵, 以及初始健康值 health. 矩阵中非零值表示该格不安全, 经过健康值会减 1. 从左上角出发, 目标右下角, 全程需保持健康值大于 0. 求问是否可以抵达右下角.

思路

和昨日是非常类似的, 进行一个 “最短路”, 优先走健康值高的点即可. 因为优先走健康值高的点一定不劣.

实现

class Solution {
static constexpr array<int, 2> nxt[] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int n = grid.size(), m = grid.back().size();
        priority_queue<array<int, 3>> pq;
        pq.push({health, 0, 0});
        vector vis(n, vector<bool> (m));
        while (!pq.empty()) {
            auto [h, x, y] = pq.top();
            pq.pop();
            if (vis[x][y]) continue;
            vis[x][y] = true;
            h -= grid[x][y];
            if (h <= 0) continue;
            if (x == n - 1 && y == m - 1) return true;
            for (auto [tx, ty] : nxt) {
                int nx = tx + x, ny = ty + y;
                if (nx >= n || nx < 0 || ny >= m || ny < 0 || vis[nx][ny]) continue;
                pq.push({h, nx, ny});
            }
        }
        return false;
    }
};

力扣每日一题3620-恢复网络路径

日期：2026-07-03

题意

给一有向无环图, 其中每条边均已损坏且修复所需开销已给出. 同时存在部分点离线. 从点 0 出发目标为最后一点, 要求所经过边总恢复成本不大于 k 且经过的所有点均在线. 求最终路径中最小边成本最大是多少.

思路

使得最小值最大, 那应该考虑二分, 考虑二分最后一个修复的边的开销. 然后跑一个仅过在线点的最短路, 看是否可达终点且总开销是否满足需求即可.

实现

class Solution {
using ll = long long;
public:
    int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
        const int n = online.size(), m = edges.size();
        ranges::sort(edges, [&](const auto& x, const auto& y) {
            return x[2] > y[2];
        });

        auto check = [&](int mid) -> bool {
            vector<bool> vis(n);
            vector<vector<array<ll, 2>>> e(n);
            for (int i = 0; i <= mid; i++) {
                int u = edges[i][0], v = edges[i][1], c = edges[i][2];
                if (!online[u] || !online[v]) continue;
                e[u].push_back({v, c});
            }
            priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<>> pq;
            pq.push({0, 0});
            while (!pq.empty()) {
                auto [cost, u] = pq.top();
                // cout << edges[mid][2] << ' ' << u << ' ' << cost << '\n';
                pq.pop();
                if (vis[u] || cost > k) continue;
                vis[u] = true;
                for (auto [v, c] : e[u]) {
                    if (!vis[v] && (cost + c <= k)) {
                        pq.push({cost + c, v});
                    }
                }
            }
            return vis.back();
        };
            
        int lo = 0, hi = m;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (check(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        if (lo == m) return -1;
        return edges[lo][2];
    }
};

力扣每日一题2492-两个城市间路径的最小分数

日期：2026-07-04

题意

给定一个无向图, 边上有权重. 求问从第一个节点出发到最后一个节点, 可以经过的最小边权重.

思路

并没有限制走最短路与不能回头路, 同时题目保证两点相通, 那仅需找到所有与第一个点相通的边的最小权值即可.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<array<int, 2>>> adj(n);
        for (auto& e : roads) {
            int u = e[0], v = e[1], w = e[2];
            u--; v--;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        vector<bool> vis(n);
        int ans = inf;
        auto dfs = [&](this auto&& self, int u) -> void {
            if (vis[u]) return;
            vis[u] = true;
            for (auto& [v, w] : adj[u]) {
                ans = min(ans, w);
                if (!vis[v]) self(v);
            }
        };
        dfs(0);
        return ans;
    }
};

力扣每日一题1301-最大得分的路径数目

日期：2026-07-05

题意

给定含障碍物与得分的矩阵, 初始在右下角, 目标为左上角, 求问得分最大路径所得分数以及可得最大分数的路径数各是多少.

思路

分开做求最大分数与路径数都是经典 dp, 这里合一起也仅是转移方案数时多了一个分数限制而已.

实现

class Solution {
static constexpr int inf = 1e9;
static constexpr int mod = 1e9 + 7;
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        auto add = [&](int& x, int& a) {
            x += a;
            if (x >= mod) x -= mod;
        };

        int n = board.size(), m = board.back().size();
        vector f(n + 1, vector<int> (m + 1, -inf));
        vector g(n + 1, vector<int> (m + 1, 0));
        f[0][0] = 0;
        g[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'X') continue;
                int v = max({f[i][j], f[i + 1][j], f[i][j + 1]});
                if (v == f[i][j]) add(g[i + 1][j + 1], g[i][j]);
                if (v == f[i + 1][j]) add(g[i + 1][j + 1], g[i + 1][j]);
                if (v == f[i][j + 1]) add(g[i + 1][j + 1], g[i][j + 1]);
                f[i + 1][j + 1] = v;
                if (isdigit(board[i][j])) f[i + 1][j + 1] += board[i][j] - '0';
            }
        }

        if (f[n][m] < 0) return vector<int> {0, 0};
        return vector<int> {f[n][m], g[n][m]};
    }
};

力扣每日一题1288-删除被覆盖区间

日期：2026-07-06

题意

给定一个区间列表, 若某区间完全被另一区间包含, 则将其删除. 求问最后剩下的区间个数.

思路

那显然按左端点升序排序, 右端点降序排序, 如此遍历则每个点的左端点均在上一端点右侧, 仅需维护右端点的大小关系即可.

实现

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        ranges::sort(intervals, [&](const auto& x, const auto& y) {
            if (x[0] == y[0]) return x[1] > y[1];
            return x[0] < y[0];
        });
        int n = intervals.size();
        int res = 0;
        int c = -1;
        for (int i = 0; i < n; i++) {
            int l = intervals[i][0], r = intervals[i][1];
            if (r <= c) res++;
            else c = r;
        }
        return n - res;
    }
};

力扣每日一题3754-连接非零数字并乘以其数字和I

日期：2026-07-07

题意

给定一个整数, 求其 去除非零位的数 乘 其各数位和 的积.

思路

转成字符串然后按要求处理得到两个乘数再求积即可.

实现

class Solution {
using ll = long long;
public:
    ll sumAndMultiply(int n) {
        ll sum = 0, x = 0;
        string s = to_string(n);
        for (auto& ch : s) {
            int t = ch - '0';
            sum += t;
            if (t) x = x * 10 + t;
        }
        return sum * x;
    }
};

力扣每日一题3756-连接非零数字并乘以其数字和II

日期：2026-07-08

题意

给定一个数字字符串以及一些询问. 每个询问给出一个范围, 求其表示的字符串子串对应的数 去除非零位的结果 乘 其各数位和 的积.

思路

和昨天的题意一样, 只是扩大了数的长度以及变成了多次询问, 进行一个前缀和处理即可 O(1) 地查询.

实现

using ll = long long;
static constexpr int mod = 1e9 + 7;
static constexpr int N = 1e5;
ll p[N + 10];
int init = []() {
    p[0] = 1;
    for (int i = 1; i <= N; i++) {
        p[i] = p[i - 1] * 10 % mod;
    }
    return 0;
} ();

class Solution {
public:
    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> pre(n + 1), cnt(n + 1);
        vector<ll> f(n + 1);
        for (int i = 0; i < n; i++) {
            int x = s[i] - '0';
            pre[i + 1] = (pre[i] + x) % mod;
            f[i + 1] = f[i];
            cnt[i + 1] = cnt[i];
            if (x) {
                f[i + 1] = (f[i] * 10 + x) % mod;
                cnt[i + 1]++;
            }
        }

        int q = queries.size();
        vector<int> ans(q);
        for (int i = 0; i < q; i++) {
            int l = queries[i][0], r = queries[i][1] + 1;
            ans[i] = (pre[r] - pre[l] + mod) % mod * (f[r] - f[l] * p[cnt[r] - cnt[l]] % mod + mod) % mod;
        }
        return ans;
    }
};

力扣每日一题3532-针对图的路径存在性查询I

日期：2026-07-09

题意

给定一个非递减的数组 nums 以及一个非负整数 maxDiff, 规定若有 abs(nums[i] - nums[j]) <= maxDiff 则点 uv 间存在一条无向边. 给定多组询问, 每组询问求问给定两点是否联通.

思路

值之差绝对值小于某值则有边, 且权值间已排好序, 则若相邻点之间之差无超过阈值的连续子数组必互相联通. 由此标记出不同连通块即可.

实现

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<int> idx(n);
        int cur = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] > maxDiff) cur++;
            idx[i] = cur;
        }

        int q = queries.size();
        vector<bool> ans(q);
        for (int i = 0; i < q; i++) {
            int u = queries[i][0], v = queries[i][1];
            ans[i] = idx[u] == idx[v];
        }
        return ans;
    }
};

力扣每日一题3534-针对图的路径存在性查询II

日期：2026-07-10

题意

给定一个非负正整数数组 nums 与一个非负整数 maxDiff, 规定若有 abs(nums[i] - nums[j]) <= maxDiff 则点 uv 间存在一条无向边. 给定多组询问, 每组询问求问给定两点最短距离.

思路

和昨天题意还是非常类似的, 只是给出的数组不再满足非递减, 同时所求变为求最短距离. 初看其实是不太会的, 看数据范围发现最多能接受根号级别的询问复杂度, 但根号没啥符合的, 就想到 log 然后想到倍增然后就会做了. 我们排序然后双指针处理好每个数单步能跳到的最大数, 然后做一个倍增求出二幂次步能跳到的最大数. 然后就可以 log 级别的进行查询了.

实现

class Solution {
public:
    vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<int> p(n);
        ranges::iota(p, 0);
        ranges::sort(p, [&](const int& x, const int& y) {
            return nums[x] < nums[y];
        });

        vector<int> idx(n);
        for (int i = 1, cur = 0; i < n; i++) {
            if (nums[p[i]] - nums[p[i - 1]] > maxDiff) cur++;
            idx[p[i]] = cur;
        }
        int mx = __lg(n) + 1;
        vector nxt(mx, vector<int> (n, -1));
        for (int i = 0, j = 0; i < n; i++) {
            for ( ; j < n - 1 && nums[p[j + 1]] - nums[p[i]] <= maxDiff; j++);
            nxt[0][p[i]] = p[j];
        }
        for (int i = 1; i < mx; i++) {
            for (int j = 0; j < n; j++) {
                nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
            }
        }

        int q = queries.size();
        vector<int> ans(q);
        for (int i = 0; i < q; i++) {
            int u = queries[i][0], v = queries[i][1];
            if (idx[u] != idx[v]) {
                ans[i] = -1;
                continue;
            }
            if (u == v) {
                ans[i] = 0;
                continue;
            }
            if (nums[u] > nums[v]) swap(u, v);
            int res = 0;
            for (int i = mx - 1; i >= 0; i--) {
                if (nums[nxt[i][u]] < nums[v]) {
                    u = nxt[i][u];
                    res += (1 << i);
                }
            }
            ans[i] = res + 1;
        }
        return ans;
    }
};

力扣每日一题2685-统计完全连通分量的数量

日期：2026-07-11

题意

给定一个无向图, 求完全连通分量的个数.

思路

需要注意这里求的不是强连通分量而是完全连通分量. 但实际上也就多了一个所有点两两相连的要求而已. 由于是无向图, 强连通分量仅需用并查集个数就能做, 加上了两两点相连的要求, 我们就记录每个强连通分量的边数, 用边数来判断即可.

实现

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:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        DSU f(n);
        for (auto& e : edges) {
            int u = e[0], v = e[1];
            f.merge(u, v);
        }
        vector<int> sz(n);
        for (auto& e : edges) {
            int u = e[0], v = e[1];
            sz[f.find(u)]++;
            sz[f.find(v)]++;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f.fa[i] == i) {
                int t = f.sz[i];
                ans += sz[i] == t * (t - 1);
            }
        }
        return ans;
    }
};

力扣每日一题1331-数组序号转换

日期：2026-07-12

题意

给定整数数组 arr, 返回各数对应的排序后的序号.

思路

那进行一个排序去重, 然后逐元素二分查位置就好.

实现

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        auto ans = arr;
        ranges::sort(arr);
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        for (auto& x : ans) x = ranges::lower_bound(arr, x) - arr.begin() + 1;
        return ans;
    }
};

力扣每日一题1291-顺次数

日期：2026-07-13

题意

求给定范围 [low, high] 内的所有每一数位均比上一数位大 1 的数.

思路

数据范围不大, high 就多到 1e9, 那直接枚举所有符合要求的数再按范围筛掉即可.

实现

class Solution {
using ll = long long;
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;
        for (int i = 1; i < 10; i++) {
            for (ll x = i, j = i + 1; x <= high && j <= 10; x = x * 10 + j, j++) {
                if (x >= low) ans.push_back(x);
            }
        }
        ranges::sort(ans);
        return ans;
    }
};

力扣每日一题3336-最大公约数相等的子序列数量

日期：2026-07-14

题意

给定正整数数组 nums, 求能从其中取出两个无交非空且 gcd 相同的子序列对数.

思路

数据范围并不大, 最大两百, 每个数也仅有三种状态: 不取, 加入第一个子序列, 加入另一个子序列. 可以想到 dp.

实现

class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;
public:
    int subsequencePairCount(vector<int>& nums) {
        int n = nums.size();
        int m = ranges::max(nums);
        vector f(n + 1, vector (m + 1, vector<ll> (m + 1)));
        for (int i = 1; i <= m; i++) f[0][i][i] = 1;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= m; k++) {
                    f[i + 1][j][k] = (f[i][j][k] + f[i][gcd(j, x)][k] + f[i][j][gcd(k, x)]) % mod;
                }
            }
        }
        return f[n][0][0];
    }
};

力扣每日一题3658-奇数和与偶数和的最大公约数

日期：2026-07-15

题意

给定正整数 n, 求所有小于等于 n 的正奇数和与正偶数和的最大公约数.

思路

求和公式得出两个和之后可以发现最大公约数恒为 n, 当然这个数据范围直接暴力求也是可以的.

实现

class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        return n;
    }
};

力扣每日一题3867-数对的最大公约数之和

日期：2026-07-16

题意

给定正整数数组 nums, 记每个数的前缀最大值与该数的最大公约数组成的新数组为 prefixGcd. 将 prefixGcd 升序排序后令其首尾两两配对, 求所有数对的最大公约数之和.

思路

没啥意思的题, 就按照题意进行模拟求值即可.

实现

class Solution {
using ll = long long;
public:
    ll gcdSum(vector<int>& nums) {
        int n = nums.size();
        int mx = INT_MIN;
        vector<int> f(n);
        for (int i = 0; i < n; i++) {
            mx = max(mx, nums[i]);
            f[i] = gcd(mx, nums[i]);
        }
        ranges::sort(f);

        ll ans = 0;
        for (int l = 0, r = n - 1; l < r; l++, r--) ans += gcd(f[l], f[r]);
        return ans;
    }
};

力扣每日一题3312-查询排序后的最大公约数

日期：2026-07-17

题意

给定正整数数组 nums, 称其中两两数对的最大公约数组成数组为 gcdPairs; 给定一组询问, 每个询问求问 gcdPairs 中的第某大数.

思路

最大公约数 x 的出现次数应该为数组中各数的因子 x 的出现次数减去其各倍数的出现次数. 可以想到做一个容斥然后前缀和二分即可.

实现

class Solution {
using ll = long long;
public:
    vector<int> gcdValues(vector<int>& nums, vector<ll>& queries) {
        int n = nums.size();
        int mx = ranges::max(nums);
        vector<int> cnt(mx + 1);
        for (auto x : nums) cnt[x]++;

        vector<ll> f(mx + 1);
        for (int i = mx; i > 0; i--) {
            ll t = 0;
            for (int j = i; j <= mx; j += i) {
                t += cnt[j];
                f[i] -= f[j];
            }
            f[i] += t * (t - 1) / 2;
        }
        for (int i = 1; i <= mx; i++) f[i] += f[i - 1];
        int q = queries.size();
        vector<int> ans(q);
        for (int i = 0; i < q; i++) {
            ans[i] = ranges::upper_bound(f, queries[i]) - f.begin();
        }
        return ans;
    }
};

力扣每日一题1979-找出数组的最大公约数

日期：2026-07-18

题意

给定正整数数组 nums, 求其最大值与最小值的最大公约数.

思路

按题意找最大最小值然后求 gcd 即可.

实现

class Solution {
public:
    int findGCD(vector<int>& nums) {
        return gcd(ranges::max(nums), ranges::min(nums));
    }
};

力扣每日一题1081-不同字符的最小子序列

日期：2026-07-19

题意

给定字符串 s, 求包含 s 中所有不同字符且字典序最小的子序列.

思路

贪心地, 每次应当选择字典序最小的字符或后续不再出现的字符. 进行一个类似栈的操作即可.

实现

class Solution {
public:
    string smallestSubsequence(string s) {
        string ans;
        array<int, 26> cnt, vis;
        cnt.fill(0); vis.fill(0);
        for (auto& ch : s) cnt[ch - 'a']++;
        for (auto& ch : s) {
            cnt[ch - 'a']--;
            if (vis[ch - 'a']) continue;
            while (!ans.empty() && ch < ans.back() && cnt[ans.back() - 'a']) {
                vis[ans.back() - 'a']--;
                ans.pop_back();
            }
            ans += ch;
            vis[ch - 'a']++;
        }

        return ans;
    }
};

力扣每日一题1260-二维网格迁移

日期：2026-07-20

题意

给定二维矩阵, 每次操作会将每一行的尾元素移动到下一行的首元素前(尾行移动到首行), 求问操作 k 次后的矩阵.

思路

那实际上就是把它展成一维数组后循环右移 k 次.

实现

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid.back().size();
        vector<int> t(n * m);
        for (int i = 0, cur = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                t[cur++] = grid[i][j];
        
        rotate(t.begin(), t.begin() + (n * m - k % (n * m)), t.end());
        for (int i = 0, cur = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                grid[i][j] = t[cur++];

        return grid;
    }
};

力扣每日一题3499-操作后最大活跃区段数I

日期：2026-07-21

题意

给定二进制字符串, 可以最多操作一次, 使得一块被 0 包围的连续 1 串中的 1 全部翻转, 再使得一块被 1 包围的连续 0 串中的 0 全部翻转. 同时假定该字符串两端由不参与计数的 1 包围, 求处理过后该字符串的最多 1 个数.

思路

那应该是要找 0 最多的 ‘0+1+0+’ 串, 写个自动机或者像我这样偷懒进行分段找即可.

实现

class Solution {
public:
    int maxActiveSectionsAfterTrade(string s) {
        int ans = count(s.begin(), s.end(), '1');
        int mx = 0;
        for (int i = 0; i < s.size(); ) {
            int a = s.find('0', i);
            if (a == -1) break;
            int b = s.find('1', a);
            if (b == -1) break;
            int c = s.find('0', b);
            if (c == -1) break;
            int d = s.find('1', c);
            if (d == -1) {
                mx = max(mx, (int(s.size()) - c) + (b - a));
                break;
            } else {
                mx = max(mx, (d - c) + (b - a));
                i = c;
            }
        }
        return ans + mx;
    }
};

力扣每日一题3501-操作后最大活跃区段数II

日期：2026-07-22

题意

给定二进制字符串, 以及一组询问. 每个询问给定一个区间, 对于每个询问可以操作该区间一次, 使得一块被 0 包围的连续 1 串中的 1 全部翻转, 再使得一块被 1 包围的连续 0 串中的 0 全部翻转. 求对于每个询问处理过后该字符串的最多 1 个数.

思路

就是昨日题目的升级版, 变为多个区间询问. 那找 0 最多的 ‘0+1+0+’ 子串, 预处理然后写个区间查即可. 不过要注意分类讨论, 并非所有区间都是完整的.

实现

template<class T, 
	class Cmp = less<T>>
struct ST {
	const Cmp cmp = Cmp();
	int n, logn;
	vector<int> LOG;
	vector<vector<T>>st;
	ST (int x) {
		n = x;
		logn = __lg(n);
		LOG.resize(n + 1);
		st.resize(n, vector<T> (logn + 1));
		for (int i = 2; i <= n; i++) {
			LOG[i] = LOG[i / 2] + 1;
		}
	}
	void set(int i, T x) {
		st[i][0] = x;
	}
	void build() {
		for (int i = 1; i <= logn; i++) {
			for (int j = 0; j + (1 << i) - 1 < n; j++) {
				st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1], cmp);
			}
		}
	}
	T query(int l, int r) {
        if (l > r) return 0;
		int len = LOG[r - l + 1];
		return min(st[l][len], st[r - (1 << len) + 1][len], cmp);
	}
};

class Solution {
public:
    vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
        int n = s.size();
        int tot = count(s.begin(), s.end(), '1');
        vector<array<int, 2>> seq;
        seq.push_back({-1, -1});
        for (int i = 0, b = 0; i < n; i++) {
            if (i == n - 1 || s[i] != s[i + 1]) {
                if (s[i] == '0') seq.push_back({b, i + 1});
                b = i + 1; 
            }
        }
        seq.push_back({n + 1, n + 1});

        auto len = [&](int i) -> int {
            return seq[i][1] - seq[i][0];
        };
        auto merge = [&](int x, int y) -> int {
            return x > 0 && y > 0 ? x + y : 0;
        };

        int m = seq.size();
        ST<int, greater<>> st(m);
        for (int i = 0; i < m - 1; i++) {
            st.set(i, len(i) + len(i + 1));
        }
        st.build();

        int q = queries.size();
        vector<int> ans(q);
        for (int i = 0; i < q; i++) {
            int l = queries[i][0], r = queries[i][1] + 1;
            int L = lower_bound(seq.begin(), seq.end(), l, [&](const auto& p, int x) {
                return p[0] < x;
            }) - seq.begin();
            int R = upper_bound(seq.begin(), seq.end(), r, [&](int x, const auto& p) {
                return x < p[1];
            }) - seq.begin() - 1;
            int mx = 0;
            if (L <= R) {
                mx = max({st.query(L, R - 1), merge(seq[L - 1][1] - l, len(L)), merge(r - seq[R + 1][0], len(R))});
            } else if (L == R + 1) {
                mx = merge(seq[L - 1][1] - l, r - seq[R + 1][0]);
            }
            ans[i] = tot + mx;
        }
        return ans;
    }
};

力扣每日一题3513-不同XOR三元组的数目I

日期：2026-07-23

题意

给定一个排列数组 nums, 求其中任意可重三元组的不同异或和个数.

思路

注意到当排列长度大于 2 时, 所有二进制下位数与最大值相同的数均可构造出来.

实现

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return n;
        return 1 << (__lg(n) + 1);
    }
};

力扣每日一题3514-不同XOR三元组的数目II

日期：2026-07-24

题意

给定正整数数组 nums, 求其中任意可重三元组的不同异或和个数.

思路

和昨天题意还是非常像的, 但是数组从排列变成了随机数, 那就不能随便组成任意数了. 但是数据范围变小了很多, 最大数变成了 1500, 遇到这种有某个数给很小的, 基本就是考虑以此为突破口了. 最大数为 1500, 那么显然能组成的最大数为最近的 2 的幂次也就是 2048. 那先平方的组成任意二元组, 再遍历二元组以及第三个数组成三元组就好.

愿意折腾也可以学一学 FFT FWT, 但我们还是简单问题简单做吧.

实现

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int n = nums.size();
        int mx = ranges::max(nums);
        mx = 1 << (__lg(mx) + 1);
        vector<bool> f(mx), g(mx);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n ; j++) {
                f[nums[i] ^ nums[j]] = true;
            }
        }
        for (int i = 0; i < mx; i++) {
            if (!f[i]) continue;
            for (int x : nums) {
                g[i ^ x] = true;
            }
        }
        return ranges::count(g, true);
    }
};

力扣每日一题3536-两个数字的最大乘积

日期：2026-07-25

题意

给定一个正整数 n, 求其数位中任选两位的最大乘积.

思路

那遍历每一位求最大和次大数位相乘即可.

实现

class Solution {
public:
    int maxProduct(int n) {
        int mx = 0, se = 0;
        for ( ; n; n /= 10) {
            int x = n % 10;
            if (x > mx) {
                se = mx;
                mx = x;
            } else if (x > se) {
                se = x;
            }
        }
        return mx * se;
    }
};

力扣每日一题628-三个数的最大乘积

日期：2026-07-26

题意

给定整数数组 nums, 在其中任选三个不同数, 求三个数的最大乘积.

思路

和昨天不同的是变成了数组, 同时有负数的存在. 那含负数的最大三数乘积, 应该选择最大的三个数或者最小的两个数与一个最大的数. 可以像昨天一样遍历维护这几个数, 但要维护的数多了一些, 不如直接进行一个序的排偷懒, 在当前数据范围下不会慢太多的.

实现

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        return max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
    }
};

力扣每日一题1464-数组中两元素的最大乘积

日期：2026-07-27

题意

给定正整数数组 nums, 任选两个不同的数, 使得这两数各减一之差的乘积最大.

思路

不知道连出几道类似的简单题是何意味, 简单遍历维护最大次大值即可.

实现

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int mx = 0, se = 0;
        for (int x : nums) {
            if (x > mx) {
                se = mx;
                mx = x;
            } else if (x > se) {
                se = x;
            }
        }
        return (mx - 1) * (se - 1);
    }
};

力扣每日一题3517-最小回文排列I

日期：2026-07-28

题意

给定回文字符串 s, 将其转为字符组成相同且字典序最小的回文串.

思路

那记录下所有字符出现次数, 然后按字典序往回填即可.

实现

class Solution {
public:
    string smallestPalindrome(string s) {
        int n = s.size();
        array<int, 26> cnt;
        cnt.fill(0);
        for (auto& ch : s) cnt[ch - 'a']++;
        for (int i = 0, cur = 0; i < 26; i++) {
            char x = char('a' + i);
            if (cnt[i] & 1) {
                s[n / 2] = x;
                cnt[i]--;
            }
            for ( ; cnt[i]; cnt[i] -= 2, cur++) s[cur] = s[n - cur - 1] = x;
        }
        return s;
    }
};