LeetCode Contest 326

6278. Count the Digits That Divide a Number

给你一个整数 num ，返回 num 中能整除 num 的数位的数目。

如果满足 nums % val == 0 ，则认为整数 val 可以整除 nums 。

测试样例：
输入：num = 7

输出：1

解释：7 被自己整除，因此答案是 1 。

解答: 硬编码题

class Solution {
    public int countDigits(int num) {
        List<Integer> cache = new ArrayList<>();
        int dup = num;
        while (dup != 0) {
            cache.add(dup % 10);
            dup /= 10;
        }

        int res = 0;
        for (int i : cache) {
            if (num % i == 0) {
                ++res;
            }
        }
        return res;
    }
}

6279. Distinct Prime Factors of Product of Array

给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。

注意：

• 质数 是指大于 1 且仅能被 1 及自身整除的数字。
• 如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。

测试样例：
输入：nums = [2,4,3,7,10,6]

输出：4

解释：
nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7 。共有 4 个不同的质因数，所以返回 4 。

解答：硬编码题，计算质数算法。

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> prime = new HashSet<>();
        for (int i : nums) {
            int n = i;
            for (int j = 2; j <= n; ++j) {
                while (n % j == 0) {
                    prime.add(j);
                    n /= j;
                }
            }
        }
        return prime.size();
    }
}

6196. Partition String Into Substrings With Values at Most K

给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。

如果一个字符串 s 的分割满足以下条件，我们称它是一个 好 分割：

• s 中每个数位 恰好 属于一个子字符串。
• 每个子字符串的值都小于等于 k 。
  请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。

注意：

• 一个字符串的 值 是这个字符串对应的整数。比方说，"123" 的值为 123 ，"1" 的值是 1 。
• 子字符串 是字符串中一段连续的字符序列。

测试样例：
输入：s = "165462", k = 60

输出：4

我们将字符串分割成子字符串 "16" ，"54" ，"6" 和 "2" 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。

解答：基本的动态规划

class Solution {
    public int minimumPartition(String s, int k) {
        if (k < 10) {
            for (int i = 0; i < s.length(); ++i) {
                if (s.charAt(i) - '0' > k) {
                    return -1;
                }
            }
        }

        int[] dp = new int[s.length() + 1];

        for (int i = 0; i < s.length(); ++i) {
            dp[i + 1] = Integer.MAX_VALUE;
            long mul = 1, cur = 0;
            for (int j = i; j >= 0; --j) {
                cur += (s.charAt(j) - '0') * mul;
                mul *= 10;
                if (cur <= k) {
                    dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
                } else {
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

6280. Closest Prime Numbers in Range

给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：

• left <= nums1 < nums2 <= right 。
• nums1 和 nums2 都是 质数 。
• nums2 - nums1 是满足上述条件的质数对中的 最小值 。
  请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。

如果一个整数大于 1 ，且只能被 1 和它自己整除，那么它是一个质数。

测试样例：

输入：left = 10, right = 19

输出：[11,13]

解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。由于 11 比 17 小，我们返回第一个质数对。

解答：这周连考质数，一样质数公式硬算即可

class Solution {
    public int[] closestPrimes(int left, int right) {
        int last = -1, min = Integer.MAX_VALUE;
        int[] res = {-1,-1};
        for (int i = Math.max(left, 2); i <= right; ++i) {
            if (isPrime(i)) {
                if (last != -1) {
                    int d = i - last;
                    if (d < min) {
                        min = d;
                        res[0] = last;
                        res[1] = i;
                    }
                }
                last = i;
            }
        }
        return res;
    }

    private boolean isPrime(int n) {
        if (n <= 3) {
            return true;
        }
        int max = (int) Math.sqrt(n);
        for (int i = 2; i <= max; ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

元旦第一场考试，周赛还是非常简单的。老年选手手速过慢，大降分