Numbers With Same Consecutive Differences (M)
題目
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
題意
求所有的N位數，使得其中每一個數中的每相鄰兩個位的數字之差為K，
思路
用回溯法去生成每一個這樣的N位數，需要注意的坑是N=1時要考慮0，以及K=0時注意剪枝，
代碼實作
Java
class Solution {
public int[] numsSameConsecDiff(int N, int K) {
List<Integer> list = new ArrayList<>();
for (int i = N == 1 ? 0 : 1; i < 10; i++) {
dfs(0, i, 1, N, K, list);
}
int[] ans = new int[list.size()];
int i = 0;
for (int num : list) {
ans[i++] = num;
}
return ans;
}
private void dfs(int num, int digit, int index, int N, int K, List<Integer> list) {
if (digit < 0 || digit > 9) {
return;
}
num = num * 10 + digit;
if (index == N) {
list.add(num);
return;
}
dfs(num, digit + K, index + 1, N, K, list);
if (K > 0) {
dfs(num, digit - K, index + 1, N, K, list);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2192.html
標籤：其他