好久不见各位,校招也算告一段落了,博主有很多收获和成长,希望有机会分享给大家,同时也欢迎大家把感悟分享给我哦!但是今天我只是来分享一下网易2018校园招聘的部分编程题的个人思路和代码实现。
first:魔法币
小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。
思路解析
博主觉得这道题可以说是斐波那契数列的变形题,本题要的到魔法币增加的途径主要有两个,要么是2*(x+1)-1,要么是2*(x+1),由这两个途径可知前者会让魔法币变为奇数,后者会让魔法币变为偶数,故要得到N个魔法币,可以判断N是否为偶数,如果是偶数则得到N个魔法币是通过途径二获得的,否则是通过途径一获得的,并用栈存储途径号码,然后继续进行判断,知道N等于0为止。最终栈中存储的元素依次pop出栈即为得到N个魔法币的投入方案。
代码实现
//魔法币 #include<iostream> using namespace std; #include<stack>stack<int> Select(long long money){stack<int> result;bool prev=0;while(money>0){if(money%2==0){//判断N是偶数//选择二号机result.push(2);money=money/2-1;}else{//判断N不是偶数result.push(1);money=(money-1)/2;} }return result; }int main(){long long money;cin>>money;if(money>=1&&money<=1000000000){stack<int> result=Select(money);while(!result.empty()){cout<<result.top();result.pop();}cout<<endl;}return 0; }
second:相反数
为了得到一个数的"相反数",我们将这个数的数字顺序颠倒,然后再加上原先的数得到"相反数"。例如,为了得到1325的"相反数",首先我们将该数的数字顺序颠倒,我们得到5231,之后再加上原先的数,我们得到5231+1325=6556.如果颠倒之后的数字有前缀零,前缀零将会被忽略。例如n = 100, 颠倒之后是1.
思路解析
博主觉得这题主要是考察对于整数各位数字拆分的掌握,即考察对于整数取整(/)和取余(%)的应用是否熟练。本题是求整数和该整数相反数的和。
用10做取整和取余的除数,综合来说是从整数的低位开始取各位的数字再依次乘10得到该整数的相反数,微观来看是先保存原整数,每次循环都把整数除以10取余的值tmp加上当前相反数*10的值构成新的相反数,然后整数除以10取整的新的整数,直到整数为0后停止循环,最后即可求得整数和该整数相反数的和。
代码实现
#include<iostream> using namespace std;//相反数 int IsOpposite(int n){int sum=0;//先存相反数的值//后存整数和该整数相反数的和int num=n;//做运算得到相反数的中间值while(num>0){int tmp=num%10;//存num除以10的余sum=sum*10+tmp;//当前相反数的值 num=num/10;//num取整}return sum+n;//整数和该整数相反数的和 }int main(){int n;cin>>n;if(n>=1 && n<100000){cout<<IsOpposite( n)<<endl;}return 0; }
third:字符碎片
一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,"aaabbaaac"是由下面碎片组成的:'aaa','bb','c'。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。
思路解析
本题主要是统计字符串个数和字符碎片的个数,二者相除即可得字符串的所有碎片的平均长度。
相同字母组成为同一碎片,所以用ch存储前一个字母,如果ch不等于当前字母,则字符碎片个数加1,最后字符串长度除以字符碎片的个数记为字符串的所有碎片的平均长度。
代码实现
法一
//字符碎片 #include<iostream> using namespace std; #include<string>float Avglen(string & str){float sum=0;int num=1;int size=str.size();char ch=str[0];for(int i=0; i<size; i++){if(ch != str[i]){num++;ch =str[i];}sum++;}return sum/num; }int main(){string str;cin>>str;if(str.size()>=1 && str.size()<=50){float result=Avglen( str);printf("%.2lf", result);}return 0; }
法二
#include<iostream> using namespace std; #include<string>float Avglen(const char* str){float sum=0;//用来存储字符串长度int num=1;//存储字符碎片个数char ch=*str;//前一个字符const char* tmp=str;while('\0' != *tmp){if(ch != *tmp){num++;ch =*tmp;}sum++;tmp++;}return sum/num; }int main(){string str;cin>>str;if(str.size()>=1 && str.size()<=50){float result=Avglen(str.c_str());printf("%.2lf", result);}return 0; }
fourth:重排是否符合要求
小易有一个长度为N的正整数数列A = {A[1], A[2], A[3]..., A[N]}。牛博士给小易出了一个难题:对数列A进行重新排列,使数列A满足所有的A[i] * A[i + 1](1 ≤ i ≤ N - 1)都是4的倍数。小易现在需要判断一个数列是否可以重排之后满足牛博士的要求。
思路解析
本题算是一个数学逻辑题呢,除了最后一个数不用和其他数相乘满足是4的倍数外,其他都需要满足此条件。
而要让两数积尽量是4的倍数,除了两数是2的倍数(左右必须是2的倍数或者4的倍数)和其中一个为4的倍数(左右可为任意数)外,没有其他更简单的可能了。所以综合来说如果能被2整除的数和能被4整除的数大于数组总数,则能满足所有的A[i] * A[i + 1](1 ≤ i ≤ N - 1)都是4的倍数的条件。
注:遇到此列问题,可例举不同的例子来寻找规律。
代码实现
//n-1个数能被2整除,至少有一个能被4整除 #include<iostream> using namespace std; #include<vector>long long aim[100000]={0};bool IsSuit(int n){int num=0;for(int i=0; i<n; i++){if(aim[i]%2 == 0){num++;if(aim[i]%4 == 0)num++;}}if(num>=n) return true;return false; }int main(){int t;cin>>t;int n;if(1<=t && t>=10){for(int i=0; i<t; i++){cin>>n;if(n<1 || n>100000) continue;for(int j=0; j<n; j++){cin>>aim[j];}if(IsSuit(n))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}}return 0; }
分享如上,望共同进步,交流学习,愿看文的朋友们都能得偿所愿,心想的事儿都能成!^_^