967. Numbers With Same Consecutive Differences

leetcode

#array#csharp#leetcode#queue

Task

: medium

Даны два целых числа n и k, верните массив всех целых чисел длины n, где разница между каждыми двумя последовательными цифрами равна k. Вы можете вернуть ответ в любом порядке.

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

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.

C# solution

matched/original

public class Solution {
    public int[] NumsSameConsecDiff(int N, int K) {
        if (N == 1) return Enumerable.Range(0, 10).ToArray();
        
        var queue = new List<int>(Enumerable.Range(1, 9));
        for (int level = 1; level < N; ++level) {
            var nextQueue = new List<int>();
            foreach (int num in queue) {
                int tailDigit = num % 10;
                var nextDigits = new int[] { tailDigit + K, tailDigit - K };
                
                foreach (int nextDigit in nextDigits) {
                    if (nextDigit >= 0 && nextDigit < 10) {
                        nextQueue.Add(num * 10 + nextDigit);
                    }
                }
            }
            queue = nextQueue;
        }
        
        return queue.ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& NumsSameConsecDiff(int N, int K) {
        if (N == 1) return Enumerable.Range(0, 10).ToArray();
        
        var queue = new List<int>(Enumerable.Range(1, 9));
        for (int level = 1; level < N; ++level) {
            var nextQueue = new List<int>();
            foreach (int num in queue) {
                int tailDigit = num % 10;
                var nextDigits = new int[] { tailDigit + K, tailDigit - K };
                
                foreach (int nextDigit in nextDigits) {
                    if (nextDigit >= 0 && nextDigit < 10) {
                        nextQueue.push_back(num * 10 + nextDigit);
                    }
                }
            }
            queue = nextQueue;
        }
        
        return queue.ToArray();
    }
}

Java solution

matched/original

class Solution {

    public int[] numsSameConsecDiff(int N, int K) {

        if (N == 1)
            return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

        List<Integer> queue = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        for(int level = 1; level < N; ++ level) {
            ArrayList<Integer> nextQueue = new ArrayList<>();
            for (Integer num : queue) {
                Integer tailDigit = num % 10;

                ArrayList<Integer> nextDigits = new ArrayList<>();
                nextDigits.add(tailDigit + K);
                if (K != 0)
                    nextDigits.add(tailDigit - K);
                for (Integer nextDigit : nextDigits) {
                    if (0 <= nextDigit && nextDigit < 10) {
                        Integer newNum = num * 10 + nextDigit;
                        nextQueue.add(newNum);
                    }
                }
            }
            queue = nextQueue;
        }

        return queue.stream().mapToInt(i->i).toArray();
    }
}

JavaScript solution

matched/original

var numsSameConsecDiff = function(N, K) {
    if (N === 1) return [...Array(10).keys()];

    let queue = [...Array(9).keys()].map(i => i + 1);
    for (let level = 1; level < N; ++level) {
        let nextQueue = [];
        for (let num of queue) {
            let tailDigit = num % 10;
            let nextDigits = [tailDigit + K, tailDigit - K];
            for (let nextDigit of nextDigits) {
                if (nextDigit >= 0 && nextDigit < 10) {
                    nextQueue.push(num * 10 + nextDigit);
                }
            }
        }
        queue = nextQueue;
    }

    return queue;
};

Python solution

matched/original

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        if N == 1:
            return list(range(10))
        
        queue = list(range(1, 10))
        for _ in range(N - 1):
            next_queue = []
            for num in queue:
                tail_digit = num % 10
                next_digits = {tail_digit + K, tail_digit - K}
                for next_digit in next_digits:
                    if 0 <= next_digit < 10:
                        next_queue.append(num * 10 + next_digit)
            queue = next_queue
        
        return queue

Go solution

matched/original

func numsSameConsecDiff(N int, K int) []int {
    if N == 1 {
        return []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    }

    queue := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    for level := 1; level < N; level++ {
        nextQueue := []int{}
        for _, num := range queue {
            tailDigit := num % 10
            nextDigits := []int{tailDigit + K, tailDigit - K}
            for _, nextDigit := range nextDigits {
                if nextDigit >= 0 && nextDigit < 10 {
                    nextQueue = append(nextQueue, num*10+nextDigit)
                }
            }
        }
        queue = nextQueue
    }

    return queue
}

Explanation

Algorithm

Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

Инициализируйте список очередей начальными цифрами от 1 до 9.

Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.

😎