当前位置：首页 > news >正文

第430场周赛：使每一列严格递增的最少操作次数、从盒子中找出字典序最大的字符串 Ⅰ、统计特殊子序列的数目、统计恰好有 K 个相邻元素的数组数目

news 来源：原创 2025/7/21 18:37:36

Q1、使每一列严格递增的最少操作次数

1、题目描述

给你一个由非负整数组成的 m x n 矩阵 grid。

在一次操作中，你可以将任意元素 grid[i][j] 的值增加 1。

返回使 grid 的所有列 严格递增 所需的最少操作次数。

2、解题思路

逐列处理：我们需要逐列检查每一列是否满足严格递增的条件。
逐行检查：在每一列中，从第二行开始，检查当前行的元素 grid[i][j] 是否大于等于上一行元素 grid[i - 1][j]。如果是，那么我们就需要将当前元素 grid[i][j] 增加一定的值，使其大于上一行的元素。
操作计数：每次增加的操作数就是 grid[i-1][j] - grid[i][j] + 1，这是为了确保当前元素大于上一行的元素。
累加操作：将每次操作的增量累加，最终得到总操作数。

3、代码实现

class Solution {
public:int minimumOperations(vector<vector<int>>& grid) {// 获取矩阵的行数和列数int row = grid.size();int col = grid[0].size();// 记录所需的最少操作次数int ret = 0;// 遍历每一列for (int j = 0; j < col; ++j) {// 遍历每一列的每一行, 从第二行开始for (int i = 1; i < row; ++i) {// 如果当前元素不满足严格递增的条件if (grid[i][j] <= grid[i - 1][j]) {// 计算需要增加的值, 使得 grid[i][j] > grid[i-1][j]int diff = grid[i - 1][j] - grid[i][j] + 1;// 累加操作次数ret += diff;// 更新当前元素, 使其大于上一行的元素grid[i][j] += diff;}}}// 返回所需的最少操作次数return ret;}
};

在这里插入图片描述

4、复杂度分析

时间复杂度：

外层循环遍历每一列，循环次数为 col。
内层循环遍历每一行，循环次数为 row。
因此，总体时间复杂度为 O(row * col)，即矩阵的元素总数。

空间复杂度：

只使用了常数级别的额外空间，空间复杂度为 O(1)，除去输入矩阵 grid 本身。

Q2、从盒子中找出字典序最大的字符串 Ⅰ

1、题目描述

给你一个字符串 word 和一个整数 numFriends。

Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：

word 被分割成 numFriends 个非空字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
所有分割出的字符串都会被放入一个盒子中。

在所有回合结束后，找出盒子中 字典序最大的 字符串。

字符串 a 的字典序小于字符串 b 的前提是：在两个字符串上第一处不同的位置上，a 的字母在字母表中的顺序早于 b 中对应的字母。
如果前 min(a.length, b.length) 个字符都相同，那么较短的字符串字典序更小。

2、解题思路

字典序最大字符串的选择：
- 我们需要将字符串分割成 numFriends 个子字符串，但问题要求找出所有可能分割中的字典序最大部分。
- 关键在于，字典序最大部分通常是从字符串的某个位置开始的连续子字符串，且这个子字符串的长度通常是与 numFriends 的关系有关的。特别地，当你需要分割成多个子串时，最有可能的是从较后的位置开始一个字典序较大的部分。
子字符串的选择：
- 在每一次选择时，最好从字符串 word 中挑选出一个最长的可能的子字符串，以确保它在字典序中最大。
- 基于题意，选择的分割点可以变化，但每次我们从不同位置截取字符串并且计算其字典序。

3、代码实现

class Solution {
public:string answerString(string word, int numFriends) {// 如果只需要一个分割, 直接返回原始字符串if (numFriends == 1) {return word;}int n = word.size();string ret;// 遍历所有可能的分割位置, 选择字典序最大的部分for (int i = 0; i < n; ++i) {// 从位置 i 开始, 截取出后面的部分, 长度至少为 (numFriends - 1)ret = max(ret, word.substr(i, n - max(numFriends - 1, i)));}return ret;}
};

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串 word 的长度。在每次截取子字符串时，我们需要进行一次 substr 操作，时间复杂度为 O(n). 因此，在最坏的情况下，我们会进行 n 次这样的操作，总的时间复杂度是 O(n^2)。

空间复杂度：O(n)，我们使用了一个额外的字符串 ret 来存储当前字典序最大的子字符串，最多需要保存长度为 n 的字符串。

Q3、统计特殊子序列的数目

1、题目描述

给你一个只包含正整数的数组 nums 。

特殊子序列 是一个长度为 4 的子序列，用下标 (p, q, r, s) 表示，它们满足 p < q < r < s ，且这个子序列必须满足以下条件：

nums[p] * nums[r] == nums[q] * nums[s]
相邻坐标之间至少间隔一个数字。换句话说，q - p > 1 ，r - q > 1 且 s - r > 1 。

子序列指的是从原数组中删除零个或者更多元素后，剩下元素不改变顺序组成的数字序列。

请你返回 nums 中不同 特殊子序列 的数目。

2、解题思路

这道题的目标是通过合理的枚举和利用哈希表加速查找，解决这个多重条件的子序列问题。

关键观察

条件分析：
- 条件 nums[p] * nums[r] == nums[q] * nums[s] 表明 (p, r) 和 (q, s) 对应的乘积相等。
- 为了满足条件 q - p > 1、r - q > 1 和 s - r > 1，我们可以枚举中间的元素 b = nums[q] 和 c = nums[r]，然后利用哈希表来加速查找。
优化：
- 用哈希表记录一些可能的组合，避免对每个 p, q, r, s 组合进行暴力搜索。
- 哈希表 suf 用于存储 nums[p] * nums[r] 和 nums[q] * nums[s] 的配对信息。通过巧妙的存储和查找，我们能够加速计算。
步骤：
- 外层循环：首先枚举 r 和 s，然后枚举 p 和 q，利用哈希表 suf 快速匹配符合条件的组合。
- GCD 优化：通过计算 gcd(c, d)（即 nums[r] 和 nums[s] 的最大公约数），将每一对 (c, d) 的比值压缩为整数，以减少存储和计算。

3、代码实现

class Solution {
public:long long numberOfSubsequences(vector<int>& nums) {int n = nums.size();unordered_map<int, int> suf; // 用于存储组合信息long long ret = 0;// 枚举 c 和 dfor (int i = 4; i < n - 2; ++i) {int c = nums[i]; // 固定 c// 枚举 dfor (int j = i + 2; j < n; ++j) {int d = nums[j];   // 固定 dint g = gcd(c, d); // 计算 gcd(c, d)// 将分子和分母压缩为一个整数存入哈希表suf[(d / g) << 16 | (c / g)]++;}}// 枚举 bfor (int i = 2; i < n - 4; ++i) {int b = nums[i]; // 固定 b// 枚举 afor (int j = 0; j < i - 1; ++j) {int a = nums[j];   // 固定 aint g = gcd(a, b); // 计算 gcd(a, b)// 统计符合条件的组合ret += suf[(a / g) << 16 | (b / g)];}// 撤销之前对 c 和 d 的统计int c = nums[i + 2]; // 固定cfor (int j = i + 4; j < n; ++j) {int d = nums[j];                // 固定 dint g = gcd(c, d);              // 计算 gcd(c, d)suf[(d / g) << 16 | (c / g)]--; // 减去已处理的组合}}return ret; // 返回符合条件的特殊子序列数}
};

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n^2)。主要的时间消耗来自于双重循环的部分，每一对 (c, d) 和 (a, b) 都需要进行枚举和哈希表查找，最终的时间复杂度为 O(n^2)，其中 n 为数组的大小。

空间复杂度：O(n)。空间主要消耗在哈希表 suf 上，它用于存储每对 (c, d) 的压缩值，最多需要 O(n) 的空间。

Q4、统计恰好有 K 个相邻元素的数组数目

1、题目描述

给你三个整数 n ，m ，k 。长度为 n 的 好数组 arr 定义如下：

arr 中每个元素都在 闭区间 [1, m] 中。
恰好有 k 个下标 i （其中 1 <= i < n）满足 arr[i - 1] == arr[i] 。

请你返回可以构造出的 好数组 数目。

由于答案可能会很大，请你将它对 109 + 7 取余后返回。

2、解题思路

1. 问题分解

分布方式的选择：
- n−1 是数组中相邻元素对的数量。
- 从中选择 k 个位置，使这些位置上的相邻元素相等，方案数为 C(n−1,k)（组合数计算）。
填充数组：
- 相邻元素相等的部分：这 k 个位置的值可以自由选择，总共有 m 种可能（所有值都可以选）。
- 相邻元素不相等的部分：剩余的 n−k−1 个相邻位置，要求两端值不同，方法数为 $m-1)^{n-k-1}$ 。
结果公式：

$\text{结果} = C(n-1, k) \cdot m \cdot (m-1)^{n-k-1}$

其中：
- C(n−1,k) 是从 n−1 个位置中选 k 个的组合数。
- m 是相等位置的值选择。
- $m-1)^{n-k-1}$ 是不相等位置的值选择。

