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

目录

力扣每日一题66-加一

日期：2026-01-01

题意

给定整数数组 digit 表示一个大整数的各个数位。令该大整数加 1 ，返回表示结果的数位数组。

思路

那么是一个非常简单的模拟题，模拟一下加法中的进位过程即可。具体的就是在最后一位加上一，然后从低到高位检查每一位是否大于等于 10 ，若是则令该位减 10 然后给下一位进行进位即可。仅需注意最高位若需进位则需让数组多一个元素即可。

实现

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        digits.back() += 1;
        for (int i = n - 1; i > 0; i--) {
            if (digits[i] >= 10) {
                digits[i] -= 10;
                digits[i -  1]++;
            }
        }
        if (digits[0] >= 10) {
            digits[0] -= 10;
            digits.insert(digits.begin(), 1);
        }
        return digits;
    }
};

力扣每日一题961-在长度2N的数组中找出重复N次的元素

日期：2026-01-02

题意

给定偶长的整数数组 nums，其中有 nums.size() / 2 + 1 种元素，有一个元素恰重复了 nums.size() / 2 次，找到这个重复多次的元素。

思路

第一反应答案是绝对众数，那直接上摩尔投票就好。 WA 一发后才想起来摩尔投票要求所求数的出现次数严格大于 ceil(nums.size() / 2)，这里就不太适用了。但是仔细一想，还是可以用的，我们再仔细看看题目，可以注意到有且仅有答案出现了多次，其余数均只出现了一次；我们先排除掉首项，若首项为答案则剩余部分首项一定再出现一次则直接返回首项即可；若首项不为答案，剩余部分就满足了摩尔投票的使用条件。

实现

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n = nums.size();
        int ans = -1, cnt = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums.front()) return nums.front();
            if (cnt == 0) ans = nums[i];
            if (nums[i] == ans) cnt++;
            else cnt--;
        }
        return ans;
    }
};

力扣每日一题1411-给Nx3网格图涂色的方案数

日期：2026-01-03

题意

给定 n * 3 的网格，仅能使用三种不同的颜色，要求每个格子与其相邻的格子颜色不同。求问有多少种涂色方式。

思路

很明显是一个dp的问题，问题是怎么dp呢。

我们先想想若仅有 1 * 3 的网格有多少种涂色方式呢，这里我们用0、1、2分别表示不同的颜色。

010 020 121 101 212 202
012 021 102 120 201 210

显然是仅有以上 12 种情况，同时可以归纳为两种类型 ABA 与 ABC 型，即首尾相同与首尾不同的类型。

在归纳的基础上推导下一行合法的种类，显然一个 ABA 型下一行可以存在 3 个 ABA 型与 2 个 ABC 型；一个 ABC 型下一行可以存在 2 个 ABA 型与 2 个 ABC 型。

由此可以得到每行的递推公式。

实现

class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;
public:
    int numOfWays(int n) {
        ll f = 6, g = 6;
        for (int i = 1; i < n; i++) {
            ll nf = (3 * f + 2 * g) % mod;
            ll ng = (2 * f + 2 * g) % mod;
            f = nf; g = ng;
        }
        return (f + g) % mod;
    }
};

力扣每日一题1390-四因数

日期：2026-01-04

题意

给定正整数数组 nums ，求其中恰有四个因数的整数的所有因素和。

思路

数据范围不是很大 1 <= nums.size() <= 1e4 1 <= nums[i] <= 1e5。那我们可以先预处理出范围内所有数的因子个数，再求出各个数的因子和即可。

实现

static constexpr int N = 1e5;
int fac_cnt[N + 1];
int fac_sum[N + 1];
int init = []() {
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            fac_cnt[j]++;
            fac_sum[j] += i;
        }
    }
    return 0;
} ();

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            if (fac_cnt[x] == 4) ans += fac_sum[x];
        }
        return ans;
    }
};

力扣每日一题1975-最大方阵和

日期：2026-01-05

题意

给定 n * n 的整数方阵 matrix 。每次操作可任选两个相邻元素使它们均乘以 -1。求方阵最大和。

思路

所给图像为方阵，那么任意两个数之间一定存在路径使得除首尾外所有点被选取两次，换言之我们每次可任选两个数使得其正负同时颠倒。贪心地，若负数的个数为偶数个，我们可使得所有负数变为整数，答案即为所有数的绝对值之和；若负数个数为奇数个，我们可令绝对值最小的数为负数，其余数均为正数，再求和即可。/

实现

class Solution {
using ll = long long;
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        ll ans = 0;
        int mn = INT_MAX, fmn = INT_MAX;
        int fcnt = 0;
        for (const auto& m : matrix) {
            for (auto x : m) {
                if (x >= 0) {
                    ans += x;
                    mn = min(mn, x);
                } else {
                    ans -= x;
                    fmn = min(fmn, -x);
                    fcnt++;
                }
            }
        }
        if (fcnt & 1) ans -= min(fmn, mn) << 1;
        return ans;
    }
};

