LeetCode1017-负二进制转换

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/convert-to-base-2/

中文链接：https://leetcode-cn.com/problems/convert-to-base-2/

题目详述

给出数字 N，返回由若干 “0” 和 “1”组成的字符串，该字符串为 N 的负二进制（base -2）表示。

除非字符串就是 “0”，否则返回的字符串中不能含有前导零。

示例 1：

1
2
3
输入：2
输出："110"
解释：(-2) ^ 2 + (-2) ^ 1 = 2

示例 2：

1
2
3
输入：3
输出："111"
解释：(-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

示例 3：

1
2
3
输入：4
输出："100"
解释：(-2) ^ 2 = 4

提示：

  • 0 <= N <= 10^9

题目详解

  • 十进制 n 转换到 k 进制（k > 0）的方法是 除 k 取余法。
  • 最后翻转得到的结果。
1
2
3
4
5
6
7
8
9
public String toBase(int n, int k) {
    StringBuilder sb = new StringBuilder();
    while (n != 0) {
        int r = n % k;
        n /= k;
        sb.append(r);
    }
    return sb.length() > 0 ? sb.reverse().toString() : "0";
}
  • 十进制 n 转换到 k 进制（k < 0）的方法也是 除 k 取余法。
  • 只不过在余数为负数时，余数要加上进制的相反数使余数大于 0，同时要向前进 1 位。
  • 最后翻转得到的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
public String toNegativeBase(int n, int k) {
    StringBuilder sb = new StringBuilder();
    while (n != 0) {
        int r = n % k;
        n /= k;
        if (r < 0) {
            r += -k;
            ++n;
        }
        sb.append(r);
    }
    return sb.length() > 0 ? sb.reverse().toString() : "0";
}
  • 有了上面的知识，转化为 -2 进制就比较简单了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_01017 {

    public String baseNeg2(int N) {
        StringBuilder sb = new StringBuilder();
        while (N != 0) {
            int r = N % -2;
            N /= -2;
            if (r < 0) {
                r += 2;
                ++N;
            }
            sb.append(r);
        }
        return sb.length() > 0 ? sb.reverse().toString() : "0";
    }
}
  • 由于在计算机中 2 的特殊性，可以运用位运算来解决。
  • 转化为 2 进制可以像下面这样写（或者直接调用 Integer.toBinaryString()）。
1
2
3
4
5
6
7
8
public String baseNeg2(int N) {
    StringBuilder sb = new StringBuilder();
    while (N != 0) {
        sb.append(N & 1);
        N = N >> 1;
    }
    return sb.length() > 0 ? sb.reverse().toString() : "0";
}
  • 同理，转化为 -2 进制也可以运用位运算。
1
2
3
4
5
6
7
8
public String baseNeg2(int N) {
    StringBuilder sb = new StringBuilder();
    while (N != 0) {
        sb.append(N & 1);
        N = -(N >> 1);
    }
    return sb.length() > 0 ? sb.reverse().toString() : "0";
}