对给定的N位高精度正整数,去掉其中的k个数字后,使剩下的数字构成的整数最大。

Input
输入第1行为一个整数L
后面L行的每一行包括一个长度为N的高精度正整数和需要去掉的数的个数k。(1 <= N <= 1000 , 1 <= k < N)

Output
输出每一行表示每个高精度正整数去掉相应的k个数字后构成的新的最大正整数。

Sample Input
Original Transformed
2
12345 1
54321 2

Sample Output
Original Transformed
2345
543
C语言有没有比较好的解决方法或者算法思路,自己编的程序总是出现一些小问题

8个回答

哪个OJ题目吧?
按照我的理解,这题不能排序,要保持原先的顺序,扩展一下几种样例情况以及我所给出的最大数:
123123 3 输出:323
1000 2 输出:10
322123 1 输出:32223
12345 3 输出:45

这题的要求是去掉k个数之后变得尽量大,那么也就是说,要让高位的数尽量大,也就是说,使得数字从高位开始尽量呈现递减的状态(前一位数要比后一位数大或者相等),而且我们在求值的时候是可以利用递推性的,比如k=2的结果可以在k=1的时候的结果上来取,也就是说k的结果可以在k-1的基础上进行获取。
我们以 123123 3 这种情况作为例子分析:
由于k=3,所以要去掉3个数,那么我们先求去掉2个数和去掉1个数的情况。
去掉1个数,也就是输入为123123 1 的时候:我们看123123的第一位和第二位分别是1和2,显然第一位要比第二位小,不符合递减状态,所以我们删掉第一位,那么就变成了 23123
去掉2个数,也就是输入为123123 2 的时候:在去掉1个数的结果23123的基础上,我们需要再去掉一个数。我们看到第一位第二位分别是2和3,显然不符合递减状态,所以删掉第1位的2,么那变成3123
去掉3个数:在去掉2个数的结果3123的基础上,我们看到第一位第二位分别是3和1,符合递减状态,所以我们需要看第二位和第三位,第二位是1第三位是2,显然不符合递减状态,所以删掉第二位,那么得到的是323。

所以,我们可以这样做:
对于每个输入样例,我们需要做k次循环,每次循环所做的事情是从最高位开始遍历,找出不符合递减状态的第一个数,将其删掉。这样在k次循环之后我们就能获取到最大的数。
整理之后的代码:

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

//从start位置开始到end结束,整体后移一位,将end的位置覆盖掉
void moveOneStep(char * bigNum,int start,int end) {
    for (int i=end; i>start; i--) {
        bigNum[i]=bigNum[i-1];
    }
}

int main()
{
    int L;
    //输入L
    scanf("%d",&L);
    while (L--) {
        //做acm的话数组稍微开大一点点,因为有些题目会很坑,可能会出违背题目要求的内容
        char bigNum[1005];
        int k;

        //输入大数
        scanf("%s",bigNum);

        //长度
        long long length = strlen(bigNum);
        //获取k
        scanf("%d",&k);

        if (k >= length) {
            printf("不合法的输入\n");
            continue;
        }

        //核心代码
        for (int i=0; i<k; i++) {
            for (int j=i; j<length; j++) {
                if (bigNum[j] < bigNum[j+1] || j == length - 1 ) {
                    //使用了位移覆盖的方式来删除
                    moveOneStep(bigNum,i,j);
                    break;
                }
            }
        }
        //将字符串前移k位,也就是将原先后移的都移回来
        for (int i=0; i<length - k; i++) {
            bigNum[i] = bigNum[i+k];
        }
        //限定字符串长度为 length - k
        bigNum[length - k ] = '\0';

        printf("%s\n",bigNum);

    }

    return 0;
}

这是用数组来实现的方式,每删除一个都需要位移一次,复杂度近乎为0(n2),其实可以用一个当前位置指针来进行优化,不过复杂度不会有太大变化。
另外也可以用链表来实现,如果用链表来实现的话,删除将会方便很多,实现的思想是差不多的,不过如果借助一个当前位置指针的话复杂度可以下降到0(n)。

