网站推广规范,全屏网站,wordpress老萨,49you网页游戏平台Q1、最小可整除数位乘积 Ⅰ
1、题目描述
给你两个整数 n 和 t 。请你返回大于等于 n 的 最小 整数#xff0c;且该整数的 各数位之积 能被 t 整除。
2、解题思路 问题拆解#xff1a; 题目要求我们找到一个整数#xff0c;其 数位的积 可以被 t 整除。 数位的积 是指将数…Q1、最小可整除数位乘积 Ⅰ
1、题目描述
给你两个整数 n 和 t 。请你返回大于等于 n 的 最小 整数且该整数的 各数位之积 能被 t 整除。
2、解题思路 问题拆解 题目要求我们找到一个整数其 数位的积 可以被 t 整除。 数位的积 是指将数字的每一位相乘后的结果例如 123 的数位积为 1 × 2 × 3 6 1 \times 2 \times 3 6 1×2×36。 如果某个数字包含 0那么其数位积为 0此时无法被 t 整除。 算法设计 从整数 n 开始依次检查每个数字直到找到第一个满足条件的数字。 对于每个数字计算其 数位积然后判断是否可以被 t 整除。 如果可以被 t 整除则返回该数字否则继续检查下一个数字。 辅助函数digitProduct 计算一个整数的数位积。 如果数字中包含 0则直接返回 0因为数位积为 0。 边界情况 如果 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、复杂度分析
时间复杂度分析
数字检查 最坏情况下从 n 开始逐一递增检查直到找到满足条件的数字。设答案为 n k最多需要检查 k 个数字。 数位积计算 对于每个数字计算数位积的复杂度与其位数成正比假设数字最大有 O(\log n) 位。
总时间复杂度
最坏情况下复杂度为 O ( k × log n ) O(k \times \log n) O(k×logn)其中 k 是找到满足条件的数字所需的检查次数。 Q2、执行操作后元素的最高频率 Ⅰ
Q3、执行操作后元素的最高频率 Ⅱ
这两题答案一样放在一起
1、题目描述
给你一个整数数组 nums 和两个整数 k 和 numOperations 。
你必须对 nums 执行 操作 numOperations 次。每次操作中你可以
选择一个下标 i 它在之前的操作中 没有 被选择过。将 nums[i] 增加范围 [-k, k] 中的一个整数。
在执行完所有操作以后请你返回 nums 中出现 频率最高 元素的出现次数。
一个元素 x 的 频率 指的是它在数组中出现的次数。
2、解题思路
本问题的核心是如何利用 numOperations 次操作通过调整数组元素的值来使得某个元素的频率最大化。
解法 1基于前缀和的差分数组优化
使用差分数组记录可调整的范围 对于数组中每个元素 num可以通过增加范围 [−k,k] 内的整数将 num 的值调整到 [num−k,numk]。利用差分数组 diff 来记录调整范围的增减 在 diff[num-k] 位置加 1表示从该位置开始可以增加 1。在 diff[numk1] 位置减 1表示该位置之后的值减少 1。 通过遍历 diff累加值即可知道每个数的覆盖频率。 结合操作次数限制 直接记录数组中每个数 num 的原始频率 cnt[num]。更新累积频率时确保频率不超过 cnt[num] numOperations。 计算最大频率 遍历差分数组动态更新每个数的最大频率。
解法1代码实现
class Solution {
public:int maxFrequency(vectorint nums, int k, int numOperations) {unordered_mapint, int cnt; // 原始频率表mapint, 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基于滑动窗口的区间扩展
排序数组 通过排序方便计算将某个值扩展到某范围的成本特别是考虑连续区间的情况下。排序后如果将 nums[right] 扩展到等于 nums[left]可以更高效地计算操作次数。 双层滑动窗口 第一部分统计当前元素 x 的最大频率。 遍历数组时动态更新窗口内与 x 可调整范围内的值个数。 第二部分优化操作统计全局范围内的频率最大值。 边界处理 如果可以直接达到 numOperations 次操作直接返回结果。
解法2代码实现
class Solution {
public:int maxFrequency(vectorint 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 \log n) O(nlogn) O ( n ) O(n) O(n)适用于需要精确调整每个数范围的场景解法 2滑动窗口 O ( n log n ) O(n \log n) O(nlogn) O ( 1 ) O(1) O(1)适用于连续区间扩展、排序后处理的问题 Q4、最小可整除数位乘积 Ⅱ
1、题目描述
给你一个字符串 num 表示一个 正 整数同时给你一个整数 t 。
如果一个整数 没有 任何数位是 0 那么我们称这个整数是 无零 数字。
请你返回一个字符串这个字符串对应的整数是大于等于 num 的 最小无零 整数且 各数位之积 能被 t 整除。如果不存在这样的数字请你返回 -1 。
2、解题思路 因子分解检查 如果 t 包含大于 7 的质因子如 11, 13 等无法找到符合条件的整数因为我们只能用 1-9 的数位组成数字且这些数位的乘积无法包含大于 7 的质因子。 前缀 GCD 检查 对 num 逐位计算其数位乘积和 t 的 GCD。 如果整个 num 的数位乘积已经满足 t 的整除条件直接返回 num。 调整当前数字 如果 num 的乘积不能整除 t需要从低位到高位尝试调整数字 增大某一位数字使得新的数位乘积可以整除 t。从调整的位后面开始重新构造数字确保是最小无零整数。 增加数字长度 如果调整当前数字无法满足条件则结果一定比 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 前缀vectorlong 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、复杂度分析
时间复杂度
因子分解检查 O ( log t ) O(\log t) O(logt)。前缀 GCD 计算 O ( n ) O(n) O(n)其中 n 是 num 的长度。数字调整最多尝试 O ( n × log t ) O(n \times \log t) O(n×logt)。整体复杂度 O ( n × log t ) O(n \times \log t) O(n×logt)。
空间复杂度
使用了前缀 GCD 数组空间复杂度为 O ( n ) O(n) O(n)。
