别人家的面试题:统计“1”的个数

别人家的面试题:统计“1”的个数

2016/05/27 · JavaScript
· 5 评论 ·
奥门威尼斯网址,Javascript,
算法

本文作者: 伯乐在线 –
十年踪迹
。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者。

小胡子哥 @Barret李靖
给我推荐了一个写算法刷题的地方
leetcode.com,没有 ACM
那么难,但题目很有趣。而且据说这些题目都来源于一些公司的面试题。好吧,解解别人公司的面试题其实很好玩,既能整理思路锻炼能力,又不用担心漏题
╮(╯▽╰)╭。

长话短说,让我们来看一道题:

面试之中问到了一个算法:在一个字符串中,统计出现的整数的个数,连续的数字为一个整数(不考虑负数),字符串中不包含空格。我是用Java实现的。

统计各类字符个数,统计字符个数

 1 //题目:输入一行字符,分别统计其中英文字母、空格、数字和其它字符的个数
 2 //程序分析:利用while语句,条件为输入的字符不为'\n'。
 3 
 4 #include<stdio.h>
 5 
 6 int main()
 7 {
 8     char c;
 9     int letters = 0, spaces = 0, digits = 0, others = 0;
10     printf("Please input some characters\n");
11     while( (c=getchar()) != '\n' )
12     {
13         if( (c>='a'&&c<='z') || (c>='A'&&c<='Z') )
14             letters++;
15         else if( c>='0'&&c<='9' )
16             digits++;
17         else if( c==' ' )
18             spaces++;
19         else
20             others++;
21     }
22     printf("letters=%d,digits=%d,spaces=%d,others=%d\n", letters, digits, spaces, others);
23     return 0;
24 }

 

1 //
题目:输入一行字符,分别统计其中英文字母、空格、数字和其它字符的个数 2
// 程序分析:利用…

2017/04/24
很简单
%s/test/&/gn(回车)

 

统计“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());        
    }
}

1040 统计单词个数

 

2001年NOIP全国联赛提高组

 时间限制: 1
s

 空间限制: 128000
KB

 题目等级 : 黄金
Gold

题解

 

 

 

题目描述 Description

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)(管理员注:这里的不能再用指的是位置,不是字母本身。比如thisis可以算做包含2个is)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。

输入描述 Input Description

第一行为一个正整数(0<n<=5)表示有n组测试数据
每组的第一行有二个正整数(p,k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行,每行均有20个字符。
再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)
接下来的s行,每行均有一个单词。

输出描述 Output Description

每行一个整数,分别对应每组测试数据的相应结果。

 

样例输入 Sample Input

1
1 3
thisisabookyouareaoh
4
is
a
ok
sab

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

this/isabookyoua/reaoh

解题思路

这道题咋一看还挺简单的,无非是:

  • 实现一个方法 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,把所有的数字加一起就好了。

分类标签 Tags 点此展开 

 

划分型DP 动态规划 大陆地区 NOIP全国联赛提高组 2001年

AC代码:

/*
   题解: 
   把字符串ss[0..len-1]划分为k部分的最优值,需考虑
   把前i个字符划分成j个部分的最优值
   f(i,j) =Max{f(i-x,j-1)+后x个字符中的单词个数}     (i>=j且x>=1,i-x>=j-1)
   即1<=x<i-j
   对于区间[ii..jj]中含有的单词个数,逐个统计以s[kk](ii<=kk<=jj)开头的单词即可, 
 */
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 211
int n,p,k,s,f[N][41],len;
char ss[N],tt[N],w[41][N]; 
void first(){
    memset(f,0,sizeof(f));//养成清零好习惯 
    memset(w,0,sizeof(w));
    memset(tt,0,sizeof(tt));
    memset(ss,0,sizeof(ss));
    scanf("%d%d",&p,&k);
    len=0;
    for(int i=0;i<p;i++){
        scanf("%s",tt);
        for(int j=0;tt[j];j++){
            ss[len]=tt[j];len++;//字符串压栈 
        }
    }
    ss[len]='\0';
    scanf("%d",&s);//单词个数 
    for(int i=0;i<s;i++) scanf("%s",w[i]);//单词 
}
int dp(int x,int y){
    int ans=0,cur;
    for(int i=x;i<=y;i++){
        for(int j=0;j<s;j++){
            for(cur=0;w[j][cur];cur++) if(i+cur>y||w[j][cur]!=ss[i+cur]) break;
            if(w[j][cur]=='\0'){
                ans++;break;//判一下这串单词的最后一个 
            }    
        }
    }    
    return ans;
}
int main(){
    scanf("%d",&n);
    while(n--){
        first();
        for(int i=1;i<=len;i++) f[i][1]=dp(0,i-1);//初始化f 
        for(int j=2;j<=k;j++){//注意i j顺序 
            for(int i=j;i<=len;i++){
                for(int x=1;x<i-j;x++){//枚举分法 
                    int tmp=dp(i-x,i-1);
                    f[i][j]=max(f[i][j],f[i-x][j-1]+tmp);
                }
            }
        }  
        printf("%d\n",f[len][k]);          
    }
    return 0;
}

 

更快的 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

发表评论

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