LeetCode 解題紀錄 967. Numbers With Same Consecutive Differences

Numbers With Same Consecutive Differences - LeetCode

題目

給定兩個數字 n 與 k，返回一個陣列包含了所有的 n 位數數字，每個 n 位數的每個相鄰數字差必須為 k

限制

• 2 ≤ n ≤ 9
• 0 ≤ k ≤ 9

觀察

• 要列出所有排列，可以使用 backtracking

思路

• 初始一個長度為 n 的陣列，每個位置都有 9 或 10 種可能(第一個數字不能為 0)，最大為 9*10⁸
• 由於每個數字與前一個數字相差必須為 k，只針對合法的數字遞迴以減少遞迴數量
• a-b=k 或是 b-a=k 都是相差為 k，因此合法數字可能會有兩個，除了 a == b(corner case) 的時候
• 每次遞迴指標加 1，當指標到達陣列長度代表搜尋成功，即可以加入答案中

Trial 1

結果

TC：O(9^n) SC：O(9^n)

Trial 2

• 試著用 BFS 解題，用每次增加一個位數的方式尋找合法的數字
• 做完 n 次後，在 queue 的數字即是答案

結果

時間與空間複雜度不變，程式碼比較精簡，不過效率變差，主要差別可能是在計算新的數字時用到了乘法運算