找到一個整數中的最小數字

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; 
}