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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告