j179 - 資料分類 (Classification)
題目描述
題目給定一個數字字串，要求不斷地將字串中的相鄰數字相乘，直到字串長度為 1 為止。如果相乘結果為 0，則直接保留 0。
解題思路
這題的核心是模擬題目描述的相鄰數字相乘過程。程式碼使用一個 while 迴圈，只要字串長度大於 1 就持續進行相乘操作。在迴圈內部，根據字串長度分為三種情況：
- 字串長度大於 3：將前兩個數字和後兩個數字相乘，然後將結果連接起來。
- 字串長度大於 2：將前兩個數字和後兩個數字相乘，然後將結果連接起來。
- 字串長度等於 2：將兩個數字相乘，然後將結果連接起來。
在每次相乘後，將結果更新為新的字串
s。最後，如果字串長度為 0，則將其設定為 "0"。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是初始字串的長度。因為在每次迴圈中，都需要計算相乘結果並將其轉換為字串，這個過程的複雜度與字串長度有關。最壞情況下，字串長度會不斷減小，但每次減小的幅度不大，因此時間複雜度近似為 O(n^2)。
- 空間複雜度: O(n)，其中 n 是初始字串的長度。因為在每次迴圈中，都需要儲存相乘結果的字串，這個字串的長度最壞情況下與初始字串長度相同。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
string s;
int main(){
cin >> s;
while(s.size()>1){
if(s.size()>3){
int r=(s[0]-'0')*(s[1]-'0');
int l=(s[2]-'0')*(s[3]-'0');
if(s[2]=='0')l=s[3]-'0';
string nxt,nxt2;
while(r){
nxt+=r%10+'0';
r/=10;
}
reverse(nxt.begin(),nxt.end());
if(l==0)nxt2="0";
while(l){
nxt2+=l%10+'0';
l/=10;
}
reverse(nxt2.begin(),nxt2.end());
s=nxt+nxt2;
}
else if(s.size()>2){
int r=(s[0]-'0')*(s[1]-'0');
int l=(s[1]-'0')*(s[2]-'0');
string nxt,nxt2;
while(r){
nxt+=r%10+'0';
r/=10;
}
reverse(nxt.begin(),nxt.end());
if(l==0)nxt2="0";
while(l){
nxt2+=l%10+'0';
l/=10;
}
reverse(nxt2.begin(),nxt2.end());
s=nxt+nxt2;
}
else{
int r=(s[0]-'0')*(s[1]-'0');
string nxt;
while(r){
nxt+=r%10+'0';
r/=10;
}
reverse(nxt.begin(),nxt.end());
s=nxt;
}
}
if(s.size()==0)s="0";
cout << s;
}