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

目录

力扣每日一题-2144-打折购买糖果的最小开销

日期：2026-06-01

题意

给定正整数数组 cost 表示一些糖果的售价. 若每购买两颗糖果, 可以获赠任意一颗价值不大于这两颗糖果的糖, 求问购买所有糖果所需最少花费.

思路

应该是降序排序后, 每次买所剩当中最贵两颗, 赠品选第三贵那颗.

实现

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        ranges::sort(cost, greater());
        int ans = 0, n = cost.size();
        for (int i = 0; i < n; i++) {
            if (i + 2 < n) {
                ans += cost[i] + cost[i + 1];
                i += 2;
            } else ans += cost[i];
        }
        return ans;
    }
};

力扣每日一题3633-最早完成陆地和水上游乐设施的时间I

日期：2026-06-02

题意

给定四个正整数数组 landStartTime landDuration waterStartTime waterDuration, 分别表示多个陆地和水上娱乐设施的最早的开放时间以及对应所需的游乐时间. 每个类别项目至少体验一项, 求最早结束时间.

思路

数据范围不大, 也仅需各选一项, 进行一个枚枚的举和贪贪的心就好.

实现

class Solution {
public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
        const int n = landStartTime.size(), m = waterStartTime.size();
        int ans = 1e9;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = min(ans, max(landStartTime[i] + landDuration[i], waterStartTime[j]) + waterDuration[j]);
                ans = min(ans, max(waterStartTime[j] + waterDuration[j], landStartTime[i]) + landDuration[i]);
            }
        }
        return ans;
    }
};

力扣每日一题3635-最早完成陆地和水上游乐设施的时间II

日期：2026-06-03

题意

给定四个正整数数组 landStartTime landDuration waterStartTime waterDuration, 分别表示多个陆地和水上娱乐设施的最早的开放时间以及对应所需的游乐时间. 每个类别项目至少体验一项, 求最早结束时间.

思路

和昨天的题是一致的, 只是数据范围进行了扩大, 不再能直接进行枚举. 但可以想到, 最优一定是在某个项目一开放就参与, 然后(一结束/另一项目一开放)就立刻参与下一项目, 开个变量记录对应的最早结束时间, 再枚举下一活动即可.

实现

class Solution {
public:
    int earliestFinishTime(vector<int>& landS, vector<int>& landD, vector<int>& waterS, vector<int>& waterD) {
        const int n = landS.size(), m = waterS.size();
        int ans = 1e9;
        int lf = 1e9, wf = 1e9;
        for (int i = 0; i < n; i++) {
            lf = min(lf, landS[i] + landD[i]);
        }
        for (int i = 0; i < m; i++) {
            ans = min(ans, max(lf, waterS[i]) + waterD[i]);
            wf = min(wf, waterS[i] + waterD[i]);
        }
        for (int i = 0; i < n; i++) {
            ans = min(ans, max(wf, landS[i]) + landD[i]);
        }
        return ans;
    }
};

力扣每日一题3751-范围内总波动值I

日期：2026-06-04

题意

给定两个正整数 num1 与 num2. 某数若某个数位严格小于或严格大于相邻数位则为该数贡献 1 波动值, 求 [num1, num2] 范围内所有数的波动值之和.

思路

那应该就是一个数位 dp, 需要枚举每个数位填什么所得到的贡献. 这里我们需要知道 上一数与上上数的关系 上一数数值 这一数填什么 即可计算当前位贡献.

实现

