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)

贪心的策略则是：

如果有连续的1，那么可以+1
- 连续的1如果不断地进位，然后最后-1，这样就是2次操作
- 而如果每直接每个位都-1, 那么至少2次操作
对于不连续的1，那么可以-1

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