Portfolio

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. For example, 01 has one leading zero and is invalid.

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]

Constraints:

2 <= n <= 9

0 <= k <= 9

풀이

재영


const numsSameConsecDiff = (n, k) => {
  const arr = [];

  const dfs = (val) => {
    if (val.length === n) return arr.push(val);

    const lastNumber = +val[val.length - 1];
    const diffSet = new Set([lastNumber - k, lastNumber + k]);

    diffSet.forEach((diff) => {
      if (diff >= 0 && diff < 10) dfs(`${val}${diff}`);
    });
  };

  for (let i = 1; i < 10; i += 1) {
    dfs(`${i}`);
  }

  return arr;
};

효성

실패한 풀이


var numsSameConsecDiff = function(n, k) {
    const answer = [];
    
    const pushToAnswer = (str) => {
        str[0] !== '0' && answer.push(Number(str));

        if(str[str.length - 1] !== '0') {
            const reversed = str.split('').reverse().join('');
            answer.push(Number(reversed));
        }
    }
    
    if(n >= 3 && k !== 0) {
        for(let i = 0; i < 10; i++) {
            let str = '';
            let temp = i;
            let canPush = true;
            str += i;

            for(let j = 0; j < n - 1; j++) {
                temp += k;
                if(temp >= 10) {
                    canPush = false;
                    break;
                }

                str += temp;
            }

            canPush && pushToAnswer(str);
        }
    }

    for(let i = 0; i < 10; i++) {
        let str1 = '';
        let str2 = '';
        const a = i;
        const b = i + k;
        
        if(b >= 10) {
            break;
        }
        
        for(let j = 0; j < n; j++) {
            if(j % 2 === 0) {
                str1 += a;
                str2 += b;
            }
            else {
                str1 += b;
                str2 += a;
            }
        }
        
        if(a === b) {
            str1[0] !== '0' && answer.push(Number(str1));
        }
        else {
            str1[0] !== '0' && answer.push(Number(str1));
            str2[0] !== '0' && answer.push(Number(str2));
            
        }
        
    }

    return answer;
};

참고한 풀이


var numsSameConsecDiff = function(N, K) {
    let prevSet = new Set([0,1,2,3,4,5,6,7,8,9]);
    
    for (let n = 2; n <= N; n++) { // we start at 2 since n = 1 is just the one digit numbers 0 through 9
        const newSet = new Set(); [] // 현재 반복문에서 찾을 수 있는 값
        
        for (const prevVal of prevSet) { // 0~9
            const lastDig = prevVal % 10; // 10의 자리수만 체킹
            
            const plusK = lastDig + K; // 1의 자리수를 찾음
            const minusK = lastDig - K; // 1의 자리수를 찾음
            
            if (prevVal > 0 && plusK < 10) newSet.add((prevVal * 10) + plusK); 
            if (prevVal > 0 && minusK >= 0) newSet.add((prevVal * 10) + minusK);
        }
        
        prevSet = newSet;
    }

    return [...prevSet];
};

Numbers With Same Consecutive Differences

풀이