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

目录

力扣每日一题1689-十-二进制数的最少数目

日期：2026-03-01

题意

若一个十进制数每位仅为零或一且无前导零，则称其为 十-二进制数 ，给定一个字符串 n 表示一个十进制数，求问最少需要几个十-二进制数可加和为 n 。

思路

一个十-二进制数最多使得 n 某位减一，最少减零。那显然仅需使用最大位数的大小个即可。

实现

class Solution {
public:
    int minPartitions(string n) {
        return ranges::max(n) - '0';
    }
};

力扣每日一题1536-排布二进制网格的最少交换次数

日期：2026-03-02

题意

给定 n * n 的二进制方格，每次操作可以交换任意相邻两行，问是否可以让该方格主对角线以上均为 0，若可以问所需最少操作次数。

思路

显然是一个平方的贪心：若当前行不满足找最近的满足的行进行交换，交换操作类似冒泡排序。

实现

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> p(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    p[i] = n - 1 - j;
                    break;
                }
            }
        }

        int ans = 0;
        for (int i = 0, need = n - 1; i < n; i++, need--) {
            int j = i;
            for ( ; j < n && p[j] < need; j++);
            if (j == n) return -1;
            ans += j - i;
            for (int k = j; k > i; k--) p[k] = p[k - 1];
        }
        return ans;
    }
};

力扣每日一题1545-找出第N个二进制字符串中的第K位

日期：2026-03-03

题意

S_1 = "0"，当 i > 1 时 S_i = S_{i - 1} + "1" + reverse(invert(S_{i-1}))。给定正整数 n 和 k ，求 S_n 的第 k 个字符。

思路

应该是有见过很多次类似的题了。

可以考虑反向模拟，若 k 位于前半截显然无需处理，若处于后半截应沿后半截中点镜像并进行反转还原到前一个字符串，重复操作直到回到开始，记录反转次数即可得到答案。

实现

class Solution {
public:
    char findKthBit(int n, int k) {
        int len = (1 << n) - 1;
        bool t = false;
        while (k != 1) {
            len >>= 1;
            if (k == len + 1) return t ? '0' : '1';
            else if (k > len + 1) {
                t = !t;
                k = len + 1 - (k - len - 1);
            }
        }
        return t ? '1' : '0';
    }
};

力扣每日一题1582-二进制矩阵中的特殊位置

日期：2026-03-04

题意

给定 m * n 二进制矩阵 mat ，若某个位置为 1 且该位置所在行与列有且仅有该位置为 1 ，则称其特殊。求 mat 中特殊位置的个数。

思路

数据范围并不大，怎么写都是可以的。这里我是一开始读错了题，就干脆顺着写做了一些优化：记录当前行列状况以减少理论检查次数。但实际复杂度量级是一致的。

实现

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int ans = 0;
        int n = mat.size(), m = mat.back().size();
        vector<bool> p(m);
        for (int i = 0; i < n; i++) {
            bool t = false;
            for (int j = 0; j < m; j++) {
                if (mat[i][j]) {
                    if (!t && !p[j]) {
                        bool ok = true;
                        for (int k = i + 1; k < n && ok; k++) ok &= mat[k][j] == 0;
                        for (int k = j + 1; k < m && ok; k++) ok &= mat[i][k] == 0;
                        ans += ok;
                    }
                    t = p[j] = true;
                }
            }
        }
        return ans;
    }
};

力扣每日一题1758-生成交替二进制字符串的最少操作数

日期：2026-03-05

题意

给定二进制字符串 s。每步操作可任选一个字符翻转，求问使得该字符串不存在相邻相同字符所需要的最少操作次数。

思路

无相邻且相同的二进制字符串，那么有且仅有两种可能：一种以 0 开头一种以 1 开头。同时变为两者的操作次数之和为字符串长度。选择一种进行模拟，然后去较小值即可。

实现

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

力扣每日一题1784-检查二进制字符串字段

日期：2026-03-06

题意

给定二进制字符串 s ，判断其中连续 1 子段的个数是否小于两个。

思路

简单求一下连续 1 子段即可。

实现

class Solution {
public:
    bool checkOnesSegment(string s) {
        int n = s.size();
        int cnt = 0;
        for (int i = 0, j = 0; i < n; i = max(j, i + 1)) {
            if (s[i] == '0') continue;
            cnt++;
            for (j = i; j < n && s[j] == '1'; j++);
        }
        return cnt < 2;
    }
};

