LC 967. Numbers With Same Consecutive Differences

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

搜索题。两边搜索。注意Ｎ＝１的特别情况，这个时候都行。

class Solution {

private:

  unordered_map<int,vector<int>> mp ;

public:

  vector<int> numsSameConsecDiff(int N, int K) {

    if(N == ){

      vector<int> ret;

      for(int i=; i<; i++) ret.push_back(i);

      return ret;

    }

    for(int i=; i<; i++){

      int idx = i + K;

      if(idx < ) mp[i].push_back(idx);

      idx = i - K;

      if(!mp[i].empty() && mp[i][] == idx) continue;// K等于1特殊情况

      if(idx >= ) mp[i].push_back(idx);

    }

    vector<int> ret;

    for(int i=; i<; i++){

      if(!mp.count(i)) continue;

      helper(ret, N, i, );

    }

    return ret;

  }

  void helper(vector<int>& ret, int N, int start, int tmpval){

    int tt = tmpval* + start;

    if(to_string(tt).size() == N) {

      ret.push_back(tt);

      return;

    }

    if(!mp.count(start)) return ;

    vector<int> choices = mp[start];

    for(auto x : choices){

      helper(ret, N, x, tt);

    }

  }

};

再贴一个yubowen大佬的解法

typedef long long ll;

typedef vector<int> VI;

typedef pair<int,int> PII;

#define REP(i,s,t) for(int i=(s);i<(t);i++)

#define FILL(x,v) memset(x,v,sizeof(x))

const int INF = (int)1E9;

#define MAXN 100005

class Solution {

public:

  int N, K;

  void solve(int i, int ld, int val, VI &ans) {

    if (i == N) {

      ans.push_back(val);

      return;

    }

    REP(t,,) {

      int d = t ==  ? ld + K : ld - K;

      if (K ==  && t == ) continue;

      if ( <= d && d <= ) {

        solve(i+, d, val* + d, ans);

      }

    }

  }

  vector<int> numsSameConsecDiff(int _N, int _K) {

    N = _N; K = _K;

    VI ans;

    if (N == ) {

      REP(i,,) ans.push_back(i);

      return ans;

    }

    REP(s,,) solve(, s, s, ans);

    return ans;

  }

};

巴特西

LC 967. Numbers With Same Consecutive Differences

最新文章

热门文章