招商银行信用卡2018春季招聘研发(第二批)编程题

题目一

从非负整数序列0,1,2,...,n中给出包含其中n个数的子序列，请找出来未出现在该子序列中的那个数。、

输入描述：

输入为n+1个非负整数，用空格分开。

其中：首个非负整数序列的最大值n，后面的n个数字为子序列中包含的数字。

输出描述：

输出为1个数字，即未出现在子序列中的那个数。

代码

let line=readline().split(" ");
line=line.map(i=>parseInt(i));
let n=line.shift();
line.sort((a,b)=>a-b);
if(line[0]!=0) console.log("0");
for(let i=0;i<line.length-1;i++){
    if(line[i+1]-line[i]>1){
        console.log(line[i]+1);
    }
}

题目二

小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3中走法，分别是：

1.数轴上向前走一步，即n=n+1

2.数轴上向后走一步，即n=n-1

3.数轴上使劲跳跃到当前点的两倍，即n=2*n

现在小招喵在远点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？

输入描述：

小招喵想去的位置x

输出描述：

小招喵最少需的步数

解析

要用动态规划

主要注意的点就是条件的判断

如果dp[i+1]已经求出来了，那么dp[i]就是dp[i-1]和dp[i+1]的较小者+1

如果dp[i+1]没有求出来了，那么dp[i]就是dp[i-1]+1

代码

let x=readline();
x=parseInt(x);
if(x<0) x=-x;
let i=1,dp=[];
dp[0]=0;
while(i<=x){
    if(!dp[i]&&dp[i+1])
        dp[i]=Math.min(dp[i-1],dp[i+1])+1;
    else if(!dp[i]&&!dp[i+1]){
        dp[i]=dp[i-1]+1;
    }
    dp[2*i]=dp[i]+1;
    i++;
}
console.log(dp[x]);

题目三

如果一个正整数，它的质因数只包含2,3，和5，那么这个数满足条件。

同时，特别规定1也是满足条件的数字。

实例：前10个满足条件的数字是1,2,3,4,5,6,8,9,10,12.

请编写一个函数，返回第n个满足条件的数。

输入描述：

输入为n

输出描述：

输出为第n个满足条件的数

解析

还是要用动态规划，这是剑指offer上的原题，丑数那一题。

庆幸自己前段时间做了这题。

我一开始使用暴力解法，只达到了83%

后来使用了动态规划就AC了

代码

let n=readline();
n=parseInt(n);
function getNum(n){
    if(n<7) return index;
    let res=[];
    res[0]=1;
    let t2=0,t3=0,t5=0;
    for(let i=1;i<n;i++){
        res[i]=Math.min(...[res[t2]*2,res[t3]*3,res[t5]*5]);
        if(res[i]==res[t2]*2) t2++;
        if(res[i]==res[t3]*3) t3++;
        if(res[i]==res[t5]*5) t5++;
    }
    return res[n-1];
}
console.log(getNum(n));