力扣每日一题1888-使二进制字符串字符交替的最少反转次数

日期：2026-03-07

题意

给定二进制字符串 s，有以下两种操作：

  • 删除 s 首字符并将其添加到 s 尾
  • 选择 s 中任意字符翻转

求最少需要多少次操作二可使得 s 变为交替字符。

思路

首先不考虑操作一，那么题目就变为了昨天的题目，有且仅有两种结果字符串，模拟两种可能所需操作即可。

再考虑操作一，实际上就是进行任意次循环左移，同时该操作不计入代价，那实际即为所有循环左移后的最小总操作。

注意到若字符串为偶长，无论怎么左移结果都是一致的。

若为奇长，可将被左移的部分与剩余部分视作两段不同起点的交替字符串，可以想到使用一个前缀和进行优化。

实现

class Solution {
public:
    int minFlips(string s) {
        int n = s.size();
        vector <int> f(n + 1), g(n + 1);
        for (int i = 0; i < n; i++) {
            f[i + 1] = f[i] + ((i & 1) ^ (s[i] == '1'));
            g[i + 1] = i + 1 - f[i + 1];
        }
        if ((n & 1) == 0) return min(f.back(), g.back());
        int ans = n;
        for (int i = 0; i < n; i++) {
            ans = min({ans, f[i] + g[n] - g[i], g[i] + f[n] - f[i]});
        }
        return ans;
    }
};

力扣每日一题1980-找出不同的二进制字符串

日期：2026-03-08

题意

给定字符串数组 nums，内有 n 个长均为 n 的二进制数组。找出任一长度为 n 且未出现过的二进制字符串。

思路

开个集合或开个哈希找一下即可。

实现

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        vector<bool> vis(1 << n);
        for (const auto& s : nums) {
            vis[stoi(s, nullptr, 2)] = true;
        }
        for (int i = 0; i < (1 << n); i++) {
            if (!vis[i]) {
                string ans;
                for (int k = n - 1; k >= 0; k--) {
                    if (i >> k & 1) ans += '1';
                    else ans += '0';
                }
                return ans;
            }
        }
        return "";
    }
};

力扣每日一题3129-找出所有稳定的二进制数组I

日期：2026-03-09

题意

给定三个正整数 zero, one 和 limit ，求满足以下条件的二进制数组有多少个：

  • 0 的个数恰好为 zero 个
  • 1 的个数恰好为 one 个
  • 每个长度超过 limit 的子数组都同时包含 01

思路

我们首先不考虑最后一个条件，很显然是一个非常简单的 dp，以 x 为结尾的数组可由 x 与 1 - x 结尾的数组得来。

再考虑最后一个条件，超过 limit 的子数组均包含 01，即 01 最多连续出现 limit 个。

那么每个状态要减去 x 个数少 limit + 1 个同时以 1 - x 结尾的状态。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        vector f(2, vector (zero + 1, vector<int> (one + 1)));
        for (int i = 1, j = min(zero, limit); i <= j; i++) f[0][i][0] = 1;
        for (int i = 1, j = min(one, limit); i <= j; i++) f[1][0][i] = 1;
        auto cal = [&](int& x) -> void {
            if (x >= mod) x -= mod;
        };

        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                int& x = f[0][i][j];
                x = f[0][i - 1][j] + f[1][i - 1][j];
                cal(x);
                if (i > limit) x -= f[1][i - limit - 1][j] - mod;
                cal(x); 

                int& y = f[1][i][j];
                y = f[0][i][j - 1] + f[1][i][j - 1];
                cal(y);
                if (j > limit) y -= f[0][i][j - limit - 1] - mod;
                cal(y);
            }
        }
        int res = f[0][zero][one] + f[1][zero][one];
        cal(res);
        return res;
    }
};

力扣每日一题3130-找出所有稳定的二进制数组II

日期：2026-03-10

题意

给定三个正整数 zero, one 和 limit ，求满足以下条件的二进制数组有多少个：

  • 0 的个数恰好为 zero 个
  • 1 的个数恰好为 one 个
  • 每个长度超过 limit 的子数组都同时包含 01

思路

