190 - 颠倒二进制位(reverse-bit)

Create by jsliang on 2019-07-08 14:04:54
Recently revised in 2019-07-08 15:21:20

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 知识点
七 解题思路
八 进一步拓展

二 前言

返回目录

颠倒给定的 32 位无符号整数的二进制位。

示例 1:
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
      因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。

示例 2:
输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
      因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。


提示:
请注意,在某些语言(如 Java)中,没有无符号整数类型。
在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现。
因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。
因此,在上面的 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数,你将如何优化你的算法?

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
var reverseBits = function (n) {
  return parseInt((n).toString(2).padStart(32, '0').split('').reverse().join(''), 2);
};

四 执行测试

返回目录

  1. n10111100
  2. return1041389824

五 LeetCode Submit

返回目录

✔ Accepted
  ✔ 600/600 cases passed (140 ms)
  ✔ Your runtime beats 26.29 % of javascript submissions
  ✔ Your memory usage beats 88.23 % of javascript submissions (35.5 MB)

六 知识点

返回目录

  1. parseInt()parseInt(string, radix)string 为字符串,radix 为介于 2-36 之间的数。使用者告诉这个函数 string(比如 11)是 radix(比如 2 )进制的,函数将固定返回 string 以十进制时显示的数(3)。parseInt() 详细介绍
  2. toString()toString() 返回一个字符串,表示指定的数组及其元素。toString() 详细介绍
  3. padStart()padStart() 方法用另一个字符串填充当前字符串(重复,如果需要的话),以便产生的字符串达到给定的长度。填充从当前字符串的开始(左侧)应用的。padStart() 详细介绍
  4. split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。split() 详细介绍
  5. reverse()reverse() 方法将数组中元素的位置颠倒,并返回该数组。该方法会改变原数组。reverse() 详细介绍
  6. join()join() 方法将一个数组(或一个类数组对象)的所有元素连接成一个字符串并返回这个字符串。join() 详细介绍

七 解题思路

返回目录

曾经有一份真诚摆在我面前,到最后才发现,原来是笑里藏刀。

首先jsliang 的题解是:

var reverseBits = function(n) {
  n = parseInt(parseInt(n, 2).toString().split('').reverse()).toString(2);
  return n;
};

比如输入:10111100,然后输出:1000,但是测试用例却是:

✘ Wrong Answer
  ✘ 1/600 cases passed (N/A)
  ✘ testcase: '00000010100101000001111010011100'
  ✘ answer:          NaN (00000000000000000000000000000NaN)
  ✘ expected_answer:    964176192 (00111001011110000010100101000000)
  ✘ stdout:

该死的超限!!!

虽然我代码本身就是错的,哭唧唧

然后,从【评论】【题解】中翻找能解题的思路,找到其中这份,咱将其分解:

parseInt((n).toString(2).padStart(32, '0').split('').reverse().join(''), 2);

分解:

console.log(n.toString(2));
console.log(n.toString(2).padStart(32, '0'));
console.log(n.toString(2).padStart(32, '0').split('').reverse().join(''));

其中,toString(2) 将内容转换成 2 进制,然后 padStart() 将其填充到 32 个长度,如果不到 32 个长度,则以 0 填充

再通过 split('') 转数组,通过 reverse() 反转数组,通过 join('') 将数组转回字符串。

最后,通过 parseInt(str, 2) 将这个数转回二进制,完成转换。

八 进一步拓展

返回目录

最后的最后,发现一份正经的题解,小伙伴们可以瞅瞅,我就不多逼逼啦~

var reverseBits = function (n) {
  var newN = 0,
    count = 0;
  while (count <= 31) {
    if (count <= 30) {
      newN += ((n & 1) << (30 - count)) * 2;
    } else {
      newN += (n & 1);
    }
    n >>= 1;
    count++;
  }
  return newN;
};
✔ Accepted
  ✔ 600/600 cases passed (84 ms)
  ✔ Your runtime beats 99.2 % of javascript submissions
  ✔ Your memory usage beats 22.35 % of javascript submissions (36.1 MB)

不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-09 16:21:52

results matching ""

    No results matching ""