You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

967. 连续差相同的数字 - Numbers With Same Consecutive Differences

. 2 min read

[递归]


​        返回所有长度为 N 且满足其每两个连续位上的数字之间的差的绝对值为 K非负整数
​        请注意,除了数字 0 本身之外,答案中的每个数字都不能有前导零。例如,01 因为有一个前导零,所以是无效的;但 0 是有效的。
​        你可以按任何顺序返回答案。


示例 1:

输入:N = 3, K = 7
输出:[181,292,707,818,929]
解释:注意,070 不是一个有效的数字,因为它有前导零。

示例 2:

输入:N = 2, K = 1
输出:[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

solution

My solution

class Solution {
    public int[] numsSameConsecDiff(int N, int K) {
		int current_bit = 1;
		int current_num = 0;
		Stack<Integer> stack = new Stack<Integer>();
        if(N==1)
           stack.push(0); 
		int bit = N;
		for (int i = 1; i < 10; i++) {
			current_bit = i;
			current_num = 0;
			solve(stack, N, K, current_bit, current_num, bit);
		}
		int[] result = new int[stack.size()];
		int index = 0;
		while (!stack.isEmpty())
			result[index++] = stack.pop();
		System.out.println(Arrays.toString(result));
		return result;
	}

	public void solve(Stack<Integer> stack, int N, int K, int current_bit, int current_num, int bit) {
		current_num += current_bit * (int) Math.pow(10, --bit);
		if (bit == 0) {
			stack.push(current_num);
			return;
		}
		if (current_bit + K <= 9)
			solve(stack, N, K, current_bit + K, current_num, bit);
		if (K != 0 && current_bit - K >= 0)
			solve(stack, N, K, current_bit - K, current_num, bit);
	}
}

复杂度分析

Other Solution

class Solution {
public:
    void dfs(int N, int K, int last, int rate, vector<int> &ans){
        if (N==0) {
            ans.push_back(rate); 
            return;
        }
        
        if (last==-1) {
            for (int x=1; x<=9; x++)
                dfs(N-1, K, x, rate*10+x, ans);
        }else{
            if (last-K>=0) dfs(N-1, K, last-K, rate*10+last-K, ans);
            if (K!=0 && last+K<=9) dfs(N-1, K, last+K, rate*10+last+K, ans);
        }
        
        
    }
    
    vector<int> numsSameConsecDiff(int N, int K) {
        vector<int> ans; ans.clear();
        
        if (N==1) {
            for (int i=0; i<10; i++) ans.push_back(i);
            return ans;
        }
        
        dfs(N, K, -1, 0, ans);
        return ans;
    }
};

复杂度分析