1 题目描述
题目来源: https://leetcode-cn.com/problems/binary-gap/
给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。
如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。
2 解题思路与代码
2.1 原始解决方法: BinaryString+游标
2.1.1 思路
step0 边界条件: 10^9 < int型(Java)的最大值(21,4748,3647)
step1 Int型输入参数n转二进制字符串binaryStr
方法1：可利用Java基本数据类型包装类的内置函数 dataType.toBinaryString(val)
方法2：手写进制转码程序
step2 设置2个对binaryStr从左到右遍历的游标startIndex、currentIndex，并最终筛选出【最大跨步长度值】maxLengthValue；
startIndex(开始游标)： 跨步的开始下标
向后滑动/变更的条件:当前的【跨步(Gap)】刚计算完成时: 即 currentIndex(endIndex) 遇到 1 的时候
currentIndex(当前游标)：不停向后滑动的游标 or 作为跨步的结束下标
2.1.2 源码(Java)
class Solution {
public int binaryGap(int n) {
String binaryStr = Integer.toBinaryString(n);// int 转 二进制字符串
int maxLengthValue = -1;//[结果字段] 字符串Gap的最大长度值(初始值: 0 or -1)
int strLength = strLength=binaryStr.length(); // 字符串长度
int startIndex = 0;//开始游标。向后滑动/变更的条件:当前的【跨步(Gap)】刚计算完成时: 即 currentIndex(endIndex) 遇到 1 的时候
int currentIndex = 0;//当前游标。
while(currentIndex<strLength){
if(binaryStr.charAt(currentIndex) == '1') {
maxLengthValue = (currentIndex-startIndex)>maxLengthValue?(currentIndex-startIndex):maxLengthValue;
startIndex = currentIndex;
}
currentIndex++;//向后滑动
}
return maxLengthValue;
}
}
内存消耗太高，估计是：
Integer.toBinaryString(xx)函数所致
2.2 官方解决思路: 位运算 + 游标
官方解题思路: https://leetcode-cn.com/problems/binary-gap/solution/er-jin-zhi-jian-ju-by-leetcode-solution-dh2q/
2.2.1 思路
我们可以使用一个循环从 n 二进制表示的低位开始进行遍历，并找出所有的 1。
我们用一个变量 last 记录上一个找到的 1 的位置。
如果当前在第 i 位找到了 1，那么就用 i−last 更新答案，再将 last 更新为 i 即可。
在循环的每一步中，我们可以使用位运算 n & 1 获取 n 的最低位，判断其是否为 1。
在这之后，我们将 n 右移一位：n = n >> 1，这样在第 i 步时，n & 1 得到的就是初始 n 的第 i 个二进制位。
与思路1的区别
思路2：采用位运算，减少了转换位二进制的内存消耗，也减轻了判断
1是否来临的CPU资源运算压力运算方向（此因素无所谓）：思路2————从右向左滑动；思路1————从左向右滑动
last即 思路1中的startIndex
i即 思路1中的currentIndex
2.2.2 源码(Java)
class Solution {
public int binaryGap(int n) {
int last = -1, ans = 0;
for (int i = 0; n != 0; ++i) {
if ((n & 1) == 1) {
if (last != -1) {
ans = Math.max(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
}
}
or
class Solution {
public int binaryGap(int n) {
int last = -1;//设置为-1，是因为从右向左滑动，要避免 1000...00 这类 特殊情况
int maxGap = 0;
for(int i=0;n!=0;i++){
if((n&1) == 1){
if(last!=-1) {
maxGap = (i-last)>maxGap?i-last:maxGap;
}
last = i;
}
n = n>>1; // n继续向右移动1位
}
return maxGap;
}
}
Y 相关知识
Y.1 进制间转换 *
import java.util.Stack;
public class ConversionNumber {
//10进制数 转 K 进制
public static String transerToKNumber(int n, int k){
Stack stack = new Stack();
while(k<=n){
stack.push(n%k);
n = n/k;
}
stack.push(n);
StringBuilder resultStringBuilder = new StringBuilder();
while(!stack.empty()){
resultStringBuilder.append(stack.pop());
}
return resultStringBuilder.toString();
}
public static void main(String[] args) {
int n = 18; // 10进制数
int k = 2; // k 进制
System.out.println(transerToKNumber(n, k));//10010
}
}
Y.2 Java的包装类API
Y.3 Java的位运算 *
与 &
按位与&：若相对应位都为1，则为1，否则为0 “有假则假”
或 |
按位或|：若相对应位其中一个为1，则为1，否则为0 “有真则真”
异或 ^
按位异或^：若相对应位互不相同，则为1，否则为0 “相同为假，相异为真”
位右移 >>
位右移>>，符号不变: 二进制数向右移动指定位数，高位补相应0填充 “高位补0”；右移几位就除以2的几次方
位左移 <<
位左移<<:二进制数向左移动指定位数，低位补相应0填充 ”低位补0”；左移几位就乘以2的几次方
X 参考文献
868. 二进制间距 - Leetcode
