32. 找最小数

题目描述

给一个正整数NUM1，计算出新正整数NUM2，NUM2为NUM1中移除N位数字后的结果需要使得NUM2的值最小。

输入描述

1. 输入的第一行为一个字符串，字符串由0-9字符组成，记录正整数NUM1，NUM1长度小于32。
2. 输入的第二行为需要移除的数字的个数，小于NUM1长度。

输出描述

输出一个数字字符串，记录最小值NUM2。

示例1

输入：
2615371
4

输出：
131

说明：

示例2

输入：

输出：

说明：

作者：code5bug
链接：找最小数 - 华为OD统一考试(E卷)_牛客网
来源：牛客网

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.给一个正整数NUM1，计算出新正整数NUM2，NUM2为NUM1中移除N位数字后的结果，需要使得NUM2的值最小。

2.输入描述：（1）输入的第一行为一个字符串，字符串由0-9字符组成，记录正整数NUM1，NUM1长度小于32。

（2）输入的第二行为需要移除的数字的个数，小于NUM1长度

3.输出描述：输出一个数字字符串，记录最小值NUM2。

二、解题思路

1.这道题目的意思是说，给定一个正整数NUM1，和一个数字N，移除NUM1中的N位数字（N小于NUM1的长度），使得我们得到的数字NUM2是最小的

2.为了使得我们的数字NUM2最小，我们应该要保证我们移除数字之后的第一位是最小的

3.然后在前一位相同的情况下我们要保证后面的位都尽量最小

4.比如示例1中的数字2615371，我们需要移除4个数字

所以我们在26153这几个数字中，选取一个最小的，1

然后去掉这个数字前面的数字

我们的数字变成了15371，然后我们的剩余移除数字变成了2

之后我们检查537中比较小的数字，3，

移除5和7，最后剩下131就是我们能得到的最小数字了

3：28

5.所以要实现这个方法我们需要先读取字符串

char str[1000];

scanf("%s", str);

6.然后我们读取要移除的数字个数int N;

scanf("%d", &N);

7.然后对于str的前N + 1个字符我们找出最小的

int start = 0;

int len = strlen(str);

char newstr[len - N];

int idx = 0;

while(N > 0) {

int minidx = 0;

for(int i = 0; i < N + 1; i++) {

if(str[i] - '0' < str[minidx] - '0') {

minidx = i;

}

newstr[idx++] = str[minidx];

N -= minidx;

strcpy(str, str + minidx + 1);

}

strcat(newstr, str);

}

8.最后我们输出结果newstr

printf("%s", newstr);

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
    char str[1000];
    scanf("%s", str);
    int N;
    scanf("%d", &N);
    int len = strlen(str);
    char newstr[len - N];
    int idx = 0;
    while (N > 0) {
        int minidx = 0;
        for (int i = 0; i < N + 1; i++) {
            if (str[i] - '0' < str[minidx] - '0') {
                minidx = i;
            }
        }
        // printf("%s中最小的索引值是%d\n", str, minidx);
        newstr[idx++] = str[minidx];
        N -= minidx;
        strcpy(str, str + minidx + 1);
    }
    strcat(newstr, str);
    printf("%s\n", newstr);
    return 0;
}

char* removeKdigits(char* num, int k) {
    int n = strlen(num), top = 0;
    char* stk = malloc(sizeof(char) * (n + 1));
    for (int i = 0; i < n; i++) {
        while (top > 0 && stk[top] > num[i] && k) {
            top--, k--;
        }
        stk[++top] = num[i];
    }
    top -= k;

    char* ans = malloc(sizeof(char) * (n + 1));
    int ansSize = 0;
    bool isLeadingZero = true;
    for (int i = 1; i <= top; i++) {
        if (isLeadingZero && stk[i] == '0') {
            continue;
        }
        isLeadingZero = false;
        ans[ansSize++] = stk[i];
    }
    if (ansSize == 0) {
        ans[0] = '0', ans[1] = 0;
    } else {
        ans[ansSize] = 0;
    }
    return ans;
}