X

LEETCODE 1017. Convert to Base -2 解题思路分析

题目大意:

负二进制转换

给出数字 N,返回由若干 "0""1"组成的字符串,该字符串为 N负二进制(base -2表示。

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

示例 1:

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

示例 2:

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

示例 3:

输入:4
输出:"100"
解释:(-2) ^ 2 = 4

提示:

  1. 0 <= N <= 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1017

解题思路分析:

这是一道2进制的题目。 对于普通的2进制数,每一位上的1都相当于十进制中的2的n次方(n为当前位)。例如:

1 // 2的0次方 相当于10进制的1
10 // 2的1次方 相当于10进制的2
100 // 2的2次方 相当于10进制的4
111 // 111 = 1 + 10 + 100 = 1 + 2 + 4 = 7;

不过本题有些特殊,这个2进制数的每一位代表的并不是2的n次方,而是-2的n次方 ,这时需要注意的地方。那么如何将10进制数转化为负二进制数呢?利用位运算是最简单的解决办法,我们可以将N看做是一个正常的二进制数,每次取出最低位加入到返回结果中,接下来很关键,为了取二进制下一位,我们需要将N向右平移一位,这时最低位就变成了原先的下一位。不过,本题是负二进制数,因此,在向右平移一位之后,我们应该将N乘以-1。

简单啰嗦一下位运算的计算方法。

一,如何取最低位的数字。比如N = 2,对应的负二进制为:110。取最低位(最右一位)的方法是利用与(&)运算。 与运算的原则是1与1为1,1与0为0。

110 & 1 = 0; // 与运算两数位数不同是,长度短的前补零。即110 & 001 = 000 = 0
111 & 1 = 1; // 111 & 001 = 001 = 1

二,如何向右平移一位。还比如 N = 2,对应的负二进制为:110。 此时我们已经取到了最低位0,接下来要取高一位的1,我们可以利用>>将数字向右平移。

110 >> 1 = 11 // >> 1 表示向右平移1位,即删除最低一位
110 >> 2 = 1 // >> 2 表示向右平移2位
110 >> 3 = 0 // >> 3 表示向右平移3位

看下完整代码:

public String baseNeg2(int N) {
    if(N==0) return "0"; // 如果N为0,直接返回0
    String res = ""; // 定义返回结果
    while(N!=0){ // 当N不为0
        int n = N & 1; // 取得N的最低位数字
        res = n +res; // 将最低位加入到返回结果
        N = -(N>>1); // 将N向右平移一位,同时取负
    }
    return res;
}

本解法运行时间为1ms。

Runtime: 1 ms, faster than 95.72% of Java online submissions for Convert to Base -2.

Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Convert to Base -2.

如果大家对负二进制的题比较感兴趣,可看下,leetcode 1073. Adding Two Negabinary Numbers 这道题目,如果没有思路,请参考我之前的文章 LEETCODE 1073. Adding Two Negabinary Numbers 解题思路分析

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1017-convert-to-base-2-解题思路分析/
Categories: leetcode
kwantong: