LeetCode --- 143周赛

题目列表

3345. 最小可整除数位乘积 I

3346. 执行操作后元素的最高频率 I

3347. 执行操作后元素的最高频率 II

3348. 最小可整除数位乘积 II

一、最小可整除数位成绩I

由于本题的数据范围比较小，我们直接暴力枚举即可，代码如下

class Solution {
public:int smallestNumber(int n, int t) {// 最多循环 10 次，一定能遇到一个带 0 的数字for(int i = n; ; i++){ int tmp = i;int res = 1;while(tmp){res *= (tmp % 10);tmp /= 10;}if(res % t == 0)return i;}return -1;}
};

二、执行操作后元素的最高频率 I & II

在numOperations的操作内，求出现频率最高的数字的出现次数。我们可以先计算出对于任意一个数，在不考虑操作次数的情况下，最多有多少个数字能变成它，然后与操作次数求min，再加上该数字本身出现的个数即可，如何计算有多少个数字能变成它？这比较难算，我们可以换一个角度，对于给定的数字，它能变成哪些数字，我们是很容易求出的，而且它能变成的数字是一个区间，并且我们只要计算频率，所以只要对区间整体进行+1/-1的操作即可，很明显，用差分数组进行计算

由于本题的加强版数据范围太大，开数组会爆内存，所以用map来代替数组，map中记录出现变化的点的频率，这样那些频率不发生变化的点就不用遍历了，也大大降低了时间复杂度 ，代码如下

class Solution {
public:int maxFrequency(vector<int>& nums, int k, int numOperations) {int n = nums.size();unordered_map<int,int> cnt; // 统计数字出现次数// 由于数据范围太大，差分数组可以用 map 来代替，节省空间map<int,int> mp; // 统计有多少个数字能变成 yfor(auto x : nums){// 对于数字 x ，能变成 [x-k, x+k] 的任意一个数，但是变成本身不需要操作次数mp[x - k]++;mp[x]--; // 对于 x 本身来说，不需要进行操作mp[x + 1]++;mp[x + k + 1]--;cnt[x]++;}int ans = 0, pre = 0;for(auto [x, c] : mp){pre += c;ans = max(ans, min(pre, numOperations) + (cnt.count(x) ? cnt[x] : 0));}return ans;}
};

这题还有另外的空间复杂度为O(1)的解法。整体思路依旧不变：先计算出对于任意一个数，在不考虑操作次数的情况下，最多有多少个数字能变成它，关键在于我们需要正面解决如何计算有多少个数字能变成它？如何做？

首先，由于操作性质，肯定是相邻的数字更容易变成我们需要的数字，所以先将数组排序。然后我们将频率可能最大的数字分为两类：1、在 nums 数组中的数字  2、不在 nums 数组中的数字

• 对于在 nums 中的数字 x ，我们可以通过二分计算出 [x-k，x+k] 中的数字个数 / 通过三指针计算出 [x-k，x+k] 中的数字，同时要统计 x 出现的次数 cnt[x]，从而计算频率 min(right - left, numOperations + cnt[x])，其中 [left，right) 是在 [x-k，x+k] 内的数字下标区间
• 对于不在 nums 中的数字， 我们只要维护以 x = nums[i] 为右端点的区间 [x - 2k，x] 内的数字个数即可，可以用滑动窗口计算

• 注意：一旦在 nums 数组中的数字的频率>= numOperations，直接返回即可，因为不在 nums 数组中的数字的频率最多是 numOperations

代码如下

class Solution {
public:int maxFrequency(vector<int>& nums, int k, int numOperations) {int n = nums.size();ranges::sort(nums);int l = 0, r = 0, ans = 0, cnt = 0;for(int i = 0; i < n; i++){int x = nums[i];cnt++;if(i < n - 1 && x == nums[i + 1])continue;while(r < n && nums[r] - nums[i] <= k)r++;while(nums[i] - nums[l] > k)l++;// [l, r)ans = max(ans, min(r - l, cnt + numOperations));cnt = 0;}if(ans >= numOperations) return ans;// [x-2k, x]for(int left = 0, right = 0; right < n; right++){while(nums[right] - nums[left] > 2*k)left++;ans = max(ans, right - left + 1);}return min(ans, numOperations); // 操作次数最大为numOperations}
};

三、最小可整除数位成绩 II

从小到大去枚举构造所有可能的结果，代码如下

class Solution {
public:string smallestNumber(string s, long long t) {long long tmp = t;for (int i = 9; i > 1; i--) { // 本质只要枚举 2 3 5 7 即可while (tmp % i == 0) {tmp /= i;}}if (tmp > 1) { // t 包含大于 7 的质因子，即有大于 10 的因子return "-1";}int n = s.length();vector<long long> left_t(n + 1); // 从左往右，记录在保持[0, i)不变的情况下，t剩余的值left_t[0] = t;int i0 = n - 1;for (int i = 0; i < n; i++) {if (s[i] == '0') { // 如果出现 0，则 [i, n) 的数字可以任意填写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'); // [i,n)需要让 tt 变为 1int 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 长，则将 t 中的因子从大到小，依次放在个位，十位...，少的位置补1string 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;}
};