leetcode contest 326

感觉是目前做的最简单的力扣周赛了，全部都是手速题目。

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

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

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

示例 1：

输入：num = 7
输出：1
解释：7 被自己整除，因此答案是 1 。

示例 2：

输入：num = 121
输出：2
解释：121 可以被 1 整除，但无法被 2 整除。由于 1 出现两次，所以返回 2 。

示例 3：

输入：num = 1248
输出：4
解释：1248 可以被它每一位上的数字整除，因此答案是 4 。

提示：

• 1 <= num <= 109
• num 的数位中不含 0

地址

https://leetcode.cn/contest/weekly-contest-326/problems/count-the-digits-that-divide-a-number/

题意

直接遍历

思路

1. 直接对每一位上的数字取模即可统计所有可被整除的数字数目。
2. 复杂度分析：

• 时间复杂度：$O(\log n)$。其中 $n$ 表示给定的数字。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int countDigits(int num) {
        int x = num;
        int res = 0;
        while (x != 0) {
            int val = x % 10;
            if (num % val == 0) {
                res++;
            }
            x /= 10;
        }
        return res;
    }
};

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

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

注意：

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

示例 1：

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

示例 2：

输入：nums = [2,4,8,16]
输出：1
解释：
nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 210 。
共有 1 个不同的质因数，所以返回 1 。

提示：

• 1 <= nums.length <= 104
• 2 <= nums[i] <= 1000

地址

https://leetcode.cn/contest/weekly-contest-326/problems/distinct-prime-factors-of-product-of-array/

题意

素数筛选法

思路

1. 我们可以筛选出所有属于 $[1,1000]$ 范围的质数，然后对数组中的每个元素求其含有的质因子的数目。可以利用 $O(n)$ 的时间复杂度筛选出所有的素数。
2. 复杂度分析：

• 时间复杂度：$O(n \max(nums))$，其中 $n$ 为数组中的元素，$\max(nums)$ 表示数组中元素的最大值。
• 空间复杂度：$O(\max(nums))$。

代码

• 二分查找

  class Solution { public: int distinctPrimeFactors(vector<int>& nums) { int n = nums.size(); int maxVal = *max_element(nums.begin(), nums.end()); vector<int> primer; vector<bool> visit(maxVal + 1, false); for (int i = 2; i <= maxVal + 1; i++) { if(!visit[i]) { primer.emplace_back(i); for (int j = i; j <= maxVal + 1; j += i) { visit[j] = true; } } } int res = 0; unordered_set<int> cnt; for (auto x : nums) { for (auto p : primer) { if (x % p == 0) { cnt.emplace(p); } } } return cnt.size(); } };

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

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

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

• s 中每个数位 恰好 属于一个子字符串。
• 每个子字符串的值都小于等于 k 。

请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。

注意：

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

示例 1：

输入：s = "165462", k = 60
输出：4
解释：我们将字符串分割成子字符串 "16" ，"54" ，"6" 和 "2" 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。

示例 2：

输入：s = "238182", k = 5
输出：-1
解释：这个字符串不存在好分割。

提示：

• 1 <= s.length <= 105
• s[i] 是 '1' 到 '9' 之间的数字。
• 1 <= k <= 109

地址

https://leetcode.cn/contest/weekly-contest-326/problems/partition-string-into-substrings-with-values-at-most-k/

题意

贪心法

思路

1. 由于题目要求分割的连续子字符串越少越好，那么我们就要求每个字符串尽可能的大，那么明显的贪心算法，我们只需要尽可能的让每个子字符串尽可能的接近 $k$ 即可。需要注意的是，如果当前单个字符的大小已经小于 $k$，此时我们应该返回 $-1$。
2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示字符的长度。
• 空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    int minimumPartition(string s, int k) {
        int res = 0;
        long long curr = 0;
        int i = 0;
        while (i < s.size()) {
            long long curr = 0;
            int tot = 0;
            while (i < s.size() && curr * 10 + s[i] - '0' <= k) {
                curr = curr * 10 + s[i] - '0';
                i++;
                tot++;
            }
            if (tot == 0) {
                return -1;
            } else {
                res++;
            }
        }
        return res;
    }
};

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

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

• left <= nums1 < nums2 <= right 。
• nums1 和 nums2 都是 质数 。
• nums2 - nums1 是满足上述条件的质数对中的 最小值 。

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

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

示例 1：

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

示例 2：

输入：left = 4, right = 6
输出：[-1,-1]
解释：给定范围内只有一个质数，所以题目条件无法被满足。

提示：

• 1 <= left <= right <= 106

地址

https://leetcode.cn/contest/weekly-contest-326/problems/closest-prime-numbers-in-range/

题意

素数筛选

思路

1. 由于题目给定的数的范围为 $[1,10^6]$，这就表明我们可以直接利用素数筛选法，将 $[1,10^6]$ 以内的质数全部求出来即可。我们求出所有的素数以后然后求出相邻大小的素数的最小值即可，此时即可按照题目要求求出满足要求的最小素数对。当然这个即为最小孪生素数的经典数学题目。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示 $right$。我们可以利用经典的素数筛选法求出给定范围的素数即可。
• 空间复杂度：$O(n)$，其中 $n$ 表示 $right$，我们需要保存所有小于等于 $right$ 的素数。

代码

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        vector<int> primer;
        vector<bool> visit(right + 1, false);
        for (int i = 2; i <= right; i++) {
            if (!visit[i]) {
                primer.emplace_back(i);
                for (int j = i; j <= right; j += i) {
                    visit[j] = true;
                }
            }
        }
        vector<int> res;
        int mindiff = INT_MAX;
        for (int i = 1; i < primer.size(); i++) {
            if (primer[i - 1] >= left && primer[i] <= right) {
                if (primer[i] - primer[i - 1] < mindiff) {
                    res = vector<int>({primer[i - 1], primer[i]});
                    mindiff = primer[i] - primer[i - 1];
                }
            }
        }
        if (res.size() == 0) {
            return {-1, -1};
        } else {
            return res;
        }
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