小米OJ上分日记——（九）移除 K 位得到最小值
序号：#9
难度：困难
时间限制：500ms
内存限制：10M
描述
有一行由 N 个数字组成的数字字符串，字符串所表示的数是一正整数。移除字符串中的 K 个数字，使剩下的数字是所有可能中最小的。
假设：
字符串的长度一定大于等于 K
字符串不会以 0 开头
输入
一行由 N 个数字组成的数字字符串（0 < N < 20），和一个正整数 K（K < N），两个数据由空格隔开，如：1432219 3。
输出
移除 K 位后可能的最小的数字字符串。 如 1432219 移除 4, 3, 2 这 3 个数字后得到 1219，为所有可能中的最小值。
输入样例
1432219 3
10200 1
输出样例
1219
200
解析：该题如果用链表或数组做都可以，思路都是将其中相邻的k位取走比较剩下的数去最小值
数组方法：
/**
* 已引入：
* java.util.*
* 要使用其他 jar 包请使用完整路径，如：
* java.util.List> list = new java.util.ArrayList>(100);
* @param line 为单行测试数据
* @return 处理后的结果
*/
private static String solution(String line) {String[] str = line.split(" ");String str1 = str[0];int k = Integer.parseInt(str[1]);String top;//有歧义，其实是储存取走k位后剩下的值int[] topArr = new int[str1.length() - k+1];//储存所有剩下的值for (int i = 0; i < str1.length() - k+1; i++) {char[] c = str1.toCharArray();//输入的字符储存为数组for (int x = i; x < k + i; x++) {c[x] = ' ';//将k位去掉}top = "";for (int y = 0; y < c.length; y++) {if (c[y] != ' ') {top = top + c[y];}}topArr[i] = Integer.parseInt(top);}int min = topArr[0];int count = 0;for (int i = 1; i < topArr.length; i++) {if (min > topArr[i]) {min = topArr[i];count = i;}}return String.valueOf(topArr[count]);}
链表方法：
String solution(String line) {String a[] = line.split(" ");LinkedList<Integer> c = new LinkedList<Integer>();int num1 = a[0].length();int num2 = Integer.valueOf(a[1]);if(num1 <= num2)return String.valueOf(0);//如果删除的数与数的的长度相等，则返回0for(int i = 0;i<num1;i++){c.add(Integer.parseInt(String.valueOf(a[0].charAt(i))));//将所有数据插入链表}int re_num=0;for(int i = 0;i<c.size()&&re_num<num2;i++){if(c.get(i)>c.get(i+1)){c.remove(i);i = 0;re_num++;}}if(re_num<num2){for(int i = re_num;i<num2;i++){c.remove(0);}}while(c.getFirst()==0){c.remove(0);}String result = "";for(int i = 0;i<c.size();i++){result+=String.valueOf(c.get(i));}return result;}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！