[Swift]LeetCode967.连续差相同的数字|NumbersWithSameConsecutiveDifferences ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10201442.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 = 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 = 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

返回所有长度为 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]

提示：

1 <= N <= 9
0 <= K <= 9

16ms

 1 class Solution {
 2     
 3     func numsSameConsecDiff(_ digitCount: Int, _ difference: Int) -> [Int] {
 4         var result = [Int]()
 5 
 6         let start = (digitCount == 1) ? 0 : 1
 7         let end = 9
 8 
 9         for i in start...end {
10             let tempResult = Result()
11             numsSameConsecDiff(digitCount-1, difference, i, tempResult)
12             if !tempResult.val.isEmpty {
13                 result.append(contentsOf: tempResult.val)
14             }
15         }
16         
17         return result
18     }
19 
20     class Result {
21         var val: [Int] = []
22     }
23 
24     func numsSameConsecDiff(_ digitCount: Int, _ difference: Int, _ number: Int, _ result: Result) {
25         guard digitCount > 0 else {
26             result.val.append(number)
27             return
28         }
29 
30         let makeNumber: (Int) -> Void = { (nextDigit) in
31             if nextDigit >= 0 && nextDigit <= 9 {
32                 self.numsSameConsecDiff(digitCount - 1, difference, number * 10 + nextDigit, result)
33             }
34         }
35 
36         let lastDigit = number % 10
37 
38         makeNumber(lastDigit + difference)
39 
40         if difference != 0 {
41             makeNumber(lastDigit - difference)
42         }
43     }
44     
45 }

20ms

 1 class Solution {
 2     func numsSameConsecDiff(_ N: Int, _ K: Int) -> [Int] {
 3         var nums: Set = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 4         
 5         guard N != 0 else {
 6             return Array(nums.sorted())
 7         }
 8         
 9         guard N != 1 else {
10             nums.insert(0)
11             return Array(nums.sorted())
12         }
13         
14         for i in 1...(N - 1) {
15             var updatedNums: Set<Int> = []
16             for x in nums {
17                 let lastNumber = x % 10
18                 if lastNumber + K <= 9 {
19                     updatedNums.insert(10*x + (lastNumber + K))
20                 }
21                 
22                 if lastNumber - K >= 0 {
23                     updatedNums.insert(10*x + (lastNumber - K))
24                 }
25             }
26             nums = updatedNums
27         }
28         
29         if N == 0 {
30             nums.insert(0)
31         }
32         
33         return Array(nums.sorted())
34         
35     }
36 }

24ms

 1 class Solution {
 2     func numsSameConsecDiff(_ N: Int, _ K: Int) -> [Int] {
 3         var res = [Int]()
 4         if N == 1 {
 5             return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 6         }
 7         for i in 1...9 {
 8             res += helper(N - 1, K, i, i)
 9         }
10         return res
11     }
12     
13     func helper(_ N: Int, _ K: Int, _ num: Int, _ digit: Int) -> [Int] {
14         if digit > 10 || digit < 0 { return [] }
15         if N == 0 {
16             return []
17         }
18         var res = [Int]()
19         if digit + K < 10 {
20             res.append(num * 10 + digit + K)
21         }
22         if K != 0 {
23             if digit - K >= 0 {
24             res.append(num * 10 + digit - K)
25         }
26         }
27         
28         if N == 1 {
29             return res
30         }
31         
32         var ret = [Int]()
33         for r in res {
34             let a = helper(N - 1, K, r, r % 10)
35             for aa in a {
36                 ret.append(aa)
37             }
38         }
39         return ret
40     }
41 }

28ms

 1 class Solution {
 2     var v:[Int] = [Int]()
 3     var n:Int = 0
 4     var k:Int = 0
 5     var val:Int = 0
 6     func numsSameConsecDiff(_ N: Int, _ K: Int) -> [Int] {
 7         if N == 1
 8         {
 9             for i in 0...9
10             {
11                 v.append(i)
12             }
13             return v
14         }
15         n = N
16         k = K
17         val = 0
18         dfs(0,0)
19         v = v.sorted(by:>)
20         return v
21     }
22     
23     func dfs(_ cur:Int,_ pr:Int)
24     {
25         if cur == n
26         {
27             v.append(val)
28             return
29         }
30         for i in 0...9
31         {
32             if cur == 0
33             {
34                 if i != 0
35                 {
36                     val = i
37                     dfs(cur + 1,i)
38                 }
39             }
40             else
41             {
42                 val *= 10 
43                 val += i
44                 if abs(pr - i) == k
45                 {
46                     dfs(cur + 1, i)
47                 }
48                 val -= i
49                 val /= 10
50             }
51         }
52     }
53 }