2654.使数组所有元素变成1的最少操作次数
题目描述:
给你一个下标从 0 开始的 正 整数数组 nums
。你可以对数组执行以下操作 任意 次:
- 选择一个满足
0 <= i < n - 1
的下标i
,将nums[i]
或者nums[i+1]
两者之一替换成它们的最大公约数。
请你返回使数组 nums
中所有元素都等于 1
的 最少 操作次数。如果无法让数组全部变成 1
,请你返回 -1
。
两个正整数的最大公约数指的是能整除这两个数的最大正整数。
数据范围:
$2\le nums.len \le 50, 1\le nums[i] \le 10^6$
题解:
暴力枚举:
枚举所有的子数组,可以动态的更新子数组的值。可以固定数组的左端点,然后每次移动右端点,得到所有的以左端点开头的子数组 $gcd$ 值。
也可以使用线段树之类:
代码:
1 | class Solution { |