学步园

题目

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer. Make this new positive integers as small as possible.
N <= 240 and k <=N,
Example
Given an integer A = 178542, k = 4

return a string “12”

解题思路

1. 自己完成的解法是使用动态规划做的。dp[i][j] = Min(dp[i][j-1] , dp[i -1][j-1] + A[i]). 这里i表示已经选取的数的个数，j表示到当前位的数中能够选择的最小的数。完成代码后想了下，其实用动态规划确实有些浪费。
2. 网上解法：从要删除的数入手。第一个要删除的的数字，不是最大的数字，而是第一个A[i] > A[i+1] 的数，否则删除最后一个数本身的程序需要O(n*k)复杂度，使用栈优化后，复杂度变为O(n+k).
3. 看不懂网上的解法为什么数字0是可以保留在首位，如果首位为0再删除0，那么这样的话，就不满足题目中的删除K个数的意思了嘛？？？

解法一

public class Solution {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String A, int k) {
        String dp[][] = new String[A.length() - k][A.length()];
        for (String[] dp1 : dp)
            Arrays.fill(dp1, "");

        for (int i = 0; i < A.length() - k; i++) {
            for (int j = i; j < A.length(); j++) {
                if (i == 0) {
                    String ss = A.substring(j, j + 1);
                    if (j == 0 || (j > 0 && ss.compareTo(dp[i][j - 1]) < 0))
                    // if (j == 0 || (j > 0 && !ss.equals("0") && ss.compareTo(dp[i][j - 1]) < 0))
                        dp[i][j] = ss;
                    else
                        dp[i][j] = dp[i][j - 1];
                } else {
                    String x1 = dp[i - 1][j - 1] + A.substring(j, j + 1);
                    if (i == j || (j > i && dp[i][j - 1].compareTo(x1) > 0))
                        dp[i][j] = x1;
                    else
                        dp[i][j] = dp[i][j - 1];

                }
            }
        }

        String res = dp[A.length() - k - 1][A.length() - 1];
        while (res.startsWith("0")) {
            res = res.substring(1);
        }
        return res;
    }
}

解法二

public String DeleteDigits(String A, int k) {
        Stack<Integer> st = new Stack<Integer>();
        int popCount = 0;
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < A.length(); i++) {
            int num = (int) (A.charAt(i) - '0');
            if (st.isEmpty())
                st.push(num);
            else if (num >= st.peek()) {
                st.push(num);
            } else {
                if (popCount < k) {
                    st.pop();
                    i--;
                    popCount++;
                } else {
                    st.push(num);
                }
            }
        }
        while (popCount < k) {
            st.pop();
            popCount++;
        }
        while (!st.isEmpty()) {
            res.insert(0, st.pop());
        }
        while (res.length() > 1 && res.charAt(0) == '0') {
            res.deleteCharAt(0);
        }
        return res.toString();
    }