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; // 统计有多少个数字能变成 y
for(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 变为 1
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 长，则将 t 中的因子从大到小，依次放在个位，十位...，少的位置补1
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;
}
};