与昨天的题目是完全一致的，只是数据范围进行了扩大，但我们的思路是 O(one * zero) 的，在今天的复杂度依旧可行，就不过多赘述了。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        vector f(2, vector (zero + 1, vector<int> (one + 1)));
        for (int i = 1, j = min(zero, limit); i <= j; i++) f[0][i][0] = 1;
        for (int i = 1, j = min(one, limit); i <= j; i++) f[1][0][i] = 1;
        auto cal = [&](int& x) -> void {
            if (x >= mod) x -= mod;
        };

        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                int& x = f[0][i][j];
                x = f[0][i - 1][j] + f[1][i - 1][j];
                cal(x);
                if (i > limit) x -= f[1][i - limit - 1][j] - mod;
                cal(x); 

                int& y = f[1][i][j];
                y = f[0][i][j - 1] + f[1][i][j - 1];
                cal(y);
                if (j > limit) y -= f[0][i][j - limit - 1] - mod;
                cal(y);
            }
        }
        int res = f[0][zero][one] + f[1][zero][one];
        cal(res);
        return res;
    }
};

力扣每日一题1009-十进制整数的反码

日期：2026-03-11

题意

给定非负整数 n，返回其无前导零二进制表示下 01 反转后表示的十进制数。

思路

不难发现该数与该数反转相异或结果二进制表示为等长的全 1，再由异或性质即可得到答案。

实现

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) return 1;
        return ((1 << (__lg(n) + 1)) - 1) ^ n;
    }
};

力扣每日一题3600-升级后最大生成树稳定性

日期：2026-03-12

题意

给定一个有 n 个结点无向图，已有边用数组 edges_i = [u_i, v_i, s_i, must_i] 表示，其中 u v 分别表示改变的两个结点，s 表示改边的强度，must 若为 1 则该边必选且无法增强反之则可最多升级一次。同时允许你最多使得 k 条边强度翻倍。

定义一个树的稳定性为该树最小强度的边的强度。求该图可得的稳定性最大的生成树。

思路

先不考虑增强操作，显然就是一个先将必选边选上后的最大生成树，这个大家应该都有学过，从大到小将边加入生成树即可。

再考虑增强操作，显然应该基于最大生成树做，不然最小值必定更小。同时应该从最小的边开始进行增强操作。

使用并查集记录点间关系，然后记录必选边最小，自选边最小，以及自选边未能增强最小，进行比较即可。

实现

struct DSU {
	vector<int> fa;

	DSU() {}
	DSU(int n) {
		init(n);
	}

	void init(int n) {
		fa.resize(n);
		iota(fa.begin(), fa.end(), 0);
	}

	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;
		fa[y] = x;
		return true;
	}
};

class Solution {
public:
    int maxStability(int n, vector<vector<int>>& edges, int k) {
        DSU dsu(n);
        vector<int> p, t;
        int ans = INT_MAX, cnt = n - 1;
        int m = edges.size();
        for (int i = 0; i < m; i++) {
            auto& e = edges[i];
            int u = e[0], v = e[1], s = e[2], m = e[3];
            if (m) {
                if (!dsu.merge(u, v)) return -1;
                ans = min(ans, s);
                cnt--;
            } else {
                p.push_back(i);
            }
        }
        if (cnt == 0) return ans;

        ranges::sort(p, [&](const int&x, const int& y) {
            return edges[x][2] > edges[y][2];
        });
        for (int i = 0; i < p.size() && cnt; i++) {
            auto& e = edges[p[i]];
            int u = e[0], v = e[1], s = e[2];
            if (dsu.merge(u, v)) {
                cnt--;
                t.push_back(s);
            }
        }

        if (cnt > 0) return -1;
        if (k >= t.size()) return min(ans, t.back() << 1);

        return min({ans, t[t.size() - k - 1], t.back() << 1});
    }
};

力扣每日一题3296-移山所需的最少秒数

日期：2026-03-13

题意

给定数组 workerTimes 表示多名工人的工作时间，具体的第 i 名工人使山降低的第 x 米需要花费 workerTimes[i] + workerTime[i] * 2 + ... workerTimes[i] * x 秒。同时有山高 mountainHeight ，问使得山高归零所需最少秒数。

思路

数据范围不很大 mountainHeight <= 1e5，咱们直接开个优先队列，每次选出花费最小的工人即可。

实现

class Solution {
using ll = long long;
public:
    ll minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> pq;
        for (auto& x : workerTimes) {
            pq.push({x, x, x});
        }

        ll ans = 0;
        while (mountainHeight) {
            auto [t, c, x] = pq.top();
            pq.pop();
            ans = t;
            pq.push({t + c + x, c + x, x});
            mountainHeight--;
        }
        return ans;
    }
};

力扣每日一题1415-长度为n的开心字符串中字典序第k小的字符串

日期：2026-03-14

题意

若一个字符串仅含 [‘a’, ‘b’, ‘c’] 且相邻字符均不相同则称其为开心字符串。求长度为 n 的第 k 大的开心字符串。

思路

数据范围实在不大 1 <= n <= 10, 1 <= k <= 100，那直接简单问题简单做，写个深搜就好了。

实现

class Solution {
public:
    string getHappyString(int n, int k) {
        if (k > 3 * (1 << n - 1)) return "";
        string ans;
        bool ok = false;
        auto dfs = [&](this auto&& self, int i, char last) -> void {
            if (i == n) {
                if (--k == 0) ok = true;
                return;
            }
            for (auto ch : {'a', 'b', 'c'}) {
                if (ch == last) continue;
                ans += ch;
                self(i + 1, ch);
                if (ok) return;
                ans.pop_back();
            }
        };
        dfs(0, '-');

        return ans;
    }
};

力扣每日一题1622-奇妙序列奇妙序列

日期：2026-03-15

题意

要求实现一个数据结构，包含以下功能：

  • 在序列尾新增一个数
  • 将当前序列中的所有数乘以指定值
  • 将当前序列中的所有数乘以指定值
  • 查询序列指定下标的值

思路

数据范围比较大，显然是不太能直接进行模拟的。可以发现我们需要的操作为区间改与单点查，显然可以直接用带懒标记的线段树作答，但仅有单点查的情况下不太有必要，我们仅需考虑带懒标记的数组模拟即可。

我们可以将每个位置的数实际值视作 ax + b，其中 x 为记录值， a 与 b 为操作二三的影响。显然操作二三时仅需对 a 与 b 进行相应处理即可，操作四取出记录值进行计算即可。操作一我们仅需进行逆操作存储 (val - b) / a 即可。

实现

class Fancy {
using ll = long long;
static constexpr ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
};

vector<int> p;
ll add, mul;

public:
    Fancy() {
        add = 0;
        mul = 1;
    }
    
    void append(int val) {
        p.push_back((val - add + mod) % mod * qpow(mul, mod - 2) % mod);
    }
    
    void addAll(int inc) {
        add = (add + inc) % mod;
    }
    
    void multAll(int m) {
        add = add * m % mod;
        mul = mul * m % mod;
    }
    
    int getIndex(int idx) {
        if (idx >= p.size()) return -1;
        return (p[idx] * mul % mod + add) % mod;
    }
};

/**
 * Your Fancy object will be instantiated and called as such:
 * Fancy* obj = new Fancy();
 * obj->append(val);
 * obj->addAll(inc);
 * obj->multAll(m);
 * int param_4 = obj->getIndex(idx);
 */

力扣每日一题1878-矩阵中最大的三个菱形和

日期：2026-03-16

题意

给定 m * n 的正整数矩阵 grid 。求矩阵中三个最大且互不相同的正棱形边界上的元素和。

思路

没有想到啥特别好的方法，就是做一个斜向的前缀和，然后枚举最下边的点以及棱形的边长。

实现

class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid.back().size();
        vector l2d(n + 10, vector<int> (m + 10));
        auto r2d = l2d;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                l2d[i + 1][j + 1] = l2d[i][j] + grid[i][j];
                r2d[i + 1][j] = r2d[i][j + 1] + grid[i][j];
            }
        }

        int fi = 0, se = 0, th = 0;
        auto cal = [&](int x, int y, int len) -> void {
            int a0 = x - 2 * len, b0 = y;
            int a1 = x - len, b1 = y - len;
            int a2 = x - len, b2 = y + len;
            int a3 = x, b3 = y;
            int res = (l2d[a3][b3] - l2d[a1][b1])
                    + (r2d[a3 + 1][b3] - r2d[a2 + 1][b2])
                    + (r2d[a1 + 1][b1] - r2d[a0 + 1][b0])
                    + (l2d[a2 + 1][b2 + 1] - l2d[a0 + 1][b0 + 1])
                    + grid[a0][b0] - grid[a1][b1];
            if (len == 0) res = grid[x][y];
            if (res > fi) {
                th = se;
                se = fi;
                fi = res;
            } else if (res < fi && res > se) {
                th = se;
                se = res;
            } else if (res < se && res > th) {
                th = res;
            }
        };

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; i - 2 * k >= 0 && j - k >= 0 && j + k < m; k++) {
                    cal(i, j, k);
                }
            }
        }

        vector<int> ans{fi, se, th};
        while (!ans.empty() && ans.back() == 0) ans.pop_back();
        return ans;
    }
};

力扣每日一题1727-重新排列后的最大子矩阵

日期：2026-03-17

题意

给定二进制矩阵 matrix ，可将其的列按任意顺序排列，求全 1 最大子矩阵的面积。

思路

首先不考虑重排的情况，我印象中类似的题我们有写过至少两次了，显然应该是枚举底边同时维护每一列的最大连续 1 高度即可。加入排序操作显然应该是按大小排列后枚举高度同时底边尽可能取长。

实现

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix.back().size();
        vector<int> f(m), p(m);
        ranges::iota(p, 0);
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j]) f[j]++;
                else f[j] = 0;
            }
            ranges::sort(p, [&](const int& x, const int& y) {
                return f[x] > f[y];
            });
            for (int j = 0; j < m; j++) {
                ans = max(ans, (j + 1) * f[p[j]]);
            }
        }

        return ans;
    }
};

力扣每日一题3070-元素和小于等于 k 的子矩阵的数目

日期：2026-03-18

题意

给定非负整数矩阵 grid 与一个整数 k 。求有多少个包含 grid 左上角元素且元素和小于等于 k 的子矩阵。

思路

那就是一个裸的二维前缀和，做前缀和的同时判断一下大小即可。

实现

class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid.back().size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i && j) grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
                else if (i) grid[i][j] += grid[i - 1][j];
                else if (j) grid[i][j] += grid[i][j - 1];
                if (grid[i][j] <= k) ans++;
                else break;                
            }
        }
        return ans;
    }
};

力扣每日一题3212-统计X和Y频数相等的子矩阵数量

日期：2026-03-19

题意

给定字符矩阵 grid ，其中每个格子可能值为 {'X', 'Y', '.'} ，求包含左上角格且 X Y 出现次数相同 同时至少包含一个 X 的子矩阵个数。

思路

那也是可以使用二维前缀和做的，XY 其一看作 +1 另一看作 -1，出现次数相同即前缀和为 0。再额外维护以下 X 是否出现过即可。

实现

class Solution {
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid.back().size();
        vector f(n, vector<int> (m));
        vector g(n, vector<int> (m));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i && j) {
                    f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
                    g[i][j] = g[i - 1][j] | g[i][j - 1];
                } else if (i) {
                    f[i][j] = f[i - 1][j];
                    g[i][j] = g[i - 1][j];
                } else if (j) {
                    f[i][j] = f[i][j - 1];
                    g[i][j] = g[i][j - 1];
                }
                if (grid[i][j] == 'X') f[i][j]++;
                else if (grid[i][j] == 'Y') f[i][j]--;
                g[i][j] |= (grid[i][j] == 'X');
                ans += (g[i][j] && f[i][j] == 0);
            }
        }
        return ans;
    }
};

力扣每日一题3567-子矩阵的最小绝对差

日期：2026-03-20

题意

给定二维整数矩阵 grid 与一个正整数 k 。求 grid 中每个 k * k 的子矩阵中任意两不同值之间的最小绝对差值。

思路

没有什么特别好的方法吧，只能枚举每个子矩阵再对其内所有元素进行排序，相邻不同元素做差取最小。

实现

class Solution {
static constexpr int inf = 1e9;
public:
    vector<vector<int>> minAbsDiff(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid.back().size();
        vector ans(n - k + 1, vector<int> (m - k + 1));
        for (int i = n - k; i >= 0; i--) {
            for (int j = m - k; j >= 0; j--) {
                vector<int> t;
                int res = inf;
                for (int x = 0; x < k; x++)
                    for (int y = 0; y < k; y++)
                        t.push_back(grid[i + x][j + y]);
                ranges::sort(t);
                for (int i = 1; i < t.size(); i++)
                    if (t[i] != t[i - 1]) res = min(res, t[i] - t[i - 1]);
                ans[i][j] = res == inf ? 0 : res;
            }
        }
        return ans;
    }
};

力扣每日一题3643-垂直翻转子矩阵

日期：2026-03-21

题意

给定整数矩阵 grid ，上下翻转以 (x, y) 为左上角的边长为 k 的正方形子矩阵。

思路

跟着题意进行翻转即可。

实现

