精华内容
下载资源
问答
  • 给定一非负整数 num,移除这数中的 k 位数字,使得剩下的数字最小。 注意: num 的值小于 10^10000 且 ≥10^ k。 num 不会包含任何前导零。 示例 1 : 输入: num = 1432219, k = 3 输出: 1219 解释: 移除掉三...

    题目描述

    给定一个非负整数 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 list =new...

    
    /**
     *给定一个以字符串表示的非负整数 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开始推导就会发现规律, 现在假设有一数,...

    题目:一个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 个数字,使剩下的数字...一个数字移除 1 后肯定会变小,问题是变小多少,最简单直接的方法是移除掉最后一,...

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

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

    展开全文
  • 输入一个5位整数,依次输出各个位数字 #include "stdio.h" int main() { int num; char a5,a4,a3,a2,a1; printf("输入5位数字:"); scanf("%d",&num); a5=(num/10000)%10; //万位数字 a4=(num/1000)%10; ...
  • 给定一以字符串表示的非负整数num,移除这数中的k位数字,使得剩下的数字最小。 注意: num的长度小于 10002 且≥k。 num不会包含任何前导零。 示例 1 : 输入: num = "1432219", k = 3 输出: "1219" 解释: ...
  •  题目是网上看到的,意思是:给定一个数字,求解比这个数字大的最小的对称数字,如:比10大的最小的对称数字为11,比111大的最小的对称数字为:121,比9999大的最小对称数字为:10001,以此类推 思路:  这...
  • 编程练习:使用for循环,编程求100~999之间所有的水仙花数。水仙花数是指一个n位数(n≥3),它的每个位上数字的...水仙花数是指一个n位数(n≥3),它的每个位上数字的n次幂之和等于它本身。(例如:1^3 + 5^3+ 3^3 = ...
  • 剑指Offer--008-旋转数组的最小数字

    千次阅读 2016-04-10 21:36:07
    牛客OJ:旋转数组的最小数字 九度OJ:http://ac.jobdu.com/problem.php?pid=1386 GitHub代码: 008-旋转数组的最小数字 CSDN题解:剑指Offer–008-旋转数组的最小数字 牛客OJ 九度OJ CSDN题解 GitHub...
  • 然后计算 S,使其等于数组 A 当中最小的那个元素各个数位上数字之和。 最后,假如 S 所得计算结果是 奇数 的请你返回 0,否则请返回 1。 示例 1: 输入:[34,23,1,24,75,33,54,8] 输出:0 解释: 最小元素为 1,...
  • 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行...
  • * 求这两个数字的差,得:41976,把这个数字再次重复上述过程(如果不足5,则前边补0)。 * 如此往复,数字会落入某个循环圈(称为数字黑洞)。 比如,刚才的数字会落入:[82962,75933, 63954, 61974]这循环...
  • 思路:在n个位里面删除m个位,也就是找出n-m个位组成最小数 所以在区间 [0, m]里面找最小的数,对应的下标标号i 接着找区间 [i+1,m++]里面的最小数,对于下标为ii 接着找区间 [ii+1,m++]里面的最小数…… ...
  • Java实现 LeetCode 402 移掉K位数字

    万次阅读 多人点赞 2020-03-13 22:42:28
    给定一以字符串表示的非负整数 num,移除这数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 : 输入: num = “1432219”, k = 3 输出: “1219” ...
  • 请问判断3个数字之间最大,最小和中间值,要如何判断?例如: $a = 500; $b = 1500; $c = 2000; 希望得到的结果是: 最大是c,最小是a,中间为b。
  • 5位数字黑洞

    千次阅读 2017-03-06 10:30:57
    任意一5位数,比如:34256,把它的各位数字打乱,重新排列,可以得到一最大的数:65432,一个最小的数23456。求这两个数字的差,得:41976,把这个数字再次重复上述过程(如果不足5,则前边补0)。如此往复,...
  • 条件: 限制最大 100,最小0,最长两小数 输入大于100,自动变为100. 超出,2小数,自动四舍五入 以下是使用全局指令的案例 (也可以使用局部指令,可以参考文档 ...
  • 求这两个数字的差,得:41976,把这个数字再次重复上述过程(如果不足5,则前边补0)。 如此往复,数字会落入某个循环圈(称为数字黑洞)。 比如,刚才的数字会落入:[82962, 75933, 63954, 61974] 这循环圈。 ...
  • 任意一5位数,比如:34256,把它的各位数字打乱,重新排列,可以得到一最大的数:65432,一个最小的数23456。求这两个数字的差,得:41976,把这个数字再次重复上述过程(如果不足5,则前边补0)。如此往复,...
  • 题目描述:给定N个数字,输出这几个数字组成的最小整数 输入 3 9 24 48 输出: 24489 import sys n = int(sys.stdin.readline().strip()) V = [] for i in range(n): line = sys.stdin.readline().strip() ...
  • 例如输入数组{3,32,321},则打印出这三数字能排成的最小数字为321323。 思路:这题实际是考的字符串比大小,字符串是如何比大小? 1 .如果字符串相等返回值为0,不等返回其他数值。 比较方法是先比较对应...
  • 最小的k个数字和求第k小的数字

    千次阅读 2012-12-31 20:58:59
    比较常见的例子,大家都会购物吧,购物的时候如果去京东商城,当搜索某件商品的时候,搜索后的页面会呈现很多该类型的商品,但是京东总会给我们一些推荐,那么这推荐是依据什么呢?其实道理很简单,京东的后台...
  • 运行结果:分析:先选定第一个数字,然后将后面的数字依次遍历求和,并与需要的数字比较,需要n-1次,如果第一个数字不行,选择第二,依次遍历求和。。。。需要n^2次,时间复杂度比较高,但也是可以的,在面试中...
  • 例如输入数组 {3,32,321},则打印出这三数字能排成的最小数字为321323。 解题思路:  解题思路: 比较两字符串s1 S2的大小的时候,先将它们拼接起来,比较s1+s2和s2+s1哪个大,如果s1+s2大,那么说明s2...
  • 位数字密码锁

    千次阅读 2019-11-20 11:50:48
    设计一保险箱用的4位数字密码锁,该锁有规定的地址代码A、B、C、D 4输入端和一开箱钥匙孔信号E的输入端,锁的密码由实验者自编。当用钥匙开箱时,如果输入的4密码正确,则保险箱被打开;否则,电路将发出...
  • n位数,删去k后,也就是剩下一 n-k 数,那么这数要最小,我们就要保证我们我们得出的数是所有删除后得到的数的最小值。那么怎么保证呢? 问题转换一下,如果最后就剩下一,那么无意结果就是这些数字的...
  • 在一数组中,每两个数字配对,要求得到的所有配对数字的差的绝对值最小,请问怎么分配数组呢?
  • 例如输入数组{122,12,123},则输出这两能排成的最小数字12122123。 思路: 新排序规则:从整数数组中取出两数a和b,将a和b转化成字符串"a"和"b",再分别把"a"和"b"拼接成...
  • n位数,删去k后,也就是剩下一 n-k 数,那么这数要最小,我们就要保证我们我们得出的数是所有删除后得到的数的最小值。那么怎么保证呢? 问题转换一下,如果最后就剩下一,那么无意结果就是这些...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 246,318
精华内容 98,527
关键字:

个位上最小的数字是什么