力扣每月题解汇总-2026年09月
目录
2026-09-01力扣每日一题3568-清理教室的最少移动2026-09-02力扣每日一题3875-构造奇偶一致的数组I2026-09-03力扣每日一题3876-构造奇偶一致的数组II2026-09-04力扣每日一题3903-最小稳定下标I2026-09-05力扣每日一题3904-最小稳定下标II2026-09-06力扣每日一题115-不同的子序列2026-09-07力扣每日一题940-不同的子序列II2026-09-08力扣每日一题3870-统计范围内的逗号2026-09-09力扣每日一题3871-统计范围内的逗号II2026-09-10力扣每日一题2265-统计值等于子树平均值的节点数2026-09-11力扣每日一题3483-不同三位偶数的数目2026-09-12力扣每日一题3414-不重叠区间的最大得分2026-09-13力扣每日一题835-图像重叠2026-09-14力扣每日一题836-矩形重叠2026-09-15力扣每日一题2472-不重叠回文子字符串的最大数目2026-09-16力扣每日一题1621-大小为K的不重叠线段的数目2026-09-17力扣每日一题1477-找两个和为目标值且不重叠的子数组2026-09-18力扣每日一题1520-最多的不重叠子字符串2026-09-19力扣每日一题1401-圆和矩形是否有重叠2026-09-20力扣每日一题3498-字符串的反转度2026-09-21力扣每日一题3524-求出数组的X值I2026-09-22力扣每日一题3525-求出数组的X值II2026-09-23力扣每日一题1658-将x减到0的最小操作数
力扣每日一题3568-清理教室的最少移动
日期：2026-09-01
题意
给定含 障碍物 垃圾 充能区 的网格图 classroom, 初始有 energy 的能量. 每走一步需要消耗 1 能量, 经过回能区时会将能量恢复为 energy, 经过垃圾时可清理掉垃圾, 问从起点出发到清理掉所有垃圾所需的最小步数.
思路
那应该是做一个 bfs, 只是状态多了当前已清理掉的垃圾以及所剩能量.
实现
class Solution {
static constexpr array<int, 2> nxt[] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
public:
int minMoves(vector<string>& classroom, int energy) {
int n = classroom.size(), m = classroom.back().size();
vector mp(n, vector<int> (m));
int sx, sy;
int p = 0;
for (int i = 0, t = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (classroom[i][j] == 'S') {
sx = i;
sy = j;
} else if (classroom[i][j] == 'L') {
mp[i][j] = 1 << t;
p |= 1 << t;
t++;
}
}
}
queue<array<int, 5>> q;
q.push({sx, sy, energy, 0, 0});
vector vis(n, vector (m, vector<int> (p, -1)));
while (!q.empty()) {
auto [x, y, e, cur, t] = q.front();
q.pop();
if (cur == p) return t;
if (e == 0) continue;
int& d = vis[x][y][cur];
if (d >= e) continue;
d = e;
for (auto [tx, ty] : nxt) {
int nx = tx + x, ny = ty + y;
if (nx < 0 || nx >= n || ny < 0 || ny >= m || classroom[nx][ny] == 'X') continue;
q.push({nx, ny, classroom[nx][ny] == 'R' ? energy : e - 1, cur | mp[nx][ny], t + 1});
}
}
return -1;
}
};
力扣每日一题3875-构造奇偶一致的数组I
日期：2026-09-02
题意
给定一个数组 nums1, 问是否可以从中组成等长新数组 nums2 满足 (nums2[i] == nums1[i]) OR (nums2[i] == nums1[i] - nums1[j] AND i != j), 同时 nums2 中所有数奇偶性相同.
思路
注意到偶数减奇数为奇数, 因此其实所有情况下都是可以组成的.
实现
class Solution {
public:
bool uniformArray(vector<int>& nums1) {
return true;
}
};
力扣每日一题3876-构造奇偶一致的数组II
日期：2026-09-03
题意
给定一个数组 nums1, 问是否可以从中组成等长新数组 nums2 满足 (nums2[i] == nums1[i]) OR (nums2[i] == nums1[i] - nums1[j] AND i != j AND nums1[i] - nums1[j] >= 1), 同时 nums2 中所有数奇偶性相同.
思路
在昨天题意的基础上加上了 nums1[i] - nums1[j] >= 1 的条件, 换言之当前位置的数要比减数大, 也就是说最小偶数要比最小奇数大.
实现
class Solution {
public:
bool uniformArray(vector<int>& nums1) {
int odd = 0, even = 0, mnodd = INT_MAX, mneven = INT_MAX;
for (auto& x : nums1) {
if (x & 1) {
odd++;
mnodd = min(mnodd, x);
} else {
even++;
mneven = min(mneven, x);
}
}
if (even == 0 || odd == 0) return true;
return mneven > mnodd;
}
};
力扣每日一题3903-最小稳定下标I
日期：2026-09-04
题意
给定非负整数数组 nums; 定义若某位置的前缀最大值减去后缀最小值不超过 k 则称其为稳定位置. 求该数组中最早出现的稳定位置.
思路
那做一个后缀 min, 再从前往后做个前缀 max 找符合条件的点即可.
实现
class Solution {
public:
int firstStableIndex(vector<int>& nums, int k) {
int n = nums.size();
vector<int> suf(n);
suf[n - 1] = nums.back();
for (int i = n - 2; i >= 0; i--) {
suf[i] = min(suf[i + 1], nums[i]);
}
for (int i = 0, mx = 0; i < n; i++) {
mx = max(mx, nums[i]);
if (mx - suf[i] <= k) return i;
}
return -1;
}
};
力扣每日一题3904-最小稳定下标II
日期：2026-09-05
题意
给定非负整数数组 nums; 定义若某位置的前缀最大值减去后缀最小值不超过 k 则称其为稳定位置. 求该数组中最早出现的稳定位置.
思路
和昨天题意一样, 只是数据增强. 但我们昨天的做法仍是可行的, 做一个后缀min再做一个前缀max就好.
实现
class Solution {
public:
int firstStableIndex(vector<int>& nums, int k) {
int n = nums.size();
vector<int> suf(n);
suf[n - 1] = nums.back();
for (int i = n - 2; i >= 0; i--) {
suf[i] = min(suf[i + 1], nums[i]);
}
for (int i = 0, mx = 0; i < n; i++) {
mx = max(mx, nums[i]);
if (mx - suf[i] <= k) return i;
}
return -1;
}
};
力扣每日一题115-不同的子序列
日期：2026-09-06
题意
给定两个字符串 s 与 t, 求问 s 的子序列中 t 的出现次数.
思路
那应该是做一个 dp, 枚举每个 s 的前缀下各 t 的前缀出现次数. 但这里数据有点变态, 题目保证了答案在 32 位有符号整数范围内, 但实际开到 64 位也会超精度的, 用 unsigned 反而过了.
实现
class Solution {
public:
int numDistinct(string s, string t) {
if (t.size() > s.size()) return 0;
int n = t.size();
vector<unsigned> f(n + 1);
f[0] = 1;
for (const auto& ch : s) {
for (int i = n; i > 0; i--) {
if (ch == t[i - 1]) f[i] += f[i - 1];
}
}
return f.back();
}
};
力扣每日一题940-不同的子序列II
日期：2026-09-07
题意
给定字符串 s, 求问其中不同的子序列各数.
思路
那应该是做一个 dp, 维护以各字符为结尾的子序列的个数.
实现
class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;
public:
int distinctSubseqII(string s) {
array<ll, 26> f;
f.fill(0);
for (auto& ch : s) {
f[ch - 'a'] = (accumulate(f.begin(), f.end(), 0ll) + 1) % mod;
}
return accumulate(f.begin(), f.end(), 0ll) % mod;
}
};
力扣每日一题3870-统计范围内的逗号
日期：2026-09-08
题意
求 [1, n] 范围内的所有数在标准数学书写格式中, 会出现多少个 ‘,’.
思路
注意到数据范围为 1 <= n <= 1e5, 那显然只有大于等于一千的数有一个逗号.
实现
class Solution {
public:
int countCommas(int n) {
return max(0, n - 999);
}
};
力扣每日一题3871-统计范围内的逗号II
日期：2026-09-09
题意
求 [1, n] 范围内的所有数在标准数学书写格式中, 会出现多少个 ‘,’.
思路
和昨天一样的题意, 只是数据范围进行了扩大; 那么分阶段的统计贡献就好.
实现
class Solution {
using ll = long long;
public:
ll countCommas(ll n) {
ll ans = 0;
for (ll p = 1000; p <= n; p *= 1000) {
ans += max(0ll, n - p + 1);
if (p * 1000 > n) break;
}
return ans;
}
};
力扣每日一题2265-统计值等于子树平均值的节点数
日期：2026-09-10
题意
给定一棵二叉树, 求问节点值等于其子树节点平均值的点个数.
思路
那进行一个递归, 返回子树中的总权值和与点个数, 求符合条件的点数即可.
实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int averageOfSubtree(TreeNode* root) {
int ans = 0;
auto dfs = [&](this auto&& self, TreeNode* u) -> array<int, 2> {
if (u == nullptr) return {0, 0};
auto [val1, cnt1] = self(u->left);
auto [val2, cnt2] = self(u->right);
int val = val1 + val2 + u->val, cnt = cnt1 + cnt2 + 1;
if (u->val == val / cnt) ans++;
return {val, cnt};
};
dfs(root);
return ans;
}
};
力扣每日一题3483-不同三位偶数的数目
日期：2026-09-11
题意
给定个位数数组 digits, 问其中能组成的不同三位数的偶数的数量.
思路
想来半天好像都有点不太好写, 一看发现数据范围非常小, 于是写了个暴力用运行时间换思考时间了.
实现
class Solution {
public:
int totalNumbers(vector<int>& digits) {
unordered_set<int> ust;
int n = digits.size();
for (int i = 0; i < n; i++) {
if (digits[i] == 0) continue;
for (int j = 0; j < n; j++) {
if (i == j) continue;
for (int k = 0; k < n; k++) {
if (k == i || k == j || (digits[k] & 1)) continue;
ust.insert(digits[i] * 100 + digits[j] * 10 + digits[k]);
}
}
}
return ust.size();
}
};
力扣每日一题3414-不重叠区间的最大得分
日期：2026-09-12
题意
给定多个带权重的一维区间, 最多可选四个互不重叠的区间, 求选定区间最大总权重和.
思路
那应该是一个记录路径的, 有方案数限制的 dp; 方案数最多为 4, 可以直接选择再开一维记录当前已选的区间数量; 记录路径则另开一数组每次选择最大报酬的方案即可.
实现
class Solution {
using ll = long long;
public:
vector<int> maximumWeight(vector<vector<int>>& intervals) {
int n = intervals.size();
for (int i = 0; i < n; i++) intervals[i].push_back(i);
ranges::sort(intervals, [&](const auto&x, const auto& y) {
if (x[1] != y[1]) return x[1] < y[1];
return x[0] < y[0];
});
vector<int> pw(n);
for (int i = 0; i < n; i++) pw[i] = intervals[i][1];
vector f(5, vector<ll> (n + 1));
vector g(5, vector<vector<int>> (n + 1));
for (int t = 1; t <= 4; t++) {
for (int i = 1; i <= n; i++) {
ll x = f[t][i - 1];
int loc = ranges::lower_bound(pw, intervals[i - 1][0]) - pw.begin();
ll y = f[t - 1][loc] + intervals[i - 1][2];
f[t][i] = max(x, y);
if (x > y) g[t][i] = g[t][i - 1];
else {
g[t][i] = g[t - 1][loc];
g[t][i].push_back(intervals[i - 1][3]);
ranges::sort(g[t][i]);
}
if(x == y) {
g[t][i] = min(g[t][i], g[t][i - 1]);
}
}
}
return g[4][n];
}
};
力扣每日一题835-图像重叠
日期：2026-09-13
题意
给定两个零一方格, 可将其一内的所有数向上下左右任意平移并用零补齐空位, 求最终两方格相同位置均为一的位置数最多有多少.
思路
没什么好办法耶, 但注意到数据范围很小, 四次方的复杂度也能接受, 因此写个暴暴的力.
实现
class Solution {
public:
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int ans = 0;
int n = img1.size();
auto check = [&](int rbias, int cbias) -> void {
int res1 = 0, res2 = 0, res3 = 0, res4 = 0;
for (int i = rbias; i < n; i++) {
for (int j = cbias; j < n; j++) {
res1 += img1[i][j] * img2[i - rbias][j - cbias];
res2 += img1[i - rbias][j - cbias] * img2[i][j];
res3 += img1[i - rbias][j] * img2[i][j - cbias];
res4 += img1[i][j - cbias] * img2[i - rbias][j];
}
}
ans = max({ans, res1, res2, res3, res4});
};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
check(i, j);
return ans;
}
};
力扣每日一题836-矩形重叠
日期：2026-09-14
题意
给定两个二维矩阵的左下角与右上角, 问两矩阵是否相交.
思路
那就是判断(靠左下的(矩阵的右上角))是否位于(靠右上的(矩阵的左下角))的右上方.
实现
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
return min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) && min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]);
}
};
力扣每日一题2472-不重叠回文子字符串的最大数目
日期：2026-09-15
题意
给定字符串 s 与一个正整数 k, 求该字符串最多能分割为多少个长度至少为 k 且互不重合的回文子串.
思路
看到回文串分割首先是想到了马拉车算法, 然后就只剩下贪心地分割了.
实现
vector<int> manacher(string s) {
string t = "#";
for (auto c : s) {
t += c;
t += '#';
}
int n = t.size();
vector<int> r(n);
for (int i = 0, j = 0; i < n; i++) {
if (2 * j - i >= 0 && j + r[j] > i) {
r[i] = min(r[2 * j - i], j + r[j] - i);
}
while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
r[i] += 1;
}
if (i + r[i] > j + r[j]) {
j = i;
}
}
return r;
}
class Solution {
public:
int maxPalindromes(string s, int k) {
vector<int> r = manacher(s);
int n = r.size();
int ans = 0;
auto check = [&](int l) -> bool {
if (l + k >= n) return false;
return r[l + k] - 1 >= k;
};
for (int i = 0; i < n; ) {
if (check(i)) {
ans++;
i += 2 * k;
} else if (check(i + 1)) {
ans++;
i += 2 * k + 2;
} else {
i += 2;
}
}
return ans;
}
};
力扣每日一题1621-大小为K的不重叠线段的数目
日期：2026-09-16
题意
给定一条直线上的 n 个点, 要求从中切分出互不重叠的 k 条线段(线段端点间可交可不交), 求问有多少种切分方式.
思路
k 个线段, 则带两端有 k + 1 条空隙，也就是说要把 n - 1 的长度分给 2k + 1 个线段, 其中有 k 个必须非空, k + 1 个可以为空; 那转换为 n - 1 + k + 1 个球分给 2k + 1 个盒子，要求不能为空, 那直接进行一个插板法就好了.
实现
class Solution:
def numberOfSets(self, n: int, k: int) -> int:
return comb(n + k - 1, k * 2) % 1000000007
力扣每日一题1477-找两个和为目标值且不重叠的子数组
日期：2026-09-17
题意
给定正整数数组 arr 与一个正整数 target; 请寻找两个互不重叠的且和均为 target 的子数组, 求两子数组长度的最小和.
思路
那应该做一个滑动窗口遍历数组, 找到每一个和为 target 的子数组; 同时维护每个左端点以左(及在之前且与当前无重叠)的最短的满足题意的子数组长度.
实现
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int n = arr.size();
vector<int> last(n + 1, n + 1);
int ans = n + 1;
for (int l = 0, r = 0, cur = 0; r < n; r++) {
cur += arr[r];
for ( ; cur >= target; cur -= arr[l++]) {
if (cur == target) {
last[r + 1] = min(last[r + 1], r - l + 1);
ans = min(ans, last[l] + r - l + 1);
}
}
last[r + 1] = min(last[r + 1], last[r]);
}
return ans == n + 1 ? -1 : ans;
}
};
力扣每日一题1520-最多的不重叠子字符串
日期：2026-09-18
题意
给定字符串 s; 要求选出数量最多的非空子字符串, 要求这些子串互不重叠, 且若某子串含某字符则该子串必须包含 s 内的所有该字符. 若存在多组解返回总长最小的解.
思路
如果问题简化为给出多个区间, 要求返回最多无重且长度最小的区间, 那就是排序后贪心, 是比较好做的. 那如何能将问题转换为多个区间呢, 我这里是做了个前缀和并维护了各个字符的最左最右位置, 然后写了个比较变态的 (26 * 26 * 26) 的区间扩展. 比较合理的是用包含关系建个图然后 dfs, 不过字符范围就这么大, 我就偷偷懒了.
实现
class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
int n = s.size();
array<int, 26> left, right;
left.fill(-1); right.fill(-1);
vector<array<int, 26>> pre(n + 1);
for (int i = 0; i < n; i++) {
int x = s[i] - 'a';
pre[i + 1] = pre[i];
pre[i + 1][x]++;
if (left[x] == -1) left[x] = i;
right[x] = i;
}
vector<array<int, 2>> p;
for (int i = 0; i < 26; i++) {
if (left[i] == -1) continue;
int l = left[i], r = right[i];
auto check = [&]() -> bool {
for (int j = 0; j < 26; j++) {
if (pre[r + 1][j] - pre[l][j] == 0) continue;
int nl = left[j], nr = right[j];
if (nl >= l && nr <= r) continue;
l = min(l, nl);
r = max(r, nr);
return true;
}
return false;
};
while (check());
p.push_back({l, r});
}
ranges::sort(p, [&](const auto& x, const auto& y) {
return x[1] < y[1];
});
vector<string> ans;
int last = 0;
for (auto [l, r] : p) {
if (l < last) continue;
last = r;
ans.push_back(s.substr(l, r - l + 1));
}
return ans;
}
};
力扣每日一题1401-圆和矩形是否有重叠
日期：2026-09-19
题意
给定一个圆的圆心与半径, 以及一个矩形的左下与右上角; 判断该圆与该矩形是否相交.
思路
那应该是找矩形中离圆最近的点与圆心的距离.
实现
class Solution {
public:
bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
int x = clamp(xCenter, x1, x2);
int y = clamp(yCenter, y1, y2);
return (x - xCenter) * (x - xCenter) + (y - yCenter) * (y - yCenter) <= radius * radius;
}
};
力扣每日一题3498-字符串的反转度
日期：2026-09-20
题意
定义字符串的反转度为: 置 a=26 b=25…再使得每个字符与其下标相乘求和. 给定字符串 s, 求其反转度.
思路
依题进行模拟即可.
实现
class Solution {
public:
int reverseDegree(string s) {
int ans = 0;
for (int i = 0; i < s.size(); i++) {
ans += (i + 1) * (26 - (s[i] - 'a'));
}
return ans;
}
};
力扣每日一题3524-求出数组的X值I
日期：2026-09-21
题意
给定正整数数组 nums 与一个正整数 k, 可以执行一次操作将该数组的任意不重叠前缀与后缀删除但需保持数组非空; 对于所有的 x < k, 求问剩余元素乘积对 k 取模的余数为 x 的方案数是多少.
思路
k 的数据范围并不大, 枚举剩余数的右端点, 记录每个余数的方案数进行一个 dp 即可.
实现
class Solution {
using ll = long long;
public:
vector<long long> resultArray(vector<int>& nums, int k) {
const int n = nums.size();
vector<ll> f(k), ans(k);
for (int x : nums) {
vector<ll> nf(k);
x %= k;
nf[x] = 1;
for (int i = 0; i < k; i++) {
nf[x * i % k] += f[i];
}
for (int i = 0; i < k; i++) {
ans[i] += nf[i];
}
f = move(nf);
}
return ans;
}
};
力扣每日一题3525-求出数组的X值II
日期：2026-09-22
题意
思路
实现
力扣每日一题1658-将x减到0的最小操作数
日期：2026-09-23
题意
给定整数数组 nums 和一个整数 x, 每次操作可以移除该数组的第一个数或最后一个数, 并使得 x 减去该数. 求问将 x 减为 0 所需的最小操作数.
思路
换而言之, 就是剩下的数的和为 sum(nums) - x 且希望剩下的数的个数仅可能大, 那做一个滑动窗口就好.
实现
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
f = sum(nums) - x
if f < 0:
return -1
ans = -1
cur = l = 0
for r, num in enumerate(nums):
cur += num
while cur > f:
cur -= nums[l]
l += 1
if cur == f:
ans = max(ans, r - l + 1)
return -1 if ans < 0 else len(nums) - ans