题目描述：
*验证卡布列克运算。即：任意一个四位数，只要它们各个位上的数字是不全相同的，就有这样的规律：
（1）将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；
（2）将组成该四位数的四个数字由小到大排列，形成由这四个数字构成的最小的四位数（如果四个数字中含有0，则得到的数不足四位）；
（3）求两个数的差，得到一个新的四位数（高位零保留）。
重复以上过程，最后得到的结果总是6174。这个数被称为卡布列克常数。请编写一个递归函数，完成以上的卡布列克运算。
**输入格式要求："%d" 提示信息：“Enter number:”
**输出格式要求：" [%d]:%d-%d=%d\n"
程序运行示例如下：
Enter number: 1234
[1]:4321-1234=3087
[2]:8730-378=8352
[3]:8532-2358=6174

参考代码：

#include <stdio.h>
int count=0;
main()
{
    int n;
    printf("Enter number:");
    scanf("%d",&n);
    vr6174(n);
}
vr6174(int num)
{
    int each[4],max,min;
    if(num!=6174&&num)
    {
        parse_sort(num,each);
        max_min(each,&max,&min);
        num=max-min;
        printf(" [%d]:%d-%d=%d\n",++count,max,min,num);
        vr6174(num);
    }
}
parse_sort(int num,int *each)
{
    int i,*j,*k,temp;
    for(i=0;i<=4;i++)
    {
        j=each+3-i;
        *j=num%10;
        num/=10;
    }
    for(i=0;i<3;i++)
        for(j=each,k=each+1;j<each+3-i;j++,k++)
            if(*j>*k)
            {   temp=*j; *j=*k; *k=temp;}
    return;
}
max_min(int *each,int *max,int *min)
{
    int *i;
    *min=0;
    for(i=each;i<each+4;i++)
        *min=*min*10+*i;
    *max=0;
    for(i=each+3;i>=each;i--)
        *max=*max*10+*i;
    return;
}

以上就是对于本题的解题思路了，如果你觉得我的文章对你有用请点个赞支持一下吧。如果此文章有错误或者有不同的见解欢迎评论或者私信。wink~

题目：给定一个以字符串表示的非负整数 num，移除这个数中的任意 k 位数字，使得剩下的数字最小。

注意：剩余数字的前导0要删除，如果最后结果是空串，则需要返回 "0"。

工具/原料

• Eclipse

• JDK1.8

方法/步骤

1. 对于两个位数相同的数字：axxx 和 bxxx，如果 a >b ，则一定 axxx > bxxx，所以要想获取最小值，高位一定要小，基于次，算法思想如下：

   1. 从左向右，遍历数字串，并入栈，不断移除大于当前数字的栈顶数字；

   2. 注意，基于第1步的操作，当遇到0，会移除栈中所有数字，因此 0 不入栈；

   3. 遍历完毕，如果还未移除 k 位数字，则将栈顶元素弹出剩余位数即可；

   4. 通过栈中剩余数字和串中剩余数字，构建最后的返回数字串。

   

2. 编写本地测试代码。

   

3. 运行本地测试主方法，观察控制台输出，符合预期，本地测试通过。

   

4. 平台提交算法，测试通过。

   

原文：微信公众号：程序员小灰——删去k个数字后的最小值

1 题目

给定一个整数，从该整数中去掉 k 个数字，使剩下的数字组成的新整数尽可能小，那么应该选择去掉的数字。

2 思路

感觉这是个挺有意思的问题，所以当时认真的读了读也认真的想了想，真是不想不知道，一想才发现算法真的分优劣。首先这个题目是什么意思呢？一个数字移除 1 位后肯定会变小，问题是变小多少，最简单直接的方法是移除掉最后一位，那么会变小 10 倍左右，假如有一个 5 位整数 54127，移除 1 位数字如果移除最后一位变成 5412，变小了 10 倍左右，但是这肯定不是最小的。移除 1 位后变成 4 位整数，既然位数一样，那么肯定是高位的数字越小结果就越小，对于 54127 显然移除第一位变成 4127 是最小的，变小了 13倍左右。

那么是不是移除第一位一定是最小的呢？也不是，假设有一个 5 位整数 45127，移除 1 位数字如果移除最后一位变成 4512，变小了 10 倍左右，如果移除第一位变成 5127，最高位反而升高了，只变小了 8.8 倍左右，还不如移除最后一位，所以我们选择去掉的数字的原则应该是原整数的所有数字从左到右进行比较，如果发现某一位的数字大于它右面的数字，那么在删除该数字后，必然会使得该数位的值降低，因为右面比它小的数字顶替了它的位置。

再给一个例子，假如有一个整数 541270936，需要移除 3 个数字，按照上面的原则，第一个去掉的应该是 5，因为 5>4,；第二个去掉的应该是 4，因为 4>1，第三个去掉的应该是 7，因为 1<2，2<7，7>0，所以 541270936 去掉 3 个数字后得到的最小整数应该是 120936。

而且注意一下，假如有一个整数 30200，需要移除 1 个数字，按照上面的原则，应该去掉第一个数字 3，然后剩下的数字为 0200，我们应该记录为 200，所以我们要考虑处理后的数字前面要去掉 0 的情况。

3 代码实现

