第143场双周赛：最小可整除数位乘积 Ⅰ、执行操作后元素的最高频率 Ⅰ、执行操作后元素的最高频率 Ⅱ、最小可整除数位乘积 Ⅱ

Q1、最小可整除数位乘积 Ⅰ

1、题目描述

给你两个整数 n 和 t 。请你返回大于等于 n 的 最小 整数，且该整数的 各数位之积 能被 t 整除。

2、解题思路

1. 问题拆解：

   • 题目要求我们找到一个整数，其 数位的积 可以被 t 整除。

   • 数位的积 是指将数字的每一位相乘后的结果，例如 123 的数位积为 $1\times 2\times 3=6$。

   • 如果某个数字包含 0，那么其数位积为 0，此时无法被 t 整除。

2. 算法设计：

   • 从整数 n 开始依次检查每个数字，直到找到第一个满足条件的数字。

   • 对于每个数字，计算其 数位积，然后判断是否可以被 t 整除。

   • 如果可以被 t 整除，则返回该数字；否则继续检查下一个数字。

3. 辅助函数：digitProduct：

   • 计算一个整数的数位积。

   • 如果数字中包含 0，则直接返回 0，因为数位积为 0。

4. 边界情况：

   • 如果 t = 1，那么任何数字都满足条件，因此直接返回 n。

   • 如果 t > 1，需要依次检查数字，直到找到满足条件的数字。

3、代码实现

class Solution {
public:int smallestNumber(int n, int t) {// 从 n 开始检查int cur = n;while (true) {// 如果当前数字的数位积可以被 t 整除, 返回当前数字if (digitProduct(cur) % t == 0) {return cur;}cur++; // 检查下一个数字}return -1; // 理论上永远不会到达这里}// 辅助函数: 计算一个数字的数位积int digitProduct(int x) {// 初始化数位积为 1int product = 1;while (x > 0) {// 取当前数字的最低位int digit = x % 10;if (digit == 0) {// 如果包含 0, 则数位积为 0return 0;}// 更新数位积product *= digit;// 去掉最低位x /= 10;}// 返回最终的数位积return product;}
};

4、复杂度分析

时间复杂度分析

1. 数字检查：
   • 最坏情况下，从 n 开始逐一递增检查，直到找到满足条件的数字。设答案为 n + k，最多需要检查 k 个数字。
2. 数位积计算：
   • 对于每个数字，计算数位积的复杂度与其位数成正比，假设数字最大有 O(\log n) 位。

总时间复杂度：

• 最坏情况下，复杂度为 $O(k\times \log n)$，其中 k 是找到满足条件的数字所需的检查次数。

Q2、执行操作后元素的最高频率 Ⅰ

Q3、执行操作后元素的最高频率 Ⅱ

这两题答案一样，放在一起

1、题目描述

给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i ，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

2、解题思路

本问题的核心是如何利用 numOperations 次操作，通过调整数组元素的值来使得某个元素的频率最大化。

解法 1：基于前缀和的差分数组优化

1. 使用差分数组记录可调整的范围：
   • 对于数组中每个元素 num，可以通过增加范围 [−k,k] 内的整数，将 num 的值调整到 [num−k,num+k]。
   • 利用差分数组 diff 来记录调整范围的增减：
     • 在 diff[num-k] 位置加 1，表示从该位置开始可以增加 1。
     • 在 diff[num+k+1] 位置减 1，表示该位置之后的值减少 1。
   • 通过遍历 diff，累加值即可知道每个数的覆盖频率。
2. 结合操作次数限制：
   • 直接记录数组中每个数 num 的原始频率 cnt[num]。
   • 更新累积频率时，确保频率不超过 cnt[num] + numOperations。
3. 计算最大频率：
   • 遍历差分数组，动态更新每个数的最大频率。

解法1：代码实现

class Solution {
public:int maxFrequency(vector<int>& nums, int k, int numOperations) {unordered_map<int, int> cnt; // 原始频率表map<int, int> diff;          // 差分数组// 初始化频率表和差分数组for (const auto& num : nums) {cnt[num]++;          // 记录每个数的原始频率diff[num];           // 确保下面遍历的时候能够遍历到diff[num - k]++;     // 差分数组起点加 1diff[num + k + 1]--; // 差分数组终点减 1}int ret = 0, count = 0;// 遍历差分数组, 动态更新频率for (const auto& [num, c] : diff) {count += c; // 累加当前数的频率变化ret = max(ret, min(count, cnt[num] + numOperations)); // 计算最大频率}return ret;}
};

解法 2：基于滑动窗口的区间扩展

1. 排序数组：
   • 通过排序，方便计算将某个值扩展到某范围的成本，特别是考虑连续区间的情况下。
   • 排序后，如果将 nums[right] 扩展到等于 nums[left]，可以更高效地计算操作次数。
2. 双层滑动窗口：
   • 第一部分：统计当前元素 x 的最大频率。
     • 遍历数组时，动态更新窗口内与 x 可调整范围内的值个数。
   • 第二部分：优化操作，统计全局范围内的频率最大值。
3. 边界处理：
   • 如果可以直接达到 numOperations 次操作，直接返回结果。

解法2：代码实现

class Solution {
public:int maxFrequency(vector<int>& nums, int k, int numOperations) {ranges::sort(nums); // 排序数组int n = nums.size();int ret = 0, cnt = 0, left = 0, right = 0;// 计算当前值 x 的最大频率for (int i = 0; i < n; ++i) {int x = nums[i];cnt++; // 当前 x 的频率增加if (i < n - 1 && x == nums[i + 1]) {continue; // 跳过连续相同元素}// 调整左、右边界, 统计 x 的最大频率while (nums[left] < x - k) {left++;}while (right < n && nums[right] <= x + k) {right++;}ret = max(ret, min(right - left, cnt + numOperations));cnt = 0; // 重置计数}if (ret >= numOperations) {return ret;}// 优化: 全局范围统计最大频率left = 0;for (int right = 0; right < n; ++right) {int x = nums[right];while (nums[left] < x - k * 2) {left++;}ret = max(ret, right - left + 1);}return min(ret, numOperations);}
};

3、复杂度分析

两种解法的对比

解法	时间复杂度	空间复杂度	适用场景
解法 1（差分数组）	$O(n\log n)$	$O(n)$	适用于需要精确调整每个数范围的场景
解法 2（滑动窗口）	$O(n\log n)$	$O(1)$	适用于连续区间扩展、排序后处理的问题

Q4、最小可整除数位乘积 Ⅱ

1、题目描述

给你一个字符串 num ，表示一个 正 整数，同时给你一个整数 t 。

如果一个整数 没有 任何数位是 0 ，那么我们称这个整数是 无零 数字。

请你返回一个字符串，这个字符串对应的整数是大于等于 num 的 最小无零 整数，且 各数位之积 能被 t 整除。如果不存在这样的数字，请你返回 "-1" 。

2、解题思路

1. 因子分解检查：

