1017. Convert to Base -2

Leetcode 问题: 1017. Convert to Base -2
Categories:
Tags:

题目

Given an integer n, return a binary string representing its representation in base -2.

Note that the returned string should not have leading zeros unless the string is “0”.

传入一个整数 n，将它转换成 -2 进制 的数字

回传的 -2 进制数字最前方不可以有 0 除非传入的 整数 n 是 0

Example

Input: n = 2
Output: "110"
Explantion: (-2)^2 + (-2)^1 = 2

Input: n = 3
Output: "111"
Explantion: (-2)^2 + (-2)^1 + (-2)^0 = 3

Input: n = 4
Output: "100"
Explantion: (-2)^2 = 4

2 进制

2 进制计算 2^5 2^4 2^3 2^2 2^1 2^0
10 进制 32 16 8 4 2 1

-2 进制

2 进制计算 -2^5 -2^4 -2^3 -2^2 -2^1 -2^0
10 进制 -32 16 -8 4 -2 1

当 -2 进制 遇到 奇数 次方时，运算出来的答案就会变成 负 的

-3 进制

2 进制计算 -3^5 -3^4 -3^3 -3^2 -3^1 -3^0
10 进制 -243 81 -27 9 -3 1

负进制 遇到 奇数 次方时，运算出来的答案都会变成 负 的

-2 进制转换数字表

10 进制 -2 进制
10 11110
9 11001
8 11000
7 11011
6 11010
5 101
4 100
3 111
2 110
1 1
0 0
-1 11
-2 10
-3 1101
-4 1100
-5 1111
-6 1110
-7 1001
-8 1000
-9 1011
-10 1010

演算法

馀数运算

1. 馀数运算

因为是除以 -2(负数的 base)，所以原先的% mod 的馀数用来当作转换后的数字，会有变成负数的状况

数字运算 馀数
5 % -2 1
4 % -2 0
3 % -2 1
2 % -2 0
1 % -2 1
0 % -2 0
-1 % -2 -1
-2 % -2 0
-3 % -2 -1
-4 % -2 0
-5 % -2 -1

但使用 负数的 base，转换后的数字也都为正整数，所以需要将馀数都转换为正整数

2. 计算剩馀待运算数字

计算馀数后，会除以 负数的 base，去取得尚未完成转换的数字，然后继续进行转换

在原本 正数的 base 是无条件捨去，用捨弃后的剩馀数字当作下一个要运算的数字

数字运算 i / -2 Math.floor( i / -2 ) Math.ceil( i / -2 )
-5 / -2 2.5 2 3
-4 / -2 2 2 2
-3 / -2 1.5 1 2
-2 / -2 1 1 1
-1 / -2 0.5 0 1
0 / -2 0 0 0
1 / -2 -0.5 -1 0
2 / -2 -1 -1 -1
3 / -2 -1.5 -2 -1
4 / -2 -2 -2 -2
5 / -2 -2.5 -3 -2

但是因为除以 负数的 base，所以当数字是正数时，除法运算后会变成负数，而无条件捨去后，会取比这个负数小的正整数，所以数字就越取越小，所以必须要无条件进位的方式取得剩馀的数字

Note: 当 base 不是 -2 时算法不太一样，需要再确认

答案

JavaScript

function baseNeg2(sourceNumber) {
    // 如果来源数字是 0 直接回传 0
    if (sourceNumber == 0) {
        return '0';
    }
    var negativeTargetBase = -2;
    // 转换目标数字阵列
    var targetBaseNumberArray = [];
    while (sourceNumber != 0) {
        // 馀数
        var remainderNumber = Math.abs(sourceNumber % negativeTargetBase);
        // 下一进位计算数字
        sourceNumber = Math.ceil(sourceNumber / negativeTargetBase);
        // 转换目标 base 数字加到前方
        targetBaseNumberArray.unshift(remainderNumber);
    }
    // 目标数字转换并 join 成答案
    var targetBaseNumber = targetBaseNumberArray.join('');
    return targetBaseNumber;
}

TypeScript

function baseNeg2(sourceNumber: number): string {
    // 如果来源数字是 0 直接回传 0
    if (sourceNumber == 0) {
        return '0';
    }
    // 目标 base
    let negativeTargetBase = -2;

    // 转换目标数字阵列
    let targetBaseNumberArray: any = [];

    while (sourceNumber != 0) {
        // 馀数取正数
        let remainderNumber =  Math.abs(sourceNumber % negativeTargetBase);
        // 下一进位计算数字
        sourceNumber = Math.ceil(sourceNumber / negativeTargetBase);
        // 转换目标 base 数字加到前方
        targetBaseNumberArray.unshift(remainderNumber);
    }

    // 目标数字转换并 join 成答案
    let targetBaseNumber = targetBaseNumberArray.join('');

    return targetBaseNumber;
};

参考资料