class Solution {
public:
    vector<vector<int>> reverseSubmatrix(vector<vector<int>>& grid, int x, int y, int k) {
        int n = grid.size(), m = grid.back().size();
        for (int i = y; i < y + k; i++) {
            for (int u = x, d = x + k - 1; u < d; u++, d--) {
                swap(grid[u][i], grid[d][i]);
            }
        }
        return grid;
    }
};

力扣每日一题1886-判断矩阵经轮转后是否一致

日期：2026-03-22

题意

给定两大小相同的正方形矩阵 mat 和 target 。每次操作可使得 mat 中所有元素顺时针旋转 90 度。问是否可使得两矩阵一致。

思路

显然至多旋转四次即恢复原样，每次旋转后进行比较即可。

实现

class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        int n = mat.size();
        auto check = [&]() -> bool {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (mat[i][j] != target[i][j]) return false;
            return true;
        };
        auto rotate = [&]() -> void {
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++)
                    swap(mat[i][j], mat[j][i]);
                ranges::reverse(mat[i]);
            }
        };

        for (int i = 0; i < 4; i++) {
            if (check()) return true;
            rotate();
        }
        return false;
    }
};

力扣每日一题1594-矩阵的最大非负积

日期：2026-03-23

题意

给定整数矩阵 grid ，最初位于矩阵左上角，目标矩阵右下角，每步可以向下或向右移动一格，求最大路径积。

思路

首先想到当然是 dp，但是注意到这里可能是出现负数，因此我们还需要维护最负值也就是最小值。

实现

class Solution {
using ll = long long;
static constexpr int mod = 1e9 + 7;
static constexpr ll inf = 2e18;
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid.back().size();
        vector<ll> f(m, -inf), g(m, inf);
        for (int i = 0; i < n; i++) {
            vector<ll> nf(m, -inf), ng(m, inf);
            for (int j = 0; j < m; j++) {
                int& x = grid[i][j];
                if (i && j) {
                    nf[j] = max({nf[j - 1] * x, f[j] * x, ng[j - 1] * x, g[j] * x});
                    ng[j] = min({nf[j - 1] * x, f[j] * x, ng[j - 1] * x, g[j] * x});
                } else if (i) {
                    nf[j] = max(f[j] * x, g[j] * x);
                    ng[j] = min(f[j] * x, g[j] * x);
                } else if (j) {
                    nf[j] = max(nf[j - 1] * x, ng[j - 1] * x);
                    ng[j] = min(nf[j - 1] * x, ng[j - 1] * x);
                } else {
                    ng[j] = nf[j] = x;
                }
            }
            swap(f, nf);
            swap(g, ng);
        }
        return (f.back() < 0 ? -1 : f.back() % mod);
    }
};

力扣每日一题2906-构造乘积矩阵

日期：2026-03-24

题意

给定非负整数矩阵 grid ，返回等大矩阵要求每格的值为除该格元素外的所有元素之积，结果对 12345 取模。

思路

可能会想到用逆元求解，但这里需要注意 12345 并非质数，是不能使用逆元的。同时数据范围也不允许求出完整积再做除法。我们可以简单的将矩阵展开为一维数组，就可以做一个前缀积与后缀积。

实现

class Solution {
using ll = long long;
static constexpr int mod = 12345;
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid.back().size();
        vector ans(n, vector<int> (m));
        ll pre = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i][j] = pre;
                pre = pre * grid[i][j] % mod;
            }
        }
        pre = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                ans[i][j] = ans[i][j] * pre % mod;
                pre = pre * grid[i][j] % mod;
            }
        }
        return ans;
    }
};

力扣每日一题3546-等和矩阵分割I

日期：2026-03-25

题意

给定正整数矩阵 grid ，判断是否可以通过一条横线或竖线将该矩阵分割为非空且元素和相等的两部分。

思路

可以行列都做一个前缀和，然后枚举分割线即可。

实现

class Solution {
using ll = long long;
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        const int n = grid.size(), m = grid.back().size();
        vector<ll> c(n), r(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                c[i] += grid[i][j];
                r[j] += grid[i][j];
            }
        }
        for (int i = 1; i < n; i++) {
            c[i] += c[i - 1];
        }
        for (int i = 1; i < m; i++) {
            r[i] += r[i - 1];
        }
        for (int i = 0; i < n; i++) {
            if (c[i] * 2ll == c.back()) return true;
        }
        for (int i = 0; i < m; i++) {
            if (r[i] * 2ll == r.back()) return true;
        }
        return false;
    }
};

