class Solution {
public:
int minOperations(int n) {
}
};
2571. 将整数减少到零需要的最少操作数
给你一个正整数 n ，你可以执行下述操作 任意 次：
n 加上或减去 2 的某个 幂返回使 n 等于 0 需要执行的 最少 操作数。
如果 x == 2i 且其中 i >= 0 ，则数字 x 是 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 <= 105原站题解
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2023-02-20 23:08:44
@cache
def dfs(x: int) -> int:
if (x & (x - 1)) == 0: # x 是 2 的幂次
return 1
lb = x & -x
return 1 + min(dfs(x + lb), dfs(x - lb))
class Solution:
def minOperations(self, n: int) -> int:
return dfs(n)
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-02-20 23:08:27
var cache = map[int]int{}
func minOperations(n int) int {
if n&(n-1) == 0 { // n 是 2 的幂次
return 1
}
if res, ok := cache[n]; ok {
return res
}
lb := n & -n
res := 1 + min(minOperations(n+lb), minOperations(n-lb))
cache[n] = res
return res
}
func min(a, b int) int { if a > b { return b }; return a }
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-02-20 23:08:13
func minOperations(n int) int {
return bits.OnesCount(uint(3*n ^ n))
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.7 MB, 提交时间: 2023-02-20 23:07:59
class Solution {
public:
int minOperations(int n) {
return __builtin_popcount(3 * n ^ n);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.2 MB, 提交时间: 2023-02-20 23:07:45
class Solution {
public int minOperations(int n) {
return Integer.bitCount(3 * n ^ n);
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2023-02-20 23:07:34
class Solution:
def minOperations(self, n: int) -> int:
return (3 * n ^ n).bit_count()
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2023-02-20 23:07:19
class Solution {
public:
int minOperations(int n) {
int ans = 1;
while (n & (n - 1)) { // n 不是 2 的幂次
int lb = n & -n;
if (n & (lb << 1)) n += lb; // 多个连续 1
else n -= lb; // 单个 1
++ans;
}
return ans;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 37.9 MB, 提交时间: 2023-02-20 23:06:35
class Solution {
public int minOperations(int n) {
int ans = 1;
while ((n & (n - 1)) > 0) { // n 不是 2 的幂次
int lb = n & -n;
if ((n & (lb << 1)) > 0) n += lb; // 多个连续 1
else n -= lb; // 单个 1
++ans;
}
return ans;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-02-20 23:06:19
func minOperations(n int) int {
ans := 1
for n&(n-1) > 0 { // n 不是 2 的幂次
lb := n & -n
if n&(lb<<1) > 0 { // 多个连续 1
n += lb
} else {
n -= lb // 单个 1
}
ans++
}
return ans
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2023-02-20 23:06:05
'''
优先考虑消除最小的比特1
贪心的策略是：如果有多个连续 1，那么采用加法是更优的，可以一次消除多个 1；否则对于单个 1，减法更优。
'''
class Solution:
def minOperations(self, n: int) -> int:
ans = 1
while n & (n - 1): # 不是 2 的幂次
lb = n & -n
if n & (lb << 1): n += lb # 多个连续 1
else: n -= lb # 单个 1
ans += 1
return ans