f445 - 263 - Number Chains
題目描述
題目給定一個數字 n，要求不斷進行以下操作，直到出現循環：將 n 的各位數字降序排列得到 a，升序排列得到 b，然後計算 n = a - b。輸出每次計算的過程，以及循環出現前的鏈長度。
解題思路
這題的核心思路是模擬題目描述的過程，並使用一個 map (哈希表) 來檢測循環。
ma(int n)函數：將數字n的各位數字降序排列後返回新的數字。mi(int n)函數：將數字n的各位數字升序排列後返回新的數字。- 主函數中，使用
map<int, int> fd來記錄已經出現過的數字。 - 在
while迴圈中，不斷計算a - b，並將新的數字存入fd。 - 如果新的數字已經在
fd中出現，則說明出現了循環，輸出鏈長度。 - 如果沒有出現循環，則繼續計算，直到出現循環為止。
複雜度分析
- 時間複雜度: O(k * d * log d)，其中 k 是鏈長度，d 是數字的位數。每次計算
ma和mi需要對數字的各位進行排序，時間複雜度為 O(d * log d)。由於鏈長度最多為 1000，因此總時間複雜度為 O(k * d * log d)。 - 空間複雜度: O(k)，其中 k 是鏈長度。
map用於存儲已經出現過的數字，空間複雜度為 O(k)。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <map>
using namespace std;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline int ma(int n){
int a[10]={0},rt=0;
while(n){
++a[n%10];
n/=10;
}
for(int i=9;i>=0;--i){
while(a[i]){
a[i]--;
rt*=10;
rt+=i;
}
}
return rt;
}
inline int mi(int n){
int rt=0;
while(n){
rt*=10;
rt+=n%10;
n/=10;
}
return rt;
}
int main(){
int n;
while(n=read()){
cout << "Original number was " ;
write(n);cout << "\n";
int c=0;
map <int,int> fd;
while(fd[n]!=1){
fd[n]=1;
++c;
int a=ma(n),b=mi(a);
n=a-b;
write(a);cout << " - " ;
write(b);cout << " = " ;
write(n);cout << "\n";
}
cout << "Chain length " ;
write(c);
cout << "\n";
}
}