力扣每日一题3548-等和矩阵分割II

日期：2026-03-26

题意

给定正整数矩阵 grid，问是否可以通过一条横线或竖线将该矩阵分割为非空且元素和相等的两部分；或是否可以在允许删除一个单元格的前提下，可以通过一条横线或竖线将该矩阵分割为非空且元素和相等同时两部分内部联通的两块子矩阵。

思路

不考虑删除操作的情况下就与昨天完全一致，不过多赘述。

加上删除操作，即要删除的单元格为两部分之差的绝对值。故而可以考虑用哈希记录出现过的元素，然后枚举横线与竖线。只是我们需要使删除后的块内部联通，因此需要注意一些边角情况，这里我是赛时写的没太注意，就加了大量的 if-else 使得有点屎山…但是在有点懒得重写了。

实现

class Solution {
using ll = long long;
static constexpr int MX = 1e5;
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        const int n = grid.size(), m = grid.back().size();
        ll sum = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sum += grid[i][j];
                cnt[grid[i][j]]++;
            }
        }

        ll lsum = 0;
        unordered_map<int, int> lcnt;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                lsum += grid[i][j];
                lcnt[grid[i][j]]++;
            }
            ll rsum = sum - lsum;
            if (lsum == rsum) return true;
            if (labs(lsum - rsum) > MX) continue;
            if (lsum > rsum) {
                int dif = lsum - rsum;
                if (i != 0) {
                    if (m == 1) {
                        if (grid[i][0] == dif || grid[0][0] == dif) return true;
                        continue;
                    }
                    if (lcnt.count(dif)) return true;
                } else {
                    if (grid[i].front() == dif || grid[i].back() == dif) {
                        return true;
                    }
                }
            } else {
                int dif = rsum - lsum;
                if (!cnt.count(dif)) continue;
                if (m == 1) {
                    if (i == n - 1) continue;
                    if (grid[i + 1][0] == dif || grid[n - 1][0] == dif) return true;
                    continue;
                }
                if (i != n - 2) {
                    if (!lcnt.count(dif) || cnt[dif] - lcnt[dif] > 0) {
                        return true;
                    }
                } else {
                    if (grid.back().front() == dif || grid.back().back() == dif) {
                        return true;
                    }
                }
            }
        }

        lsum = 0; lcnt.clear();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                lsum += grid[j][i];
                lcnt[grid[j][i]]++;
            }
            ll rsum = sum - lsum;
            if (lsum == rsum) return true;
            if (labs(lsum - rsum) > MX) continue;
            if (lsum > rsum) {
                int dif = lsum - rsum;
                if (i != 0) {
                    if (n == 1) {
                        if (grid[0][i] == dif || grid[0][0] == dif) return true;
                        continue;
                    }
                    if (lcnt.count(dif)) return true;
                } else {
                    if (grid[0][i] == dif || grid[n - 1][i] == dif) {
                        return true;
                    }
                }
            } else {
                int dif = rsum - lsum;
                if (!cnt.count(dif)) continue;
                if (n == 1) {
                    if (i == m - 1)continue;;
                    if (grid[0][i + 1] == dif || grid[0][m - 1] == dif) return true;
                    continue;
                }
                if (i != m - 2) {
                    if (!lcnt.count(dif) || cnt[dif] - lcnt[dif] > 0) {
                        return true;
                    }
                } else {
                    if (grid[0][m - 1] == dif || grid[n - 1][m - 1] == dif) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
};

力扣每日一题2946-循环移位后的矩阵相似检查

日期：2026-03-27

题意

给定整数矩阵 mat ，将其奇数行循环右移 k 位，偶数行循环左移 k 位。判断矩阵移动前后是否一致。

思路

按题意比较每个元素与其后第 k 个元素是否一致即可，因为 a[i] == a[i + k] 与 a[i + k] == a[i] 是一致的。

实现

class Solution {
public:
    bool areSimilar(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat.back().size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] != mat[i][(j + k) % m]) return false;
            }
        }
        return true;
    }
};

力扣每日一题2573-找出对应LCP矩阵的字符串

日期：2026-03-28

题意

给定非负整数矩阵 lcp，其中 lcp[i][j] 表示字符串 s[i : ] 与 s[j : ] 的最长公共前缀长度。求满足给定 lcp 条件且字典序最小的小写字母字符串 s。

思路

