网易2017内推笔试编程题合集（二）

1、【*】[编程题] 混合颜料

你就是一个画家！你现在想绘制一幅画，但是你现在没有足够颜色的颜料。为了让问题简单，我们用正整数表示不同颜色的颜料。你知道这幅画需要的n种颜色的颜料，你现在可以去商店购买一些颜料，但是商店不能保证能供应所有颜色的颜料，所以你需要自己混合一些颜料。混合两种不一样的颜色A和颜色B颜料可以产生(A XOR B)这种颜色的颜料(新产生的颜料也可以用作继续混合产生新的颜色,XOR表示异或操作)。本着勤俭节约的精神，你想购买更少的颜料就满足要求，所以兼职程序员的你需要编程来计算出最少需要购买几种颜色的颜料？ 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

解读题目：就和线性代码里求线性方程组差不多，通过线性变换求极大线性无关组。而题目把“线性变换”改成了“异或变换”，原理是一样的，就是求一组能表示所有颜色的“基”，最后保留一个上三角矩阵。

题目转变为进行多次输入，每次输入n个数，将这些数之间进行多次异或操作，其中一个数可能被异或多次，看最后能剩余多少不重复的数，输出数量即可。

矩阵的秩定义：是其行向量或列向量的极大无关组中包含向量的个数。

秩求法：用初等行变换化成梯矩阵，梯矩阵中非零行数就是矩阵的秩。

 

1^1=0; 0^0=0;1^0=1; 0^1=1;

虽然不是理解的非常透彻，但是还是记住这种解题方式吧~

 

AC代码：

#include<iostream>
#include<vector>
#include<algorithm>
usingnamespace std;
//求一个数的二进制最高位是哪位
intgetHighBit(int num){
    int highbit=0;
    while(num){
        //将该数的二进制右移一位，等同于除以2
        num >>= 1;
        highbit++;
    }
    return highbit;
}
 
int main(){
    vector<int> colors;
    int n; //表示有n个数
    while(cin>>n){
        colors.clear();
        int result = 0;
        int i,tmp;
        for(i=0;i<n;i++){
            cin>>tmp;
            colors.push_back(tmp);
        }//输入
 
        //先将color从小到大排序
        sort(colors.begin(), colors.end());
        int bigger, smaller;
        //bigger始终指向最后一位
        //smaller始终指向倒数第二位
 
        //当只有两种颜色时，可退出循环，因为此时不可能有更少的情况了
        while(colors.size()>2){
            bigger = (int) (colors.size() - 1);
            smaller = bigger-1;
            // 如果两者的最高位相同，说明最高位可以消掉，
            // 将两者 xor ，或者说将矩阵两行相减消掉最高位
            if(getHighBit(colors[bigger]) ==getHighBit(colors[smaller])){
                tmp = colors[bigger] ^colors[smaller];
 
                //因为已将colors进行了排序，从后两位开始比较是比较的两个最大的数
                //而且最高位已被消除掉，所以xor得到的结果一定比这两个数小
 
                //如果tmp这个比比较的两个数都小的数都没有找到，则将tmp加入colors数组中，进行再次异或xor
                //异或得到的结果不在colors中时
                if(find(colors.begin(),colors.end(), tmp) == colors.end()){
                    colors.push_back(tmp);
                    sort(colors.begin(),colors.end());
                }
 
            }else{
                result++;
            }
 
            //出现else的情况是最大的那个数的最高位是1，而该位在smaller中是0，说明所有数的最高位已经只有bigger是1了。
            //这样它已经不可能被消掉了，结果+1
 
            //如果两个最大数的最高位可以消掉，那么消除之后，最大数已被消掉，没有用了
            //如果两个最大数的最高位不可以消掉，那么结果+1，最大数也没有用了。
            //弹出最大数
            colors.pop_back();
 
        }//while
        cout<<result+2<<endl;
 
    }//while
 
 
    return 0;
}

2、【*】[编程题] 幸运的袋子

一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1+ 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：题目可以转化为符合条件的集合真子集个数。每次从全集中选择若干元素（小球）组成子集（袋子）。结论：对于任意两个正整数a,b如果满足a+b>a*b，则必有一个数为1。下面来证明这个结论：设a=1+x, b=1+y，则1+x+1+y

>(1+x)*(1+y)，可推出1>x*y，则x,y必有一个为0，即a,b有一个为1。

推广到任意k个正整数，假设a1,a2,...ak，如果不满足给定条件，即和sum小于积pro，如果此时在选择一个数b，能使其满足sum+b>pro*b，则b必然为1，反之，如果选择的b>1，则sum+b<=pro*b，即a1,a2,...ak,b不满足给定条件。

 

因此，一开始就将球按标号升序排序。每次从小到大选择，当选择到a1,a2,...ak-1时满足给定条件，而再增加选择ak时不满足条件(ak必然大于等于max(a1,a2,...ak-1))，继续向后选择更大的数，必然无法满足。因此，可以进行剪枝。

如果有多个1，当k=1时，sum(1)>pro(1)不满足条件，但是下一个元素仍为1，则可以满足1+1>1*1，所以需要判断当前ak是否等于1。

 

c++代码：

#include<iostream>
#include<vector>
#include<algorithm>
usingnamespace std;
int n;  //表示n个数
vector<int>x;
 
int dfs(intindex, long long sum, long long pro){
    int i,res=0;
    for(i=index; i<n;i++){
        sum += x[i];
        pro *= x[i];
        if(sum>pro){
            res += 1+dfs(i+1, sum, pro);
        }else if(x[i] == 1){
            res += dfs(i+1, sum, pro);
        }else{
            break;
        }
        sum -= x[i];
        pro /= x[i];
        while(i<n-1 && x[i] ==x[i+1]){i++;}
    }
    return res;
}
 
 
int main(){
 
    while(cin>>n){
        int i,tmp;
        for(i=0;i<n;i++){
            cin>>tmp;
            x.push_back(tmp);
        }//for
 
        sort(x.begin(), x.end());
        cout<<dfs(0,0,1)<<endl;
 
    }//while
    return 0;
}

3、[编程题] 不要二

