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. 第二题

// 有限制条件，求最值，两组输入，游戏只能玩一次——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());
    }
}