1017.负二进制转换

发表于 | 分类于
字数统计: 415 | 阅读时长 ≈ 1

一、题目描述

给出数字 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

提示：

  1. 0 <= N <= 10^9

二、题解

1.算法描述

  • 栈+二进制转化的变形

2.个人分析

这道题是负二进制转换

我们先回忆一下二进制转换：

  1. 对给定的整数N进行短除，将余数压入栈中，
  2. 当最后除数为一时，停止短除，并将最后的一压入栈中，
  3. 最后将栈反转过来即可。

参考这一过程，我们可以基本捋清楚负二进制转换的过程：

  1. 对给定的整数N进行短除，将余数压入栈中，但是，我们会发现：余数可能为-1，所以我们对这个余数进行特殊处理，令其为一，此时的N = (N - 1) / -2
  2. 二三步不变

3.代码

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
#define maxSize __INT16_MAX__
char *baseNeg2(int N)
{
    if (N == 0)
        return "0";
    int stack[maxSize];
    int top = -1;
    while (N != 1)
    {
        int mod = N % -2;
        if (mod < 0)
        {
            mod = 1;
            stack[++top] = mod;
            N = (N - 1) / -2;
        }
        else
        {
            stack[++top] = mod;
            N = N / -2;
        }
    }
    stack[++top] = 1;

    char *res = (char *)malloc(maxSize * sizeof(char));
    int i = 0;
    while (top != -1)
    {
        res[i++] = stack[top--] + '0';//将数字转换为字符
    }
    res[i++] = '\0';
    return res;
}