题目描述

给定一个非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意: num 的值小于 10^10000 且 ≥10^ k。 num 不会包含任何前导零。 示例 1 : 输入: num = 1432219, k = 3 输出: 1219 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 : 输入: num = 10200, k = 1 输出: 200 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 : 输入: num = 10, k = 2 输出: 0 解释: 从原数字移除所有的数字，剩余为空就是0。

题目分析

这道题可以从删除多余元素和直接获得结果元素出发。先说删除多元素的算法，我们需要将当前递减序列如4321，依次删除4，3...，是不是一直按照非严格递增的顺序前进，删除递减序列就行了呢？遇到有相同数字怎么办呢？比如说：44321，当前删除最后一个4后得到4321，指针停留在3的位置，如果我们直接看后一个元素与3的大小关系，就有问题了（前面还有一个4），这种情况可以采用观察当前元素和前一个元素的方法，删除了元素需要将下标减2。除此之外，还需要将数组进行移动，还要处理。这种方法是不是很麻烦且容易出错，用直接获得结果元素就简单多了。假设num=1463，k=1，我们构造一个区间即start=0、end=k=1，然后在这个区间中找最小值加入结果字符串中，即在14中选最小，得到1，更新start=0；然后我们继续++start（得到1），end++（得到2），然后在46中选最小值，得到4，加入结果集字符串中，更新start=1，然后同上面步骤直到end=4。这样就可以保证我们能删除k个元素，且保证当前最高位的数值最小，为什么初始化时要选k+1的区间大小呢？因为前k+1个数内一定存在结果字符串中起始元素，因为只删除k个元素（防止num=400000，k=1的情况中4被加入结果集中，后面的区间大小可能小于k+1）。从当前的区间中选一个最小数值意味着当前最高位是当前最小的。为什么结果集中的第二个元素必须在当前end之前呢，因为我们知道首元素是初始化区间中的最小值，这样才能保证最高位是最小的，首元素确定后，他前面的元素肯定不能选，只能选其后，如果超过了end那么最后删除的元素将多余k个，我们只能在首元素之后和end之前选最小。看出来了吗？这个算法真的很巧妙。

算法实现

删除多余元素

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int num;
	cin >> num;
	char** result = new char*[num];
	for (int i = 0;i < num;i++)
	{
		char* number=new char[10000];
		int k;
		cin >> number;
		cin >> k;
		int size = strlen(number);
		for (int j = 1;j < size;j++)
		{
			if (number[j-1] > number[j] && --k >= 0)
			{
				char* src = number+j;
				char* dst = number + j - 1;
				while ((*dst++ = *src++) != '\0');
				j=0;
				size--;
			}
		}
		while (k > 0)
		{
			number[--size] = '\0';
			k--;
		}
		if (size <= 0)
		{
			result[i] = new char[2];
			result[i][0] = '0';
			result[i][1] = '\0';
		}
		else
		{
			size--;
			int m = 0;
			for (;m < size;m++)
				if (number[m] != '0')
					break;
			result[i] = new char[size - m + 2];
			char* src = number+m;
			char* dst = result[i];
			while ((*dst++ = *src++) != '\0');
		}
		/*cout << result[i];
		cout << endl;*/
	}
	for (int i = 0;i < num;i++)
	{
		for (int j = 0;j < strlen(result[i]);j++)
		{
			cout << result[i][j];
		}
		cout << endl;
	}
    return 0;
}

直接增加元素

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int num;
	cin >> num;
	char** result = new char*[num];
	for (int i = 0;i < num;i++)
	{
		char* number=new char[10001];
		int k;
		cin >> number;
		cin >> k;
		int size = strlen(number);
		if(k==size)
		{
			result[i]=new char[2];
			result[i][0]='0';
			result[i][1]='\0';
			continue;
		}
		int curSize=size-k;
		char* cur=new char[curSize+1];
		int count=0;
		int start=0,end=k;
		while(end<size)
		{
			char min=number[start];
			int minIndex=start;
			for(int j=start+1;j<=end;j++)
			{
				if(number[j]<min)
				{
					min=number[j];
					minIndex=j;
				}
			}
			cur[count++]=min;
			start=minIndex+1;
			end++;
		}
		cur[curSize]='\0';
		int m = 0;
		for (;m < curSize;m++)
			if (cur[m] != '0')
				break;
		if(m==curSize)
		{
			result[i]=new char[2];
			result[i][0]='0';
			result[i][1]='\0';
			continue;
		}
		result[i] = new char[curSize - m];
		char* src = cur+m;
		char* dst = result[i];
		while ((*dst++ = *src++) != '\0');
	}
	for (int i = 0;i < num;i++)
	{
		cout<<result[i];
		cout << endl;
	}
    return 0;
}


 

/**
 *给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小
 */


class Solution {
    public String removeKdigits(String num, int k) {

           String resullt ="";

        List<Integer>  list  =new ArrayList<Integer>();

        for (int i = 0 ;i<num.length();i++){

             int number =Integer.parseInt(String.valueOf(num.charAt(i)));

            while (list.size()!=0 && k>0 && (list.get(list.size()-1)>number)){

                list.remove(list.size()-1);

                k--;

            }

            if (number!=0||list.size()!=0)

            {

                list.add(number);

            }

        }

        while (list.size()!=0 &&k>0)

        {

            list.remove(list.size()-1);

            k--;

        }

        for (int i =0 ;i<list.size();i++)

        {

            if (list.get(i)==0&&resullt.length()==0)

            {



            }

            else

            {resullt=resullt+list.get(i);}

        }

         if (resullt.equals(""))

           resullt=String.valueOf(0);

        return  resullt;

    }

}

题目：一个n位的数，去掉其中的k位，问怎样去掉使得留下来的那个（n-k）位的数最小？

分析：（删数问题，可用贪心算法求解），方法就是从简单入手，慢慢复杂。从n=1开始推导就会发现规律，

现在假设有一个数，124682385，

假如k = 1，则结果为12462385,k = 2，结果为1242385……

可以知道：最优解是删除出现的第一个左边>右边的数，因为删除之后高位减小，很容易想...那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解...

def solution(num, k):
    s = str(num)
    flag = True
    while k:
        for i in range(len(s)-1):
            #每次删除第一个比下一个数字大的数
            if s[i] > s[i+1]:
                s = s.replace(s[i],'',1)
                flag = False
                break

        #如果所有数字递增，则删除最后几个数字直接返回
        if flag:
            s = s[:len(s)-k]
        k -= 1
    return int(s)

 

原文：微信公众号：程序员小灰——删去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 总结

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