这个题目有点变态的。正文说的和例子不是一回事。
正确的描述题目的方式是,输出每一行表示每个高精度正整数去掉相应的k个数字后(不改变原先字符顺序)构成的新的最大正整数。

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void * a, const void * b)
{
    return *(char *)b - *(char *)a;
}
int main()
{
    char s[100];
    char r[100];
    int n;
    scanf("%s", s);
    strcpy(r, s);
    scanf("%d", &n);
    qsort(s, strlen(s), sizeof(char), cmp);
    int minpos = strlen(s) - 1;
    for (int i = strlen(s) - 1; i >= 0; i--)
    {
        if (r[i] == s[minpos]) { r[i] = '\0'; i = strlen(s); minpos--; }
        if (minpos < strlen(s) - n) break;
    }
    int x = 0;
    for (int j = 0; j < strlen(s); j++)
    {
        if (r[j] != '\0')
        {
            x *= 10;
            x += r[j] - '0';
        }
    }
    printf("%d", x);
    return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void * a, const void * b)
{
    return *(char *)b - *(char *)a;
}
int main()
{
    char s[100];
    int n;
    scanf("%s", s);
    scanf("%d", &n);
    qsort(s, strlen(s), sizeof(char), cmp);
    s[strlen(s) - n] = '\0';
    printf("%s", s);
    return 0;
} 

#include

int main()
{
int inter = 0;
int k = 0;
int n = 0;
int a[10] = {0};

scanf("%d",inter);
scanf("%d",k);

while(inter){
    a[inter%10] += 1;
    inter /= 10;
    n++;
    }

    if(n <k)
        exit(-1);
    if(n = k){
    inter = 0;
    printf("%d", inter);
    }
    for(int i = 9; i > 0 ; i--){
        while(a[i]&& n ){
            printf("%d",i);
            a[i]--;
            n--;
            }
    printf("\n");
    }

return 0;

}

思路就是把最大的数放在最高位,也就是按降序排序

其实核心就是排序(每个数位的数字从大到小)后输出(N-k个),输出没有什么好说的,排序算法也没有什么好说的。将一个数字的每一位取出,有两种思路:
1.循环或者递归 取余
2.数字转字符串按位截取,每一位再转数字
效率上我没有比对过,不过你的数字长度能达到1000,还是直接字符串来表示这个数吧。输出同样也用字符串。

先取模取出各位上的数字,对这些数字进行从小到大姐的排序
最后,将排序后的数字乘 10 相加,再组成最终的数字

