8.16 大疆笔试题(没参加,看别人复盘的题目写的)
题目来自:https://www.nowcoder.com/discuss/479182?channel=1009&source_id=home_feed
1. 第一题:图的路径问题。说是用dijkstra算法,听说过,不懂,后续可以去了解一下
有许多程序员都热爱玩游戏,而小J自称为游戏王,曾玩过几百种游戏,几乎所有能玩到的游戏大作都玩遍了。随着时间的推移,他发觉已经没有游戏可以让他玩了!于是他想改玩一些古老的游戏,以成为真正的“游戏王”。他希望在接下来的一段时间内将过去出的游戏全部玩一遍,但是毕竟时间有限,因此他感到很苦恼。于是他想到一个计划,他先将每个游戏标上一个成就值,同时对每个游戏都估算一个通关所需要的天数,他计划在未来X天内让自己玩游戏的成就达到最大,那么他应该怎么做计划呢?(假设每个游戏最多只计划玩一遍,而且每个游戏必须玩完通关才能取得成就值,且通关每个游戏最小时间单位是1天)
输入描述
第一行输入两个整数N和X,中间用空格隔开,其中N表示游戏的数目N(1<=N<=10),X表示计划玩游戏的总时间天数 (1<=X<=1000)。
第二行输入第1个游戏的成就值A1(0<=A1<=10000) 和 通关所需要花费时间B1天 (1<=Bi<=500) 中间用空格隔开。
第N+1行输入第N游戏的成就值An(0<=An<=10000) 和 通关所需要花费时间Bn天(1<=Bn<=500) 中间用空格隔开
输出描述
可以达到成就之和的最大值。
样例输入
2 2
10 1
20 2
样例输出
20
提示
输入样例二:
3 4
10 2
18 3
10 2
输出样例二:
20
2. 第二题
有许多程序员都热爱玩游戏,而小J自称为游戏王,曾玩过几百种游戏,几乎所有能玩到的游戏大作都玩遍了。随着时间的推移,他发觉已经没有游戏可以让他玩了!于是他想改玩一些古老的游戏,以成为真正的“游戏王”。他希望在接下来的一段时间内将过去出的游戏全部玩一遍,但是毕竟时间有限,因此他感到很苦恼。于是他想到一个计划,他先将每个游戏标上一个成就值,同时对每个游戏都估算一个通关所需要的天数,他计划在未来X天内让自己玩游戏的成就达到最大,那么他应该怎么做计划呢?(假设每个游戏最多只计划玩一遍,而且每个游戏必须玩完通关才能取得成就值,且通关每个游戏最小时间单位是1天)
输入描述
第一行输入两个整数N和X,中间用空格隔开,其中N表示游戏的数目N(1<=N<=10),X表示计划玩游戏的总时间天数 (1<=X<=1000)。
第二行输入第1个游戏的成就值A1(0<=A1<=10000) 和 通关所需要花费时间B1天 (1<=Bi<=500) 中间用空格隔开。
第N+1行输入第N游戏的成就值An(0<=An<=10000) 和 通关所需要花费时间Bn天(1<=Bn<=500) 中间用空格隔开
输出描述
可以达到成就之和的最大值。
样例输入
2 2
10 1
20 2
样例输出
20
提示
输入样例二:
3 4
10 2
18 3
10 2
输出样例二:
20
// 有限制条件,求最值,两组输入,游戏只能玩一次——0-1背包 import java.util.Scanner; public class Main{ public static void main(String[] args) { //有限制条件时间,两组输入求最值,背包问题 //每个游戏只能玩一次,0-1背包 Scanner sc = new Scanner(System.in); //数量 int num = sc.nextInt(); //限制条件:时间 int time = sc.nextInt(); //成就值 int[] values = new int[num]; //花费时间 int[] times = new int[num]; for(int i=0;i<num;i++){ values[i] = sc.nextInt(); times[i] = sc.nextInt(); } //背包 int[] dp = new int[time+1]; //0-1背包,从后往前遍历,外层遍历为数量,内层遍历为限制条件 for(int i=0;i<num;i++){ for(int j=time;j>=times[i];j--){ dp[j] = Math.max(dp[j],dp[j-times[i]] + values[i]); } } System.out.println(dp[time]); } }
3. 第三题
小C平时最喜欢玩数字游戏,最近他碰到一道有趣的数字题,他和他的好朋友打赌,一定能在10分钟内解出这道题,成功完成,小C就可以得到好朋友送他的Switch游戏机啦,你能帮助小C赢得奖品吗?
题目是这样的:给定一个非负的、字符串形式的整形数字,例如“12353789”,字符串的长度也就是整形数字的位数不超过10000位,并且字符串不会以0开头,小C需要挑选出其中K个数字(K小于字符串的长度)并删掉他们,使得剩余字符组成新的整数是最小的。
输入描述
第一行输入一串纯数字形式的字符串,组成一个正整数
第二行输入一个正整数K (K < 字符串的长度)
输出描述
输出一个数字(字符串格式)
样例输入
71245323308
4
样例输出
1223308
提示
输入样例二:
1683212
3
输出样例二:
1212
输入样例三:
100
1
输出样例三:
0
//学到了:如果要对字符串进行删减,可以先将字符串存到StringBuilder中。 //要对字符串进行删减,先预存到StringBuilder中,然后通过delete(start,end)或deleteCharAt(index)进行删减。主要问题在于通过while循环找到要删除的前一个字符的位置。 import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int count = sc.nextInt(); //还有考虑字符串后面有空字符的情况 if(count == 0 || count > str.length() || str == "" || str.trim() == ""){ System.out.println(str); } //k不能大于str的长度 if(count >= str.length()){ System.out.println("0"); } //使用StringBuilder进行delete,先存入str StringBuilder builder = new StringBuilder(str); while(count > 0){ int index = 0; //while循环排除不用删的字符:如果后一个字符大于等于当前字符,index++跳过当前 while(index < builder.length()-1 && builder.charAt(index) <= builder.charAt(index+1)){ index++; } //排除完之后,删除前一个 builder.deleteCharAt(index); count--; } //结果的开头不能为0,因此builder.charAt(0)=='0'需要全部移除 while(builder.length() != 0 && builder.charAt(0) == '0'){ builder.deleteCharAt(0); } System.out.println(builder.toString()); } }