目录
6278.统计能整除数字的位数 - 简单ac
6279.数组乘积中的不同质因数数目 - 质因数
6196.将字符串分割成值不超过K的子字符串 - 贪心
6280.范围内最接近的两个质数 - 质数筛 + 贪心
6278.统计能整除数字的位数 - 简单ac
6278. 统计能整除数字的位数
class Solution {public int countDigits(int num) {int res=0,t=num;while(t>0){int x=t%10;if(num%x==0) res++;t/=10;}return res;}
}6279.数组乘积中的不同质因数数目 - 质因数
6279. 数组乘积中的不同质因数数目
思路：
数组乘积的不同质因数 因为数据范围
1 <= nums.length <= 10^4
2 <= nums[i] <= 1000sum最大为
比long long还大
所以不能直接计算sum的质因数
其实数组乘积的质因数就是数组各元素的质因数
要求数目 用set去重即可
class Solution {
public:int distinctPrimeFactors(vector<int>& nums) {set<int>s;for(int x:nums){for(int i=2;i<=x/i;i++)if(x%i==0) {while(x%i==0) x/=i,s.insert(i);}if(x>1) s.insert(x);} return s.size();}
};
6196.将字符串分割成值不超过K的子字符串 - 贪心
6196. 将字符串分割成值不超过 K 的子字符串
思路：
要满足条件的子串数最小 则要让每个子串在不超过k的情况下最大
则枚举每一个s[i]
如果单位数就超过了k 说明再怎么分割都无法满足条件（最小分割单位为1） return -1
否则累加数字 如果累加的数x>k
说明x去掉最后一位数就是 在不超过k情况下最大的数 所以i-- res++
因为最后一个子串没办法加上 所以最后res要＋1
class Solution {
public:int minimumPartition(string s, int k) {int res=0;long long x=0;for(int i=0;i<s.size();i++){if(s[i]-'0'>k) return -1;x=x*10+(s[i]-'0');if(x>k) res++,x=0,i--;}return res+1;}
};6280.范围内最接近的两个质数 - 质数筛 + 贪心
6280. 范围内最接近的两个质数
思路：
先把范围内的质数存入v数组 数组内顺序肯定是从小到大的
如果质数的个数<2 则不可能找到满足条件的质数对 return -1
要求差值最小，那肯定是数组内两两间最小，不断更新答案即可
class Solution {
public:bool isprime(int x){if(x<2) return false;for(int i=2;i<=x/i;i++)if(x%i==0) return false;return true;}vector<int> closestPrimes(int left, int right) {vector<int> v;vector<int> res{0,0x3f3f3f3f};for(int i=left;i<=right;i++) if(isprime(i)) v.push_back(i);if(v.size()<2) return vector<int>{-1,-1};for(int i=0;i<v.size()-1;i++){int t=v[i+1]-v[i];if(res[1]-res[0]>t){res[0]=v[i];res[1]=v[i+1];}}return res;}
};
