LC LCP 14. 切分数组

2021-02-04 07:14

阅读：573

标签：public turn 一个 vector leetcode void col table info

link

技术图片

解法：

maxprime存一个数的最大质因数，primeMin[i] 一个数n的质因数存在i，以n结尾所分得的最小子数组数。

class Solution {
public:
    static const int maxn=1000000;
    int maxprime[maxn+1];
    int primeMin[maxn+1];
    void primetable(){
        for(int i=2;i){
            maxprime[i]=1;
        }
        vectorint> primes;
        for(int i=2;i){
            if(maxprime[i]==1){
                for(int j=i;ji){
                    maxprime[j]=i;
                }
            }
        }
    }

    int splitArray(vectorint>& nums) {
        primetable();
        int n=nums.size();
        vectorint> dp(n+1,0);
        for(int i=0;i){
            int num=nums[i];
            int idx=0;
            dp[i+1]=1+dp[i];
            while(num!=1){
                int prime=maxprime[num];
                if(primeMin[prime]==0) primeMin[prime]=dp[i]+1;
                else primeMin[prime]=min(primeMin[prime],dp[i]+1);
                dp[i+1]=min(dp[i+1],primeMin[prime]);
                num/=prime;
            }
        }
        return dp[n];
    }
};

LC LCP 14. 切分数组

标签：public turn 一个 vector leetcode void col table info

原文地址：https://www.cnblogs.com/FEIIEF/p/12796276.html

上一篇：C语言整数的输出

下一篇：Python 爬虫知识清单【更】

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：LC LCP 14. 切分数组
文章链接：http://soscw.com/index.php/essay/50783.html

亲，登录后才可以留言！

LC LCP 14. 切分数组

评论

热门文章

推荐文章

最新文章

置顶文章