91program
91program 回复caozhy: 要你多嘴,LZ 自己会判断。你以为你又是老大了,想把自己的思想强加于别人!你他妈的以为你是谁啊!以后你跟一次爷爷的帖子,爷爷就骂孙子一次。你准备好了吗,孙子?
3 年多之前 回复
caozhy
贵阳老马马善福专门编写代码的老马就是我! 这种答案基本上也就是把lz的题目又抄了一遍,而且还抄错了。
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
删数问题给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个
删数问题 Description 给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1 行是1 个正整数a。第2 行是正整数k。 Output 程序运行结束时,将计算出的最小数输出到文件output.txt中。 Sample Input 178543 4 Sample Output 13
一个n位的数,去掉其中的k个数,使剩下的数最小
一个n位的数,去掉其中的k位,问怎样去使得留下来的(n-k)位数按原来的前后顺序组成的数最小 思路一: 分析:求一共n位,求其中的m位组成的数最小。那么这个m位的数,最高位应该在原数的最高位到第m位区间找,要不然就不能当第m位了。 比如一个数:8 4 7 9 6 3 5 2 n = 8, k = 3; 1.第一个数应在 8 —— 3 间(含8和3)选最小的,应为3 2.第二个数应在5——2 间(含...
算法题—n位正整数去掉k(k<=n)位数字得到最小数
问题描述:给定n位正整数a,去掉其中任意k 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 输入:多组测试数据,每组测试数据的第一行是1个正整数a(a,第二行是正整数k(k 输出:删掉个数字后的最小数,每组测试数据输出单独一行,如果首位数字为0,删除首位数字。 #include #define MAX 10000000 int num[MAX]; //返回删除的位置 int
删除K个数字,使剩下的数字串最大(最大数字)
问题描述 给你一个整数 n,使得从 n 中删除 k 个数字之后的数字最大。 样例输入 1432219 3 样例输出 4329 private static int[] solution(int[] array, int k) { if (null == array || array.length == 0 || k &lt;= 0) { ...
键盘输入一个高精度的正整数n(<=240位),去掉任意s(s<n)个数字后,将剩下的数字按原左右次序组成一个新的正整数。
一、题目分析 很经典的一个题目。采用贪心策略。 这个题目其实可以分成两个小题。 1),使剩下的数最小。 2),使剩下的正整数最小。这时,删除的数字数s 就不能等于 n。以及删除后等于0或0...0就不行了。 1, 使剩下的数最小。 思路:依次遍历正整数的各位数字,将单调递减区间的第一个数字删掉,如果整个字符串已经单调递增排列的话,将最后一个删除. 代码(OJ上没有找到这道题,
对n个数字右移k位
<span style="font-size:14px;">#include<iostream> using namespace std; #include<math.h> #include<string.h> void Reverse(char* a, int left, int right) { for (; left < right; left++, right
输入一个高精度的正整数n,去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对所给的n和s,寻找一种方案使得剩下的数字组成的新数最小。
#include <iostream> #include <string> using namespace std;//从字符串v中从下标j开始删除s个字符,删除的字符保存在s_del中 void min_num(string &v, int &s,int j,string &s_del) { if ( 0 != s) { //如果j小于0则从第0个字符开始
n位正整数去掉k位数字得到最小数(回溯法C++代码)
本代码文档利用回溯法思想,实现了n位正整数去掉k位数字得到最小数,并且含有测试代码,非常简单,详细,准确!
输入n个整数,输出其中最大的k个
题目为:输入n个整数,输出其中最大的k个 例如输入1,2,3,4,5,6,7,8这8个数字,则最大的是6,7,8 代码: function test5($arr,$k) { $new_arr = []; $arr_length = count($arr); for ($i=0; $i &lt; $arr_length; $i++) { if( co...
PHP输入n个整数,输出其中最大的k个
输入n个整数,输出其中最大的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最大的3个数字为8,7和6。   /**    * 输入n个整数,输出其中最大的k个  * @param unknown $arr n个整数数组  * @param unknown $k  最大数量  */ function test2($arr,$k){    $len = count($...
输入n个整数,找出其中最小的K个数
vector&amp;lt;int&amp;gt; GetLeastNumbers_Solution(vector&amp;lt;int&amp;gt; input, int k) { int len=input.size(); vector&amp;lt;int&amp;gt; vec; if(len&amp;lt;k||len&amp;lt;=0) return vec; ...
N位数去掉k位后最大结果(java)
问题描述: 比如给一个数字:857352749,与一个K:2 从 857352749 中删除2个数字使删除后的数字结果最大 解决方式: 1、每次从数字左边到右边找,如果发现左边的数比右边的少,那就把左边的数字删掉 2、如果遍历到最后一个数字都没有发现,那就把最后一个数字删掉 下面是java代码: private static int getamax(int[] num, int ...
找出N个整数中最大的K个数python
N个数中找到最大的K个数,如果在python中可以很简单: N个数组成容器,然后调用内置排序方法进行切片即可; 方法为 sorted(N)[-K:];
NYOJ-448 寻找最大数
寻找最大数 时间限制:1000 ms  |  内存限制:65535 KB 难度:2 描述 请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大, 比如当n=92081346718538,m=10时,则新的最大数是9888   输入第一行输入一个正整数T,表示有T组测试数据 每组测试数据占一行,每行有两个数n,m(n可能是一个很
数字组合问题(N个正整数连接起来最大)
/* 数字组合问题:     设有N个正整数,现在需要你设计一个程序,使他们连接在一起成为最大的数字, 例3个整数 12,456,342 很明显是45634212为最大,4个整数 342,45,7,98显然为98745342最大 程序要求:输入整数N 接下来一行输入N个数字,最后一行输出最大的那个数字! */ /* 解题思路:      看到题目首先想到如何使两个数连接在一起最大,
【练习题】给定两个整数n和k,返回1 ... n中k个数的所有组合
例: For example, If n = 4 and k = 2, a solution is [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 分析题目:例子中,n=4,k=2; 1,2,3,4 两个数一组组合 我们通常的思路就是先选定第一个数,从1开始,然后分别和后面的数组合,1完了,再向后遍...
返回正整数n中数字的个数
题目:编写程序,使得函数返回正整数n中的数字的个数。 #include #include int num_digits(int n); int main(){ int n; printf("Enter a number: ",n); scanf("%d",&n);     int result=num_digits(n); printf("%d\n",result); retu
给定两个整数n和k,返回1 ... n中k个数的所有可能组合。
本题源自leetcode ------------------------------------------------- 思路回溯法 vector > combine(int n, int k) { vector> result; if(nn) return result; vector path;
删除k个数字后的最小值
给定一个只包含数字的字符串,要求在原字符串基础上删除k个数字后,使新字符串的数字最小。 题目来源:LeetCode-402. Remove K Digits,原题目如下: Given a non-negative integernumrepresented as a string, removekdigits from the number so that the new number...
删去k个数字后的最小值
参考:程序员小灰 题目来源:漫画:删去k个数字后的最小值 substring() 方法返回字符串的子字符串。 语法 public String substring(int beginIndex) 或 public String substring(int beginIndex, int endIndex) 参数 beginIndex -- 起始索引(包括), 索引从 0 开始。 e...
c++求解n位正整数删除k位之后的最小值
1.问题的重述       给定一个n位正整数a, 去掉其中k个数字后按原左右次序将组成一个新的正整数。对给定的a, k寻找一种方案,使得剩下的数字组成的新数最小。 2.问题的分析       根据问题所述首先我们先把n为正整数拆分成每一个数字存在一个数组arr[N]中,例如正整数19687,拆分之后存在数组 arr[5]={7,8,6,9,1},然后对这个数组按从打到小进行排序(也可以从小...
n个整数中最小的K个数
题目描述 输入n个整数,找出其中最小的K个数。 输入示例 例如输入4,5,1,6,2,7,3,8这8个数字,k=4 输出实例 则最小的4个数字是1,2,3,4。 方法一 思路如下: 找出当前k个元素中最大值的索引值,剩余n-k中的值一次与当前list中最大值作比较,如果小于最大值,则将当前值替换最大值索引处的值,依次循环,最后list中前k个元素为最小值。 java代...
打印1到最大的N位整数
输入一个3,则需要打印出0~999;输入一个4,则需要打印出0~9999 ,这里输入数的大小没有限制,因此我们要考虑到大数的问题。所以我们使用字符串数组来保存所要打印的数,因此程序关键是让字符串数组循环自增。 打印的核心代码:public void printToMax(){ //将字符串数组中的值初始化为零 for(int i = 0 ; i < s.length ; i++)
已知一个整数n,求n^n的前k位
这个题目咋眼不是很难,不就是求一下nnn^n么,大不了计算机费点时间,但是当你真的把代码写好后,你会发现当n=15(1515=43789389038085937515^{15}=437893890380859375)的时候,你的变量就扛不住了,再大了就产生了溢出,咋办呢?我们可以换个角度想一个这个问题,假设 y=nny=n^n 于是 log10y=nlog10n\log_{10} y=n\lo
有一十进制正整数,移除其中的k个数,使剩下的数字是所有可能中最大的。假设:字符串的长度一定大于等于k,字符串不会以0开头
有一十进制正整数,移除其中的k个数,使剩下的数字是所有可能中最大的。 假设: 字符串的长度一定大于等于k 字符串不会以0开头 输入: 一行由正整数组成的数字字符串,和一个正整数k,俩个数据用空格隔开, 如:1432219 3 输出: 移除k位后可能的最大的数字字符串。 如1432219移除1 ,2,1这三个数字后得到4329,为所有可能中的最大值。 例子: 1432219 3 输出: 4329 代...
【数据结构】中对n个数字右移k位
【数据结构】中对n个数字右移k位
给定n个数,求其中4个数的和是否能为0
设a #include #include #include #include using namespace std; const int maxn = 1000 + 2; int num[maxn]; int main() {     int n;     scanf("%d",&n);
n个数选k(k
如9个数选4个数,备选数可正可负,最后选取的4个数要求绝对值最大。怎么做?rn如rn-1 0 -2 8 10 3 12 -110 22rn选取的四个数为-1,0,-2,-110最大和为|(-1)+(-2)+(-110)|=113
打印从0~最大n位数字
输入一个数n,输出从0到最大的n位数字。 测试用例: 0,1,-1,1000 #include&amp;lt;iostream&amp;gt; #include&amp;lt;string.h&amp;gt; using namespace std; void printnum(char* num) { int i=0; while(num[i]=='0') i++; for...
删除k个数字使剩下数字最小(大)
如:1593121212去掉3个数,剩下1121212最小。 思路如下: 删除k个,可以采用贪心算法,每次删除1个 那么每次删哪一个呢? 若N&amp;lt;2,那就不用纠结了,因为最多只有一个选择 若N&amp;gt;=2,则该整数可以写成XabY,X,Y分别是前缀和后缀,长度可以为0. a,b是相邻的两个数字,且a在b的左边。我们面临的选择就是删除a还是删除b的问题。若删除a,删除后变为XbY; 若删除b,...
最大的k个数
题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 思路1:暴力求解法:全排序,输出前k个 class Solution { public: vector GetLeastNumbers_Solution(vector input, int k) { vector res;
找出最大的k个数
这是一个算法中很常见的问题,遇到这个题开始像我这种还未养成算法思维的人,第一想法就是先排序然后直接去前K个大的数就好。 但居然在笔试中遇到这个题,那最最普通的这种解法肯定肯定是无法满足结果的。 而且一旦数据量一大,即便排序效率高也需要花上不少时间。这里不再谈普通的解决方法。 第二种解法是利用快排算法,做相应改变,执行有限次数获取前K大的数。 假设N个数存储在集合S中,从S中 随机 取一个数X,...
寻找最大的K个数
寻找最大的K个数
寻找最大的k个数
简述给定n个数,从中找到最大的k个数 思路 思路1:最简单的想法,把给定的n个数排序一遍,再取前k个数,复杂度是O(n*logn) + O(k),这里排序用的是快排,顺手下了一个,代码如下 void quickSort(int* array, int begin, int end) { int first = begin; int last = end; int key =
找最大的k个数
可以用基于vector的heap,或者使用基于红黑树的set, 来实现最大的k个数
给定范围n内给定数字m的个数
给定范围n内给定数字m的个数 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数? 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。 ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。 编程之美上给出的规律: 如果第i位(自右至左,从1开始标号)上的...
n位整数去掉m位后求最大值问题
真的不知道该用一个怎样的题目去描述这个算法。。。 问题简要描述: 给出一个长整数以及要去掉的位数,保证剩下的数字按顺序组合的整数值最大。 输入:长整数,要去掉的位数 输出:处理之后的最大值 可重复输入输出,需要验证合法性 大体思路: 1.可以用数组存储长整数,可以用strlen()方法求得其长度,假设为n,如果去掉其中的m位,则剩余的最大数的最高位的位置就应该在前m+1位中寻找,不然
topK问题——N个数中取最大的K个数
topK问题在海量数据中找出出现频率最高的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为topK问题。N个数中取最大的K个数,用小根堆;N个数中取最小的K个数,用大根堆。例题1:100万个数中,找到其中最大的100个数。(N个数中取最大的K个数)思路:(1) 定义两个数组,arr用于存储海量数据N,top用于存储小根堆K;(2) 将海量数据的前K个元素先填满top堆;(3) 调整...
从K个数里面找出最大的N个数,圣诞快乐!
我要从大约20个数里面找出最大的3个数,所以我自己改写了一份code。我手动输入10个数字,然后希望输出3个最大的数字,但是结果只有最大的数字是正确的,第二个和第三个都是不对的,不知道哪个环节出了问题,很是纳闷,欢迎大家的建议。 圣诞节快乐rnrn[code=c]rn#include rn#define N 3rnrnint main()rnrn int i,j;rn int area; rn int maxArea[N]; rn int empty = N;rnrn for(j=0;j<10;j=j+1)rn rn printf("Input:");rn scanf("%d",&area);rn printf("\n");rnrn if(empty > 0)rn rn maxArea[N-empty]=area;rnrn empty=empty-1;rn rn elsern rn for(i=0; i < N; i=i+1)rn rn if(area>maxArea[i])rn rn maxArea[i]=area;rnrn break;rn rn rn rn rn printf("Area1=%d\n",maxArea[0]);rn printf("Area2=%d\n",maxArea[1]);rn printf("Area3=%d\n",maxArea[2]);rnrn[/code]
Python从N个数中找到最大的K个数
提出问题: 如何在某集合里面找出最大或最小的N个元素。 解决思路: 找出最大或最下的N个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大N个和nsmallest()求最小N个。 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq.nlargest(4,nums)) ...
相关热词 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池 c#5.0 安装程序 c# 分页算法