c276 - 沒有手機的下課時間
題目描述
題目要求模擬一個猜數字遊戲，給定一個四位數的答案和一系列猜測，對於每個猜測計算 A 和 B 的數量，並輸出結果。A 代表猜測數字與答案數字在相同位置上且數值相同的數字個數，B 代表猜測數字與答案數字數值相同但位置不同的數字個數。
解題思路
程式碼直接模擬了遊戲的規則。對於每次猜測，程式碼首先計算 A 的數量，然後計算 B 的數量。計算 A 的數量時，直接比較猜測數字和答案數字在相同位置上的數值是否相同。計算 B 的數量時，先將 A 的位置標記為已匹配，然後再比較猜測數字和答案數字的數值是否相同，如果相同且位置不同，則將 B 的數量加一。
複雜度分析
- 時間複雜度: O(n * k)，其中 n 是猜測次數，k 是數字的位數 (本題為 4)。因為對於每次猜測，都需要遍歷數字的每一位進行比較。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a,b,c;
int n,A=0,B=0;
while(cin >> c){
cin >> n;
for(;n>0;n--){
a[0]=c[0];
a[1]=c[1];
a[2]=c[2];
a[3]=c[3];
cin >> b;
if(b[0]==a[0]){
a[0]='a';b[0]='a';A++;
}
if(b[1]==a[1]){
a[1]='a';b[1]='a';A++;
}
if(b[2]==a[2]){
a[2]='a';b[2]='a';A++;
}
if(b[3]==a[3]){
a[3]='a';b[3]='a';A++;
}
if(A<4){
if(b[0]!='a'){
if(b[0]==a[1]){
b[0]='a';a[1]='a';B++;
}
else if(b[0]==a[2]){
b[0]='a';a[2]='a';B++;
}
else if(b[0]==a[3]){
b[0]='a';a[3]='a';B++;
}
}
if(b[1]!='a'){
if(b[1]==a[0]){
b[1]='a';a[0]='a';B++;
}
else if(b[1]==a[2]){
b[1]='a';a[2]='a';B++;
}
else if(b[1]==a[3]){
b[1]='a';a[3]='a';B++;
}
}
if(b[2]!='a'){
if(b[2]==a[1]){
b[2]='a';a[1]='a';B++;
}
else if(b[2]==a[0]){
b[2]='a';a[0]='a';B++;
}
else if(b[2]==a[3]){
b[2]='a';a[3]='a';B++;
}
}
if(b[3]!='a'){
if(b[3]==a[1]){
b[3]='a';a[1]='a';B++;
}
else if(b[3]==a[0]){
b[3]='a';a[0]='a';B++;
}
else if(b[3]==a[2]){
b[3]='a';a[2]='a';B++;
}
}
}
printf("%dA%dB\n",A,B);
A=0;B=0;
}
}
}