comments | difficulty | edit_url | tags | ||||
---|---|---|---|---|---|---|---|
true |
中等 |
|
给定一个整数数组 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 <= 1000
1 <= nums[i] <= 105
我们设计一个函数
时间复杂度
class Solution:
def validSubarraySplit(self, nums: List[int]) -> int:
@cache
def dfs(i):
if i >= n:
return 0
ans = inf
for j in range(i, n):
if gcd(nums[i], nums[j]) > 1:
ans = min(ans, 1 + dfs(j + 1))
return ans
n = len(nums)
ans = dfs(0)
dfs.cache_clear()
return ans if ans < inf else -1
class Solution {
private int n;
private int[] f;
private int[] nums;
private int inf = 0x3f3f3f3f;
public int validSubarraySplit(int[] nums) {
n = nums.length;
f = new int[n];
this.nums = nums;
int ans = dfs(0);
return ans < inf ? ans : -1;
}
private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] > 0) {
return f[i];
}
int ans = inf;
for (int j = i; j < n; ++j) {
if (gcd(nums[i], nums[j]) > 1) {
ans = Math.min(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
class Solution {
public:
const int inf = 0x3f3f3f3f;
int validSubarraySplit(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
if (f[i]) return f[i];
int ans = inf;
for (int j = i; j < n; ++j) {
if (__gcd(nums[i], nums[j]) > 1) {
ans = min(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
};
int ans = dfs(0);
return ans < inf ? ans : -1;
}
};
func validSubarraySplit(nums []int) int {
n := len(nums)
f := make([]int, n)
var dfs func(int) int
const inf int = 0x3f3f3f3f
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] > 0 {
return f[i]
}
ans := inf
for j := i; j < n; j++ {
if gcd(nums[i], nums[j]) > 1 {
ans = min(ans, 1+dfs(j+1))
}
}
f[i] = ans
return ans
}
ans := dfs(0)
if ans < inf {
return ans
}
return -1
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}