11. Common Permutation (CPE10567, UVA10252) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔，售價 199 元，
購買電子檔可將筆記與完整解答帶著走，
坐車、上課時皆可隨時複習，
不受網路或廣告影響，
若有需要請來信購買 greens2314@gmail.com
題目
- 找出 a 與 b 字串中相同的字串(稱為 x 字串)， 將 x 字串重新排列後為 a 與 b 的子序列
- 例如 a b c d e 的其中一個子序列是 a e
- 例如 z e i o u 的其中一個子序列是 e i u
輸入說明
- 每組測試資料有 2 行，
- 第 1 行是 a 字串，第 2 行是 b 字串
- 字串長度最多是 1000 個小寫的字母
輸出說明
- 如果有多個 x 符合上述條件 (a 與 b 字串中相同的字串)，則按照字母順序印出
- 印出一組結果要換行
- 補充：字母若在 a 與 b 字串同時出現多次，則需印出多次
解題技巧
- 統計 a 與 b 個字串中，相同字母 a ~ z 出現的次數
- 將出現的字母照 a ~ z排序
- 將共同出現過的字母印出，此字母出現幾次就印出幾個
解題過程
取得測試資料
- 使用 while 迴圈與 scanner.hasNextLine()，偵測是否有測試資料
- 當測試資料輸入時
- 使用 scanner.nextLine() 取得整行句子，統一轉小寫
宣告陣列
- 統計 a 與 b 個字串中，相同字母 a ~ z 出現的次數
- 宣告兩個陣列長度26，索引位置 0 ~ 25，countA 儲存 a 字串、countB 儲存 b 字串的字母出現次數
- 陣列寫法，注意字母與整數的轉換 - 大轉小
- char 轉 int
- 16 bits 轉 32 bits ：小轉大
- 隱含式轉換，無風險
分析字串
- 使用 for 迴圈與 String 類別中的 charAt() 方法，逐一讀取字串中的每一個字元
- 判斷字元是否為字母(測資有包含空白)
- 使用Character 的 isLetter() 方法，或判斷是否介於 a~z 或介於 97~122 之間
- 將字母減 97 或減 ‘a’字元 ，可取得 0 ~ 25 的值，可對應陣列索引位置
- 將特定陣列索引的數值 + 1
輸出
- 使用 for 逐一讀陣列中的數值
- 取得特定索引(也就是某一個字母)在 countA 與 countb 陣列中的最小值，呼叫Math.min()，例如 for 的 i = 25 時
- countA[25]的值 = 字母 z 在 a 字串出現的次數
- countB[25]的值 = 字母 z 在 b 字串出現的次數，取出兩者的最小值
- 使用 for 迴圈，根據最小值印出字母
- a 字串 = cccddde，c 出現 3 次， d 出現 3 次
- b 字串 = cdddd， c 出現 1 次， d 出現 4 次
- 共同出現 cd 字母，其中 c 共同出現 1 次，d 共同出現 3 次
留言
張貼留言