辽宁省网站备案注销,宜昌seo,团员注册网站,平面设计免费网站题目列表
3345. 最小可整除数位乘积 I
3346. 执行操作后元素的最高频率 I
3347. 执行操作后元素的最高频率 II
3348. 最小可整除数位乘积 II
一、最小可整除数位成绩I 由于本题的数据范围比较小#xff0c;我们直接暴力枚举即可#xff0c;代码如下
class Solution {
p…题目列表
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(vectorint nums, int k, int numOperations) {int n nums.size();unordered_mapint,int cnt; // 统计数字出现次数// 由于数据范围太大差分数组可以用 map 来代替节省空间mapint,int mp; // 统计有多少个数字能变成 yfor(auto x : nums){// 对于数字 x 能变成 [x-k, xk] 的任意一个数但是变成本身不需要操作次数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-kxk] 中的数字个数 / 通过三指针计算出 [x-kxk] 中的数字同时要统计 x 出现的次数 cnt[x]从而计算频率 min(right - left, numOperations cnt[x])其中 [leftright) 是在 [x-kxk] 内的数字下标区间对于不在 nums 中的数字 我们只要维护以 x nums[i] 为右端点的区间 [x - 2kx] 内的数字个数即可可以用滑动窗口计算 注意一旦在 nums 数组中的数字的频率 numOperations直接返回即可因为不在 nums 数组中的数字的频率最多是 numOperations
代码如下
class Solution {
public:int maxFrequency(vectorint 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();vectorlong 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;}
};
