用进制转换 + 字符串巧解算法题

又刷了一份金山办公的卷子,金山的东西是真的简单,前端题两道题目触及到了我的知识盲区,每个盲区都写一篇笔记来记一下。

这篇笔记主要是对应的这个卷子的算法题,是我一下没有想到的操作,觉得有点意思。

题目

算法题这边是一个这样的题目,很简单:

计算一个整数的二进制表示中连续出现1最多的次数。
比如13的二进制是:1101,那么他的二进制表示中连续出现的1最多为2次,所以答案就是2。

看到这个问题我的第一反应是短除法,写了个这样的东西出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while(line = readline()) {
let i = parseInt(line);
let max_count = 0;
let count = 0;
while (i != 1) {
if (i % 2 == 1) {
count++;
} else {
if (count > max_count){
max_count = count;
}
count = 0;
}
i = Math.floor(i / 2);
}
count++;
if (count > max_count){
max_count = count;
}
print(max_count);
}

但如果是在JavaScript下,其实有更加方便的解决方案(不一定更快) —— 直接转成二进制,而后用正则做匹配。

进制转换

在JavaScript里面,进制转换是一个基本技能,方法如下:

1
2
var num = parseInt(line);
num = num.toString(2);

上面的代码就把一个十进制的num转换成了二进制,以字符串存储,任何的数字都可以通过toString方法,给它传参数,转换成二进制。

对于得到的东西,用正则匹配/1+/g里面的连续的1,得到各种连续1的数组,然后取里面最长的一个就行了。

小结

这个解法确实是利用了JavaScript的优势,但是感觉有一点把简单的问题复杂化,其实最根本的短除法就可以很好地解决问题,对于任意进制这个题目也有解。

但是对于一些可能会出现的更复杂的题目,利用进制转换 + 字符串处理或许是一个不错的思路。