寻找整数中的最小数

Question

给定一个 n 位数字和一个数字 'k'。您必须从数字中删除“k”位数字，并从剩余的“n-k”位数字中给出最短的数字，以使数字序列保持不变。例如，如果数字是 637824 且 k = 3。那么您必须从给定数字中删除 3 位数字。剩余数字组成的数字应尽可能小，数字顺序不得改变。所以输出应该是 324.

我使用的与包含排除逻辑相同的方法：

输入 63119 且 K=2:

Select 9 + (6311) 的最小值 = 19 或不要 select 9，select 1 + (631) 的最小值 = 11 并且 最后取所有 .

的最小值

对于输入 4567813 和 k=3:

Select 3 和 1 以及最小值 (45678) = 413

我正在使用递归逻辑来解决这个问题，但我无法用代码实现它，我现在已经精疲力尽了。我需要有关此递归的帮助。我不寻求更好的解决方案。

    #define min(a, b) ((a)>(b)?(b):(a));

    int minimum(char *s, int i, int j)
    {
            if (i == j)
                    return s[i] - '0';
            return min(s[j]-'0', minimum(s, i, j-1));
    }

    int add_up(char *s, int i, int j)
    {
            int sum = 0, mul = 1;
            while(i < j) {
                    sum = sum + (s[j] - '0')*mul;
                    j--;mul *= 10;
            }
            return sum;
    }

    int foo(char *s, int size, int j, int k)
    {
            int sum = 0, i, mul = 1;
            if (k < 0 || j > size || j < 0)
                    return 0;
            if ((k == 0) && (j != 0))
                    return add_up(s, 0, j);
            if ((k == 1) && (j != 0))
                    return minimum(s, 0, j);
            if (k-1 == j)
                    return add_up(s, 0, j);
            for (i=k;i>=0;i--) {
                    sum += min((s[j]-'0')+10*foo(s, size, j-1, k-1), foo(s, size, j-1, k));
            }
            return sum;
    }

    int main()
    {
            char s[] = {"4567813"};
            printf("%d\n", foo(s, strlen(s)-1, strlen(s)-1, 2));
            return 0;
    }

Answer 1

你说过最终取了所有的最小值但是你取了所有的最小值然后添加了它们。您需要为每个 i 取最小值，并在 sum 中保存所有 i 的最小值。请参阅代码以进行说明。你的 add_up 函数也有错误，它应该添加到 i<=j.

int add_up(char *s, int i, int j)
{
    int sum=0, mul=1;
    while(i <= j) {  // modification here
        sum=sum + (s[j] - '0')*mul;
        j--; mul*=10;
    }
    return sum;
}

int foo(char *s, int size, int j, int k)
{
    int sum=INT_MAX, i, mul=1;
    if(k < 0 || j > size || j < 0)
        return 0;
    if((k == 0) && (j != 0))
        return add_up(s, 0, j);
    if((k == 1) && (j != 0))
        return minimum(s, 0, j);
    if(k-1 == j)
        return add_up(s, 0, j);
    for(i=k; i>=0; i--) {
        int res=min((s[j]-'0')+10*foo(s, size, j-1, k-1), foo(s, size, j-1, k));  
        sum=min(sum,res); // minimum over all possible i
    }
    return sum;
}

寻找整数中的最小数

finding minimum number in a integer

algorithm

recursion

dynamic-programming