2023-01-01 第 326 场周赛

6278. 统计能整除数字的位数

class Solution {
    public int countDigits(int num) {
        int tmp = num, ans = 0;
        while (tmp > 0) {
           if ( num % (tmp % 10) == 0) {
               ans++;
           }
            tmp /= 10;
        }
        return ans;
    }
}

6279. 数组乘积中的不同质因数数目

求出所有的数的质因子，用set存储。

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer>set = new HashSet<>();
        for (int num : nums) {
            process(num,set);
        }
        return set.size();
    }
    
    public void process(int num, Set<Integer> set) {
        int sqrt = (int)Math.sqrt(num);
        int tmp = num;
        for (int i = 2; i <= sqrt && i <= tmp; ) {
            if (tmp % i == 0) {
                set.add(i);
                tmp /= i;
            } else {
                i++;
            }
        }
        if (tmp != 1) {
            set.add(tmp);
        }
    }
}

6196. 将字符串分割成值不超过 K 的子字符串

动态规划，dp[i]表示前i个字符串不超过k的最小分割数。

class Solution {
    public int minimumPartition(String s, int k) {
        String num = k + "";
        int n = s.length(), len = num.length();
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i-1)-'0' > k) {
                return -1;
            }
            String str = s.substring(0,i);
            dp[i] = Integer.MAX_VALUE;
            if (i < 9 && Integer.parseInt(str) <= k) {
                dp[i] = 1;
                continue;
            }
            for (int j = 1; j <= len; j++) {
                if (i-j >= 0) {
                    String ss = str.substring(i-j);
                    if (Integer.parseInt(ss) <= k) {
                        dp[i] = Math.min(dp[i],dp[i-j]+1);
                    }
                }
            }
        }
        return dp[n];
    }
}

6280. 范围内最接近的两个质数

暴力方法，求出left到right之间的所有质数，然后遍历取最理想的质数对。

class Solution {
    public int[] closestPrimes(int left, int right) {
        List<Integer> list = new ArrayList<>();
        int[] ans = new int[]{-1,-1};
        int dis = Integer.MAX_VALUE;
        p(left,right,list);
        int n = list.size();
        for (int i = 0; i < n; i++) {
            if (i+1 < n && list.get(i+1) - list.get(i)< dis) {
                dis = list.get(i+1) - list.get(i);
                ans[0] = list.get(i);
                ans[1] = list.get(i+1);
            }
        }
        return ans;
    }
    
    public void p(int left, int right,List<Integer> list) {
        for (int i = left;i <= right; i++) {
            if (process(i)) {
                list.add(i);
            }
        }
    }
    
    public boolean process(int num) {
        if (num == 2) {
            return true;
        }
        if (num == 1) {
            return false;
        }
        int sqrt = (int)Math.sqrt(num);
        for (int i = 2; i <= sqrt;i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}