• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= N <= 9
  2. 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. 1 <= N <= 9
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode299.猜数字游戏|BullsandCows发布时间:2022-07-13
下一篇:
[Swift]LeetCode1185.一周中的第几天|DayoftheWeek发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap