Skip to content

Latest commit

 

History

History
105 lines (92 loc) · 2.92 KB

967. Numbers With Same Consecutive Differences.md

File metadata and controls

105 lines (92 loc) · 2.92 KB

967. Numbers With Same Consecutive Differences

leetcode Daily Challenge on August 18th, 2020.

Difficulty : Medium

Related Topics : Dynamic Programming

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 <= 9
  • 0 <= K <= 9

Solution

  • mine
    • Java
      • Runtime: 2 ms, faster than 85.42%, Memory Usage: 38.9 MB, less than 86.84% of Java online submissions 
        // O(L^2)time
// O(L)space
// L = res.length
public int[] numsSameConsecDiff(int N, int K) {
    LinkedList<Integer> res = new LinkedList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
    for (int i = 1; i < N; i++) {
        int size = res.size();
        for (int j = 0; j < size; j++) {
            int t = res.removeFirst();
            if (t == 0) continue;
            int mod = t % 10;
            if (K == 0) {
                res.add(t * 10 + mod);
                continue;
            }
            if (mod - K >= 0) {
                res.add(t * 10 + mod - K);
            }
            if (mod + K < 10) {
                res.add(t * 10 + mod + K);
            }
        }
    }
    int[] arr = new int[res.size()];
    int i = 0;
    while (!res.isEmpty()) {
        arr[i++] = res.removeFirst();
    }
    return arr;
}
  • the most votes
  • Runtime: 5 ms, faster than 44.95%, Memory Usage: 39.3 MB, less than 51.80% of Java online submissions 
    // If K >= 5, time and Space O(N)
// If K <= 4, time and space O(2^N)
public int[] numsSameConsecDiff(int N, int K) {
    List<Integer> cur = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
    for (int i = 2; i <= N; ++i) {
        List<Integer> cur2 = new ArrayList<>();
        for (int x : cur) {
            int y = x % 10;
            if (x > 0 && y + K < 10)
                cur2.add(x * 10 + y + K);
            if (x > 0 && K > 0 && y - K >= 0)
                cur2.add(x * 10 + y - K);
        }
        cur = cur2;
    }
    return cur.stream().mapToInt(j->j).toArray();
}