C++程式查詢將數字變為0所需的最小操作次數

假設我們有一個包含n位數字的數字字串S。認為S表示一個數字時鐘，整個字串顯示一個從0到10^n - 1的整數。如果數字較少，則會顯示前導0。遵循以下操作：

  • 將時鐘上的數字減少1，或者

  • 交換兩個數字

我們希望時鐘以所需的最小運算元顯示0。我們必須計算執行此操作所需的次數。

因此，如果輸入類似於S = "1000"，則輸出將為2，因為我們可以將第一個1與最後一個0交換，因此字串現在變為"0001"，然後將其減少1以獲得"0000"。

步驟

為了解決這個問題，我們將遵循以下步驟：

n := size of S
x := digit at place S[n - 1]
for initialize i := 0, when i <= n - 2, update (increase i by 1), do:
   if S[i] is not equal to '0', then:
      x := x + (digit at place S[i]) + 1
return x

示例

讓我們看看以下實現以更好地理解：

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
   int n = S.size();
   int x = S[n - 1] - '0';
   for (int i = 0; i <= n - 2; i++)
      if (S[i] != '0')
         x = x + S[i] + 1 - '0';
   return x;
}
int main() {
   string S = "1000";
   cout << solve(S) << endl;
}

輸入

"1000"

輸出

2

更新於: 2022年3月3日

232 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告