一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的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语言的实现大体一致,在此不再撰述。
代码如下: