{"id":4577,"date":"2018-12-30T14:16:34","date_gmt":"2018-12-30T22:16:34","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4577"},"modified":"2018-12-31T08:49:56","modified_gmt":"2018-12-31T16:49:56","slug":"967-numbers-with-same-consecutive-differences","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/967-numbers-with-same-consecutive-differences\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 967. Numbers With Same Consecutive Differences"},"content":{"rendered":"\n

Problem<\/strong><\/h2>\n\n\n\n

Return all non-negative<\/strong> integers of length N<\/code> such that the absolute difference between every two consecutive digits is K<\/code>.<\/p>\n\n\n\n

Note that every<\/strong> number in the answer must not<\/strong> have leading zeros except<\/strong> for the number 0<\/code> itself. For example, 01<\/code> has one leading zero and is invalid, but 0<\/code> is valid.<\/p>\n\n\n\n

You may return the answer in any order.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>N = 3, K = 7\nOutput: <\/strong>[181,292,707,818,929]\nExplanation: <\/strong>Note that 070 is not a valid number, because it has leading zeroes.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>N = 2, K = 1\nOutput: <\/strong>[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= N <= 9<\/code><\/li>
  2. 0 <= K <= 9<\/code><\/li><\/ol>\n\n\n\n
    Solution: Search<\/strong><\/h2>\n\n\n\n
    Time complexity: O(2^N)
    Space complexity: O(N)<\/p>\n\n\n\n
    \n
    C++\/DFS<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 8ms\nclass Solution {\npublic:\n  vector numsSameConsecDiff(int N, int K) {\n    vector ans;\n    if (N == 1) ans.push_back(0);\n    for (int i = 1; i <= 9; ++i)\n      dfs(N - 1, K, i, ans);\n    return ans;\n  }\nprivate:\n  void dfs(int N, int K, int cur, vector& ans) {\n    if (N == 0) {\n      ans.push_back(cur);\n      return;\n    }\n    int l = cur % 10;\n    if (l + K < 10)\n      dfs(N - 1, K, cur * 10 + l + K, ans);\n    if (l >= K && K != 0)\n      dfs(N - 1, K, cur * 10 + l - K, ans);\n  }\n};\n<\/pre>\n\n<\/div>
    C++\/BFS<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 4 ms\nclass Solution {\npublic:\n  vector numsSameConsecDiff(int N, int K) {\n    deque q{1,2,3,4,5,6,7,8,9};\n    if (N == 1) q.push_front(0);\n    while (--N) {\n      int size = q.size();\n      while (size--) {\n        int num = q.front(); q.pop_front();\n        int r = num % 10;\n        if (r + K <= 9)\n          q.push_back(num * 10 + r + K);\n        if (r - K >= 0 && K != 0)\n          q.push_back(num * 10 + r - K);\n      }\n    }\n    return vector(cbegin(q), cend(q));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem 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.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,177,42],"class_list":["post-4577","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-medium","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4577","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4577"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4577\/revisions"}],"predecessor-version":[{"id":4588,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4577\/revisions\/4588"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}