967. Numbers With Same Consecutive Differences

 1import java.util.HashSet;
 2import java.util.Set;
 3
 4/**
 5 * @author lxn
 6 * @description 967. Numbers With Same Consecutive Differences
 7 * @create 2020-02-26 23:04
 8 */
 9public class Algorithm967 {
10    public static void main(String[] args) {
11        int N = 3;
12        int K = 7;
13        int[] res = new Solution967().numsSameConsecDiff(N, K); // res = {181, 292, 707, 818, 929}
14    }
15}
16
17class Solution967 {
18    public int[] numsSameConsecDiff(int N, int K) {
19        Set<Integer> cur = new HashSet();
20        for (int i = 1; i <= 9; ++i) cur.add(i); // cur放1~9
21
22        // 遍历1~N-1
23        for (int steps = 1; steps <= N - 1; ++steps) {
24            Set<Integer> cur2 = new HashSet();
25            for (int x : cur) { // 遍历cur
26                int d = x % 10; // 取当前的最后一个数字，然后看看下一个是d-K还是d+K，d-K和d+K都要在0~9的范围内。
27                // d - K肯定<=9, 因为d和K都在0~9的范围内，但因为两个谁大谁小不确定，所以可能是负数，所以只有满足>=0，就满足条件。
28                if (d - K >= 0) cur2.add(10 * x + (d - K)); // 在原来的基础上后面加一个数，原来的是都要进位(乘以10)了，再加上个位。
29                // d + K肯定>=0，但可能大于9,所以要判断一下。注意：这两个if可能两个都走。
30                if (d + K <= 9) cur2.add(10 * x + (d + K)); // 同上，只是个位数不同
31            }
32            cur = cur2; // steps = 1时, cur2 = {18 29 70 81 92}; steps = 2, cur2 = {181, 292, 707, 818, 929}
33        }
34
35        if (N == 1) cur.add(0); // 一位数的时候才有0，两位数及以上的不要加！
36
37        // 把cur里的数放数组里，供最后返回结果
38        int[] res = new int[cur.size()];
39        int t = 0;
40        for (int x : cur) res[t++] = x;
41
42        return res;
43    }
44}