Try   HackMD

APCS實作題2025年1月第2題:字串操作

日期:2025年1月15日
作者:王一哲
ZeroJudge 題目連結

題目

問題描述

給一個字串

S,有三種字串操作,分別如下

  1. 編號0,兩兩交換:將字串內相鄰兩個字元交換,例如字串 "apcsntnu" 先分組成 (ap)(cs)(nt)(nu),將會交換為 (pa)(sc)(tn)(un),即得到 "pasctnun"。
  2. 編號1,兩兩排序:將字串內相鄰兩個字元按照字典序排序,字元的字典序為
    a<b<<z
    ,例如字串 "family" 先分組成 (fa)(mi)(ly),將會交換成 (af)(im)(ly),即得到 "afimly"。
  3. 編號2,完美重排:假設字串長度為
    n
    ,將字串內的字元編號為
    0,1,2,,n1
    ,將字串分成兩半為
    0,1,2,,n21
    n2,n2+1,n2+2,,n1
    ,並且組合成
    0,n2,1,n2+1,,n21,n2+1
    。例如 "apcsntnu" 拆成 "apcs" 和 "ntnu",然後交錯成 "anptcnsu"。

給定

k 個操作,請依序操作字串,輸出最後的字串結果。

輸入說明

第一行輸入一個字串

S (2|S|100),字串長度保證為偶數。接下來一行輸入一個正整數
k
,接下來有
k
行,每一行有一個數字,種類為
0,1,2

子題配分

  • 60%:
    |S|10,k=1
    且保證操作為完美重排
  • 40%:無限制

輸出格式

輸出操作完之後的字串內容。

範例輸入1

apcsntnu
1
2

範例輸出1

anptcnsu

範例輸入2

facebook
4
2
0
2
1

範例輸出2

bocfkoae



Python 程式碼

寫法1,利用字串的索引值,不自訂函式

費時最久約為 23 ms,使用記憶體最多約為 3.3 MB,通過測試。

S = input().strip() # 輸入的字串 n = len(S) # 字串長度 k = int(input()) # 操作次數 for _ in range(k): # 執行 k 次 op = int(input()) # 操作種類 t = "" # 儲存操作結果用的空字串 if op == 0: # 操作0,兩兩交換 for i in range(0, n, 2): # i 每次加 2 t += S[i+1] + S[i] elif op == 1: # 操作1,兩兩排序 for i in range(0, n, 2): # i 每次加 2 a, b = S[i], S[i+1] # 取出兩個字元 a, b if a <= b: t += a+b # 如果 a <= b,將 a+b 接到 t 最後面 else: t += b+a # 反之,將 b+a 接到 t 最後面 else: # 操作2,完美重排 for i in range(n//2): # 執行 n//2 次 t += S[i] + S[n//2 + i] S = t # t 字串存到 S print(S)

寫法2,利用字串的索引值,自訂函式

費時最久約為 20 ms,使用記憶體最多約為 3.4 MB,通過測試。

# 寫法2,利用字串的索引值,自訂函式 def zero(s): # 操作0,兩兩交換 t = "" # 儲存操作結果用的空字串 for i in range(0, len(s), 2): # i 每次加 2 t += s[i+1] + s[i] return t def one(s): # 操作1,兩兩排序 t = "" # 儲存操作結果用的空字串 for i in range(0, len(s), 2): # i 每次加 2 a, b = S[i], S[i+1] # 取出兩個字元 a, b if a <= b: t += a+b # 如果 a <= b,將 a+b 接到 t 最後面 else: t += b+a # 反之,將 b+a 接到 t 最後面 return t def two(s): # 操作2,完美重排 t = "" # 儲存操作結果用的空字串 n = len(s) # 字串長度 for i in range(n//2): # 執行 n//2 次 t += S[i] + S[n//2 + i] return t S = input().strip() # 輸入的字串 k = int(input()) # 操作次數 for _ in range(k): # 執行 k 次 op = int(input()) # 操作種類 if op == 0: S = zero(S) elif op == 1: S = one(S) else: S = two(S) print(S)

寫法3,利用字串切片 (slice) 及 zip

Python 的字串及串列的切片,語法為

S[起點:終點:間隔]

取出的資料包含起點,起點預設值為開頭;不包含終點,終點預設值為結尾;間隔預設值為1,如果間隔為2每次跳兩格,如果間隔為-1會倒過來取值。如果想要將一個字串反向輸出,可以寫成

S[::-1]

