算是有點延續上周還是這周寫的
畢竟題目蠻相似的,換句話說就是…
不用動腦啊啊啊
修一修就submit了,結果….Time Limit Exceeded QQ
class Solution(object): count = 0 def getPermutation(self, n, k): nums = [] for i in range(1,n+1): nums.append(i) return self.dfs(nums,[],k) def dfs(self, nums, ans,k): if not nums: self.count += 1 if self.count == k: return "".join(str(x) for x in ans) else: return None for i in range(len(nums)): tmp = self.dfs(nums[:i]+nums[i+1:], ans+[nums[i]],k) if tmp != None: return tmp
不過好像也是,我只是想知道其中一個branch,好像沒必要走不必要的path
原本這個tree上,我應該只要知道每次要走第幾個分支就好了
拿(4,9)這個input做例子
4!總共有24個組合,1到4開頭的會各有6(3!)個,聽起來很像廢話
但就是這個廢話(真的是很多廢話),好了不說廢話了XD
把剛剛我們要找9的去除以6
9/6 = 1….3
所以代表我從root出發要走的分支是第二個分支”2″,然後並把2從array pop掉
這時候數字array剩三個數字(1,3,4) ,每個數字開頭分別是2(2!)個
再重複剛剛的作法
3 / 2 = 1…1
一樣還是第二個分支”3″,然後並2 pop掉
重複這樣的步驟直到原先的array被抽光
“2314”就是答案惹
class Solution(object): def getPermutation(self, n, k): nums = [] mul = 1 ans = "" for i in range(1,n+1): nums.append(i) mul *= i k -= 1 while nums: mul = mul/n i = k / mul k = k % mul ans += str(nums.pop(i)) n -= 1 return ans
看討論區最熱門的solution也是這個解法,但這應該是O(N^2)吧
list pop就是O(N)的時間,討論區是用Java array要remove也是O(N)
BTW,不小心更新到主題惹,害我很想換主題,不然修CSS好累
好像有個OceanWP的模組可以用用看,希望可以找到合適我的主題RRRR