力扣每日一题1161-最大层内元素和

日期：2026-01-06

题意

给定一颗二叉树，求和最大的层号。

思路

很自然想到层序遍历树的每一层以求每层和再进行比较，层序遍历就会先想到 bfs。

实现

/**
 * 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 maxLevelSum(TreeNode* root) {
        if (root == nullptr) return -1;
        
        vector<int> f;
        queue<pair<TreeNode* , int>> q;
        q.emplace(root, 0);
        while (!q.empty()) {
            auto [u, d] = q.front();
            q.pop();
            if (u == nullptr) continue;
            if (d >= f.size()) f.push_back(0);
            f[d] += u->val;
            q.emplace(u->left, d + 1);
            q.emplace(u->right, d + 1);
        }

        int mx = INT_MIN, ans;
        for (int i = 0; i < f.size(); i++) {
            if (mx < f[i]) {
                mx = f[i];
                ans = i;
            }
        }
        return ans + 1;
    }
};

力扣每日一题1339-分裂二叉树的最大乘积

日期：2026-01-07

题意

给定一棵二叉树，删除其中一条边使其变为两棵树，使得两棵树的节点和之积最大，求最大积。

思路

若 v 的父节点为 u ，我们删除边 (u, v)，显然可以得到两部分：v 及其子树、u 所在树除去 v 及其子树；所得乘积即为 v子树和 乘以 整棵树和 - v字数和。由此我们可以想到使用 dfs 求出整个树的和以及各节点子树和即可。

实现

/**
 * 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 {
using ll = long long;
static constexpr int mod = 1e9 + 7;
public:
    int maxProduct(TreeNode* root) {
        ll ans = 0;
        int sum = 0;
        
        auto dfs1 = [&](this auto&& self, TreeNode* u) -> int {
            if (u == nullptr) return 0;
            sum += u->val;
            u->val += self(u->left);
            u->val += self(u->right);
            return u->val;
        };
        dfs1(root);

        auto dfs2 = [&](this auto&& self, TreeNode* u) -> void {
            if (u == nullptr) return;
            ans = max(ans, 1ll * u->val * (sum - u->val));
            self(u->left);
            self(u->right);
        };
        dfs2(root);

        return ans % mod;
    }
};

力扣每日一题1458-两个子序列的最大点积

日期：2026-01-08

题意

给定两个整数数组 nums1 和 nums2 ，返回这两个数组中两个长度相等的非空子序列的最大点积。

思路

比较明显的是 dp，枚举两个数组中各数的乘积加上当前两数之前可得的最大点积。两个数组各数的乘积可以看作一个二维矩阵，其前可得最大点积即为当前位置左上的最大值，可以想到用前缀max维护。

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector f(n + 2, vector<int> (m + 2, -inf));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = max(f[i][j], max(f[i - 1][j - 1], 0) + nums1[i - 1] * nums2[j - 1]);
                f[i][j + 1] = max(f[i][j + 1], f[i][j]);
                f[i + 1][j] = max(f[i + 1][j], f[i][j]);
            }
        }
        return f[n][m];
    }
};

力扣每日一题865-具有所有最深节点的最小子树

日期：2026-01-09

题意

给定一颗二叉树，求包含所有最深结点的最小子树。

思路

换而言之就是求所有最深结点的 LCA。解决树形深度问题，很容易是想到使用 dfs 求深度，同时递归的 归 过程又暗合了 LCA 的性质。

实现

/**
 * 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* subtreeWithAllDeepest(TreeNode* root) {
        int mx = -1;
        TreeNode* ans = nullptr;
        auto dfs = [&](this auto&& self, TreeNode* u, int dep = 0) -> int {
            if (u == nullptr) {
                mx = max(mx, dep - 1);
                return dep - 1;
            }
            int l = self(u->left, dep + 1);
            int r = self(u->right, dep + 1);
            if (l == r && l == mx) {
                ans = u;
            }
            return max(l, r);
        };
        dfs(root);
        return ans;
    }
};

力扣每日一题712-两个字符串的最小ASCII删除和

日期：2026-01-10

题意

给定两个字符串 s1 和 s2 ，可任意删除这两字符串中的字符，求使得两字符串相等所需删除字符的 ASCII 值的最小和。

思路

那么实际就是仅运行删除操作的编辑距离，只是代价转换为了所删除字符的 ASCII 值；或者看作最长公共子序列也是可以的。求最小删除也可以转换为最大保留，就是一个很经典的 dp 问题了。

实现

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        int sum = accumulate(s1.begin(), s1.end(), 0) + accumulate(s2.begin(), s2.end(), 0);
        vector f(n + 1, vector<int> (m + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + int(s1[i - 1]);
                } else {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return sum - f[n][m] * 2;
    }
};

力扣每日一题85-最大矩形

日期：2026-01-11

题意

给定 01 矩阵，找出仅包含 1 的面积最大的矩形的面积。

思路

我们应该有做过类似的题，但我有点想不起来是哪题了。

假如以某行为底，以底向上的连续 1 的个数为高，那么这题就是一个经典的 柱形图最大矩形面积。进行一个枚举中心向两边扩展可得最大面积，即做一个单调栈求每个数前后缀的第一个小于该数的位置即可。

扩展到这个题目，就是枚举每一行，若某位置为 1 则高度加上之前累计，若为 0 则高度清零，然后做上述过程即可。

实现

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix.back().size();
        int ans = 0;
        vector<int> h(m);
        for (const auto& line : matrix) {
            vector<int> pre(m, -1);
            vector<int> stk;
            for (int i = 0; i < m; i++) {
                if (line[i] == '1') h[i]++;
                else h[i] = 0;

                while (!stk.empty() && h[stk.back()] >= h[i]) stk.pop_back();
                if (!stk.empty()) pre[i] = stk.back();
                stk.push_back(i); 
            }
            stk.clear();
            for (int i = m - 1; i >= 0; i--) {
                while (!stk.empty() && h[stk.back()] >= h[i]) stk.pop_back();
                int nxt = stk.empty() ? m : stk.back();
                ans = max(ans, (nxt - pre[i] - 1) * h[i]);
                stk.push_back(i);
            }
        }
        return ans;
    }
};

力扣每日一题1266-访问所有点的最小时间

日期：2026-01-12

题意

给定多个二维点用数组 points 表示，初始位于首个点，每秒可以沿坐标轴方向移动一个单位长度距离或斜向移动 sqrt(2) 个单位长度到相邻点。必须按给定顺序访问这些点，求到达最后一个点最少花费多少时间。

思路

必须按顺序访问，那仅需关注两点之间距离。手玩一下可以发现若两点不在同行或同列，肯定是优先使用斜向距离，最多斜向 min(abs(cur_x - nxt_x), abs(cur_y - nxt_y)) 次，到达同行或同列后沿坐标轴方向移动剩余距离即 max(abs(cur_x - nxt_x), abs(cur_y - nxt_y)) - min(abs(cur_x - nxt_x), abs(cur_y - nxt_y))。所以答案就是两者相加，横纵坐标差的最大值。

实现

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int ans = 0;
        int n = points.size();
        int cx = points[0][0], cy = points[0][1];
        for (int i = 1; i < n; i++) {
            int nx = points[i][0], ny = points[i][1];
            ans += max(abs(nx - cx), abs(ny - cy));
            cx = nx; cy = ny;
        }
        return ans;
    }
};

力扣每日一题3453-分割正方形I

日期：2026-01-13

题意

给定数组 squares 表示多个与坐标轴平行的可能互相重叠的正方形。找到一个最小的纵坐标，使得其对应的水平线使得其上下的图形面积相等（重叠区域重复计数）。

思路

首先想到的是二分，二分水平线的位置然后根据正方形与水平线的位置关系计算某部分面积。只是这里因为面积涉及到浮点数计算，所以我们最好不要使用值域二分而是使用次数二分，主要是因为浮点数的精度误差可能导致答案误差与过多的时间开销。

实现

class Solution {
using ll = long long;
public:
    double separateSquares(vector<vector<int>>& squares) {
        ll sum = 0;
        for (const auto& s : squares) {
            sum += 1ll * s[2] * s[2];
        }
        double m = sum / 2.0;

        auto cal = [&](double h) -> double {
            double res = 0;
            for (const auto& s : squares) {
                int x = s[0], y = s[1], l = s[2];
                if (1.0 * (y + l) <= h) res += 1.0 * l * l;
                else if (1.0 * y >= h) ;
                else res += 1.0 * l * (h - y);
            }
            return res;
        };

        double lo = 0, hi = 1e9;
        int T = 64;
        while (T--) {
            double mid = (lo + hi) / 2;
            if (cal(mid) >= m) hi = mid;
            else lo = mid;
        }
        return lo;
    }
};

力扣每日一题3453-分割正方形II

日期：2026-01-14

题意

给定数组 squares 表示多个与坐标轴平行的可能互相重叠的正方形。找到一个最小的纵坐标，使得其对应的水平线使得其上下的图形面积相等（重叠区域不重复计数）。

思路

与昨天的题目仅仅相差一个字，就是重复区域不再重复计数，但是难度就提升了非常多。因为重叠区域不好计算所以我们不能再使用二分了，只能进行一个扫描线操作。

实现

template<class Info, class Tag>
struct SegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void set(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            set(2 * p, l, m, x, v);
        } else {
            set(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void set(int p, const Info &v) {
        set(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void update(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        update(2 * p, l, m, x, y, v);
        update(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void update(int l, int r, const Tag &v) {
        return update(1, 0, n, l, r, v);    
    }
};

struct Tag {
    int add = 0;
    void apply(Tag t) {
        add += t.add;
    }
};

struct Info {
    int mi = 0;
    int cnt = 0;
    void apply(Tag t) {
        mi += t.add;
    }
};

Info operator+(const Info &a, const Info &b) {
    if (a.mi < b.mi) {
        return a;
    } else if (a.mi > b.mi) {
        return b;
    } else {
        return {a.mi, a.cnt + b.cnt};
    }
}

using S = SegmentTree<Info, Tag>;

class Solution {
using ll = long long;
public:
    double separateSquares(vector<vector<int>>& squares) {
        vector<array<int, 4>> f;
        vector<int> a;
        for (const auto& s : squares) {
            int x = s[0], y = s[1], len = s[2];
            a.push_back(x);
            a.push_back(x + len);
            f.push_back({y, x, x + len, 1});
            f.push_back({y + len, x, x + len, -1});
        }
        ranges::sort(f);
        ranges::sort(a);
        int n = a.erase(unique(a.begin(), a.end()), a.end()) - a.begin();
        int length = a.back() - a.front();

        S StT(n);
        for (int i = 0; i < n - 1; i++) {
            StT.set(i, {0, a[i + 1] - a[i]});
        }

        vector<array<ll, 2>> record;
        ll cur = 0;
        int m = f.size();
        for (int i = 0; i < m - 1; i++) {
            auto [y, tl, tr, t] = f[i];
            int l = ranges::lower_bound(a, tl) - a.begin();
            int r = ranges::lower_bound(a, tr) - a.begin();
            StT.update(l, r, {t});
            auto res = StT.query(0, n);
            int p = res.mi == 0 ? res.cnt : 0;
            record.push_back({cur, length - p});
            cur += 1ll * (length - p) * (f[i + 1][0] - y);
        }

        int lo = ranges::lower_bound(record, cur, {}, [](auto& node) {
            return node[0] * 2;
        }) - record.begin() - 1;
        auto [res, len] = record[lo];
        return f[lo][0] + (cur - res * 2) / (len * 2.0);
    }
};

力扣每日一题2943-最大化网格图中正方形空洞的面积

日期：2026-01-15

题意

给定 n + 2 * m + 2 的网格图，并给定不为最上下左右的横线集合 hBars 与竖线集合 vBars。可任意删除给定集合中的线条，求可得最大中无线条的正方形面积。

思路

显然对于这些线条我们应该能删尽删，求得可行最大边长后再还原回去即可。对于可行最大边长，应为横竖集合中最长连续子段中的较小值，面积即为边长平方。

实现

class Solution {
public:
    int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
        ranges::sort(hBars);
        ranges::sort(vBars);
        auto cal = [](vector<int>& a) -> int {
            int res = 1;
            int n = a.size();
            for (int i = 0; i < n; ) {
                int j = 1;
                for ( ; i + j < n && a[i] + j == a[i + j]; j++);
                res = max(res, j);
                i += j;
            }
            return res;
        };
        int mn = min(cal(vBars), cal(hBars));
        return (mn + 1) * (mn + 1);
    }
};

力扣每日一题2975-移除栅栏得到的正方形田地的最大面积

日期：2026-01-16

题意

给定有边框的 (m - 1) * (n - 1) 矩形田地，其中有横纵栅栏用数组 hFences 与 vFences 表示栅栏的位置。可以任意移除某些栅栏，求可形成的最大正方形田地面积。

思路

要形成正方形，则横纵能空出相同长度的空地，即存在两栅栏差相等。这没有什么技巧吧，这题的数据范围也较小，进行一个暴力枚举记录横纵可能出现的长，取共有最长即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
using ll = long long;
public:
    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        hFences.push_back(1); hFences.push_back(m);
        vFences.push_back(1), vFences.push_back(n);
        ranges::sort(hFences); ranges::sort(vFences);
        int h = hFences.size(), v = vFences.size();
        unordered_set<int> hlen;
        for (int i = 0; i < h; i++)
            for (int j = i + 1; j < h; j++)
                hlen.insert(hFences[j] - hFences[i]);
        
        int mx = 0;
        for (int i = 0; i < v; i++)
            for (int j = i + 1; j < v; j++)
                if (hlen.count(vFences[j] - vFences[i]))
                    mx = max(mx, vFences[j] - vFences[i]);

        if (mx == 0) return -1;
        return 1ll * mx * mx % mod;
    }
};

力扣每日一题3047-求交集区域内的最大正方形面积

日期：2026-01-17

题意

给定二维平面上的多个矩阵，用数组 bottomLeft 与 topRight 分别表示各矩阵的左下角与右上角坐标。求可放入某两矩形交集的最大正方形面积。

思路

数据范围不是很大，最多有 1e3 个不同矩阵，也没什么比较好的方法，进行一个枚举即可。枚举两个矩形的交集，求可放其中的最大正方形，再取最大。

实现

class Solution {
using ll = long long;
public:
    ll largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
        int n = bottomLeft.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int adx = bottomLeft[i][0], ady = bottomLeft[i][1];
            int aux = topRight[i][0], auy = topRight[i][1];
            for (int j = i + 1; j < n; j++) {
                int bdx = bottomLeft[j][0], bdy = bottomLeft[j][1];
                int bux = topRight[j][0], buy = topRight[j][1];
                ans = max(ans, 
                    min(min(aux, bux) - max(adx, bdx), min(auy, buy) - max(ady, bdy))
                );
            }
        }
        return 1ll * ans * ans; 
    }
};

力扣每日一题1895-最大的幻方

日期：2026-01-18

题意

给定 m * n 的矩阵 grid ，求最大的 每一行每一列以及对角线和都相等 的正方形大小。

思路

也没什么特别好的方法，同时数据范围也比较小 1 <= n, m <= 50 ，进行一个暴力验证就好。

实现

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

        auto cal = [&](int x, int y) -> int {
            int res = 0;
            vector<int> c, r;
            for (int len = 1; ; len++) {
                if (x + len > n || y + len > m) break;
                c.push_back(0); r.push_back(0);
                bool ok = true;
                int f = 0, g = 0;
                for (int i = 0; i < len - 1; i++) {
                    r.back() += grid[x + len - 1][y + i];
                    c.back() += grid[x + i][y + len - 1];
                }
                for (int i = 0; i < len; i++) {
                    r[i] += grid[x + i][y + len - 1];
                    c[i] += grid[x + len - 1][y + i];
                    ok &= (r[i] == r[0]) && (c[i] == c[0]);
                    f += grid[x + i][y + i];
                    g += grid[x + i][y + len - 1 - i];
                }
                if (ok && f == g && f == r[0]) res = max(res, len);
            }
            return res;
        };

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = max(ans, cal(i, j));
            }
        }
        return ans;
    }
};

力扣每日一题1292-元素和小于等于阈值的正方形的最大边长

日期：2026-01-19

题意

给定 m * n 的矩阵 mat 与一个整数阈值 threshold 。求最大元素和小于等于 threshold 的正方形边长。

思路

求某个矩形元素和大小，比较自然想到二维前缀和。再枚举求一下最大长即可。

实现

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int n = mat.size(), m = mat.back().size();
        vector pre(n + 1, vector<int> (m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] + mat[i][j] - pre[i][j];
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for ( ; i + ans <= n && j + ans <= m; ans++) {
                    int sum = pre[i + ans][j + ans] - pre[i][j + ans] - pre[i + ans][j] + pre[i][j];
                    if (sum > threshold) break;
                }
            }
        }
        return ans - 1;
    }
};

力扣每日一题3314-构造最小位运算数组I

日期：2026-01-20

题意

给定质数数组 nums，求答案数组 ans 使得对于每一个下标 i 均满足 ans[i] | (ans[i] + 1) == nums[i] ，同时 ans[i] 尽可能小，若无法满足则 ans[i] == -1

思路

x 与 x + 1 一定是一奇一偶，相或则一定是奇数，所以偶数统统无解。而奇数，我们手玩几个数不难发现应转为二进制消去其尾连续 1 的最高位即可。

实现

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        for (auto& x : nums) {
            if (x & 1) {
                for (int i = 1; ; i++) {
                    if (!(x >> i & 1)) {
                        x ^= 1 << (i - 1);
                        break;
                    }
                }
            } else {
                x = -1;
            }
        }
        return nums;
    }
};

力扣每日一题3315-构造最小位运算数组II

日期：2026-01-21

题意

给定质数数组 nums，求答案数组 ans 使得对于每一个下标 i 均满足 ans[i] | (ans[i] + 1) == nums[i] ，同时 ans[i] 尽可能小，若无法满足则 ans[i] == -1

思路

那与 昨天 其实是完全一样的，只是 nums[i] 的取值范围从 1e3 提高到了 1e9 ，也就是卡掉了暴力枚举的做法，但我们的做法是不受影响的。

实现

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        for (auto& x : nums) {
            if (x & 1) {
                for (int i = 1; ; i++) {
                    if (!(x >> i & 1)) {
                        x ^= 1 << (i - 1);
                        break;
                    }
                }
            } else {
                x = -1;
            }
        }
        return nums;
    }
};

力扣每日一题3507-移除最小数对使数组有序I

日期：2026-01-22

题意

给定数组 nums ，每次操作将选择最左 相邻元素对和最小的的一对 删除，在原位置加入它们的和。求令该数组变为非递减最小的操作次数。

思路

我们选择维护 相邻元素和及其位置 当前剩余元素位置及其大小 相邻且递减的元素个数，模拟删除操作即可。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
public:
    int minimumPairRemoval(vector<int>& nums) {
        int n = nums.size();
        set<array<ll, 2>> sum;
        set<array<ll, 2>> index{{0, nums[0]}};
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            index.insert({i, nums[i]});
            sum.insert({nums[i] + nums[i - 1], i - 1});
            cnt += nums[i - 1] > nums[i];
        }

        int ans = 0;
        while (cnt) {
            ans++;
            auto [s, cur] = *sum.begin();
            sum.erase(sum.begin());

            auto it = index.lower_bound({cur, -inf});
            auto nxt = next(it);
            auto [it0, it1] = *it;
            auto [nxt0, nxt1] = *nxt;
            cnt -= it1 > nxt1;

            if (it != index.begin()) {
                auto [itt0 ,itt1] = *prev(it);
                cnt -= itt1 > it1;
                cnt += itt1 > s;
                sum.erase({itt1 + it1, itt0});
                sum.insert({itt1 + s, itt0});
            }
            auto itt = next(nxt);
            if (itt != index.end()) {
                auto [itt0, itt1] = *itt;
                cnt -= nxt1 > itt1;
                cnt += s > itt1;
                sum.erase({nxt1 + itt1, nxt0});
                sum.insert({s + itt1, it0});
            }

            index.erase(it);
            index.erase(nxt);
            index.insert({it0, s});
        }
        return ans;
    }
};

力扣每日一题3510-移除最小数对使数组有序II

日期：2026-01-23

题意

给定数组 nums ，每次操作将选择最左 相邻元素对和最小的的一对 删除，在原位置加入它们的和。求令该数组变为非递减最小的操作次数。

思路

题目与昨天是完全一样的，只是数据范围进行了扩大，数组大小从 50 扩大到了 1e5，也就是卡掉了暴力。但为我们 昨日的做法 是没有问题的。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
public:
    int minimumPairRemoval(vector<int>& nums) {
        int n = nums.size();
        set<array<ll, 2>> sum;
        set<array<ll, 2>> index{{0, nums[0]}};
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            index.insert({i, nums[i]});
            sum.insert({nums[i] + nums[i - 1], i - 1});
            cnt += nums[i - 1] > nums[i];
        }

        int ans = 0;
        while (cnt) {
            ans++;
            auto [s, cur] = *sum.begin();
            sum.erase(sum.begin());

            auto it = index.lower_bound({cur, -inf});
            auto nxt = next(it);
            auto [it0, it1] = *it;
            auto [nxt0, nxt1] = *nxt;
            cnt -= it1 > nxt1;

            if (it != index.begin()) {
                auto [itt0 ,itt1] = *prev(it);
                cnt -= itt1 > it1;
                cnt += itt1 > s;
                sum.erase({itt1 + it1, itt0});
                sum.insert({itt1 + s, itt0});
            }
            auto itt = next(nxt);
            if (itt != index.end()) {
                auto [itt0, itt1] = *itt;
                cnt -= nxt1 > itt1;
                cnt += s > itt1;
                sum.erase({nxt1 + itt1, nxt0});
                sum.insert({s + itt1, it0});
            }

            index.erase(it);
            index.erase(nxt);
            index.insert({it0, s});
        }
        return ans;
    }
};

力扣每日一题1877-数组中最大数对和的最小值

日期：2026-01-24

题意

给定偶长的整数数组 nums ，将其两两配对，使得最大数对和最小。

思路

最大与最小、次大与次小…这样的贪心是比较符合直觉的。证明也并不难，因为最大数若不与最小数配对，其和一定大于最大与最小和。

实现

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        int ans = 0;
        ranges::sort(nums);
        int n = nums.size();
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            ans = max(ans, nums[l] + nums[r]);
        }
        return ans;
    }
};

力扣每日一题1984-学生分数的最小差值

日期：2026-01-25

题意

给定整数数组 nums 表示多个学生的成绩，从中任选出 k 个学生，使得这几个学生中成绩最高与最低分差值最小化，求该最小差。

思路

所选择的学生应该是排序后连续的 k 个，因为若不连续则其差值一定更大。故排序后枚举首尾即可。

实现

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        ranges::sort(nums);
        int ans = INT_MAX;
        for (int i = 0, j = k - 1; j < n; i++, j++) {
            ans = min(ans, nums[j] - nums[i]);
        }
        return ans;
    }
};

力扣每日一题1200-最小绝对差

日期：2026-01-26

题意

给定各不相同的整数数组 arr ，找出所有最小绝对差的元素对，升序返回。

思路

绝对差最小一定出现在排序后的相邻元素，因为排序后相邻元素之绝对差一定小于非相邻元素。故排序后遍历找最小，并记录对应数对即可。

实现

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        vector<vector<int>> ans;
        int mn = INT_MAX;
        int n = arr.size();
        ranges::sort(arr);
        for (int i = 1; i < n; i++) {
            int diff = arr[i] - arr[i - 1];
            if (mn > diff) {
                ans = {{arr[i - 1], arr[i]}};
                mn = diff;
            } else if (mn == diff) {
                ans.push_back({arr[i - 1], arr[i]});
            }
        }
        return ans;
    }
};

力扣每日一题3650-边反转的最小路径总成本

日期：2026-01-27

题意

给定一个边有向且带权的图，权值表示为过该边的代价。同时每个节点有一个一次性开关，可用于单次地反转某条边，经过反转的边代价翻倍。问从第一个点到最后一个点所需最小代价。

思路

最短路首先想到的是迪杰斯特拉，不太一样的是我们每个结点有一个一次性反向的开关。但仔细一想，这其实是不影响的，我们每个点最多是访问一次的，开关的使用限制并不影响决策。因此我们只是多了一些双倍代价的反向边而已。

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int minCost(int n, vector<vector<int>>& edges) {
        vector<vector<array<int, 2>>> e(n);
        for (const auto& vec : edges) {
            int u = vec[0], v = vec[1], w = vec[2];
            e[u].push_back({v, w});
            e[v].push_back({u, 2 * w});
        }

        vector dis(n, inf);
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto [cost, u] = pq.top();
            pq.pop();
            if (dis[u] <= cost) continue;
            dis[u] = cost;
            for (const auto& [v, w] : e[u]) {
                if (cost + w >= dis[v]) continue;
                pq.push({cost + w, v});
            }
        }
        int ans = dis[n - 1];
        if (ans == inf) return -1;
        return ans;
    }
};

力扣每日一题3651-带传送的最小路径成本

日期：2026-01-28

题意

给定 m * n 的矩阵 grid 。有两种移动方式，一种为向左或向下移动到相邻格，代价为目标格子的值；另一种为传送至任意值小于等于当前位置的单元格，代价为 0，但至多传送 k 次。求从左上角到右下角所需最小代价。

思路

走格子最小代价，很自然想到使用 dp，但这里多了一个传送操作。我们观察数据范围 2 <= n, m <= 80 && 0 <= k <= 10 ，这个数据范围是不大的，但搜也是不行的。但我们想到若第 i 次传送到值为 x 的格子，那么一定是来自于第 i - 1 次传送且值大于等于 x 的格子，可以想到使用一个后缀 min 维护传送最小代价，跑 k 次 dp 即可。

实现

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        const int n = grid.size(), m = grid.front().size();
        const int inf = 1e9;

        int mx = 0;
        for (const auto& vec : grid) mx = max(mx, ranges::max(vec));
        vector ump(k + 1, vector<int> (mx + 1, inf));

        vector f(k + 1, vector (n, vector<int> (m, inf)));
        f[0][0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i && j) f[0][i][j] = min(f[0][i - 1][j], f[0][i][j - 1]) + grid[i][j];
                else if (i) f[0][i][j] = f[0][i - 1][j] + grid[i][j];
                else if (j) f[0][i][j] = f[0][i][j - 1] + grid[i][j];
                ump[0][grid[i][j]] = min(ump[0][grid[i][j]], f[0][i][j]);
            }
        }

        for (int t = 1; t <= k; t++) {
            for (int i = mx - 1; i >= 0; i--) {
                ump[t - 1][i] = min(ump[t - 1][i], ump[t - 1][i + 1]);
            }
            for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                f[t][i][j] = min(f[t][i][j], ump[t - 1][grid[i][j]]);
            }
            
            for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (i && j) f[t][i][j] = min(f[t][i][j], min(f[t][i - 1][j], f[t][i][j - 1]) + grid[i][j]);
                else if (i) f[t][i][j] = min(f[t][i][j], f[t][i - 1][j] + grid[i][j]);
                else if (j) f[t][i][j] = min(f[t][i][j], f[t][i][j - 1] + grid[i][j]);
                ump[t][grid[i][j]] = min(ump[t][grid[i][j]], f[t][i][j]);
            }
        }
        
        int ans = inf;
        for (int t = 0; t <= k; t++) {
            ans = min(ans, f[t][n - 1][m - 1]);
        }
        return ans;
    }
};

力扣每日一题2976-转换字符串的最小成本I

日期：2026-01-29

题意

给定等长小写字母字符串 source 和 target ，以及两个等长小写字符数组 original 和 changed 与一个与这两字符数组等长的整数数组 cost。对于任意 source 中字符若存在 ch=original[i] 则可令该字符花费代价 cost[i] 变为 changed[i] 。求令 source 变为 target 所需的最小代价。

思路

可以首先处理出不同字符互相转换所需的最小代价，也就是一个 26 * 26 的最短路。对于全员最短路就可以用 Floyd 算法进行处理，得到各最小代价后遍历求和即可。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
static constexpr int N = 26;
public:
    ll minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        vector e(N, vector<ll> (N, inf));
        for (int i = 0; i < N; i++) e[i][i] = 0;
        int n = source.size(), m = original.size();
        for (int i = 0; i < m; i++) {
            ll& x = e[original[i] - 'a'][changed[i] - 'a'];
            x = min(x, 1ll * cost[i]);
        }

        for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
        
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            ll c = e[source[i] - 'a'][target[i] - 'a'];
            if (c == inf) return -1;
            ans += c;
        }
        return ans;
    }
};

力扣每日一题2977-转换字符串的最小成本II

日期：2026-01-30

题意

给定两小写字母字符串 source 和 target ，以及两个等长小写字母字符串数组 original 和 changed ，以及一个与这两字符串数组等长的整数数组 cost 。其中 cost[i] 表示将字符串 original[i] 改为 changed[i] 的代价。每次操作可任选 source 中的子串进行修改操作，但任意操作的范围要么相同要么互不相交。求将 source 转为 target 所需的最小代价。

思路

和昨天题目非常类似但难度又非常不同。昨天单次修改为单字符，今天为修改子串，但好在限制了每次修改的子串要么相同要么互不相交。

那么显然是要将原字符串分割为多个子串，分别进行修改操作求最小代价，那应该是进行一个 记搜 或 dp。

进行分割后不同的字符串之间互相转换的最小代价就与昨天类似，是一个全源最短路，使用 Floyd 即可。

剩下的问题就是如何处理分割字符串，首先想到是使用哈希，根据长度进行分组再转 Floyd，但后续 dp 操作时每增加一个字符就要哈希一次所需代价还是较大的，要么我们自行实现字符串哈希使其可以做到尾加字符时 O(1) 地计算哈希值，要么使用更高效的方法。那就可以想到使用字典树进行处理。

实现

static constexpr int N = 26;
static constexpr int M = 5e5;
static int tot = 1, num = 0;
static array<int, N + 1> trie[M];
static void _clear(int x) {
    trie[x].fill(0);
}
static void _init() {
    num = 0;
    tot = 1;
    _clear(tot);
}
static int _add(const string& s) {
    int u = 1;
    for (const auto& ch : s) {
        int& v = trie[u][ch - 'a'];
        if (v == 0) {
            v = ++tot;
            _clear(v);
        }
        u = v;
    }
    if (trie[u][N] == 0) trie[u][N] = ++num;
    return trie[u][N];
}
static int _nxt(int u, char ch) {
    return trie[u][ch - 'a'];
}

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
public:
    ll minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
        _init();
        int n = source.size(), m = original.size();
        vector<int> oid(m), cid(m);
        for (int i = 0; i < m; i++) {
            oid[i] = _add(original[i]);
            cid[i] = _add(changed[i]);
        }

        vector dis(num + 1, vector<ll> (num + 1, inf));
        for (int i = 1; i <= num; i++) dis[i][i] = 0;
        for (int i = 0; i < m; i++) {
            ll& x = dis[oid[i]][cid[i]];
            x = min(x, 1ll * cost[i]);
        }
        for (int k = 1; k <= num; k++) {
            for (int i = 1; i <= num; i++) {
                if (dis[i][k] == inf) continue;
                for (int j = 1; j <= num; j++) {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }

        vector<ll> f(n + 1, inf);
        f[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (source[i] == target[i]) f[i] = f[i + 1];
            int x = 1, y = 1;
            for (int j = i; j < n; j++) {
                x = _nxt(x, source[j]);
                y = _nxt(y, target[j]);
                if (x == 0 || y == 0) break;
                if (trie[x][N] == 0 || trie[y][N] == 0) continue;
                f[i] = min(f[i], f[j + 1] + dis[trie[x][N]][trie[y][N]]);
            }
        }
        if (f[0] == inf) return -1;
        return f[0];
    }
};

力扣每日一题744-寻找比目标字母大的最小字母

日期：2026-01-31

题意

给定非递减字符数组 letters，找出 letters 中大于字符 target 的最小字符。

思路

数组已经排序，那么直接进行一个二分就好。

实现

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        auto it = ranges::upper_bound(letters, target);
        return it == letters.end() ? letters.front() : *it;
    }
};