class Solution {
public:
int validSubarraySplit(vector<int>& nums) {
}
};
2464. 有效分割中的最少子数组数目
给定一个整数数组 nums。
如果要将整数数组 nums 拆分为 子数组 后是 有效的，则必须满足:
1，且nums 的每个元素只属于一个子数组。返回 nums 的 有效 子数组拆分中的 最少 子数组数目。如果不能进行有效的子数组拆分，则返回 -1。
注意:
示例 1:
输入: nums = [2,6,3,4,3] 输出: 2 解释: 我们可以通过以下方式创建一个有效的分割: [2,6] | [3,4,3]. - 第一个子数组的起始元素是 2，结束元素是 6。它们的最大公约数是 2，大于 1。 - 第二个子数组的起始元素是 3，结束元素是 3。它们的最大公约数是 3，大于 1。 可以证明，2 是我们在有效分割中可以获得的最少子数组数。
示例 2:
输入: nums = [3,5] 输出: 2 解释: 我们可以通过以下方式创建一个有效的分割: [3] | [5]. - 第一个子数组的起始元素是 3，结束元素是 3。它们的最大公约数是 3，大于 1。 - 第二个子数组的起始元素是 5，结束元素是 5。它们的最大公约数是 5，大于 1。 可以证明，2 是我们在有效分割中可以获得的最少子数组数。
示例 3:
输入: nums = [1,2,1] 输出: -1 解释: 不可能创建有效的分割。
提示:
1 <= nums.length <= 10001 <= nums[i] <= 105原站题解
python3 解法, 执行用时: 648 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-22 10:07:55
from math import gcd
class Solution:
def validSubarraySplit(self, nums: List[int]) -> int:
if nums[0] == 1 or nums[-1] == 1:
return -1
d = {-1: 0}
for i in range(len(nums)):
if nums[i] == 1:
continue
min_length = 2000
for j in range(i + 1):
if j - 1 in d and gcd(nums[j], nums[i]) > 1:
min_length = min(min_length, d[j - 1] + 1)
if min_length < 2000:
d[i] = min_length
return d.get(len(nums) - 1, -1)
python3 解法, 执行用时: 52 ms, 内存消耗: 20.5 MB, 提交时间: 2023-10-22 10:07:44
def min_factor(n):
sieve = list(range(n + 1))
sieve[2::2] = [2] * (n // 2)
for i in range(3, int(n ** 0.5) + 2, 2):
if sieve[i] == i:
sieve[i * i::2 * i] = [i] * ((n - i * i) // (2 * i) + 1)
return sieve
N = 100010
table = min_factor(N)
class Solution:
def validSubarraySplit(self, nums: List[int]) -> int:
f = {}
pre = 0
for num in nums:
cur = N
while num != 1:
f[table[num]] = min(f.get(table[num], N), pre + 1)
cur = min(cur, f[table[num]])
num //= table[num]
pre = cur
return pre if pre != N else -1
java 解法, 执行用时: 233 ms, 内存消耗: 39.7 MB, 提交时间: 2023-10-22 10:07:25
class Solution {
public int validSubarraySplit(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
if(nums[0]== 1 || nums[n-1] == 1) {
return -1;
}
Arrays.fill(dp,Integer.MAX_VALUE-100);
dp[0] = 0;
dp[1] = 1;
for(int i = 2;i<=n;i++) {
for(int j = i;j>=1;j--) {
if(gcd(nums[i-1],nums[j-1]) != 1) {
dp[i] = Math.min(dp[i],dp[j-1]+1);
}
}
}
return dp[n] == Integer.MAX_VALUE-100?-1:dp[n];
}
public int gcd(int x, int y) {
if(y != 0) {
return gcd(y,x%y);
}else {
return x;
}
}
}
cpp 解法, 执行用时: 232 ms, 内存消耗: 8.6 MB, 提交时间: 2023-10-22 10:06:56
class Solution {
public:
int validSubarraySplit(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n+1,1e9);
dp[0]=0; // dp[i]以第i个元素结尾能够分割出来的最少子数组数量
for(int i=1;i<=n;i++){
for(int j=i;j;j--){
if(__gcd(nums[i-1],nums[j-1])>1) dp[i]=min(dp[j-1]+1,dp[i]);
}
}
return dp[n]==1e9?-1:dp[n];
}
};