Java面试题:总括几个字符串中整数的个数

外人家的面试题:计算“1”的个数

2016/05/27 · JavaScript
· 5 评论 ·
Javascript,
算法

正文笔者: 伯乐在线
十年踪迹
。未经小编许可,禁绝转发!
接待插手伯乐在线 专栏审核人

小胡子哥 @Barret李靖
给自个儿引进了叁个写算法刷题的地点
leetcode.com,没有 ACM
那么难,但难点很有意思。并且传闻那一个难点都来源于一些铺面的面试题。好呢,解解外人公司的面试题其实很有趣,不仅能收拾思路训练才干,又不用思量漏题
╮(╯▽╰)╭。

长话短说,让大家来看一道题

面试之中问到了二个算法:在三个字符串中,总计现身的子弹头的个数,一而再三番两次的数字为叁个整数(不考虑负数),字符串中不带有空格。作者是用Java完毕的。

统计“1”的个数

给定三个非负整数 num,对于放肆 i,0 ≤ i ≤ num,总计 i
的值对应的二进制数中 “1” 的个数,将这几个结果再次回到为贰个数组。

例如:

当 num = 5 时,重临值为 [0,1,1,2,1,2]。

/** * @param {number} num * @return {number[]} */ var countBits =
function(num) { //在这里处实今世码 };

1
2
3
4
5
6
7
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
    //在此处实现代码
};
/**
* a10b20c30de40fg
* 思路:首先要遍历所有的字符,判断每个字符是不是数字,是数字的话就把它放在一个StringBuilder对象
* 里面并标记,下面一个字符要是数字就加在后面,不是数字的话,就把当前的StringBuilder里面的数字
* 塞到list里面,最后判断list长度即可
*/

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String s = scanner.next();
    scanner.close();    
    if (s != null && s.length() != 0) {
        List<Integer> list = new ArrayList<Integer>();
        StringBuilder sb = new StringBuilder();
        boolean isChar = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                sb.append(s.charAt(i));
                if (i == s.length() - 1) {
                    list.add(Integer.parseInt(sb.toString()));
                    sb.setLength(0);
                }
                isChar = false;
            } else {
                if (sb.length() > 0 && isChar == false) {
                    list.add(Integer.parseInt(sb.toString()));
                    sb.setLength(0);
                }
                isChar = true;
            }
        }
        System.out.println(list.size());        
    }
}

解题思路

那道题咋生龙活虎看还挺轻松的,无非是:

  • 兑现多个格局 countBit,对大肆非负整数
    n,总括它的二进制数中“1”的个数
  • 循环 i 从 0 到 num,求 countBit(i),将值放在数组中回到。

JavaScript中,计算 countBit 能够取巧:

function countBit(n){ return n.toString(2).replace(/0/g,””).length; }

1
2
3
function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}

上边的代码里,我们平昔对 n 用 toString(2)
转成二进制表示的字符串,然后去掉在那之中的0,剩下的就是“1”的个数。

下一场,大家写一下完完全全的先后:

版本1