費時最久約為 22 ms,使用記憶體最多約為 3.3 MB,通過測試。

# 寫法3,利用字串切片 (slice) 及 zip S = input().strip() # 輸入的字串 n = len(S) # 字串長度 for _ in range(int(input())): # 執行 k 次 op = int(input()) # 操作種類 t = "" # 儲存操作結果用的空字串 if op == 0: # 操作0,兩兩交換 for a, b in zip(S[::2], S[1::2]): t += b+a elif op == 1: # 操作1,兩兩排序 for a, b in zip(S[::2], S[1::2]): t += a+b if a <= b else b+a else: # 操作2,完美重排 for a, b in zip(S[:n//2], S[n//2:]): t += a+b S = t # t 字串存到 S print(S)

寫法4,先將字串轉成串列 (list),再利用切片 (slice) 修改串列內容

這是我看到最有 Python 風格的寫法,但是對於初學者最難看懂。由於 Python 的字串不能透過索引值修改某個字元的內容,所以要先將字串轉成串列才行。費時最久約為 27 ms,使用記憶體最多約為 3.3 MB,通過測試。

S = list(input()) # 輸入的字串轉成串列 n = len(S) # 串列長度 for _ in range(int(input())): # 執行 k 次 op = int(input()) # 操作種類 if op == 0: # 操作0,兩兩交換 S[::2], S[1::2] = S[1::2], S[::2] elif op == 1: # 操作1,兩兩排序 for i in range(0, n, 2): # 執行 n//2 次 S[i:i+2] = sorted(S[i:i+2]) else: # 操作2,完美重排 S[::2], S[1::2] = S[:n//2], S[n//2:] print("".join(S)) # 將 S 接成字串再輸出



C++ 程式碼

寫法1,利用字串的索引值,不自訂函式

費時最久約為 3 ms,使用記憶體最多約為 352 kB,通過測試。

#include <iostream> #include <string> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string S; cin >> S; // 輸入的字串 int n = (int)S.size(); // 字串長度 int k; cin >> k; // 操作次數 for(int j=0, op; j<k; j++) { // 執行 k 次 cin >> op; // 操作種類 if (op == 0) { // 操作0,兩兩交換 for(int i=0; i<n; i+=2) { // i 每次加 2 char a = S[i]; // 暫存 S[i] S[i] = S[i+1]; // S[i] 重設為 S[i+1] S[i+1] = a; // S[i+1] 重設為 a } } else if (op == 1) { // 操作1,兩兩排序 for(int i=0; i<n; i+= 2) { // i 每次加 2 char a = S[i], b = S[i+1]; // 取出兩個字元 a, b if (a > b) { // 如果 a > b S[i] = b; S[i+1] = a; // S[i] 重設為 b,S[i+1] 重設為 a } } } else { // 操作2,完美重排 string t = S; // 字串 S 暫存到 t for(int i=0; i<n/2; i++) { // 執行 n/2 次 S[2*i] = t[i]; S[2*i+1] = t[n/2+i]; // S[2*i] 重設為 t[i],S[2*i+1] 重設為 t[n/2+1] } } } cout << S << "\n"; return 0; }

寫法2,利用字串的索引值,自訂函式

費時最久約為 3 ms,使用記憶體最多約為 344 kB,通過測試。

#include <iostream> #include <string> using namespace std; string zero(string s) { // 操作0,兩兩交換 string t = ""; // 暫存輸出結果的空字串 for(int i=0; i<(int)s.size(); i+=2) t = t + s[i+1] + s[i]; return t; } string one(string s) { // 操作1,兩兩排序 string t = ""; // 暫存輸出結果的空字串 for(int i=0; i<(int)s.size(); i+=2) { if (s[i] <= s[i+1]) t = t + s[i] + s[i+1]; else t = t + s[i+1] + s[i]; } return t; } string two(string s) { // 操作2,完美重排 string t = ""; // 暫存輸出結果的空字串 int n = (int)s.size(); // 字串長度 for(int i=0; i<n/2; i++) t = t + s[i] + s[n/2+i]; return t; } int main() { ios::sync_with_stdio(0); cin.tie(0); string S; cin >> S; // 輸入的字串 int k; cin >> k; // 操作次數 for(int j=0, op; j<k; j++) { // 執行 k 次 cin >> op; // 操作種類 if (op == 0) S = zero(S); else if (op == 1) S = one(S); else S = two(S); } cout << S << "\n"; return 0; }




tags:APCSPythonC++