入门算法题

鹿酒 2016/10/23 算法

本篇文章有三道题。

题不难，但是很有意思。

# 第一题·将功赎过

题目描述：

小赛是一名幸运的程序员。

虽然他成功帮助小朋友以最快时间夺回了狼堡，但是面试官却打算和他说拜拜了。

理由是——游戏天赋太高，有不s务正业、走火入魔的倾向QAQ……

尽管小赛很不能接受这个理由，可是却只能心灰意冷地吃下这个结果。

然而，在他即将走出门的时候，面试官给了幸运的小赛一个最后的机会。

原来，面试官的手机被他调皮的儿子小明用一个数字作为密码锁上了。

小明只记得这个数字的十进制范围是l~r，且这个数的二进制表示中恰有m个1，却不记得确切的数字了。

面试官可急坏了。这才有了小赛一个将功赎过的机会。

他想要让小赛算出，他最坏情况下，要试多少次密码才能确保打开手机呢？

请输出这个次数。

1.输入

输入仅一行，包含三个整数l,r,m，其中l,r表示这个数的十进制范围是l~r，m表示这个数的二进制表示中有m个1.

数据保证——

对于30%的测试点，0<=l<=r<=20，0<=m<=5，

对于70%的测试点，0<=l<=r<=1000，0<=m<=10，

对于100%的测试点，0<=l<=r<=2000000，0<=m<=24.

2.输出

输出一行，包含一个整数，表示面试官最坏情况下，要试多少次密码才能确保打开手机。

如果小明记错了（也就是不存在任何一个数满足），则输出"-1"（不含引号)。

解题思路：

1.根据题目给的条件，至少需要生命 l , r , m , count

四个变量，依次表示十进制时数字下限、数字上限、二进制时1的个数、成功次数。

2.所以我找到了for循环的条件：l < i < r ；还有成功的判定条件：数字是二进制时1的存在个数 == m 。

主要会用到的函数：toString(n);把数字转换成n进制，用字符串输出。

解题代码：

var line = read_line().split(" ");
var l = parseInt(line[0]),
 r = parseInt(line[1]),
    m = parseInt(line[2]);
var count=0;
for(var i = l;i <= r;i++){
 var B = i.toString(2);//把 l ~ r 中的值，转换成二进制
    for(var j = 0;j < B.length;j++){
      var num = 0; 
      if(B[j] == 1){
       num++;//统计二进制下 1 的个数
      }
    }
    if(num == m){//当1的个数与设定值一致，可能性+1
     count++;
    }
 if(count <= 0){
  count = -1;
 }
}

print(count);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

按照我的思路，写的代码经过检测，系统提示：所有测试数据正确率为20%！〒▽〒

问题在哪呢？既然逻辑没有错，那就是某些细节，比如效率低下或溢出之类的。

经过测试，我找到了新方式。

var line = read_line().split(" ");
var l = parseInt(line[0]),
    r = parseInt(line[1]),
    m = parseInt(line[2]);
var count = 0;
for(var i = l;i <= r;i++){
    var B = i.toString(2);
    var n = 0;//改动1
    for(var j = 0;j < B.length;j++){
      if(B[j] == 1){
          n++;
      }
    }
    if(n == m){
        count++;
    }
}
print(count ? count : -1);//改动2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这回，系统提示：所有测试数据正确率为80%！

我之前想的很可能正确。确实，缩减、优化语句可以提高正确率。可是还没到100%...

# 第二题·约会

题目描述：

Bob和Alice有个约会，一大早Bob就从点(0,0)出发，前往约会地点(a,b)。

Bob没有一点方向感，因此他每次都随机的向上下左右四个方向走一步。简而言之，如果Bob当前在(x,y)，那么下一步他有可能到达(x+1,y), (x-1,y), (x,y+1),(x,y-1)。

很显然，当他到达目的地的时候，已经很晚了，Alice早已离去。

第二天，Alice质问Bob为什么放她鸽子，Bob说他昨天花了s步到达了约会地点。

Alice怀疑Bob是不是说谎了。你能否帮她验证一下？

1.输入

输入三个整数a,b,s

2.输出

输出“Yes”，如果Bob可能用s步到达(a,b)；否则输出“No”，不需要输出引号。

解题思路：

题目很短，但是我刚开始看到的时候被绕进去了，就是没有找到题目的判定条件。
已知条件：X轴偏移量 = a；Y轴偏移量 = b；步数 = s。
根据题目隐藏的条件，我知道了：总步数至少等于X、Y轴偏移量之和。
很明显，这一个判定条件肯定不能完全筛选。再次阅读题目，还有一点需要注意：因为Bob存在着多走的现象，我们只需要判断他多走的路程是否符合往返（去+、回-）和等于0。那具体条件呢？多走的路程是否是偶数。
第一条：s-a-b >= 0;第二条：((s-a-b) & 1) == 0;
详细说明第二条：&运算把两侧的值转换成二进制进行运算（同1为1，否则为0）。

有一点需要说明：因为象限内可能有负值，所以需要给a,b取绝对值。用到了函数Math.abs(n);取n的绝对值。

解题代码：

var line = read_line().split(" ");
var a = Math.abs(line[0]),
 b = Math.abs(line[1]),
    s = parseInt(line[2]);
if(s-a-b>=0 && ((s-a-b)&1)==0){
 print("Yes");
}else{
 print("No");
}

1
2
3
4
5
6
7
8
9

完成率100%，Nice！

# 第三题·上台阶

题目描述：

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

注：规定从一级到一级有0种走法。

1.输入

输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40), 表示楼梯的级数。

2.输出

对于每个测试实例，请输出不同走法的数量。

解题思路：

1.已知条件：m，表示楼梯层数

2.条件很少，所以我第一个想到的是通过遍历从一层到当前层以内的每一层的总共可能性，但是这个很明显不对。

3.看了一下别人的答案，答案中通过回调的方法实现（跟斐波那契数列类似）。

4.但是我还是没看明白这是为什么，所以找到一个笨办法：一一列举，然后找规律。。。

5.规律找到了：0，1，2，3，5，8···。神似1，1，2，3，5，8···。

6.所以通过回调函数得到数组前两项之和即可。

解题代码：

function getCount(num){
 //先设置前两项
    if(num == 1){
     return 1;
    }
    if(num == 2){
     return 2;
    }
    //一般情况，求前两项和
    return getCount(num-1)+getCount(num-2);
}
//获得数据
var line;
var data[];
while(line = read_line()){
 data.push(line);
}
for(var i = 1;i < data.lenght;i++){
 print(getCount(data[i-1]));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

上面的题来自于赛码网

鹿酒的博客