使用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