飞道的博客

7道腾讯算法编程真题，你能做对几道？包含一道趣味题

2021-04-17 14:07 255人阅读  评论(0)

       1、生成格雷码

       在一组数字的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码(GrayCode)，请编写一个函数，使用递归的方法生成N位的格雷码。给定一个整数n，请返回n位的格雷码，顺序从0开始。

importjava.util.Scanner;

publicclassMain{

	publicstaticvoidmain(String[]args){
		Scannersc=newScanner(System.in);
		while(sc.hasNext()){
			intk=sc.nextInt();
			String[]gelei=studyenglish(k);
			StringBuildersb=newStringBuilder();
			for(inti=0;i<gelei.length;i++){
				if(i==0){
					sb.append("[");
				}
				sb.append('"');
				sb.append(gelei[i]);
				if(i==gelei.length-1){
					sb.append('"');
					sb.append("]");
				}else{
					sb.append('"');
					sb.append(',');
				}
			}
			System.out.println(sb.toString());
		}
		sc.close();
	}

	publicstaticString[]studyenglish(intk){
		String[]strings=newString[(int)Math.pow(2,k)];
		if(k==1){
			strings[0]="0";
			strings[1]="1";
			returnstrings;
		}else{
			String[]result=studyenglish(k-1);
			for(inti=0;i<result.length;i++){
				strings[i]="0"+result[i];
				strings[strings.length-1-i]="1"+result[i];
			}
		}
		returnstrings;
	}
}

       2、微信红包

       春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半，请帮小明找到该红包金额。给定一个红包的金额数组gifts及它的大小n，请返回所有红包的金额。若没有金额超过红包总数的一半，返回0。

       测试样例：[1,2,3,2,2],5 返回：2

importjava.util.*;

publicclassGift{
publicintgetValue(int[]gifts,intn){
//writecodehere
	intans=gifts[0];
	intcount=1;
	for(inti=0;i<gifts.length;i++){
		if(gifts[i]!=ans){
		count--;
		}else
		count++;
		if(count==0){
			count=1;
			ans=gifts[i];
		}
}
		count=0;
		for(intg:gifts){
		if(g==ans)
				count++;
		else
		count--;
		}
		returncount>0?ans:0;
		}
}

       3、编码

       假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的index为0，aa的index为1，aaa的index为2，以此类推。编写一个函数，输入是任意一个编码，输出这个编码对应的index。

       输入描述：输入一个待编码的字符串,字符串长度小于等于100。
       输出描述：输出这个编码的index。

importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;

publicclassMain{

publicstaticvoidmain(String[]args)throwsIOException{
	BufferedReaderreader=newBufferedReader(newInputStreamReader(System.in));
	Stringstr;
	while((str=reader.readLine())!=null){
		char[]chars=str.trim().toCharArray();
		inttemp=0,sum=0;
		for(inti=0;i<4;i++){
				temp*=25;
				if(i<chars.length){
				temp+=chars[i]-'a';
		}
		sum+=temp;
		if(i<chars.length-1){
			sum+=1;
			}
		}
		System.out.println(sum);
		}
	}
}

       4、游戏任务标记

       游戏里面有很多各式各样的任务，其中有一种任务玩家只能做一次，这类任务一共有1024个，任务ID范围[1,1024]。请用32个unsignedint类型来记录这1024个任务是否已经完成（初始状态都是未完成）。输入两个参数，都是任务ID，需要设置第一个ID的任务为已经完成；并检查第二个ID的任务是否已经完成。输出一个参数，如果第二个ID的任务已经完成输出1，如果未完成输出0。如果第一或第二个ID不在[1,1024]范围，则输出-1。

importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;
importjava.lang.Math;
publicclassMain{
privatestaticint[]s=newint[32];
privatestaticinttestId(intset,intcheck){
//ID检查
if(set>1024||check>1024){
	return-1;
}
//index为int数组的下标（0~31）bit为int变量的第几位（0~31）例如1--s[1]=2^31
intset_index=(set-1)/32;
intset_bit=set%32;
intcheck_index=(check-1)/32;
intcheck_bit=32*(check_index+1)-check;
//设置第一个ID任务完成
s[set_index]=s[set_index]|(int)Math.pow(2,set_bit);
//检查第二个任务是否完成
if((s[check_index]&(int)Math.pow(2,check_bit))!=0){
	return1;
	}
	else{
	return0;
	}
}
publicstaticvoidmain(String[]args)throwsIOException{
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
String[]str=br.readLine().split("");
intset=Integer.parseInt(str[0]);
intcheck=Integer.parseInt(str[1]);
System.out.println(testId(set,check));
	}
}

       5、素对数

       给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。如输入为10,程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）。

importjava.util.*;
importjava.io.*;

publicclassMain{
	publicstaticvoidmain(String[]args)throwsIOException{
	BufferedReaderbeader=newBufferedReader(newInputStreamReader(System.in));
	inttarget=Integer.parseInt(beader.readLine());//获取到输入的数
	int[]numbs=newint[target];
	intcount=0;
	intresult=0;
	for(inti=2;i<target;i++){
		intjudge=0;
		for(intj=2;j<i;j++){
			if(i%j==0){
			judge=1;
			break;
		}
}
	if(judge==0){
	numbs[count]=i;
	count++;
	}
}
	for(inti=0;i<count-1;i++){
		for(intj=i;j<count;j++){
			if((numbs[i]+numbs[j])==target){
				result++;
				break;
			}
		}
}
System.out.println(result);
	}
}

       6、数字转换机

       小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：
       当按下了红色按钮，两个数字同时加1。
       当按下了蓝色按钮，两个数字同时乘2。
       小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

       输入描述：输入包括一行，一行中有四个正整数a，b，A，B，（1≤a，b，A，B≤10^9）。
       输出描述：如果小Q可以完成转换，输出最少需要按动按钮的次数，否则输出-1。

importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;

publicclassMain{
	publicstaticvoidmain(String[]args)throwsIOException{
		BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
		String[]str=br.readLine().split("");
		inta=Integer.parseInt(str[0]);
		intb=Integer.parseInt(str[1]);
		intA=Integer.parseInt(str[2]);
		intB=Integer.parseInt(str[3]);

	System.out.println(solution(a,b,A,B));

}

privatestaticintsolution(inta,intb,intA,intB){
	if(a==A&&b==B)
	return0;
	elseif(a!=A&&b==B)
	return-1;
	elseif(a==A&&b!=B)
	return-1;
	elseif(a>A||b>B)
	return-1;

if((A&1)==0&&(B&1)==0){
	intres=solution(a,b,A/2,B/2);
	if(res==-1)
	return-1;
	returnres+1;
	}
	else{
		intres=solution(a,b,A-1,B-1);
		if(res==-1)
		return-1;
		returnres+1;
		}
	}
}

       7、趣味题

       小Q在学习许多排序算法之后灵机一动决定自己发明一种排序算法，小Q希望能将n个不同的数排序为升序。小Q发明的排序算法在每轮允许两种操作：
       1、将当前序列中前n-1个数排为升序
       2、将当前序列中后n-1个数排为升序
       小Q可以任意次使用上述两种操作，小Q现在想考考你最少需要几次上述操作可以让序列变为升序。

publicclassMain{
	publicstaticvoidmain(String[]args){
	System.out.print(2);
	}
}

关注我，后续内容更精彩～


转载：https://blog.csdn.net/xDroid_linzhuo/article/details/115655896
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场