Leetcode 第 143 场双周赛题解

题目1：3345. 最小可整除数位乘积 I

思路

至多循环 10 次，一定会遇到个位数为 0 的数字，数位乘积是 0，一定是 t 的倍数。

所以暴力枚举即可。

代码

/** @lc app=leetcode.cn id=3345 lang=cpp** [3345] 最小可整除数位乘积 I*/// @lc code=start
class Solution
{
public:int smallestNumber(int n, int t){for (int i = n; i <= n + 10; i++)if (digitMultSum(i) % t == 0)return i;return -1;}// 辅函数 - 求数字 x 的各数位之积int digitMultSum(int x){int res = 1;while (x){res *= (x % 10);x /= 10;}return res;}
};
// @lc code=end

复杂度分析

时间复杂度：O(logn)。

空间复杂度：O(1)。

题目2：3346. 执行操作后元素的最高频率 I

思路

差分数组。

设 x=nums[i]。x 可以变成 [x−k,x+k] 中的整数。注意对于同一个 nums[i] 至多操作一次。

反过来想，对于一个整数 y，有多少个数可以变成 y？

这可以用差分计算，也就是把 [x−k,x+k] 中的每个整数的出现次数都加一。

计算差分的前缀和，就得到了有 sumD 个数可以变成 y。

如果 y 不在 nums 中，那么 y 的最大频率为 min(sumD,numOperations)。

如果 y 在 nums 中，且出现了 cnt 次，那么有 sumD−cnt 个其他元素（不等于 y 的数）可以变成 y，但这不能超过 numOperations，所以有 min(sumD−cnt,numOperations) 个其他元素可以变成 y，再加上 y 自身出现的次数 cnt，得到 y 的最大频率为 cnt+min(sumD−cnt,numOperations)=min(sumD,cnt+numOperations)。

代码

/** @lc app=leetcode.cn id=3346 lang=cpp** [3346] 执行操作后元素的最高频率 I*/// @lc code=start
class Solution
{
public:int maxFrequency(vector<int> &nums, int k, int numOperations){unordered_map<int, int> cnt;map<int, int> diff;for (int x : nums){cnt[x]++;diff[x];       // 把 x 插入 diff，以保证下面能遍历到 xdiff[x - k]++; // 把 [x-k, x+k] 中的每个整数的出现次数都加一diff[x + k + 1]--;}int ans = 0, sum_d = 0;for (auto &[x, d] : diff){sum_d += d;ans = max(ans, min(sum_d, cnt[x] + numOperations));}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。

题目3：3347. 执行操作后元素的最高频率 II

同第二题。

题目4：3348. 最小可整除数位乘积 II

思路

题解：https://leetcode.cn/problems/smallest-divisible-digit-product-ii/solutions/2984014/bao-sou-zuo-fa-lei-si-shu-wei-dp-by-endl-nkoo/

代码

/** @lc app=leetcode.cn id=3348 lang=cpp** [3348] 最小可整除数位乘积 II*/// @lc code=start
class Solution
{
public:string smallestNumber(string s, long long t){long long tmp = t;for (int i = 9; i > 1; i--){while (tmp % i == 0){tmp /= i;}}if (tmp > 1){ // t 包含大于 7 的质因子return "-1";}int n = s.length();vector<long long> left_t(n + 1);left_t[0] = t;int i0 = n - 1;for (int i = 0; i < n; i++){if (s[i] == '0'){i0 = i;break;}left_t[i + 1] = left_t[i] / gcd(left_t[i], s[i] - '0');}if (left_t[n] == 1){ // s 的数位之积是 t 的倍数return s;}// 假设答案和 s 一样长for (int i = i0; i >= 0; i--){while (++s[i] <= '9'){long long tt = left_t[i] / gcd(left_t[i], s[i] - '0');int k = 9;for (int j = n - 1; j > i; j--){while (tt % k){k--;}tt /= k;s[j] = '0' + k;}if (tt == 1){return s;}}}// 答案一定比 s 长string ans;for (int i = 9; i > 1; i--){while (t % i == 0){ans += '0' + i;t /= i;}}ans += string(max(n + 1 - (int)ans.length(), 0), '1');ranges::reverse(ans);return ans;}
};
// @lc code=end

复杂度分析