您的位置 首页 > 娱乐休闲

打基础之LeetCode算法题第36日:如何求二进制数相邻1的间距?

一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧,一开始就弄些重量级的,什么人工智能,机器学习的算法,还要有大量的数学以及优化的知识,小白们估计会很郁闷,当然我也不一定能做出来对吧。

我计划每题给出两种语言的解决方案,一种静态语言,一种动态语言。

我选择C语言和python,本来考虑Java,但是篇幅有限,有兴趣的朋友自己试试

LeetCode 868. 二进制间距(Binary Gap)

问题描述:

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

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

示例:

C语言实现:

首先我们观察不同整数的二进制形式,观察再对它们做某些数值操作的时候的的变化。

我们会发现当对一个整数进行左移位的时候,存在下面的规律:

即如果我们对一个数值进行左移会形成一系列新的数,我们只需要统计这些数中,一个奇数到相邻的另一个奇数之间的左移次数最大值为多少即可。

代码如下:

我们在对整数进行左移动的同时就可以统计次数。变量m用来统计可能的最大次数,变量c用来统计某一对相邻的奇数间左移的次数,所以对于不同的奇数对,c都要重置为0。

另外有更好的解法。只是依赖编译器。

以gcc编译器为例,我们有如下的解法:

我们用GCC内置函数__builtin_ffs()来求的最右边的1的位置。

第一次调用__builtin_ffs()主要是为了去除最右边的0,然后循环里面再次调用__builtin_ffs()获得的就是相邻1的间距了。

python语言的实现:

python的实现有很多种办法。比如我们可以将其转换成二进制字符串,用处理字符串的方式来处理。

这里我们的思路和上面C语言的实现大体一致,在此不再撰述。

代码如下:

责任编辑: 鲁达

1.内容基于多重复合算法人工智能语言模型创作,旨在以深度学习研究为目的传播信息知识,内容观点与本网站无关,反馈举报请
2.仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证;
3.本站属于非营利性站点无毒无广告,请读者放心使用!

“打基础之LeetCode算法题第36日如何求二进制数相邻1的间距,”边界阅读