跳转至

3556. 最大质数子字符串之和

题目描述

给定一个字符串 s，找出可以由其 子字符串 组成的 3个最大的不同质数 的和。

返回这些质数的 总和 ，如果少于 3 个不同的质数，则返回 所有 不同质数的和。

质数是大于 1 且只有两个因数的自然数：1和它本身。

子字符串 是字符串中的一个连续字符序列。 

注意：每个质数即使出现在 多个 子字符串中，也只能计算 一次 。此外，将子字符串转换为整数时，忽略任何前导零。

 

示例 1：

输入： s = "12234"

输出： 1469

解释：

  • 由 "12234" 的子字符串形成的不同质数为 2 ，3 ，23 ，223 和 1223。
  • 最大的 3 个质数是 1223、223 和 23。它们的和是 1469。

示例 2：

输入： s = "111"

输出： 11

解释：

  • 由 "111" 的子字符串形成的不同质数是 11。
  • 由于只有一个质数，所以结果是 11。

 

提示：

  • 1 <= s.length <= 10
  • s 仅由数字组成。

解法

方法一：枚举 + 哈希表

我们可以枚举所有的子字符串，然后判断它们是否是质数。由于题目要求我们返回最大的 3 个不同质数的和，因此我们可以使用一个哈希表来存储所有的质数。

在遍历完所有的子字符串后，我们将哈希表中的质数按从小到大的顺序排序，然后取出最大的 3 个质数进行求和。

如果哈希表中质数的数量小于 3，则返回所有质数的和。

时间复杂度 \(O(n^2 \times \sqrt{M})\)，空间复杂度 \(O(n^2)\)，其中 \(n\) 为字符串的长度，而 \(M\) 为字符串中最大的子字符串的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def sumOfLargestPrimes(self, s: str) -> int:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            return all(x % i for i in range(2, int(sqrt(x)) + 1))

        st = set()
        n = len(s)
        for i in range(n):
            x = 0
            for j in range(i, n):
                x = x * 10 + int(s[j])
                if is_prime(x):
                    st.add(x)
        return sum(sorted(st)[-3:])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public long sumOfLargestPrimes(String s) {
        Set<Long> st = new HashSet<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            long x = 0;
            for (int j = i; j < n; j++) {
                x = x * 10 + (s.charAt(j) - '0');
                if (is_prime(x)) {
                    st.add(x);
                }
            }
        }

        List<Long> sorted = new ArrayList<>(st);
        Collections.sort(sorted);

        long ans = 0;
        int start = Math.max(0, sorted.size() - 3);
        for (int idx = start; idx < sorted.size(); idx++) {
            ans += sorted.get(idx);
        }
        return ans;
    }

    private boolean is_prime(long x) {
        if (x < 2) return false;
        for (long i = 2; i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    long long sumOfLargestPrimes(string s) {
        unordered_set<long long> st;
        int n = s.size();

        for (int i = 0; i < n; ++i) {
            long long x = 0;
            for (int j = i; j < n; ++j) {
                x = x * 10 + (s[j] - '0');
                if (is_prime(x)) {
                    st.insert(x);
                }
            }
        }

        vector<long long> sorted(st.begin(), st.end());
        sort(sorted.begin(), sorted.end());

        long long ans = 0;
        int cnt = 0;
        for (int i = (int) sorted.size() - 1; i >= 0 && cnt < 3; --i, ++cnt) {
            ans += sorted[i];
        }
        return ans;
    }

private:
    bool is_prime(long long x) {
        if (x < 2) return false;
        for (long long i = 2; i * i <= x; ++i) {
            if (x % i == 0) return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func sumOfLargestPrimes(s string) (ans int64) {
    st := make(map[int64]struct{})
    n := len(s)

    for i := 0; i < n; i++ {
        var x int64 = 0
        for j := i; j < n; j++ {
            x = x*10 + int64(s[j]-'0')
            if isPrime(x) {
                st[x] = struct{}{}
            }
        }
    }

    nums := make([]int64, 0, len(st))
    for num := range st {
        nums = append(nums, num)
    }
    sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
    for i := len(nums) - 1; i >= 0 && len(nums)-i <= 3; i-- {
        ans += nums[i]
    }
    return
}

func isPrime(x int64) bool {
    if x < 2 {
        return false
    }
    sqrtX := int64(math.Sqrt(float64(x)))
    for i := int64(2); i <= sqrtX; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function sumOfLargestPrimes(s: string): number {
    const st = new Set<number>();
    const n = s.length;

    for (let i = 0; i < n; i++) {
        let x = 0;
        for (let j = i; j < n; j++) {
            x = x * 10 + Number(s[j]);
            if (isPrime(x)) {
                st.add(x);
            }
        }
    }

    const sorted = Array.from(st).sort((a, b) => a - b);
    const topThree = sorted.slice(-3);
    return topThree.reduce((sum, val) => sum + val, 0);
}

function isPrime(x: number): boolean {
    if (x < 2) return false;
    for (let i = 2; i * i <= x; i++) {
        if (x % i === 0) return false;
    }
    return true;
}

评论