题目描述
给定一个整数数组 nums。
如果对于每个索引 i > 0，nums[i] 的值能被 nums[i - 1] 整除，则该数组称为 美丽 数组。
在一次操作中，你可以给任何元素 nums[i] （其中 i > 0）增加 1。
返回使数组变美的 最小操作数。
示例 1：
输入：nums = [3,7,9]
输出：2
解释：
在 nums[1] 上进行两次操作使数组变美：[3,9,9]
示例 2：
输入：nums = [1,1,1]
输出：0
解释：
给定数组已经是美丽的。
示例 3：
输入：nums = [4]
输出：0
解释：
这个数组只有一个元素，所以它已经是美丽的。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 50
解法
方法一：动态规划 + 枚举
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def minOperations(self, nums: List[int]) -> int:
f = {nums[0]: 0}
for x in nums[1:]:
g = {}
for pre, s in f.items():
cur = (x + pre - 1) // pre * pre
while cur <= 100:
if cur not in g or g[cur] > s + cur - x:
g[cur] = s + cur - x
cur += pre
f = g
return min(f.values())
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public int minOperations(int[] nums) {
Map<Integer, Integer> f = new HashMap<>();
f.put(nums[0], 0);
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
Map<Integer, Integer> g = new HashMap<>();
for (var entry : f.entrySet()) {
int pre = entry.getKey();
int s = entry.getValue();
int cur = (x + pre - 1) / pre * pre;
while (cur <= 100) {
int val = s + (cur - x);
if (!g.containsKey(cur) || g.get(cur) > val) {
g.put(cur, val);
}
cur += pre;
}
}
f = g;
}
int ans = Integer.MAX_VALUE;
for (int v : f.values()) {
ans = Math.min(ans, v);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution {
public:
int minOperations(vector<int>& nums) {
unordered_map<int, int> f;
f[nums[0]] = 0;
for (int i = 1; i < nums.size(); i++) {
int x = nums[i];
unordered_map<int, int> g;
for (auto [pre, s] : f) {
int cur = (x + pre - 1) / pre * pre;
while (cur <= 100) {
int val = s + (cur - x);
auto jt = g.find(cur);
if (jt == g.end() || jt->second > val) {
g[cur] = val;
}
cur += pre;
}
}
f = move(g);
}
int ans = INT_MAX;
for (auto& it : f) {
ans = min(ans, it.second);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | func minOperations(nums []int) int {
f := map[int]int{nums[0]: 0}
for i := 1; i < len(nums); i++ {
x := nums[i]
g := make(map[int]int)
for pre, s := range f {
cur := (x + pre - 1) / pre * pre
for cur <= 100 {
val := s + (cur - x)
if old, ok := g[cur]; !ok || old > val {
g[cur] = val
}
cur += pre
}
}
f = g
}
ans := math.MaxInt32
for _, v := range f {
ans = min(ans, v)
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | function minOperations(nums: number[]): number {
let f = new Map<number, number>();
f.set(nums[0], 0);
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
const g = new Map<number, number>();
for (const [pre, s] of f.entries()) {
let cur = Math.floor((x + pre - 1) / pre) * pre;
while (cur <= 100) {
const val = s + (cur - x);
const old = g.get(cur);
if (old === undefined || old > val) {
g.set(cur, val);
}
cur += pre;
}
}
f = g;
}
return Math.min(...f.values());
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | use std::collections::HashMap;
impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
let mut f: HashMap<i32, i32> = HashMap::new();
f.insert(nums[0], 0);
for i in 1..nums.len() {
let x = nums[i];
let mut g: HashMap<i32, i32> = HashMap::new();
for (&pre, &s) in f.iter() {
let mut cur = ((x + pre - 1) / pre) * pre;
while cur <= 100 {
let val = s + (cur - x);
match g.get(&cur) {
None => {
g.insert(cur, val);
}
Some(&old) => {
if val < old {
g.insert(cur, val);
}
}
}
cur += pre;
}
}
f = g;
}
*f.values().min().unwrap()
}
}
|