[leetcode] 868. Binary Gap

[leetcode] 868. Binary Gap

Description

Given a positive integer n, find and return the longest distance between any two adjacent 1’s in the binary representation of n. If there are no two adjacent 1’s, return 0.

Two 1’s are adjacent if there are only 0’s separating them (possibly no 0’s). The distance between two 1’s is the absolute difference between their bit positions. For example, the two 1’s in “1001” have a distance of 3.

Example 1:

Input: n = 22Output: 2Explanation: 22 in binary is "10110".The first adjacent pair of 1's is "10110" with a distance of 2.The second adjacent pair of 1's is "10110" with a distance of 1.The answer is the largest of these two distances, which is 2.Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 5Output: 2Explanation: 5 in binary is "101".

Example 3:

Input: n = 6Output: 1Explanation: 6 in binary is "110".

Example 4:

Input: n = 8Output: 0Explanation: 8 in binary is "1000".There aren't any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 5:

Input: n = 1Output: 0

Constraints:

1 <= n <= 109

分析

题目的意思是：求一个数二进制两个相邻1的最大距离，比如101的距离是2。思路也是很直接，把一个数变成二进制形式，然后遍历求最大值就行了。我用了两个循环。发现参-用了一个循环，即一个数的二进制形式不会超过32位，就遍历32次就行了。同时更新二进制的值，然后跟新最大值res，思路不错，学习一下。

代码

class Solution: def binaryGap(self, n: int) -> int: ones=[] while(n>0): t=n%2 ones.append(t) n=n//2 ones.reverse() l=0 res=0 for i in range(len(ones)): if(ones[i]==1): res=max(i-l,res) l=i return res

参考文献

​​solution​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。