[討論] 排列組合的演算法解題

作者: applebeing (蘋果人)   2020-08-31 14:46:23
求職時線上測驗的問題,有算出解答,但覺得應該有更好的解法,
向各位版友請教解題想法。
問題如下:
一個七位數的數字,從第七位到個位數的順序開始比對。
若當前位數的值,不小於曾出現過的數的最大值,就記錄起來。
請問紀錄結果為四個數字的可能組合數有幾組?
例:
2334849 - 由左至右
第一位數 2 加入紀錄
第二位數 3 大於等於2,加入紀錄
第三位數 3 大於等於3,加入紀錄
第四位數 4 大於等於3,加入紀錄
第五位數 8 大於等於4,加入紀錄
第六位數 4 不紀錄
第七位數 9 大於等於8,加入紀錄
紀錄結果為 6
6429748 - 紀錄 69 (2個數)
4629889 - 紀錄 4699(4個數)
各位數可以為 0,例如 0001234、0007899 也符合要求。
我用迴圈跑 1~一千萬涵蓋七位數,每個數字都檢查紀錄結果,得出組數。
跑了五分多鐘,很笨也很沒有效率。
想請問是否有更效率的解題方式?
請大家指教,感謝!

Links booklink

Contact Us: admin [ a t ] ucptt.com