二货小易有一个W*H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。
对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:
( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根
小易想知道最多可以放多少块蛋糕在网格盒子里。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：一开始拿到题目时，别慌，分析一下。发现当欧几里得距离等于2的时候，只有(x1-x2)=2或-2&& (y1-y2)=0和(x1-x2)=0 && (y1-y2)=2或-2的时候。那我们只要遍历一遍所有的格子即可，用二维数组ground来标记是否已经遍历过和不能放的情况，0表示可以放蛋糕，1表示不能放蛋糕。从[0][0]位置开始，当ground[i][j]=0时，计数count加一，把[i][j]位置置为1，并且[i+2][j]、[i-2][j]、[i][j-2]、[i][j+2]这四个位置如果是合法也置为1。最后输出count即可。

 

c++代码：

#include<iostream>
usingnamespace std;
intground[1002][1002];
int w,h;  //长和宽
 
//判断x,y是否在范围内
bool isOk(intx, int y){
    return (x>=0 && y>=0&& x<w && y<h);
}
 
int main(){
 
    while(cin>>w>>h){
        int i,j;
 
        //给每个格子初始化为0
        for(i=0;i<w;i++){
            for(j=0;j<h;j++){
                ground[i][j] = 0;
            }
        }//for
 
        int count=0;
        for(i=0;i<w;i++){
            for(j=0;j<h;j++){
                if(ground[i][j] == 0){
                    count++;
                    ground[i][j] = 1;
                    if(isOk(i-2, j)){
                        ground[i-2][j] = 1;
                    }
                    if(isOk(i+2, j)){
                        ground[i+2][j] = 1;
                    }
                    if(isOk(i, j-2)){
                        ground[i][j-2] = 1;
                    }
                    if(isOk(i, j+2)){
                        ground[i][j+2] = 1;
                    }
                }
            }
        }
        cout<<count<<endl;
 
    }//while
    return 0;
}

4、[编程题] 解救小易

有一片1000*1000的草地，小易初始站在(1,1)(最左上角的位置)。小易在每一秒会横向或者纵向移动到相邻的草地上吃草(小易不会走出边界)。大反派超超想去捕捉可爱的小易，他手里有n个陷阱。第i个陷阱被安置在横坐标为x_i ，纵坐标为y_i 的位置上，小易一旦走入一个陷阱，将会被超超捕捉。你为了去解救小易，需要知道小易最少多少秒可能会走入一个陷阱，从而提前解救小易。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：只要算出所有陷阱到[1][1]位置的距离，取最小距离即可。

 

c++代码：

#include<iostream>
#include<vector>
#include<limits.h>
#include<cmath>
usingnamespace std;
 
int main(){
    int n; //表示有n个陷阱
    while(cin>>n){
        vector<int> x;
        vector<int> y;
        int i,j,tmp;
        for(i=0;i<n;i++){
            cin>>tmp;
            x.push_back(tmp);
        }
        for(i=0;i<n;i++){
            cin>>tmp;
            y.push_back(tmp);
        }
 
        //初始从[1][1]出发
        int res=INT_MAX;
        for(i=0;i<n;i++){
            tmp = (int) (fabs(x[i] - 1) +fabs(y[i] - 1));
            if(tmp<res){
                res = tmp;
            }
        }
        cout<<res<<endl;
    }//while
    return 0;
}

 

5、[编程题] 统计回文

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：
* 在A的第一个字母之前: "baba" 不是回文 
* 在第一个字母‘a’之后: "abba" 是回文 
* 在字母‘b’之后: "abba" 是回文 
* 在第二个字母'a'之后 "abab" 不是回文 
所以满足条件的答案为2 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

c++代码：

#include<iostream>
usingnamespace std;
 
boolisOk(string s){
    //判断s是否是回文字符串
    int left=0,right=s.length()-1;
    while(left<right){
        if(s[left] != s[right]){
            return false;
        }else{
            left++;
            right--;
        }
    }//while
    return true;
}
 
int main(){
    string a,b; //输出把字符串B插入字符串A之后构成一个回文串的方法数
    while(cin>>a){
        cin>>b;
        int count=0;
        int i,len;
        len=a.length();
        for(i=0;i<=len;i++){
            string s; //表示新的字符串
            s = a.substr(0, i) + b +a.substr(i, len-i);
            if(isOk(s)){
                count++;
            }
        }//for
        cout<<count<<endl;
    }//while
    return 0;
}

6、[编程题] 饥饿的小易

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x_0。对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 * x + 3或者8 * x + 7。因为使用神秘力量要耗费太多体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置(比如：位置0，位置1,000,000,007，位置2,000,000,014等)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：

用哈希表存储已访问的点，使用队列存储待访问的点，bfs广度优先遍历

其中乘法可以用移位代替。

 

c++代码：

#include<iostream>
#include<map>
#include<queue>
usingnamespace std;
#define MOD1000000007LL
#define MAX100000
int main(){
    long long x;
    map<long long, long long> count;
    queue<long long> num;
    while(cin>>x){
        count.clear();
        num.push(x);
        long long tmp1,tmp2;
        count[x] = 1;
        while(!num.empty()){
            tmp1 = num.front();
            num.pop();
            //当队列非空时，循环
            if(tmp1 == 0){
                break;
            }
            if(count[tmp1]>MAX){
                continue;
            }
            tmp2 = (tmp1*4+3)%MOD;
            if(count.find(tmp2) ==count.end()){
                num.push(tmp2);
                count[tmp2] = count[tmp1]+1;
            }
            tmp2 = (tmp1*8+7)%MOD;
            if(count.find(tmp2) ==count.end()){
                num.push(tmp2);
                count[tmp2] = count[tmp1]+1;
            }
        }
       cout<<(num.size()?count[tmp1]-1:-1)<<endl;
 
    }//while
    return 0;
}

7、[编程题] 两种排序方法

考拉有n个字符串字符串，任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法： 1.根据字符串的字典序排序。例如：
"car" < "carriage" < "cats" <"doggies < "koala"
2.根据字符串的长度排序。例如：
"car" < "cats" < "koala" <"doggies" < "carriage"
考拉想知道自己的这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以需要你来帮忙验证。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

c++代码：

#include<iostream>
#include<vector>
#include<algorithm>
usingnamespace std;
int main(){
    int n; //n个字符串
    while(cin>>n){
        vector<string> str,tmp;
        string s;
        int i;
        int flag1=0;  //判断是否按字典序
        int flag2=0;  //判断是否按长度排序
        for(i=0;i<n;i++){
            cin>>s;
            str.push_back(s);
        }//输入
 
        tmp = str;
        sort(tmp.begin(), tmp.end());
        int len_tmp = str[0].length();
        for(i=1;i<n;i++){
            if(flag1 == 1 && flag2 ==1){
                break;
            }
            if(flag1 == 0 && str[i] !=tmp[i]){
                flag1 = 1;
            }
            if(flag2 == 0 &&len_tmp>str[i].length()){
                flag2 = 1;
            }
            len_tmp = str[i].length();
        }
        if(flag1 == 1 && flag2 == 1){
           cout<<"none"<<endl;
        }else if(flag1 == 0 && flag2 ==0){
           cout<<"both"<<endl;
        }else if(flag1){
           cout<<"lengths"<<endl;
        }else{
           cout<<"lexicographically"<<endl;
        }
    }//while
    return 0;
 
}

8、[编程题] 小易喜欢的单词

小易喜欢的单词具有以下特性：
1.单词每个字母都是大写字母
2.单词没有连续相等的字母
3.单词没有形如“xyxy”(这里的x，y指的都是字母，并且可以相同)这样的子序列，子序列可能不连续。
例如：
小易不喜欢"ABBA"，因为这里有两个连续的'B'
小易不喜欢"THETXH"，因为这里包含子序列"THTH"
小易不喜欢"ABACADA"，因为这里包含子序列"AAAA"
小易喜欢"A","ABA"和"ABCBA"这些单词
给你一个单词，你要回答小易是否会喜欢这个单词。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：对于三个条件，一个一个来判断，设置flag=0表示喜欢，flag=1表示不喜欢。用str存储输入的字符串。

（1）遍历一遍str，如果有一个字符是小写字母就将flag=1。

（2）在（1）的遍历过程中加入判断str[i]与str[i+1]是否相等，只要有一对相等的就将flag=1。

（3）在（1）的遍历过程中记录每个字母出现的次数，另外用一个字符串str1将str中出现次数大于1的字符取出来，组成新的str1。对于str1，设置两层循环，i从[0,len-4]，j从[i+1,len-3]，len是str1的长度。即每次取两个字符xy，然后从str1中下标[j+1,len-1]中去找是否还有xy，如果还有说明可以组成xyxy，将flag=1。否则循环完还没有的话，flag=0。

 

c++代码：

#include<iostream>
#include<cctype>
#include<cstring>
#include<map>
usingnamespace std;
 
int main(){
    string str;
    while(cin>>str){
        int len= (int) str.length();
        int i,j,flag=0;  //flag=0喜欢，flag=1不喜欢
        map<char, int> cnt;
        for(i=0;i<len;i++){
            //1.喜欢每个单词都是大写字母
            if(islower(str[i])){
                flag=1;
                break;
            }
            //2.单词没有连续相等的字母
            if(i<len-1 && str[i] ==str[i+1]){
                flag=1;
                break;
            }
            cnt[str[i]] ++;
        }
 
        //将字符串中只出现一次的字符去掉。
        string str1 = "";
        if(!flag){
            string::iterator it;
           for(it=str.begin();it!=str.end();it++){
                if(cnt[*it] > 1){
                    str1+=*it;
                }
            }
 
            if(str1.length()>=4){
                string tmp="";
                len=str1.length();
                //此时的str是已经去掉了只出现一次字符的字符串了
                for(i=0;i<=len-4 &&!flag;i++){
                    for(j=i+1;j<=len-3&& !flag;j++){
                        tmp.push_back(str1[i]);
                        tmp.push_back(str1[j]);
                        if(str1.substr(j+1,len-j-1).find(tmp)!=string::npos){
                            flag=1;
                            break;
                        }
                    }
 
                }//for
            }//if
 
        }//if
 
        if(flag){
            //不喜欢
           cout<<"Dislikes"<<endl;
        }else{
           cout<<"Likes"<<endl;
        }
 
 
    }//while
    return 0;
 
}

9、[编程题] Fibonacci数列

Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

c++代码：

#include<iostream>
#include<vector>
#include<cmath>
usingnamespace std;
vector<int>fibo;
int main(){
    int n;
    fibo.push_back(0);
    fibo.push_back(1);
    while(cin>>n){
        int start=0;
        while(fibo[start]<=n){
            start++;
            if(start>=fibo.size()){
               fibo.push_back(fibo[start-1]+fibo[start-2]);
            }
        }//while
        if(start == 0){
            cout<<fabs(fibo[start]-n);
        }else{
            cout<<min(fabs(fibo[start]-n),fabs(fibo[start-1]-n));
        }
 
    }//while
    return 0;
}

10、[编程题] 数字游戏

小易邀请你玩一个数字游戏，小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来，然后你需要从这一系列数字中选取一部分出来让它们的和等于小易所说的数字。例如：如果{2,1,2,7}是你有的一系列数，小易说的数字是11.你可以得到方案2+2+7 = 11.如果顽皮的小易想坑你，他说的数字是6，那么你没有办法拼凑出和为6现在小易给你n个数，让你找出无法从n个数中选取部分求和的数字中的最小数。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

c++代码：

您的代码已保存

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

case通过率为90.00%

#include<iostream>
#include<vector>
usingnamespace std;
vector<int>x;
 
vector<vector<int>> res;
vector<int>ans;
 
void dfs(intstart, int sum, int target){
    //start表示从第start个数开始，sum是当前和，target为目标和
    if(sum == target){
        res.push_back(ans);
        return;
    }else if(sum>target){
        return;
    }else{
        for(int i=start; i<x.size();i++){
            ans.push_back(x[i]);
            dfs(i+1, sum+x[i], target);
            ans.pop_back();
        }
    }
 
}
 
bool judge(intn){
    //判断n是否可由x中的数组成
    res.clear();
    ans.clear();
    dfs(0, 0, n);
    if(res.size()>0){
        return true;
    }else{
        return false;
    }
}
 
int main(){
    int n; //n个数
    while(cin>>n){
        int i,tmp;
        for(i=0;i<n;i++){
            cin>>tmp;
            x.push_back(tmp);
        }//输入
        i=1;
        while(judge(i)){
            i++;
        }
        cout<<i<<endl;
    }//while
    return 0;
}

 

从网上看到的一个巧妙的解法：

思路：将 sum(A0, An) 和 An+1 比较，如果sum小，而且和An+1之间存在gap（存在gap是指（An+1）-sum>=2），就说明sum和An+1之间存在一个最小的不能由n个数选取求和组成的数，否则不管sum和An+1连续或者比An+1大，都说明根据前n项求和计算能得到的区间覆盖当前值，可以继续向后check。注意当算到sum时，就已经可以获得1~sum之间所有的数了，所以后面的数必须是1~sum+1之间的数，如果后面的数是sum+2，那么显然此时得不到sum+1了。

 

AC代码：

#include<iostream>                              
#include<vector>
#include<algorithm>
usingnamespace std;
int main(){
    int n; //有n个数
    while(cin>>n){
        vector<int> x;
        int i,tmp;
        for(i=0;i<n;i++){
            cin>>tmp;
            x.push_back(tmp);
        }//for
 
        sort(x.begin(), x.end());  //从小到大排序
 
        int miss=0;
        for(i=0;i<n;i++){
            if(x[i]>miss+1){break;}
            miss += x[i];
        }
        cout<<miss+1<<endl;
 
    }//while
    return 0;
 
}