function countBit(n){ return n.toString(2).replace(/0/g,”).length; }
function countBits(nums){ var ret = []; for(var i = 0; i <= nums;
i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
function countBit(n){
   return n.toString(2).replace(/0/g,”).length;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面这种写法拾贰分得益,好处是 countBit 利用 JavaScript
语言特色完成得特别简练,坏处是豆蔻梢头旦以后要将它改写成此外语言的本子,就有超级大可能率懵B了,它不是很通用,并且它的属性还决定于Number.prototype.toString(2) 和 String.prototype.replace 的兑现。

就此为了追求更加好的写法,大家有必要思虑一下 countBit 的通用实现法。

咱俩说,求二个莫西干发型的二进制表示中 “1” 的个数,最普通的本来是叁个 O(logN)
的措施:

function countBit(n){ var ret = 0; while(n > 0){ ret += n & 1; n
>>= 1; } return ret; }

1
2
3
4
5
6
7
8
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}

为此我们有了版本2

如此完毕也很简单不是吗?不过那样完成是不是最优?建议此处思考10分钟再往下看。


比如借使换个问法也是千篇后生可畏律的,总括一个字符串中现身整数的和,只要求在上边步向四个遍历list,把富有的数字加一齐就好了。

更快的 countBit

上一个本子的 countBit 的大运复杂度已是 O(logN)
了,难道仍为能够更加快吗?当然是能够的,大家无需去看清每一个人是或不是“1”,也能掌握n 的二进制中有多少个“1”。

有二个门槛,是基于以下二个定律:

  • 对此自由 n, n ≥ 1,犹如下等式创立:

countBit(n & (n – 1)) === countBit(n) – 1

1
countBit(n & (n – 1)) === countBit(n) – 1

以此比较轻巧驾驭,我们只要想转手,对于自由 n,n – 1 的二进制数表示正好是 n
的二进制数的最末贰个“1”退位,由此 n & n – 1 正好将 n
的最末壹个人“1”消去,举个例子:

  • 6 的二进制数是 110, 5 = 6 – 1 的二进制数是 101,6 & 5
    的二进制数是 110 & 101 == 100
  • 88 的二进制数是 1011000,87 = 88 – 1 的二进制数是
    1010111,88 & 87 的二进制数是 1011000 & 1010111 == 1010000

于是乎,我们有了多少个更加快的算法:

版本3

function countBit(n){ var ret = 0; while(n > 0){ ret++; n &= n – 1; }
return ret; } function countBits(nums){ var ret = []; for(var i = 0; i
<= nums; i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret++;
        n &= n – 1;
    }
    return ret;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面的 countBit(88) 只循环 3 次,而“版本2”的 countBit(88) 却要求循环
7 次。

优化到了这么些程度,是还是不是总体都甘休了吗?从算法上来讲宛如早就是十二万分了?真的吗?再给大家30 秒时间思索一下,然后再往下看。


if (list.size() > 0) {
    int sum = 0;
    for (int i = 0; i < list.size(); i++) {
        sum = sum + list.get(i);
    }
    System.out.println(sum);
}

countBits 的小时复杂度

考虑 countBits, 上边的算法:

  • “版本1” 的日子复杂度是 O(N*M),M 决意于 Number.prototype.toString
    和 String.prototype.replace 的复杂度。
  • “版本2” 的岁月复杂度是 O(N*logN)
  • “版本3” 的时间复杂度是 O(N*M),M 是 N 的二进制数中的“1”的个数,介于
    1 ~ logN 之间。

上面四个本子的 countBits 的岁月复杂度都高于 O(N)。那么有未有的时候间复杂度
O(N) 的算法呢?

实际上,“版本3”已经为大家提示了答案,答案就在上边的非常定律里,作者把相当等式再写贰遍:

countBit(n & (n – 1)) === countBit(n) – 1

1
countBit(n & (n – 1)) === countBit(n) – 1

也等于说,假设大家了然了 countBit(n & (n - 1)),那么大家也就精晓了
countBit(n)

而我们清楚 countBit(0) 的值是 0,于是,大家得以很简单的递推:

版本4

function countBits(nums){ var ret = [0]; for(var i = 1; i <= nums;
i++){ ret.push(ret[i & i – 1] + 1); } return ret; }

1
2
3
4
5
6
7
function countBits(nums){
   var ret = [0];
   for(var i = 1; i <= nums; i++){
       ret.push(ret[i & i – 1] + 1);
   }
   return ret;
}

本来就那样简单,你想到了呢 ╮(╯▽╰)╭

如上正是全部的原委,轻便的难点思虑起来很风趣吗?程序猿就应有追求康健的算法,不是吧?

那是 leetcode
算法面试题连串的率刚开始阶段,下意气风发期大家谈谈别的黄金年代道题,那道题也很有意思:判别几个非负整数是还是不是是
4 的整数十次方
,别告诉作者你用循环,想想更抢眼的艺术吧~

打赏协助自身写出更加多好作品,谢谢!


打赏小编

打赏支持作者写出越来越多好文章,谢谢!

任选意气风发种支付办法

图片 1
图片 2

3 赞 8 收藏 5
评论

有关小编:十年踪迹

图片 3

月影,奇舞蹈艺术团司令员,热爱前端开垦,JavaScript
技师范大学器晚成枚,能写代码也能打杂卖萌说段子。
个人主页
·
笔者的篇章
·
14
·
    

图片 4

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图