2571.将整数减少到零需要的最少操作数

链接：2571.将整数减少到零需要的最少操作数
难度：Medium
标签：贪心、位运算、动态规划
简介：返回使 n 等于 0 需要执行的 最少 操作数。

题解 1 - cpp

• 编辑时间：2023-02-19
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：bfs，考虑所有可能加上减去的lowbit。

# define lb(x) ((x) & (-x))
class Solution {
public:
    int minOperations(int n) {
        unordered_set<int> s;
        queue<int> q;
        q.push(n);
        s.insert(n);
        int size = 1, step = 1;
        while (q.size()) {
            int num = q.front(), lbnum = lb(num);
            if (lbnum == num) return step;
            q.pop();
            int next1 = num + lbnum;
            if (!s.count(next1)) {
                s.insert(next1);
                q.push(next1);
            }
            int next2 = num - lbnum;
            if (!s.count(next2)) {
                s.insert(next2);
                q.push(next2);
            }
            if (--size == 0) {
                size = q.size();
                step++;
            }
        }
        return 1;
    }
};

题解 2 - cpp

• 编辑时间：2023-02-19
• 内存消耗：6.3MB
• 编程语言：cpp
• 解法介绍：dfs，加上减去lowbit。

# define lb(x) ((x) & (-x))
class Solution {
public:
    unordered_map<int, int> m;
    int dfs(int num) {
        if (m.count(num)) return m[num];
        int lbnum = lb(num);
        if (lbnum == num) return m[num] = 1;
        return m[num] = min(dfs(num + lbnum), dfs(num - lbnum)) + 1;
    }
    int minOperations(int n) {
        return dfs(n);
    }
};

题解 3 - python

• 编辑时间：2023-02-19
• 执行用时：32ms
• 内存消耗：15.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minOperations(self, n: int) -> int:
        def lb(num): return num & (-num)
  
        @cache
        def dfs(num: int) -> int:
            lbnum = lb(num)
            if lbnum == num:
                return 1
            return min(dfs(num - lbnum), dfs(num + lbnum)) + 1
        return dfs(n)

题解 4 - cpp

• 编辑时间：2023-02-19
• 执行用时：676ms
• 内存消耗：66.2MB
• 编程语言：cpp
• 解法介绍：bfs，考虑所有可能加上减去的数字。

# define lb(x) ((x) & (-x))
class Solution {
public:
    int minOperations(int n) {
        unordered_set<int> s;
        queue<int> q;
        q.push(n);
        s.insert(n);
        int size = 1, step = 1;
        while (q.size()) {
            int num = q.front();
            // cout << "num = " << num << ", step = " << step << ", size = " << size << endl;
            if (lb(num) == num) return step;
            q.pop();
            for (int i = 0; i <= 20; i++) {
                int next1 = num + pow(2, i);
                if (next1 <= pow(2, 17) && !s.count(next1)) {
                    s.insert(next1);
                    q.push(next1);
                }
                int next2 = num - pow(2, i);
                if (next2 > 0 && !s.count(next2)) {
                    s.insert(next2);
                    q.push(next2);
                }
            }
            if (--size == 0) {
                size = q.size();
                step++;
            }
        }
        return 1;
    }
};

题解 5 - rust

• 编辑时间：2023-02-19
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

use std::collections::HashMap;
impl Solution {
    pub fn min_operations(n: i32) -> i32 {
        let mut map = HashMap::<i32, i32>::new();
        Solution::dfs(n, &mut map)
    }
    pub fn dfs(num: i32, map: &mut HashMap<i32, i32>) -> i32 {
        if (map.contains_key(&num)) {
            *map.get(&num).unwrap()
        } else {
            let lb = num & -num;
            if lb == num {
                1
            } else {
                let res = Solution::dfs(num - lb, map).min(Solution::dfs(num + lb, map)) + 1;
                map.insert(num, res);
                res
            }
        }
    }
}