Problem
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
Solution: Search
Time complexity: O(2^N)
Space complexity: O(N)
C++/DFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, running time: 8ms class Solution { public: vector<int> numsSameConsecDiff(int N, int K) { vector<int> ans; if (N == 1) ans.push_back(0); for (int i = 1; i <= 9; ++i) dfs(N - 1, K, i, ans); return ans; } private: void dfs(int N, int K, int cur, vector<int>& ans) { if (N == 0) { ans.push_back(cur); return; } int l = cur % 10; if (l + K < 10) dfs(N - 1, K, cur * 10 + l + K, ans); if (l >= K && K != 0) dfs(N - 1, K, cur * 10 + l - K, ans); } }; |
C++/BFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, running time: 4 ms class Solution { public: vector<int> numsSameConsecDiff(int N, int K) { deque<int> q{1,2,3,4,5,6,7,8,9}; if (N == 1) q.push_front(0); while (--N) { int size = q.size(); while (size--) { int num = q.front(); q.pop_front(); int r = num % 10; if (r + K <= 9) q.push_back(num * 10 + r + K); if (r - K >= 0 && K != 0) q.push_back(num * 10 + r - K); } } return vector<int>(cbegin(q), cend(q)); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment