leetcode868：二进制间距（binary_gap）

[carloscn]

问题描述

Note, 我们对原题进行了修改：两个相邻1之间有多少个0

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。

示例 1：

输入：n = 22 输出：2 解释：22 的二进制是 "10110" 。 在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。 第一对相邻的 1 中，两个 1 之间的距离为 2 。 第二对相邻的 1 中，两个 1 之间的距离为 1 。 答案取两个距离之中最大的，也就是 2 。 示例 2：

输入：n = 8 输出：0 解释：8 的二进制是 "1000" 。 在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。 示例 3：

输入：n = 5 输出：2 解释：5 的二进制是 "101" 。   提示：

1 <= n <= 109

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/binary-gap

[carloscn]

问题分析

按照正常的思维和步骤，我们想把十进制数值转换为二进制字符串，然后二进制字符串不断地判定两个1之间的距离。但这样会增加一倍的复杂度。因此我们，一边转换，一边判定。

10进制转2进制，取除数的余数。

我们可以塑造一个队列：

• 入队数值，每次运算的二进制的值；
• 入队规则，队列空&&准入队的值是1，或者队列不空&&准入队的值是0 可以入队
• 出队规则，队列非空&&准入队的值是1，
  • 记录队列的长度
  • 比较过往最大值
  • 清空队列
  • 该准入队的值1入队

fn binary_gap(n: i32) -> i32
{
    let mut input:i32 = n;
    let mut queue:Vec<i32> = vec![];
    let mut max:i32 = 0;

    while input != 0 {
        let mut m = 0;
        let mut d:i32 = 0;
        m = input % 2;
        // en-queue
        if (queue.is_empty() && 1 == m) ||
           (!queue.is_empty() && 0 == m) {
            queue.push(m);
        }
        // de-queue
        if !queue.is_empty() && 1 == m {
            d = (queue.len() - 1) as i32;
            max = d.max(max);
            queue.clear();
            queue.push(m);
        }
        input /= 2;
    }

    max
}

[carloscn]

code

https://review.gerrithub.io/c/carloscn/structstudy/+/551231 https://github.com/carloscn/structstudy/commit/751fd1bb22bb5d01b7acb2cdc06c62e4fdfb1562

[carloscn]

补充说明

这是我们第一次引入ChatGPT帮助我们设计单元测试的用例。 感谢ChatGPT。