使用C ++将N整除25所需的最小给定移动次数。
问题陈述
给定数字N,且不带前导零。任务是找到使N可以被25整除所需的最小移动数。每次移动时,可以交换任意两个相邻的数字,并确保在任何时候数字都不能包含任何前导零。如果无法将N除以25,则打印-1
如果N=5071,则需要移动4次才能将其除以25
5071 → 5701 → 7501 → 7510 → 7150
算法
1. Iterate over all pairs of digits in the number. Let the first digit in the pair is at position ‘i’ and the second is at position ‘j’. 2. Place these digits to the last two positions in the number 3. If the number has a leading zero. Find the leftmost nonzero digit and move it to the first position. 4. If the current number is divisible by 25 then update the answer with the number of swaps
示例
#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
int requiredMoves(long long n){
string str = to_string(n);
int ans = INT_MAX;
int len = str.size();
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
if (i == j)
continue;
string temp = str;
int cnt = 0;
for (int k = i; k < len - 1; ++k) {
swap(temp[k], temp[k + 1]);
++cnt;
}
for (int k = j - (j > i); k < len - 2; ++k) {
swap(temp[k], temp[k + 1]);
++cnt;
}
int pos = -1;
for (int k = 0; k < len; ++k) {
if (temp[k] != '0') {
pos = k;
break;
}
}
for (int k = pos; k > 0; --k) {
swap(temp[k], temp[k - 1]);
++cnt;
}
long long num = atoll(temp.c_str());
if (num % 25 == 0)
ans = min(ans, cnt);
}
}
if (ans == INT_MAX)
return -1;
return ans;
}
int main(){
int n = 5071;
cout << "Minimum required moves: " << requiredMoves(n) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它生成以下输出-
Minimum required moves: 4
热门推荐
1 狗狗下楼训练
3 狗狗训练头盔
6 狗狗训练机构
7 训练狗狗步骤
9 狗狗能训练
10 狗狗基本动作训练方法
11 怎么训练狗狗叼饭盆
12 狗狗一岁了还能训练吗
13 训练狗狗的
14 宁波狗狗训练
15 训练狗狗拉屎
16 教狗狗训练
17 狗狗要怎么训练上厕所
18 狗狗靠的训练