[LeetCode] Permutation Sequence

算是有點延續上周還是這周寫的

畢竟題目蠻相似的，換句話說就是…

不用動腦啊啊啊

修一修就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