Medium

题目描述

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

返回可以形成的三个最大不同质数的和。如果少于三个质数，则返回所有可用质数的和。如果无法形成质数，则返回 0。

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

示例 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 只包含数字。

解题思路

这道题需要我们找出字符串中所有可能子串形成的质数，然后返回最大的三个质数之和。

解题思路：

  1. 生成所有子串：遍历字符串的所有可能子串，将其转换为整数。需要注意处理前导零的情况。

  2. 质数判断：对每个生成的数字进行质数判断。可以使用经典的质数判断算法：检查从2到√n的所有数字是否能整除n。

  3. 去重存储：使用集合（Set）来存储所有找到的质数，自动去重。

  4. 排序取最大值：将所有质数排序，取最大的三个（如果不足三个则取全部）求和。

算法步骤：

  • 双重循环生成所有子串
  • 将子串转换为整数（自动处理前导零）
  • 对每个整数进行质数检测
  • 将质数存入集合去重
  • 对质数集合排序，取前3个最大值求和

时间复杂度优化： 由于字符串长度最大为10，所以最多有55个子串，每个子串最大值不超过10^10，质数判断的时间复杂度为O(√n)，总体复杂度是可接受的。

代码实现

class Solution {
public:
    bool isPrime(long long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (long long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    long long sumOfLargestPrimes(string s) {
        set<long long> primes;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                string substr = s.substr(i, j - i + 1);
                long long num = stoll(substr);
                if (isPrime(num)) {
                    primes.insert(num);
                }
            }
        }
        
        vector<long long> primeList(primes.rbegin(), primes.rend());
        long long sum = 0;
        for (int i = 0; i < min(3, (int)primeList.size()); i++) {
            sum += primeList[i];
        }
        
        return sum;
    }
};

class Solution:
    def isPrime(self, n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for i in range(3, int(n**0.5) + 1, 2):
            if n % i == 0:
                return False
        return True
    
    def sumOfLargestPrimes(self, s: str) -> int:
        primes = set()
        n = len(s)
        
        for i in range(n):
            for j in range(i, n):
                substr = s[i:j+1]
                num = int(substr)
                if self.isPrime(num):
                    primes.add(num)
        
        prime_list = sorted(primes, reverse=True)
        return sum(prime_list[:3])

public class Solution {
    private bool IsPrime(long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public long SumOfLargestPrimes(string s) {
        HashSet<long> primes = new HashSet<long>();
        int n = s.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                string substr = s.Substring(i, j - i + 1);
                long num = long.Parse(substr);
                if (IsPrime(num)) {
                    primes.Add(num);
                }
            }
        }
        
        var primeList = primes.OrderByDescending(x => x).ToList();
        long sum = 0;
        for (int i = 0; i < Math.Min(3, primeList.Count); i++) {
            sum += primeList[i];
        }
        
        return sum;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var sumOfLargestPrimes = function(s) {
    function isPrime(n) {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        for (let i = 3; i * i <= n; i += 2) {
            if (n % i === 0) return false;
        }
        return true;
    }
    
    const primes = new Set();
    
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            const substring = s.slice(i, j + 1);
            const num = parseInt(substring);
            if (isPrime(num)) {
                primes.add(num);
            }
        }
    }
    
    const sortedPrimes = Array.from(primes).sort((a, b) => b - a);
    return sortedPrimes.slice(0, 3).reduce((sum, prime) => sum + prime, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² × √m)n为字符串长度，m为子串对应的最大数值，需要生成O(n²)个子串，每个子串需要O(√m)时间判断质数
空间复杂度O(k)k为不同质数的个数，用于存储质数集合