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

题目链接

Leetcode.2571 将整数减少到零需要的最少操作数 rating : 1649

题目描述

给你一个正整数 n n n ，你可以执行下述操作 任意 次：

n n n 加上或减去 2 2 2 的某个 幂

返回使 n n n 等于 0 0 0 需要执行的 最少 操作数。

如果 x = 2 i x = 2^i x=2i 且其中 i ≥ 0 i \geq 0 i≥0 ，则数字 x x x 是 2 2 2 的幂。

示例 1：

输入：n = 39 输出：3 解释：我们可以执行下述操作：

n 加上 20 = 1 ，得到 n = 40 。n 减去 23 = 8 ，得到 n = 32 。n 减去 25 = 32 ，得到 n = 0 。 可以证明使 n 等于 0 需要执行的最少操作数是 3 。 示例 2：

输入：n = 54 输出：3 解释：我们可以执行下述操作：

n 加上 21 = 2 ，得到 n = 56 。n 加上 23 = 8 ，得到 n = 64 。n 减去 26 = 64 ，得到 n = 0 。 使 n 等于 0 需要执行的最少操作数是 3 。 提示： 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105 解法：贪心

我们用 c n t cnt cnt 表示连续的 1 1 1 的个数 ， a n s ans ans 表示操作数。

此时遇到的是 0 0 0：

如果此时 c n t = 1 cnt = 1 cnt=1，那么此时直接选择减去这个 1 1 1 即可，即 a n s = a n s + 1 ans = ans + 1 ans=ans+1， c n t = 0 cnt = 0 cnt=0；如果此时 c n t > 1 cnt > 1 cnt>1，那么此时有多个连续的 1 1 1，所以我们选择相加，将这多个 1 1 1 变为 1 个 1 1 1，即 a n s = a n s + 1 ans = ans + 1 ans=ans+1， c n t = 1 cnt = 1 cnt=1；

最后如果 c n t = 1 cnt = 1 cnt=1，说明还有一个 1 1 1 ，直接减去即可，即 a n s = a n s + 1 ans = ans + 1 ans=ans+1；

如果 c n t > 1 cnt > 1 cnt>1，说明最后还有多个连续的 1 1 1，我们需要用两步将其减为 0 0 0，即 a n s = a n s + 2 ans = ans + 2 ans=ans+2。

时间复杂度： O ( l o g n ) O(logn) O(logn)

C++代码：

class Solution { public: int minOperations(int n) { int ans = 0 , cnt = 0; while(n){ if(n & 1) cnt++; else{ if(cnt == 1) ans++ , cnt = 0; else if(cnt > 1) ans++ , cnt = 1; } n >>= 1; } if(cnt == 1) ans++; else if(cnt > 1) ans += 2; return ans; } };