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

https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/

这题想到贪心稍有点难,可以先考虑递归搜索的情况.

每次扩展的时候其实不用考虑所有的bit,只需要考虑lowbit的就行,然后加上记忆化搜索。

class Solution:
    def minOperations(self, n: int) -> int:
        import functools
        @functools.cache
        def search(x):
            if x & (x - 1) == 0: return 1
            # to get the lowest bit.
            lb = x & -x
            return 1 + min(search(x + lb), search(x - lb))

        return search(n)

贪心的策略则是:

class Solution:
    def minOperations(self, n: int) -> int:
        ans = 1

        while n & (n-1) != 0:
            lb = n & (-n) # (1 << lowbit)
            if (n & (lb << 1)): n += lb # 如果连续的1,那么直接加上,可能造成连续进位
            else: n-=lb # 删除这个位上的1
            ans += 1

        return ans