1611. 使整数变为0的最少操作次数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。返回将 n 转换为 0 的最小操作次数。

示例 1：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 2：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

提示：

0 <= n <= 10⁹

# 思路

直接递归

# 解法

class Solution {
    private int[] store = new int[31];

    public int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int kn = 31 - Integer.numberOfLeadingZeros(n);
        return minNumTo2k(n & ~(1 << kn), kn - 1) + 1 + min2kToZero(kn - 1);
    }

    private int min2kToZero(int k) {
        if (store[k] == 0) {
            store[k] = minimumOneBitOperations(1 << k);
        }
        return store[k];
    }

    private int minNumTo2k(int n, int k) {
        if (n == 0 && k == 0) {
            return 1;
        }

        int kn = 31 - Integer.numberOfLeadingZeros(n);
        if (k > kn) {
            return minNumTo2k(n, k - 1) + 1 + min2kToZero(k - 1);
        }
        return minimumOneBitOperations(n & ~(1 << kn));
    }
}****

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 总结

分析出几种情况，然后分别对各个情况实现

#Java