2. 高效实现

为了快速计算上述公式，我们需要：

预处理阶乘与阶乘的模逆（通过费马小定理）。
使用快速幂计算大次幂取模。

3、代码实现

const int MOD = 1'000'000'007; // 模数
const int MAX_SIZE = 100'000;  // 阶乘数组的最大值vector<long long> factorial(MAX_SIZE);    // 阶乘数组
vector<long long> invFactorial(MAX_SIZE); // 阶乘逆数组// 快速幂计算 (x^n) % MOD
long long qpow(long long x, int n) {long long result = 1;while (n > 0) {if (n % 2 == 1) { // 如果当前位是 1result = result * x % MOD;}x = x * x % MOD; // 平方递推n /= 2;}return result;
}// 初始化阶乘和阶乘逆
auto initializeFactorials = [] {// 0 的阶乘factorial[0] = 1;for (int i = 1; i < MAX_SIZE; ++i) {factorial[i] = factorial[i - 1] * i % MOD;}// 计算阶乘逆, 使用费马小定理 (a^(MOD-1) ≡ 1) 求逆元invFactorial[MAX_SIZE - 1] = qpow(factorial[MAX_SIZE - 1], MOD - 2);for (int i = MAX_SIZE - 2; i >= 0; --i) {invFactorial[i] = invFactorial[i + 1] * (i + 1) % MOD;	// 倒序计算}return 0;
}();// 计算组合数 C(n, m) = n! / (m! * (n-m)!)
long long comb(int n, int m) {if (m > n || m < 0) {return 0; // 检查无效情况}return factorial[n] * invFactorial[m] % MOD * invFactorial[n - m] % MOD;
}class Solution {
public:int countGoodArrays(int n, int m, int k) {// 根据公式计算: C(n-1, k) * m * (m-1)^(n-k-1) % MODlong long result = comb(n - 1, k);result = result * m % MOD;result = result * qpow(m - 1, n - k - 1) % MOD;return result;}
};

在这里插入图片描述

4、复杂度分析

时间复杂度：

初始化阶乘与逆阶乘数组：O(MAX_SIZE)。
单次查询组合数：O(1)。
快速幂：O(log⁡(n−k−1))。
总体复杂度：近似 O(MAX_SIZE+log⁡(n−k−1))。

空间复杂度：

阶乘与逆阶乘数组：O(MAX_SIZE)。

Q1、使每一列严格递增的最少操作次数

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q2、从盒子中找出字典序最大的字符串 Ⅰ

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q3、统计特殊子序列的数目

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q4、统计恰好有 K 个相邻元素的数组数目

1、题目描述

2、解题思路

1. 问题分解

2. 高效实现

3、代码实现

4、复杂度分析

相关文章：