Lintcode：182. 删除数字

描述

给出一个字符串 A, 表示一个 n 位正整数, 删除其中 k 位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。

找到删除 k 个数字之后的最小正整数。

N <= 240, k <= N

样例

给出一个字符串代表的正整数 A 和一个整数 k, 其中 A = 178542, k = 4

返回一个字符串 "12"

自己思路：采取的贪心策略如果前一个数大于后一个数，那么就把大的数删去，这样剩下的就是最小整数

    public String DeleteDigits(String A, int k) {int i = 1;StringBuilder sb = new StringBuilder(A);while (k > 0 && i < sb.length()){if (sb.charAt(i-1) > sb.charAt(i) && sb.charAt(i-1) != '0'){sb.replace(i-1,i,"");k--;i = 1;}elsei++;}if (k > 0)sb.delete(sb.length()-k, sb.length());while (sb.charAt(0) == '0'){sb.deleteCharAt(0);}return sb.toString();}

dalao思路：也是同样思路，但dalao写法更简洁

  public String DeleteDigits2(String A, int k) {// write your code here// use greedy algorithm// start from begining, delete k digits that is not in an increasing orderif(A == null || A.length() == 0){return "0";}if(k <= 0){return A;}StringBuilder sb = new StringBuilder(A);for(int i = 0; i < k; i++){int j;for(j = 0; j < sb.length() - 1 && sb.charAt(j) <= sb.charAt(j + 1); j++){}sb.delete(j, j + 1);}// delete all prefix "0"while(sb.length() > 1 && sb.charAt(0) == '0'){sb.delete(0, 1);}return sb.toString();}

summary：把限制数目的k作为遍历的硬指标，这样就会简洁很多