6.最小新整数

梦想是能睡八小时的猪 / 2023-08-03 / 原文

【题目】
给定一个十进制正整数n(0<n<1000000000)，每个数位上数字均不为0。n的位数为m。

现在从m位中删除k位(0<k<m)，求生成的新整数最小为多少？

例如: n=9128456,k=2,则生成的新整数最小为12456。

【输入】
第一行t, 表示有t组数据；

接下来t行，每一行表示一组测试数据，每组测试数据包含两个数字n,k。

【输出】
t行，每行一个数字，表示从n中删除k位后得到的最小整数。

【输入样例】
2
9128456 2
1444 3
【输出样例】
12456
1

【思路】

1.每次删除第一个大于右边的数，让数组变成不单调递增序列，这样值最小（小的值在前面）

2.如果删除完了所有大于右边的数，那么从后往前删除最大的数即可

【代码】

 public static int[] coupons(int[] n, int[] k) {
        // 1.每次删除第一个大于右边的数，让数组变成不单调递增序列，这样值最小（小的值在前面）
        // 2.如果删除完了所有大于右边的数，那么从后往前删除最大的数即可
        int[] result = new int[n.length];
        // 遍历每一个输入的数
        for (int i = 0; i < n.length; i++) {
            // 将int按位转换成arraylist保存
            StringBuilder res = new StringBuilder();
            char[] temp = String.valueOf(n[i]).toCharArray();
            ArrayList<Integer> nums = new ArrayList<>();
            for (char c : temp) {
                nums.add((int) c - '0');
            }
            // 1.先删除比右边大的数，尝试让nums变成一个单调非递增的序列
            //  只要删除位数还大于零，就从头开始查找第一个大于右边的数
            while (k[i] > 0) {
                // 记录本次寻找到末尾找到大于右边的数
                int flag = 0;
                for (int j = 0; j < nums.size() - 1; j++) {
                    // 每次删除后，都从头开始找 找到了就删除，并修改待删除数，并将flag置1同时break
                    if (nums.get(j) > nums.get(j + 1)) {
                        nums.remove(j);
                        k[i]--;
                        flag = 1;
                        break;
                    }
                    // 如果遍历到结尾都没有找到比右边大的，那么已经是一个单调非递增了，直接从后往前依次删除最大的数即可
                    if (flag == 0) {
                        break;
                    }
                }
            }
            // 2.如果到这还有位数没删除完，说明单调非递增了，从后往前删除
            if (k[i] > 0) {
                while (k[i] > 0) {
                    nums.remove(nums.size() - 1);
                    k[i]--;
                }
            }
            // Arraylist拼接成Stringbuilder
            for (int c : nums) {
                res.append((char) (c + '0'));
            }
            // Stringbuilder转换成int保存
            result[i] = Integer.parseInt(res.toString());
        }
        return result;
    }