White's Studio.

Leetcode-二进制间距

Leetcode
2018/08/05 Share

Leedcode-二进制间距

在 leedcode 里做了一道题， 题目是这样的

给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。

如果没有两个连续的 1，返回 0 。

示例 1：

1
2
3
4
5
6
7
8
输入：22
输出：2
解释：
22 的二进制是 0b10110 。
在 22 的二进制表示中，有三个 1，组成两对连续的 1 。
第一对连续的 1 中，两个 1 之间的距离为 2 。
第二对连续的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。

示例 2：

1
2
3
4
输入：5
输出：2
解释：
5 的二进制是 0b101 。

示例 3：

1
2
3
4
输入：6
输出：1
解释：
6 的二进制是 0b110 。

示例 4：

1
2
3
4
5
输入：8
输出：0
解释：
8 的二进制是 0b1000 。
在 8 的二进制表示中没有连续的 1，所以返回 0 。

提示：

  • 1 <= N <= 10^9

这题做了两个算法

  1. 第一种算法的思路，化简成二进制之后，先把所有值等于1的位置放到一个数组里面，然后再遍历这个数组，拿出相邻最大的值，如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} N
 * @return {number}
 */
var binaryGap = function(N) {
  let bytes = N.toString(2)
  // console.info(`[bytes=:>${JSON.stringify(bytes)}`)

  let indexArray = []

  for (let i = 0; i < bytes.length; i++) {
    // console.info(`[bytes[i]]:==:>${JSON.stringify(bytes[i])}`)
    if (bytes[i] === '1') indexArray.push(i)
  }
  if (indexArray.length < 2) return 0
  let max = 0
  for (let i = 0; i < indexArray.length - 1; i++) {
    max = Math.max(max, indexArray[i + 1] - indexArray[i])
  }
  return max
}

然而这个算法的时间复杂度是 $$O(n)$$ ,执行用时居然这么大：116 ms， 我的提交执行用时 已经战胜 11.76 % 的 javascript 提交记录

看来可以更快的，很明显并不用再次遍历的， 再第一次遍历就可以找出最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} N
 * @return {number}
 */
var binaryGap = function(N) {
  let bytes = N.toString(2)
  // console.info(`[bytes=:>${JSON.stringify(bytes)}`)

  let indexArray = []

  let lastIndex = undefined
  let max = 0
  for (let i = 0; i < bytes.length; i++) {
    // console.info(`[bytes[i]]:==:>${JSON.stringify(bytes[i])}`)
    if (bytes[i] === '1') {
      if (lastIndex >= 0) {
        max = Math.max(i - lastIndex, max)
      }
      lastIndex = i
    }
  }
  return max
}

这个算法已经是我提交时候最快的了，时间复杂度也是$$O(n)$$, 然而只有一次 for的循环。 我的提交执行用时 已经战胜 100.00 % 的 javascript 提交记录

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/08/05/Leetcode-二进制间距/

发表日期: August 5th 2018, 10:09:41

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Leedcode-二进制间距
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm