38. Count and Say

38. Count and Say 

https://leetcode.com/problems/count-and-say/

解釋

輸入 1 輸出 1
輸入 n 數出 n-1 輸出中從頭到尾數過去

範例

1 1
2 11 // 1個1
3 21 // 2個1
4 1211 // 1個2, 1個1
5 111221 // 1個1, 1個2, 2個1
6 312211 // 3個1, 2個2, 1個1

解法

1. 遞迴 n=1 "1", CountAndSet(k) = 數出 CountAndSet(k-1)
2. 每次數的時候若是和前一個字不同，把數的結果加入輸出
3. 可以塞一個結尾符號方便末端處理


留言

張貼留言

這個網誌中的熱門文章

46. Permutations & 47. PermutationsII

  46 .  Permutations  https://leetcode.com/problems/permutations/ 遞迴代入深度 深度 = 長度  將目前解加入解集合中 若沒有則把目前解往下遞迴 深度+1 頭開始選，選過的item不能再選(需要紀錄) 每次遞迴完後把最後 一個元素拿出來繼續選下一個 Python append solution 需要先做 slice 以免變成 copy by addr P(n, d) perm(items, d, n, cur, ans)      if d == n:          ans.append(cur[:])          return      for i: 0 to len(items)          used[i] = True          cur.append(items[i])          perm(items, d+1, n, cur, ans)          cur.pop()          used[i] = False 47 需排除已存在解， 1. 直接方式：if not cur in ans:  ans.append(cur[:]) 2. 在迴圈時就排除 last = -11 # 請設定在 constraint 以外 if items[i] == last: continue last = cur.pop()
閱讀完整內容