資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告