class Solution {
using ll = long long;
public:
    ll totalWaviness(ll num1, ll num2) {
        string s = to_string(num1), t = to_string(num2);
        int n = s.size(), m = t.size();
        vector f(m, vector (m, vector (3, vector<ll> (10))));

        auto cal = [&](this auto&& self, int i, int cnt, int p, int last, int lo, int hi) -> ll {
            if (i == m) return cnt;
            ll& res = f[i][cnt][p][last];
            if (res && !lo && !hi) return res - 1;

            int l = 0, r = 9;
            if (lo && i >= m - n) l = s[i - m + n] - '0';
            if (hi) r = t[i] - '0';
            ll cur = 0;
            int fill = !lo || i > m - n;
            for (int x = l; x <= r; x++) {
                int np;
                if (!fill || x == last) np = 0;
                else if (x < last) np = 1;
                else np = 2;
                int ncnt = cnt;
                if (p + np == 3) ncnt++;
                int nlo = 0, nhi = 0;
                if (lo && x == l) nlo = 1;
                if (hi && x == r) nhi = 1;
                cur += self(i + 1, ncnt, np, x, nlo, nhi);
            }

            if (!lo && !hi) res = cur + 1;
            return cur;
        };

        return cal(0, 0, 0, 0, 1, 1);
    }
};

力扣每日一题3753-范围内总波动值II

日期：2026-06-05

题意

给定两个正整数 num1 与 num2. 某数若某个数位严格小于或严格大于相邻数位则为该数贡献 1 波动值, 求 [num1, num2] 范围内所有数的波动值之和.

思路

和昨天一样的题, 仅仅是数据范围增强了. 看到按数位贡献应该就比较自然想到是数位 dp.

实现

class Solution {
using ll = long long;
public:
    ll totalWaviness(ll num1, ll num2) {
        string s = to_string(num1), t = to_string(num2);
        int n = s.size(), m = t.size();
        vector f(m, vector (m, vector (3, vector<ll> (10))));

        auto cal = [&](this auto&& self, int i, int cnt, int p, int last, int lo, int hi) -> ll {
            if (i == m) return cnt;
            ll& res = f[i][cnt][p][last];
            if (res && !lo && !hi) return res - 1;

            int l = 0, r = 9;
            if (lo && i >= m - n) l = s[i - m + n] - '0';
            if (hi) r = t[i] - '0';
            ll cur = 0;
            int fill = !lo || i > m - n;
            for (int x = l; x <= r; x++) {
                int np;
                if (!fill || x == last) np = 0;
                else if (x < last) np = 1;
                else np = 2;
                int ncnt = cnt;
                if (p + np == 3) ncnt++;
                int nlo = 0, nhi = 0;
                if (lo && x == l) nlo = 1;
                if (hi && x == r) nhi = 1;
                cur += self(i + 1, ncnt, np, x, nlo, nhi);
            }

            if (!lo && !hi) res = cur + 1;
            return cur;
        };

        return cal(0, 0, 0, 0, 1, 1);
    }
};

力扣每日一题2574-左右元素和的差值

日期：2026-06-06

题意

给定正整数数组 nums, 求每个元素其左元素和与其右元素和之差的绝对值.

思路

那进行一个前后缀和再做差就好.

实现

class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n), pre(n);
        for (int i = 0; i < n - 1; i++) {
            pre[i + 1] = nums[i] + pre[i];
        }
        for (int i = n - 1, suf = 0; i >= 0; i--) {
            ans[i] = abs(suf - pre[i]);
            suf += nums[i];
        }
        return ans;
    }
};

力扣每日一题2196-根据描述创建二叉树

日期：2026-06-07

题意

给定数组 descriptions_i = [parent_i, child_i, isLeft_i] 表示若 isLeft == 1 则值为 child 的节点是值为 parent 的节点的左儿子, 反正为右儿子. 构建出对应的二叉树并返回其根节点.

思路

开一个哈希记录每个值对应的节点指针, 再记录所有无父节点的节点作为根节点候选即可.

实现

