class Solution {
public:
int splitArray(vector<int>& nums) {
}
};
LCP 14. 切分数组
给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。
示例 1：
输入：
nums = [2,3,3,2,3,3]输出：
2解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。
示例 2：
输入：
nums = [2,3,5,7]输出：
4解释：只有一种可行的切割：[2], [3], [5], [7]
限制：
1 <= nums.length <= 10^52 <= nums[i] <= 10^6原站题解
java 解法, 执行用时: 344 ms, 内存消耗: 63.3 MB, 提交时间: 2023-07-01 13:47:31
class Solution {
public int splitArray(int[] nums) {
int n = nums.length;
// minPrime[i]表示数字i的最小质因数
int[] minPrime = new int[1000001];
//primeList表示[2,maxNum]所有的质数列表
List<Integer> primeList = new ArrayList<>();
int maxNum = 2; //最大的数字
for(int num : nums) maxNum = Math.max(maxNum, num);
//进行欧拉筛，获取[2,maxNum]之间所有数字对应的最小质因数，同时获取所有质数
for(int i = 2; i <= maxNum; i++){
//当前i是质数，加到质数列表,最小质因数是自己
if(minPrime[i] == 0){
primeList.add(i);
minPrime[i] = i;
}
//当前是合数，则进行欧拉筛，标记所有i对应的倍数，将其最小质因数标记
for(int j = 0; j < primeList.size(); j++){
int prime = primeList.get(j);
if(i*prime > maxNum) break;
else if(i%prime == 0) break;
else minPrime[i*prime] = prime;
}
}
//for(int i = 2; i <= maxNum; i++) System.out.println(i + " min prime is " + minPrime[i]);
//dp[i]表示当前数组新增一个数i后的最少分组数
int[] dp = new int[1000001];
//初始化，默认每个数字一组
for(int prime : primeList) dp[prime] = n;
//先处理最左边的数字，利用欧拉筛找出nums[0]所有的质因数，初始化dp
for(int i = nums[0]; i > 1; i /= minPrime[i]){
dp[minPrime[i]] = 0;
}
int res = 1;
//开始dp递推所有数字nums[i]对应的dp分组数量
for(int i = 0; i < n; i++){
res = i+1;
for(int x = nums[i]; x > 1; x /= minPrime[x]){
res = Math.min(res, dp[minPrime[x]]+1);
}
if(i == n-1) break;
for(int x = nums[i+1]; x > 1; x /= minPrime[x]){
dp[minPrime[x]] = Math.min(dp[minPrime[x]], res);
}
}
return res;
}
}
golang 解法, 执行用时: 420 ms, 内存消耗: 28.3 MB, 提交时间: 2023-07-01 13:46:14
func splitArray(nums []int) int {
length := len(nums)
if length == 1 {
return 1
}
// 1、动态规划-记录位置i的最少切分数
divides := make([]int, length)
// 2、难点：记录素数prime的最佳位置， 对于[6, 7, 11, 13, 2]: 6 的素数集: 2和3
// 则表示约数中含有2和3的数字，可以和位置0的数字6组成子数组，即：
// primePosMap[2] = 0, primePosMap[3] = 0，primePosMap[7] = 1
primePosMap := make(map[int]int)
// 3、难点：通过构造素数速查表：primeMinMap[num]表示任意数字num的最小质数
max := 0
for i := 0; i < length; i++ {
if nums[i] > max {
max = nums[i]
}
}
primeMinMap := make([]int, max+10)
for i := 2; i <= max; i++ { // get新知识点：素数筛构造速查表
if primeMinMap[i] == 0 {
for j := i; j <= max; j += i {
if primeMinMap[j] == 0 {
primeMinMap[j] = i
}
}
}
}
// 初始化位置0
divides[0] = 1
num := nums[0]
for {
// a：通过速查表，快速找到数字num的最小素数。
prime := primeMinMap[num]
primePosMap[prime] = 0
// b：num/prime后得到新的数字 num2, 继续执行步骤a
for num%prime == 0 {
num = num / prime
}
if num == 1 {
break
}
}
for i := 1; i < length; i++ {
divides[i] = i + 1 // 动态更新
num = nums[i]
for {
prime := primeMinMap[num]
if _, ok := primePosMap[prime]; !ok {
primePosMap[prime] = i
} else if divides[primePosMap[prime]] > divides[i-1]+1 {
// 难点2：动态更新primePosMap，[2, 3, 5, 7, 11, 13, 17, 4, 49, 41, 51]中，
// 一开始primePosMap[7]=3，之后由于4和49的加入，primePosMap[7]=8
primePosMap[prime] = i
}
currentPos := primePosMap[prime]
if currentPos == 0 {
divides[i] = 1
break
} else if divides[currentPos-1]+1 < divides[i] {
divides[i] = divides[currentPos-1] + 1
}
for num%prime == 0 {
num = num / prime
}
if num <= 1 {
break
}
}
}
//for prime, pos := range primePosMap {
// fmt.Printf("%d -- %d \n", prime, pos)
//}
//for i, s := range divides {
// fmt.Printf("%d --- %d --- %d\n", i, nums[i], s)
//}
return divides[length-1]
}
python3 解法, 执行用时: 748 ms, 内存消耗: 39 MB, 提交时间: 2023-07-01 13:45:40
max_num = 1000000
min_factor = [1] * (max_num + 1)
p = 2
# O(M loglog M)
while (p <= max_num):
i = p
while i * p <= max_num:
if min_factor[i * p] == 1:
min_factor[i * p] = p
i += 1
p += 1
while p <= max_num:
if min_factor[p] == 1:
break
p += 1
class Solution:
def splitArray(self, nums) -> int:
f = {}
n = len(nums)
x = nums[0]
INF = 100000000
while True:
if min_factor[x] == 1:
f[x] = 1
break
f[min_factor[x]] = 1
x //= min_factor[x]
min_prev = 1
for i in range(1, n):
x = nums[i]
min_cur = INF
while True:
if min_factor[x] == 1:
f[x] = min(f.get(x, INF), min_prev + 1)
min_cur = min(min_cur, f[x])
break
f[min_factor[x]] = min(f.get(min_factor[x], INF), min_prev + 1)
min_cur = min(min_cur, f[min_factor[x]])
x //= min_factor[x]
min_prev = min_cur
return min_prev
cpp 解法, 执行用时: 456 ms, 内存消耗: 248.8 MB, 提交时间: 2023-07-01 13:45:22
class Solution {
public:
int min_prime[1000010], prime[100010];
vector<int> g; // 数组g[i]表示加入质数i时数组最少可以切成几份
int cnt, NMAX;
int splitArray(vector<int>& nums) {
cnt = 0;// 记录有多少个质数
NMAX = 0; // 记录最大数
for(auto x: nums)
NMAX = max(NMAX, x);
// 用欧拉筛法找出所有数的最小质数
for(int i=2; i<=NMAX; i++){
if(!min_prime[i]){
// i 是个质数
min_prime[i] = i; // i 的最小质数是自己
prime[++cnt] = i; // 记录质数 i
}
for(int j=1; j<=cnt && i*prime[j]<=NMAX; j++){
min_prime[i*prime[j]] = prime[j]; // 数 i*prime[j] 的最小质数是 prime[j]
if(i % prime[j] == 0) break; // 欧拉筛的核心是让每一个合数被最小的质因数筛去, 所以这里必须break
}
}
int ans = 0;
g.resize(1000010, nums.size()); // 初始化 g， 先让g尽可能大
for(auto x: nums){
// 遍历每一个数
int tmp = nums.size(); // 临时变量，用于记录在分解x时数组的最少子数组数
while(x>1){
// 遍历数 x 的每一个质因子
int factor = min_prime[x]; // 拿到一个最小质因子
// ans: 上一次迭代的最优解
// ans+1: 数x单独分作一份
// g[factor]: 数x与邻近的一份数组并在一起
g[factor] = min(ans+1, g[factor]);
tmp = min(tmp, g[factor]);
x = x/factor; // 更新数x
}
ans = tmp;
}
return ans;
}
};