字典序最小的小写字母字符串， 那么应该从 ‘a’ 开始填起且尽可能多的填最小字母。同时若 lcp[i][j] == 0 即表明 s[i] != s[j] 反之则相等。由此可以想到我们贪心地尝试填满，再校验所得字符串是否符合条件即可。

实现

class Solution {
public:
    string findTheString(vector<vector<int>>& lcp) {
        int n = lcp.size();
        string s(n, 0);
        for (int i = 0, ch = 0; i < n; i++) {
            if (s[i] == 0) {
                if (ch >= 26) return "";
                s[i] = char('a' + ch);
                for (int j = i + 1; j < n; j++) {
                    if (lcp[i][j]) s[j] = char('a' + ch);
                }
                ch++;
            }
        }
        for (int i = 0; i < n; i++)
            if (s[i] == 0) return "";

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int t = 0;
                if (s[i] == s[j]) t = 1 + ((i != n - 1 && j != n - 1) ? lcp[i + 1][j + 1] : 0);
                if (t != lcp[i][j]) return "";
            }
        }
        return s;
    }
};

力扣每日一题2839-判断通过操作能否让字符串相等I

日期：2026-03-29

题意

给定两个长度为 4 的小写字母字符串 s1 与 s2, 每次操作可任选一个字符串的距离相隔等于 2 的字符交换位置.问任意次操作后是否可使得两个字符串相同.

思路

距离间隔为 2 的字符可以互换位置, 也就说是对字符串奇偶进行了一个分类, 若两字符奇位置的字符数量完全相同且偶位置的字符数量完全相同, 即可完成操作使得两字符相同.

实现

class Solution {
public:
    bool canBeEqual(string s1, string s2) {
        int n = s1.size();
        array<int, 26> cnt[2];
        cnt[0].fill(0); cnt[1].fill(0);
        for (int i = 0; i < n; i++) {
            cnt[i & 1][s1[i] - 'a']++;
            cnt[i & 1][s2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (cnt[0][i] || cnt[1][i]) return false;
        return true;
    }
};

力扣每日一题2840-判断通过操作能否让字符串相等II

日期：2026-03-30

题意

给定两个长度相同的小写字母字符串 s1 与 s2, 每次操作可任选一个字符串的距离相隔为偶数的字符交换位置.问任意次操作后是否可使得两个字符串相同.

思路

没错，和昨天的题目其实是完全一样的，只是字符串的长度扩大同时操作可以一步到位直接交换任意两个位置奇偶性相同的字符。现在整合到了一月一篇放在一起应该会更明显一些，对于这种 I II 的题我其实也都是先看题意是否相同，若相同先做 plus 版再复制回简单版的。

实现

class Solution {
public:
    bool checkStrings(string s1, string s2) {
        int n = s1.size();
        array<int, 26> cnt[2];
        cnt[0].fill(0); cnt[1].fill(0);
        for (int i = 0; i < n; i++) {
            cnt[i & 1][s1[i] - 'a']++;
            cnt[i & 1][s2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (cnt[0][i] || cnt[1][i]) return false;
        return true;
    }
};

力扣每日一题3474-字典序最小的生成字符串

日期：2026-03-31

题意

给定长度发别为 n 和 m 的字符串 str1 和 str2; 要求满足以下条件的字典序最小的字符串 s:

  • 若 str1[i] == 'T' 则 s[i : i + m] == str2
  • 若 str1[i] == 'F' 则 s[i : i + m] != str2

思路

看着确实很难做啊！但是注意到数据范围其实很小 1 <= n <= 1e4; 1 <= m <= 500 , 那么我们完全可以做一个 O(n*m) 的模拟就好。不知道为什么这题会是 hard.

实现

class Solution {
public:
    string generateString(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        string s(n + m - 1, 0);
        for (int i = 0; i < n; i++) {
            if (str1[i] == 'T') {
                for (int j = 0; j < m; j++) {
                    if (s[i + j] && s[i + j] != str2[j]) return "";
                    s[i + j] = str2[j];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (str1[i] == 'F') {
                int last = -1;
                for (int j = 0; j < m; j++) {
                    if (s[i + j]) {
                        if (s[i + j] != str2[j]) {
                            last = -2;
                            break;
                        }
                    } else {
                        if (str2[j] == 'a') last = i + j;
                        else {
                            last = -2;
                            break;
                        }
                    }
                }
                if (last == -1) return "";
                else if (last > -1) s[last] = 'b';
            }
        }
        for (auto& ch : s) if (ch == 0) ch = 'a';
        return s;
    }
};