Open KyrieSu opened 8 years ago
這一題是無腦幹題,不需要討論,只需要實做XD 檔名請命名為 : CPE014_yourname.cpp
這題讓我想到之前寫 Haskell(functional programming) 用 Haskell 可以幾行就寫完
我覺得函數式語言可以去接觸看看 他是用完全不同的思考方式在寫程式 雖然學了之後就不見得有實用價值 但可以讓你在寫其他語言的時候用不同角度看待問題
Haskell的教學是直接看這個網站就可以了嗎? http://openhome.cc/Gossip/CodeData/HaskellTutorial/
那個連結是對的 但是超連結點下去有點問題喔 要不要重放
codedata 的教學之前看過還不錯 有好幾篇 可以慢慢看 時間不多的話不用學太深 懂一些基本用法就可以了
我這題晚一點會傳實作~~~
我用unordered_map來做,也可以用string array來做
嗯嗯 不過這似乎不是重點 應該是怎麼把 abc def 變成
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
比較難 如果數字更多的話會有更多組合
哈哈 我剛好現在遇到這個地雷XD
後來覺得這一題有點難,最後的組合這邊不知道怎麼處理,因為我不知道要開多少變數來紀錄QQ
我先上傳到最後輸出之前的
@Larry850806
我們都卡在不知道怎麼組合字串,這題可能要麻煩你實作一次!
給一點提示 你們先做一個題目
輸入 1 就輸出 1 3 就輸出 123 依此類推 12 就輸出 123456789101112 試試看不要用迴圈做
看懂了..... 這是遞迴吧?!
嗯嗯 遞迴可以長出一個遞迴樹 上面那個題目是每次只往下分支出一個 children 所以整條樹就是一條線
原題目則是一次分支出三個 children 原本只有一個點就是什麼都不輸出 輸入 23 的話會分支兩次 所以最下層會有 1 x 3 x 3 = 9 個點 每個點分別是不同結果
講得有點抽象不知道你們看不看得懂 簡而言之就是遞迴 終端條件設好就沒問題了
我把提示的部分打出來了,是類似這樣的打法嗎?
嗯嗯對 有一點點小瑕疵 不過觀念是對的
return sol(input-1,vec);
這個不要 return
OK~~已修改了 不過我還是看不出來題目跟遞迴的相關性啊QQ
整個結果變化大概是這樣
[null] 分裂出三個 ["a", "b", "c"] 複製三次 ["a", "a", "a", "b", "b", "b", "c", "c", "c"] 分裂出三個 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
如果後面還有的話就再繼續複製跟分裂
我現在在東部玩沒辦法 coding 可能要等我週末回去
嗯嗯嗯 你玩~~
只是想問為什麼這種題目會想到遞迴,有甚麼特點嗎~~
如果一個大問題可以拆成許多小問題 而這些小問題又相似 那就可以用遞迴
以這題來講那些類似的小問題就是複製跟分裂 測資小少做幾次 測資大多做幾次 不管測資大小都是一直重複同樣的動作 很像 D&C 的概念 所以用遞迴
補充 上面說如果有很多"類似"的小問題就用遞迴 如果很類似甚至有相同的小問題時就可以用 DP 加速 把算過的小問題的答案 cache 起來 綜合許多小問題的答案後得到最後大問題的解
我寫完囉 https://github.com/KyrieSu/Code_cpp/blob/master/CPE/phone_larry.cpp
如果輸入 "23" 剛開始的 input = "23", arr = []
處理完 '2' 之後 newInput = "3", newArr = ["a", "b", "c"]
然後再處理 '3' newInput = "", newArr = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
這時候 input 已經空了 所以就輸出
實際測了幾組測資
input:
234
output:
["adg", "adh", "adi", "aeg", "aeh", "aei", "afg", "afh", "afi", "bdg", "bdh", "bdi", "beg", "beh", "bei", "bfg", "bfh", "bfi", "cdg", "cdh", "cdi", "ceg", "ceh", "cei", "cfg", "cfh", "cfi"]
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.