爱奇艺Java笔试题解

//最大字典子序列
//解题思路：例如一个字符串asdfghj，我们首先需要遍历一遍字符串，找到字典排序最大的s，
//然后接下来遍历dfghj，找到最大的j。此时j是最后一个字符，
//搜索结束，字典排序最大的子字符串即为sj。
public class AiQYI {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.next();
        char[] charArray = inputStr.toCharArray();
        int maxPos = 0;//记录最大的字符所在的位置
        StringBuffer sb = new StringBuffer();
        while (maxPos < charArray.length) {
            int maxVlue = Integer.MIN_VALUE;//记录本次遍历得到的最大字符
            for (int i = maxPos; i < charArray.length; i++) {
                if (charArray[i] > maxVlue) {
                    maxVlue = charArray[i];
                    maxPos = i;
                }
            }
            sb.append((char) maxVlue);
            maxPos++;
        }
        System.out.println(sb.toString());
    }
}

	

public class AiQYI2 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[3];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        int x = arr[0], y = arr[1], z = arr[2];
        if ((y - x) % 2 == 0) {
            System.out.println((y - x) / 2 + z - y);
        } else {
            int sum1 = z - y;
            int sum2 = z - x - sum1;// x使用了1,1以后和Z的差值
            if (sum2 % 2 == 0) {
                System.out.println(sum1 + sum2 / 2);
            } else {
                System.out.println(sum1 + sum2 / 2 + 2);
            }
        }
    }
}

	

public class AiQYI3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();// 颜色种类
        int m = scanner.nextInt();// 盒子放置m个糖果
        int[] l = new int[n];
        int[] r = new int[n];
        int least = 0;
        int[] avaliable = new int[n];// 表示每一种颜色剩余可以加的
        for (int i = 0; i < r.length; i++) {
            l[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
            least += l[i];
            avaliable[i] = r[i] - l[i];
        }
        int target = m - least; //dp[i][j]表示前i种糖果装满容量为j的背包的方法数。一定要用long，不然会爆，只能过70% long[][] dp = new long[n + 1][target + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;//初始化
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                for (int k = 0; k <= avaliable[i - 1]; k++) {
                    if (j - k >= 0)
                        dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        System.out.println(dp[n][target]);
    }
}