Skip to content

第 326 场周赛

比赛链接

Date: 2023-01-01

A 统计能整除数字的位数

使用 to_string 转换为字符串，方便遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int countDigits(int num) {
        int res = 0;
        string s = to_string(num);
        for (auto c : s) {
            int d = c - '0';
            if (num % d == 0) {
                res++;
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
class Solution:
def countDigits(self, num: int) -> int:
    res = 0
    for c in str(num):
        if num % int(c) == 0:
            res += 1
    return res

复杂度分析

  • 时间复杂度：\(O(C)\)
  • 空间复杂度：\(O(1)\)

B 数组乘积中的不同质因数数目

对于每个数字分别计算质因数即可，用 set 来计数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_set<int> st;
        for (auto x : nums) {
            for (int i = 2; i * i <= x; i++) {
                if (x % i) continue;
                while (x % i == 0) x /= i;
                st.insert(i);
            }
            if (x > 1) st.insert(x);
        }
        return st.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        cnt = Counter()
        for x in nums:
            i = 2
            while i * i <= x:
                if x % i != 0:
                    i += 1
                    continue
                cnt[i] += 1
                while x % i == 0:
                    x /= i
                i += 1
            if x > 1:
                cnt[x] += 1
        return len(cnt)

复杂度分析

  • 时间复杂度：\(O(n\sqrt m)\)，其中 \(m\) 是数字大小
  • 空间复杂度：\(O(m)\)

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

动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.size();
        vector<int> d(n + 1, 1E9);
        d[0] = 0;
        s = "0" + s;
        for (int i = 1; i <= n; i++) {
            string t = "";
            for (int j = i; j >= i - 10 && j > 0; j--) {
                t = s[j] + t;
                if (stoll(t) <= k) {
                    d[i] = min(d[i], d[j - 1] + 1);
                }
            }
        }
        return d[n] < 1E9 ? d[n] : -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        n = len(s)
        s = "0" + s
        d = [1e9] * (n + 1)
        d[0] = 0
        for i in range(1, n + 1):
            j = i
            while j >= i - 10 and j >= 1:
                if int(s[j:i+1]) <= k:
                    d[i] = min(d[i], d[j - 1] + 1)
                j -= 1
        return d[n] if d[n] < 1e9 else -1

复杂度分析

  • 时间复杂度：\(O(10n)\)
  • 空间复杂度：\(O(n)\)

D 范围内最接近的两个质数

质数筛模版题，注意 1 不是质数

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        int n = right;
        vector<int> v(n + 1), p(n + 1);
        int m = 0, res = INT_MAX, x = 0, y = 0, last = -1;
        for (int i = 2; i <= n; i++) {
            if (v[i] == 0) {
                p[++m] = i;
                if (i >= left) {
                    if (last != -1) {
                        if (i - last < res) {
                            res = i - last;
                            x = last, y = i;
                        }
                    }
                    last = i;
                }
            }
            for (int j = 1; j <= m; j++) {
                if (p[j] > n / i) break;
                v[p[j] * i] = 1;
                if (i % p[j] == 0) break;
            }
        }
        if (res == INT_MAX) return {-1, -1};
        else return {x, y};
    }
};

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)
本文访问 次