推 applebeing: 感謝想法分享，很易懂且效率很好耶。 27.121.223.216 09/01 18:56
基本想法是一個個位數iterate過去
有個簡單的剪枝手段：不可能達成4個的時候就不用往下數了
例如10000xx，最多就3個數
再來是個簡單的算小計手段：已經數到四個數了，剩下的位數只能在已知最大值之內
例如1234xyz中的xyz各能在(0,1,2,3,4)中任選，所以這類共5^3=125個
我試了下python，光用上面這兩招沒特別雕語法
大概可以跑在一秒多
原po可以參考看看
還有版友想得到其他有效手段嗎？
剛剛又發現一個不錯的手段：建表查表
例如前面算過1234xyz這類共125個
建個表，key是“ 前四位數最大為4，且已經數到4個數了”，值是125
以後再碰到這種case就直接小計125
遇到表上沒有的就往下拆分算完再加進表內
加上這招可以壓到0.03秒左右
※ 引述《applebeing (蘋果人)》之銘言：
: 求職時線上測驗的問題，有算出解答，但覺得應該有更好的解法，
: 向各位版友請教解題想法。
: 問題如下：
: 一個七位數的數字，從第七位到個位數的順序開始比對。
: 若當前位數的值，不小於曾出現過的數的最大值，就記錄起來。
: 請問紀錄結果為四個數字的可能組合數有幾組？
: 例：
: 2334849 - 由左至右
: 第一位數 2 加入紀錄
: 第二位數 3 大於等於2，加入紀錄
: 第三位數 3 大於等於3，加入紀錄
: 第四位數 4 大於等於3，加入紀錄
: 第五位數 8 大於等於4，加入紀錄
: 第六位數 4 不紀錄
: 第七位數 9 大於等於8，加入紀錄
: 紀錄結果為 6
: 6429748 - 紀錄 69 （2個數）
: 4629889 - 紀錄 4699（4個數）
: 各位數可以為 0，例如 0001234、0007899 也符合要求。
: 我用迴圈跑 1~一千萬涵蓋七位數，每個數字都檢查紀錄結果，得出組數。
: 跑了五分多鐘，很笨也很沒有效率。
: 想請問是否有更效率的解題方式？
: 請大家指教，感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.189.166 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1598928609.A.178.html
※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 10:53:29
※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 10:55:03
※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 10:57:40
※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 11:18:55