   • 如果 t 包含大于 7 的质因子（如 11, 13 等），无法找到符合条件的整数，因为我们只能用 1-9 的数位组成数字，且这些数位的乘积无法包含大于 7 的质因子。

2. 前缀 GCD 检查：

   • 对 num 逐位计算其数位乘积和 t 的 GCD。

   • 如果整个 num 的数位乘积已经满足 t 的整除条件，直接返回 num。

3. 调整当前数字：

   • 如果 num 的乘积不能整除 t，需要从低位到高位尝试调整数字：
     • 增大某一位数字，使得新的数位乘积可以整除 t。
     • 从调整的位后面开始重新构造数字，确保是最小无零整数。

4. 增加数字长度：

   • 如果调整当前数字无法满足条件，则结果一定比 num 长。

   • 将 t 分解为 2−9 的因子组合，构造最小无零整数。

3、代码实现

class Solution {
public:string smallestNumber(string s, long long t) {// 检查 t 是否包含大于 7 的质因子long long temp = t;for (int i = 9; i > 1; i--) {while (temp % i == 0) {temp /= i;}}// t 包含大于 7 的质因子, 无法生成符合条件的数字if (temp > 1) {return "-1";}// 数字的长度int n = s.length();// gcdPrefix[i] 表示从左到第 i 个字符的 gcd 前缀vector<long long> gcdPrefix(n + 1, 0);gcdPrefix[0] = t;// 第一个 0 出现的位置, 默认为最后一位int firstZeroIndex = n - 1;// 计算前缀 gcd 并找到第一个 0for (int i = 0; i < n; i++) {if (s[i] == '0') {// 记录第一个 0 出现的位置firstZeroIndex = i;break;}gcdPrefix[i + 1] = gcdPrefix[i] / gcd(gcdPrefix[i], s[i] - '0');}// 如果 num 的各位乘积是 t 的倍数, 直接返回 numif (gcdPrefix[n] == 1) {return s;}// 尝试调整 num, 使其成为满足条件的最小无零数字for (int i = firstZeroIndex; i >= 0; i--) {while (++s[i] <= '9') {long long reducedT = gcdPrefix[i] / gcd(gcdPrefix[i], s[i] - '0');// 当前可用的最大数字int maxDigit = 9;for (int j = n - 1; j > i; j--) {while (reducedT % maxDigit != 0) {// 寻找下一个可用的最大数字maxDigit--;}reducedT /= maxDigit;// 更新当前数字s[j] = '0' + maxDigit;}if (reducedT == 1) {// 找到满足条件的最小无零数字return s;}}}// 如果无法通过调整当前 num 实现目标, 答案一定比 num 长string result;for (int i = 9; i > 1; i--) {while (t % i == 0) {result += '0' + i;t /= i;}}// 补充剩余的位数为 1result += string(max(n + 1 - (int)result.length(), 0), '1');// 反转字符串以得到最终结果reverse(result.begin(), result.end());return result;}
};

4、复杂度分析

1. 时间复杂度：

• 因子分解检查：$O(\log t)$。
• 前缀 GCD 计算：$O(n)$，其中 n 是 num 的长度。
• 数字调整：最多尝试 $O(n\times \log t)$。
• 整体复杂度：$O(n\times \log t)$。

空间复杂度：

• 使用了前缀 GCD 数组，空间复杂度为 $O(n)$。