理清思路后，就来简单用代码实现一下这个算法，

    @Test
    public void testRemoveKDigits() {
        removeKDigits1("541270936", 3);
    }

    /**
     * author：MrQinshou
     * Description:初版，以 k 为外层循环，每次外循环再去遍历全部字符串，每次删除一个数字
     * date:2018/11/27 20:21
     * param
     * return
     */
    public static String removeKDigits1(String string, int k) {
        // 以删除多少位为外层循环
        for (int i = 0; i < k; i++) {
            // 定义一个标志位记录是否有高位的数字被删除
            boolean hasCut = false;
            // 每次循环遍历目标字符串的所有字符
            for (int j = 0; j < string.length() - 1; j++) {
                char a = string.charAt(j);
                char b = string.charAt(j + 1);
                // 如果当前字符（高位数字）比下一个字符（低位数字）要大
                // 则截取字符串，并置标志位为 true
                if (a > b) {
                    string = string.substring(0, j) + string.substring(j + 1, string.length());
                    hasCut = true;
                    break;
                }
            }
            // 如果没有高位数字被删除，则删除最后一个数字
            if (!hasCut) {
                string = string.substring(0, string.length() - 1);
            }
            // 去掉前面的 0
            string = removeZero(string);
            System.out.println("string--->" + string);
        }
        if (string.length() == 0) {
            System.out.println("删除 " + k + " 个数字后的最小值--->" + 0);
            return "0";
        }
        System.out.println("删除 " + k + " 个数字后的最小值--->" + string);
        return string;
    }

    /**
     * author：MrQinshou
     * Description:去掉字符串前面的 0
     * date:2018/11/27 20:23
     * param
     * return
     */
    private static String removeZero(String string) {
        for (int i = 0; i < string.length() - 1; i++) {
            if (string.charAt(0) != '0') {
                break;
            }
            string = string.substring(1, string.length());
        }
        return string;
    }

运行一下打印如下：

结果是木有任何问题的，LeeCode 上有这道题，移掉 K 位数字，放到上面是玩耍一下（记得注释掉打印）：

貌似效率是有点低呀，接着往下看发现智慧与美貌并存的小灰介绍了另外一种方式来解答该题目。

4 优化

原整数的长度记为 n，上面的算法因为外层循环 k 次，内层循环每次为 n 次，时间复杂度为 O(kn)，最坏的情况下 k=n，则时间复杂度为 O(n²)。我们可以换一种思路，不让它嵌套循环，只遍历原整数一遍，用一个栈来存放所有数字，让数字一个个入栈，然后当入栈的数字比前面的数字要小时，则让前面的数字出栈，最后把栈内元素去掉 0 再处理成字符串，变成我们想要的结果。

    /**
     * author：MrQinshou
     * Description:最终版，用栈来实现
     * date:2018/11/27 20:23
     * param
     * return
     */
    public static String removeKDigits(String string, int k) {
        // 创建一个栈，用于接收所有的数字
        char[] stack = new char[string.length()];
        int top = 0;
        // 定于一个 copyK 等于 k，用于记录需要移除多少位数字，也就是需要
        // 出栈多少次，k 在最后还要用于确定新整数的长度，所以不要直接
        // 操作 k
        int copyK = k;
        for (int i = 0; i < string.length(); i++) {
            // 前一个数字大于当前数字时并且还有剩余次数，前一个数字出栈，栈顶指针前移
            // 注意这里是 while 不能是 if，如整数 45127，k=2 时，当指针
            // 指向数字 1 时，如果用 if，只会比较一次，让前一个数字 5 出
            // 栈，但 1 仍小于 4，所以 4 也应该出栈，所以需要用 while
            // 比较完前面所有数字
            while (top > 0 && stack[top - 1] > string.charAt(i) && copyK > 0) {
                top--;
                copyK--;
            }
            stack[top] = string.charAt(i);
            top++;
            System.out.println("stack--->" + Arrays.toString(stack));
        }
        // 找到栈中第一个非 0 数字的位置，以此构建新的整数字符串
        int offset = 0;
        for (int i = 0; i < stack.length; i++) {
            if (stack[offset] == '0') {
                offset++;
            }
            // 加了 else 跳出后反而效率会降低，一脸懵逼
            // else {
            // break;
            // }
        }
        // 新整数的长度为原整数的长度减去 k
        // 如果 offset 大于等于新整数的长度，则返回 0，否则从第一个
        // 非 0 数字开始截取到与新整数长度相等的数字作为返回值
        System.out.println("删除 " + k + " 个数字后的最小值--->" + (offset >= string.length() - k ? "0" : new String(stack, offset, string.length() - k - offset)));
        return offset >= string.length() - k ? "0" : new String(stack, offset, string.length() - k - offset);
    }

上面的遍历时的 while 要注意，不能是 if，这个问题我刚开始也纠结了好久，如整数 45127，k=2 时，当指针指向数字 1 时，如果用 if，只会比较一次，而且比 1 大的应该有 5 和 4 两个数字。

运行结果如下：

接下来就可以在 LeeCode 上愉快地玩耍了（记得注释掉打印），最后的去掉 0 我改成了 for 循环没有用小灰文中的 while 循环，效率还高了一点点：

5 总结

以前在面试中没有怎么遇到过算法题，刚开始看到这个题目的时候还觉得很有趣，等自己真的去理解思路的时候还是有点困难，特别是后面的优化，这也说明了栈这种数据结构也是蛮有用的，继续努力。