数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律使用 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
更新于: 2019年10月31日
296 次查看
广告