/**
 * 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:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        unordered_map<int, TreeNode*> ump;
        unordered_set<int> np;
        for (auto& d : descriptions) {
            int parent = d[0], child = d[1], isLeft = d[2];
            TreeNode* p = nullptr;
            TreeNode* c = nullptr;
            if (ump.count(parent)) p = ump[parent];
            else {
                p = new TreeNode(parent);
                ump[parent] = p;
                np.insert(parent);
            }
            if (ump.count(child)) c = ump[child];
            else {
                c = new TreeNode(child);
                ump[child] = c;
            }

            if (isLeft) p->left = c;
            else p->right = c;

            if (np.count(child)) np.erase(child);
        }

        return ump[*np.begin()];
    }
};

力扣每日一题2161-根据给定数字划分数组

日期：2026-06-08

题意

给定整数数组 nums, 以及一个整数 pivot. 请将所有小于 pivot 的数移动至所有等于对应数的数前面, 同时所有等于该数的数移动到所有大于该数的数前面. 同时保留小于该数部分的数之间的原相对位置关系, 以及保留大于该数部分的数之间的原相对位置关系.

思路

好像因为我尝试压缩题意反而使得题目更难读懂了. 实际就是将数组按顺序分为小于指定数、等于指定数、大于指定数这三个个部分, 然后再拼起来就好.

实现

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> ans, suf;
        int cnt = 0;
        for (auto& x : nums) {
            if (x < pivot) ans.push_back(x);
            else if (x == pivot) cnt++;
            else suf.push_back(x);
        }
        ans.insert(ans.end(), cnt, pivot);
        ans.insert(ans.end(), suf.begin(), suf.end());
        return ans;
    }
};

力扣每日一题3689-最大子数组总值I

日期：2026-06-09

题意

给定整数数组 nums 与一个整数 k. 定义子数组价值为其最大最小值之差. 请选出恰好 k 个非空且允许重叠且端点可任选无限次的子数组, 使得它们价值和最大.

思路

允许重叠且端点可任选无限次, 那统统选整个数组好了, 那就是 k 个最大最小值之差.

实现

class Solution {
using ll = long long;
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        ll mx = ranges::max(nums);
        ll mn = ranges::min(nums);
        return (mx - mn) * k;
    }
};

力扣每日一题3691-最大子数组总值II

日期：2026-06-10

题意

给定整数数组 nums 与一个整数 k. 定义子数组价值为其最大最小值之差. 请选出恰好 k 个非空且允许重叠但两两不可完全相同的子数组, 使得它们价值和最大.

思路

在昨天的基础上增加了不能选择相同子数组的限制, 那仅需在此基础上固定各左端点选择, 逐步减小右端点范围, 进行一个优先队列排序就好.

实现

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) {
		int len = LOG[r - l + 1];
		return min(st[l][len], st[r - (1 << len) + 1][len], cmp);
	}
};

class Solution {
using ll = long long;
public:
    ll maxTotalValue(vector<int>& nums, int k) {
        int n = nums.size();
        ST<int, greater<>> mx(n);
        ST<int, less<>> mn(n);
        for (int i = 0; i < n; i++) {
            mx.set(i, nums[i]);
            mn.set(i, nums[i]);
        }
        mx.build();
        mn.build();
        auto query = [&](int l, int r) -> ll {
            return mx.query(l, r) - mn.query(l, r);
        };

        priority_queue<array<ll, 3>> pq;
        for (int i = 0; i < n; i++) {
            pq.push({query(i, n - 1), i, n - 1});
        }

        ll ans = 0;
        for (int i = 0; i < k; i++) {
            auto [cur, l, r] = pq.top();
            pq.pop();
            ans += cur;
            if (l <= r - 1) pq.push({query(l, r - 1), l, r - 1});
        }
        return ans;
    }
};

力扣每日一题3558-给边赋权值的方案数I

日期：2026-06-11

题意

给定一颗树, 可将每条边的权值设置为 0 或 1. 任选一个深度最大的点, 使得根到该点的路径权值和为奇数, 求问有几种设置方案.

思路

和为奇数, 则共有奇数条边权值为奇数. 任选深度最大的点, 那深度一样的情况下, 根到对应点的边数均一样. 仅需求出最大深度即可.

实现

class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;

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

public:
    int assignEdgeWeights(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            int& u = e[0], v = e[1];
            u--; v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        int d = 0;
        auto dfs = [&](this auto&& self, int u, int fa, int cur) -> void {
            d = max(d, cur);
            for (auto& v : adj[u]) {
                if (v == fa) continue;
                self(v, u, cur + 1);
            }
        };
        dfs(0, -1, 0);

        return powMod(2, d - 1);
    }
};

力扣每日一题3559-给边赋权值的方案数II

日期：2026-06-12

题意

给定一颗树, 可将每条边的权值设置为 0 或 1. 给定一组询问 queries, 每组询问给出两个点, 求问这两点之间路径权值和为奇数的方案数.

思路

和昨天也没太大区别, 就是根到最深点变成了任意两点, 那想办法求出任意两点距离就好. 那可以想到是一个 LCA 问题, 可以树链剖分也可以倍增. 树剖常数低, 倍增好写好理解. 这里我写的是倍增.

实现

class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;

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

public:
    vector<int> assignEdgeWeights(vector<vector<int>>& edges, vector<vector<int>>& queries) {
        int n = edges.size() + 1;
        vector<vector<int>> adj(n);
        vector<int> d(n);
        int mx = __lg(n) + 1;
        vector<vector<int>> f(mx, vector<int> (n, -1));
        for (auto& e : edges) {
            int& u = e[0], v = e[1];
            u--; v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        auto dfs = [&](this auto&& self, int u, int fa, int dep) -> void {
            d[u] = dep;
            for (auto v : adj[u]) {
                if (v == fa) continue;
                f[0][v] = u;
                self(v, u, dep + 1);
            }
        };
        dfs(0, -1, 0);

        for (int i = 1; i < mx; i++) {
            for (int j = 0; j < n; j++) {
                if (f[i - 1][j] != -1) f[i][j] = f[i - 1][f[i - 1][j]];
            }
        }
        auto lca = [&](int u, int v) -> int {
            if (d[u] < d[v]) swap(u, v);
            for (int i = mx - 1; i >= 0; i--) {
                if (f[i][u] != -1 && d[f[i][u]] >= d[v]) u = f[i][u];
            }
            if (u == v) return u;
            for (int i = mx - 1; i >= 0; i--) {
                if (f[i][u] != f[i][v]) {
                    u = f[i][u];
                    v = f[i][v];
                }
            }
            return f[0][u];
        };

        int q = queries.size();
        vector<int> ans(q);
        for (int i = 0; i < q; i++) {
            int u = queries[i][0], v = queries[i][1];
            u--; v--;
            if (u == v) {
                ans[i] = 0;
                continue;
            }
            int fa = lca(u, v);
            int dis = d[u] + d[v] - 2 * d[fa];
            ans[i] = powMod(2, dis - 1);
        }
        return ans;
    }
};

力扣每日一题3838-带权单词映射

日期：2026-06-13

题意

给定字符串数组 words, 以及一个权重字典 weights 表示每个字符的权重. 其中每个字符串的权重为其各字符的权重和. 使得各字符串权重对 26 取模, 将其转换为倒数第 (权重 % 26) 个英文小写字符. 求完全转换结果.

思路

没什么特别的, 根据题意进行权重求和与转换即可.

实现

class Solution {
const string s = "zyxwvutsrqponmlkjihgfedcba";
public:
    string mapWordWeights(vector<string>& words, vector<int>& weights) {
        string ans;
        for (auto& w : words) {
            int cur = 0;
            for (auto& ch : w) {
                cur += weights[ch - 'a'];
            }
            ans += s[cur % 26];
        }
        return ans;
    }
};

力扣每日一题2130-链表最大孪生和

日期：2026-06-14

题意

给定正整数链表, 求正数第 i 个数与倒数第 i 个数的和的最大值.

思路

我这里偷了懒, 开了个 vector 记录整个链表的值. 如果想要不开额外空间, 应该是一个快慢指针找到中点, 然后中点之后的链表翻转, 再双指针遍历.

实现

/**
 * 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:
    int pairSum(ListNode* head) {
        vector<int> t;
        for ( ; head != nullptr; head = head->next) {
            t.push_back(head->val);
        }
        int ans = 0;
        for (int i = 0, j = t.size() - 1; i < j; i++, j--) {
            ans = max(ans, t[i] + t[j]);
        }
        return ans;
    }
};

力扣每日一题2095-删除链表的中间节点

日期：2026-06-15

题意

给定链表, 删除其中间节点.

思路

进行一个快慢指针就好.

实现

/**
 * 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* deleteMiddle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return nullptr;

        ListNode* s = head;
        ListNode* f = head->next->next;
        for ( ; f != nullptr && f->next != nullptr; s = s->next, f = f->next->next);
        ListNode* t = s->next;
        s->next = s->next->next;
        return head;
    }
};

力扣每日一题2612-用特殊操作处理字符串I

日期：2026-06-16

题意

给定字符串 s, 按其指示从左到右遍历顺序操作: 若当前字符为字母则将其加入到结果当中; 若为 ‘*’ 则将结果中的最后一个字符删去; 若为 ‘#’ 将结果复制到当前结果末尾; 若为 ‘%’ 则将结果翻转. 求最终操作结果.

思路

数据范围不太大, 依据给定字符串进行一个模拟即可.

实现

class Solution {
public:
    string processStr(string s) {
        string result;
        for (const auto& ch : s) {
            if (ch == '*') {
                if (!result.empty()) result.pop_back();
            } else if (ch == '#') result += result;
            else if (ch == '%') reverse(result.begin(), result.end());
            else result += ch;
        }
        return result;
    }
};

力扣每日一题3614-用特殊操作处理字符串II

日期：2026-06-17

题意

给定字符串 s, 按其指示从左到右遍历顺序操作: 若当前字符为字母则将其加入到结果当中; 若为 ‘*’ 则将结果中的最后一个字符删去; 若为 ‘#’ 将结果复制到当前结果末尾; 若为 ‘%’ 则将结果翻转. 求最终操作结果中的第 k 个字符是什么.

思路

数据范围已经大了很多, 是无法从头到尾进行模拟的. 那只能是从尾到头去记录, 反推出要求字符的来源即可. 但需要注意可能存在空删的操作, 因此还需从头处理记录空删的操作位置.

实现

class Solution {
using ll = long long;
public:
    char processStr(string s, long long k) {
        k++;
        ll len = 0;
        const int n = s.size();
        unordered_set<int> tmp;
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (ch == '*') {if (len) {len--; tmp.insert(i);}}
            else if (ch == '#') len <<= 1;
            else if (ch == '%') ;
            else len++;
        }
        if (len < k) return '.';
        char ans = '.';
        for (int i = n - 1; i >= 0; i--) {
            char ch = s[i];
            if (ch == '*') {if (tmp.count(i)) len++;}
            else if (ch == '#') {
                len >>= 1;
                if (k <= len) continue;
                k -= len;
            } else if (ch == '%') {
                k = len - k + 1;
            } else {
                if (len == k) {
                    ans = s[i];
                    break;
                }
                len--;
            }
        }
        return ans;
    }
};

力扣每日一题1344-时钟指针的夹角

日期：2026-06-18

题意

问 hour 时 minutes 分时, 时针与分针之间较小角的角度是多少.

思路

每分钟时针转 360 / 12 / 60 == 0.5 度, 每分钟分针转 360 / 60 == 6 度. 做差计算即可.

实现

class Solution {
public:
    double angleClock(int hour, int minutes) {
        double ans = abs(0.5 * (60 * hour + minutes) - 6 * minutes);
        return min(ans, 360.0 - ans);
    }
};

力扣每日一题1732-找到最高海拔

日期：2026-06-19

题意

给定整数数组 gain, 表示每个点与前一点的净海拔差, 求这些点的最高海拔.

思路

那就是给定一个差分结果, 将其还原找最大即可.

实现

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int ans = 0;
        int n = gain.size();
        for (int i = 0, t = 0; i < n; i++) {
            t += gain[i];
            ans = max(ans, t);
        }
        return ans;
    }
};

力扣每日一题1840-最高建筑高度

日期：2026-06-20

题意

有 n 个相邻建筑, 要求第 1 栋建筑高为 0 且任意两相邻建筑之间高度差不大于 1; 同时给定一组约束条件 restrictions[i] = [id, maxHeight] 表示第 id 个建筑最高高度不超过 maxHeight. 求问可以满足所有限制条件下的最高建筑高度.

思路

且先仅关注相邻的有约束条件的建筑高度, 显然某建筑的最高高度为 原生限制 和 前一建筑一直增高到此建筑 的最小值. 前后扫描一遍即可得各建筑约束则可得最高点.

实现

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        int m = restrictions.size();
        if (m == 0) return n - 1;
        ranges::sort(restrictions);
        vector<int> f(m);
        f[0] = min(restrictions[0][1], restrictions[0][0] - 1);

        for (int i = 1; i < m; i++) {
            int id = restrictions[i][0], h = restrictions[i][1];
            f[i] = min(f[i - 1] + id - restrictions[i - 1][0], h);
        }
        for (int i = m - 2; i >= 0; i--) {
            int id = restrictions[i][0], h = restrictions[i][1];
            f[i] = min(f[i], f[i + 1] + restrictions[i + 1][0] - id);
        }

        int ans = 0;
        for (int i = 1; i < m; i++) {
            int id = restrictions[i][0], h = restrictions[i][1];
            ans = max(ans, (id - restrictions[i - 1][0] + f[i] + f[i - 1]) / 2);
        }
        return max({ans, (restrictions[0][0] - 1 + f[0]) / 2, n - restrictions[m - 1][0] + f[m - 1]});
    }
};

力扣每日一题1833-雪糕的最大数量

日期：2026-06-21

题意

给定正整数数组 costs 表示若干雪糕的价格, 共有 coins 块钱, 求问最多买多少支雪糕.

思路

显然应该排序后从便宜的开始买, 进行一个贪贪的心就好.

实现

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        ranges::sort(costs);
        int ans = 0;
        for (auto& x : costs) {
            if (coins >= x) {
                ans++;
                coins -= x;
            } else break;
        }
        return ans;
    }
};

力扣每日一题1189-“气球”的最大数量

日期：2026-06-22

题意

给定字符串 text, 求问其中的字符可以组成多少个 ‘balloon’

思路

使用哈希记录每个字符出现的次数, 答案即为 ‘balloon’ 几个字符出现的最小次数, 需要注意 l 与 o 的值需要除以二即可.

实现

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        cnt = {ch: 0 for ch in "balloon"}
        for ch in text:
            if ch in "balloon":
                cnt[ch] += 1
        cnt['l'] //= 2
        cnt['o'] //= 2
        return min(cnt.values())

力扣每日一题3699-锯齿形数组的总数I

日期：2026-06-23

题意

给定三个正整数 n l 和 r. 表示要构造一个长度为 n, 每个元素取值范围在 [l, r] 的数组, 同时要求满足任意两个相邻元素都不想等且任意三个连续元素不能构成一个严格递增或严格递减的序列. 求问有多少种满足条件的构造法.

思路

这题数据范围很好啊, 3 <= n <= 2000 && 1 <= l < r <= 2000. 题意要求换言而之就是除首尾元素外每个元素都是极大或极小值点, 总的取值范围又比较小, 可以想到进行一个 dp, 枚举每一位数选择每一个数相对上一数变大或变小有多少种方案数. 这里我是赛时写的, 就直接上 MInt 板子了显得有点多, 但核心其实很简单的.

实现

using ll = long long;
using ull = unsigned long long;
using u32 = unsigned;

template<typename T>
constexpr T power(T a, ull b) {
    T res {1};
    for (; b != 0; b /= 2, a *= a) {
        if (b % 2 == 1) {
            res *= a;
        }
    }
    return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return 1ULL * a * b % P;
}

template<ull P>
constexpr ull mulMod(ull a, ull b) {
    ull res = a * b - ull(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

template<typename U, U P>
requires std::unsigned_integral<U>
struct ModIntBase {
public:
    constexpr ModIntBase() : x(0) {}
    
    template<typename T>
    requires std::integral<T>
    constexpr ModIntBase(T x_) : x(norm(x_ % T {P})) {}
    
    constexpr static U norm(U x) {
        if ((x >> (8 * sizeof(U) - 1) & 1) == 1) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = norm(P - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, P - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<P>(x, rhs.val());
        return *this;
    }
    
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() != rhs.val();
    }
    
    friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() < rhs.val();
    }
    
private:
    U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;

template<ull P>
using ModInt64 = ModIntBase<ull, P>;

constexpr u32 P = 1000000007;
using Z = ModInt<P>;

class Solution {
public:
    int zigZagArrays(int n, int l, int r) {
        int m = r - l + 1;
        vector f(2, vector<Z> (m));
        for (int i = 0; i < n - 1; i++) {
            vector nf(2, vector<Z> (m));
            Z pre = 0;
            for (int j = 0; j < m; j++) {
                nf[1][j] += pre;
                if (i == 0) pre += 1;
                else pre += f[0][j];
            }
            pre = 0;
            for (int j = m - 1; j >= 0; j--) {
                nf[0][j] += pre;
                if (i == 0) pre += 1;
                else pre += f[1][j];
            }
            swap(f, nf);
        }
        return (accumulate(f[0].begin(), f[0].end(), Z(0)) + accumulate(f[1].begin(), f[1].end(), Z(0))).val();
    }
};

力扣每日一题3700-锯齿形数组的总数II

日期：2026-06-24

题意

给定三个正整数 n l 和 r. 表示要构造一个长度为 n, 每个元素取值范围在 [l, r] 的数组, 同时要求满足任意两个相邻元素都不想等且任意三个连续元素不能构成一个严格递增或严格递减的序列. 求问有多少种满足条件的构造法.

思路

和昨日题意完全一样, 只是数据范围导致做法无法一样 3 <= n <= 1e9 && 1 <= l < r <= 75, 但思路还是一样的, 可以注意到昨日的 dp 转移方程可以使用矩阵快速幂来进行优化.

实现

using ll = long long;
const int MOD = 1e9 + 7;

struct Matrix {
    int size;
    std::vector<std::vector<ll>> m;

    Matrix(int n, bool identity = false) : size(n) {
        m.assign(n, std::vector<ll>(n, 0));
        if (identity) {
            for (int i = 0; i < n; i++) m[i][i] = 1;
        }
    }

    Matrix operator*(const Matrix& other) const {
        Matrix result(size);
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (m[i][k] == 0) continue;
                ll val = m[i][k];
                for (int j = 0; j < size; j++) {
                    result.m[i][j] += val * other.m[k][j];
                    if (result.m[i][j] >= 8LL * MOD)
                        result.m[i][j] %= MOD;
                }
            }
        }
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                result.m[i][j] %= MOD;
            }
        }
        return result;
    }

    Matrix pow(ll exp) const {
        Matrix base = *this;
        Matrix result(size, true);
        while (exp > 0) {
            if (exp & 1) result = result * base;
            base = base * base;
            exp >>= 1;
        }
        return result;
    }
};

class Solution {
public:
    int zigZagArrays(int n, int l, int r) {
        int m = r - l;
        Matrix trans(m);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m - i; j++) {
                trans.m[i][j] = 1;
            }
        }

        Matrix mat = trans.pow(n - 2);

        ll ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                ans = (ans + mat.m[i][j] * (m - j) % MOD * 2) % MOD;
            }
        }
        return ans;
    }
};

力扣每日一题3737-统计主要元素子数组数目I

日期：2026-06-25

题意

给定整数数组 nums 与一个整数 target, 求问 target 为出现次数严格大于数组长度一半的子数组的个数.

思路

那可以简单将所有数分为 target 和 非target, 符合题意的子数组则为 ((taget数) - (非target数) > 0) 的子数组. 可以想到是则加一否则减一, 对应子数组区间和大于零. 则可以想到用前缀和维护区间和, 枚举右端点, 用树状数组查询满足条件的左端点个数.

实现

template<class T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int x) : n(x), a(x + 1) {}
    T query(int x) {
        T res = 0;
        while (x) {
            res += a[x];
            x -= (x & -x);
        }
        return res;
    }
    void add(int x, T val) {
        while (x <= n) {
            a[x] += val;
            x += (x & -x);
        }
        return;
    }
};

class Solution {
using ll = long long;
public:
    ll countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        Fenwick<ll> f(2 * n + 10);
        int cur = n + 2;
        ll ans = 0;
        f.add(cur, 1);
        for (auto& x : nums) {
            cur += (x == target ? 1 : -1);
            ans += f.query(cur - 1);
            f.add(cur, 1);
        }
        return ans;
    }
};

力扣每日一题3739-统计主要元素子数组数目II

日期：2026-06-26

题意

给定整数数组 nums 与一个整数 target, 求问 target 为出现次数严格大于数组长度一半的子数组的个数.

思路

和昨日题意一样, 仅数据范围扩大无法暴力. 但我们昨日的思路依旧可行.

实现

template<class T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int x) : n(x), a(x + 1) {}
    T query(int x) {
        T res = 0;
        while (x) {
            res += a[x];
            x -= (x & -x);
        }
        return res;
    }
    void add(int x, T val) {
        while (x <= n) {
            a[x] += val;
            x += (x & -x);
        }
        return;
    }
};

class Solution {
using ll = long long;
public:
    ll countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        Fenwick<ll> f(2 * n + 10);
        int cur = n + 2;
        ll ans = 0;
        f.add(cur, 1);
        for (auto& x : nums) {
            cur += (x == target ? 1 : -1);
            ans += f.query(cur - 1);
            f.add(cur, 1);
        }
        return ans;
    }
};

力扣每日一题3020-子集中元素的最大数量

日期：2026-06-27

题意

给定正整数数组 nums, 求问从中找出任意集合, 可以排列成形如 [x, x^2, x^4..., x^k, x^(k/2)...,x] 数组的最大子集大小.

思路

这个要求就注定数据范围不大, 使用哈希记录各个数出现的次数然后枚举起点 x 即可.

实现

class Solution {
using ll = long long;
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<ll, int> cnt;
        for (auto& x : nums) cnt[x]++;

        int ans = 1;
        if (cnt.count(1)) ans = (cnt[1] - 1) | 1;
        for (auto [x, t] : cnt) {
            if (x == 1) continue;
            int res = 0;
            ll y = x;
            while (cnt.count(y) && cnt[y] >= 2) {
                res += 2;
                y *= y;
            }
            if (cnt.count(y)) res++;
            else res--;
            ans = max(ans, res);
        }
        return ans;
    }
};

力扣每日一题1846-减小和重新排列数组后的最大元素

日期：2026-06-28

题意

给定正整数数组 arr, 每次操作可将其任意重排, 或将任意数替换为小于该数的任意正整数. 任意操作后要求该数组以 1 开始, 任意相邻两数之差绝对值小于等于 1. 求问可得满足条件的数组的最大值.

思路

因为仅能将数调小, 所以不能简单的用数组长度得答案. 但显然将首换为 1, 然后进行一个贪贪的心就好.

实现

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        int n = arr.size();
        ranges::sort(arr);
        arr[0] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1] + 1) {
                arr[i] = arr[i - 1] + 1;
            }
        }
        return arr.back();
    }
};

力扣每日一题1967-作为子字符串出现在单词中的字符串数目

日期：2026-06-29

题意

给定字符串数组 patterns 和一个字符串 word, 问 patterns 中有多少个字符串是 word 的子串.

思路

这题数据范围好小, 就简单的暴力好了. 如果数据范围大些那应该是用 AC自动机.

实现

class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        int ans = 0;
        for (auto& s : patterns) {
            ans += word.contains(s);
        }
        return ans;
    }
};

力扣每日一题1358-包含所有三种字符的子字符串数目

日期：2026-06-30

题意

给定仅含 abc 的字符串 s, 求每个字符至少出现一次的子串个数.

思路

那枚举右端点, 维护满足条件的左端点即可.

实现

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int ans = 0;
        array<int, 3> cnt; cnt.fill(0);
        int t = 0;
        for (int l = 0, r = 0; r < n; r++) {
            if (cnt[s[r] - 'a']++ == 0) t++;
            while (t == 3) {
                ans += n - r;
                if (--cnt[s[l++] - 'a'] == 0) t--;
            }
        }
        return ans;
    }
};