前往
大廳
主題

[leetcode]1643. Kth Smallest Instructions

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-22 12:00:01 | 巴幣 2 | 人氣 226

題目: 1643. Kth Smallest Instructions
難度: Hard
目前下列解法的時間複雜度: O((row+col)**2) 。若能省掉建n取m的表格,則 O(row+col) 。或是你覺得 row+col>30 再來談,則O(1)


題目說明

原情境略。
給一堆字元 H 和 V ,最多各 15 個,
求用完這些字元的第 k 個(字典)排列順序的字串。


解法: 跟我用在 8-puzzle solver狀態壓縮很像

1. 想想看: 前面的字元什麼時候要改變,或是用更奇怪的理解方式: 進位(每位數不呈冪次方)
2. k 剩得夠多就讓他進位
3. 從高位數做到低位數
4. 注意題目的 k 是 1-index 。而 10 進位時, 0~9 就有 10 個。


範例註解 70 lines 的 source code

創作回應

相關創作

更多創作