Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/967.html
967. Numbers With Same Consecutive Differences (Medium)
Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.
Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.
You may return the answer in any order.
Example 1:
Input: N = 3, K = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Example 2:
Input: N = 2, K = 1 Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
Note:
1 <= N <= 90 <= K <= 9
Related Topics:
Dynamic Programming
Solution 1.
// OJ: https://leetcode.com/problems/numbers-with-same-consecutive-differences/
// Time: O(N)
// Space: O(N)
class Solution {
vector<int> ans;
void dfs(int num, int i, int N, int K) {
if (i == N) {
ans.push_back(num);
return;
}
if (num % 10 + K <= 9) dfs(num * 10 + (num % 10 + K), i + 1, N, K);
if (K != 0 && num % 10 - K >= 0) dfs(num * 10 + (num % 10 - K), i + 1, N, K);
}
public:
vector<int> numsSameConsecDiff(int N, int K) {
for (int i = N == 1 ? 0 : 1; i <= 9; ++i) dfs(i, 1, N, K);
return ans;
}
};
Java
-
class Solution { public int[] numsSameConsecDiff(int N, int K) { if (N == 1) { int[] nums = new int[10]; for (int i = 0; i < 10; i++) nums[i] = i; return nums; } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 1; i <= 9; i++) { int nextDigit1 = i - K, nextDigit2 = i + K; if (nextDigit1 >= 0) queue.offer(i * 10 + nextDigit1); if (K != 0 && nextDigit2 < 10) queue.offer(i * 10 + nextDigit2); } for (int digits = 3; digits <= N; digits++) { int size = queue.size(); for (int i = 0; i < size; i++) { int num = queue.poll(); int lastDigit = num % 10; int nextDigit1 = lastDigit - K, nextDigit2 = lastDigit + K; if (nextDigit1 >= 0) queue.offer(num * 10 + nextDigit1); if (K != 0 && nextDigit2 < 10) queue.offer(num * 10 + nextDigit2); } } int length = queue.size(); int[] nums = new int[length]; for (int i = 0; i < length; i++) nums[i] = queue.poll(); return nums; } } -
// OJ: https://leetcode.com/problems/numbers-with-same-consecutive-differences/ // Time: O(N) // Space: O(N) class Solution { vector<int> ans; void dfs(int num, int i, int N, int K) { if (i == N) { ans.push_back(num); return; } if (num % 10 + K <= 9) dfs(num * 10 + (num % 10 + K), i + 1, N, K); if (K != 0 && num % 10 - K >= 0) dfs(num * 10 + (num % 10 - K), i + 1, N, K); } public: vector<int> numsSameConsecDiff(int N, int K) { for (int i = N == 1 ? 0 : 1; i <= 9; ++i) dfs(i, 1, N, K); return ans; } }; -
class Solution: def numsSameConsecDiff(self, n: int, k: int) -> List[int]: ans = [] def dfs(n, k, t): if n == 0: ans.append(t) return last = t % 10 if last + k <= 9: dfs(n - 1, k, t * 10 + last + k) if last - k >= 0 and k != 0: dfs(n - 1, k, t * 10 + last - k) for i in range(1, 10): dfs(n - 1, k, i) return ans ############ class Solution(object): def numsSameConsecDiff(self, N, K): """ :type N: int :type K: int :rtype: List[int] """ if N == 1: return [0, 1,2,3,4,5,6,7,8,9] res = [] for i in range(1, 10): self.dfs(res, i, N - 1, K) return list(set(res)) def dfs(self, res, curint, N, K): if N == 0: res.append(curint) return last = curint % 10 if last + K <= 9: self.dfs(res, curint * 10 + last + K, N - 1, K) if last - K >= 0: self.dfs(res, curint * 10 + last - K, N - 1, K)