题目列表
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;}
};