找到一个整数中的最小数字

Question

给定一个n位数字和一个数字'k'。您必须从号码中删除'k'个数字，并从剩余的'n-k'个数字中输入最短的数字，以使数字序列保持不变。例如，如果数字是637824且k = 3，那么您必须从给定数字中删除3位数字。由其余数字形成的数字应尽可能小，并且数字序列不得改变。所以输出应当是我已经使用相同夹杂物排斥逻辑324

方法：

输入63119和K = 2：

选择9 +最小的（6311）= 19或 别选择9，选择1 +最小（631）= 11和最后取最少全部。

对于输入4567813和K = 3：

选择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中保存最小值。请参阅代码以进行澄清。还有你的add_up函数有bug，它应该加到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; 
}