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

[Swift]LeetCode957.N天后的牢房|PrisonCellsAfterNDays

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

  • If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
  • Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Example 1:

Input: cells = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: 
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

  1. cells.length == 8
  2. cells[i] is in {0, 1}
  3. 1 <= N <= 10^9

8 间牢房排成一排,每间牢房不是有人住就是空着。

每天,无论牢房是被占用或空置,都会根据以下规则进行更改:

  • 如果一间牢房的两个相邻的房间都被占用或都是空的,那么该牢房就会被占用。
  • 否则,它就会被空置。

(请注意,由于监狱中的牢房排成一行,所以行中的第一个和最后一个房间无法有两个相邻的房间。)

我们用以下方式描述监狱的当前状态:如果第 i 间牢房被占用,则 cell[i]==1,否则 cell[i]==0

根据监狱的初始状态,在 N 天后返回监狱的状况(和上述 N 种变化)。

示例 1:

输入:cells = [0,1,0,1,1,0,0,1], N = 7
输出:[0,0,1,1,0,0,0,0]
解释:
下表概述了监狱每天的状况:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

示例 2:

输入:cells = [1,0,0,1,0,0,1,0], N = 1000000000
输出:[0,0,1,1,1,1,1,0]

提示:

  1. cells.length == 8
  2. cells[i] 的值为 0 或 1 
  3. 1 <= N <= 10^9

16ms
 1 class Solution {
 2     func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
 3         var cells = cells
 4         var N:Int = N % 14
 5         if N == 0
 6         { 
 7             N = 14
 8         }
 9         for i in 0..<N
10         {
11             var temp:[Int] = [Int](repeating:0,count:cells.count)
12             temp[0] = 0
13             temp[7] = 0
14             for j in 1..<7
15             {
16                  temp[j] = 1 - cells[j - 1]^cells[j + 1]
17             }
18             cells = temp
19         }
20         return cells
21     }
22 }

16ms

 1 class Solution {
 2     func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
 3         var currentDay = processDay(cells)
 4         let originalCells = currentDay
 5         var count = 0
 6 
 7         repeat {
 8             currentDay = processDay(currentDay)
 9             count += 1
10         } while currentDay != originalCells
11 
12         let fullCycle = (N-1) % count
13 
14         if fullCycle == 0 {
15             return currentDay
16         } else {
17             for _ in 1...fullCycle {
18                 currentDay = processDay(currentDay)
19             }
20             return currentDay
21         }
22     }
23 
24     func processDay(_ cells: [Int]) -> [Int] {
25         var newCells = [0]
26 
27         for i in 1..<cells.count - 1 {
28             newCells.append(cells[i-1] == cells[i+1] ? 1 : 0)
29         }
30 
31         newCells.append(0)
32 
33         return newCells
34     }
35 }

20ms

 1 class Solution {
 2     func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
 3         var arr:[Int] = [Int](repeating:0,count:512)
 4         var pre:[Int] = cells
 5         var cur:[Int] = [Int]()
 6         arr[getSum(pre)] = 0
 7         for i in 1...N
 8         {
 9             cur = [Int](repeating:0,count:8)
10             for j in 1..<7
11             { 
12                 if pre[j - 1] == pre[j + 1]
13                 {
14                     cur[j] = 1
15                 }
16             }
17             if arr[getSum(cur)] == 0
18             {
19                 arr[getSum(cur)] = i
20             }
21             else
22             {
23                 var p:Int = arr[getSum(cur)]
24                 var d:Int = (N - i) % (i - p)
25                 for k in 0..<512
26                 {
27                     if arr[k] == p + d
28                     {
29                         return getArr(k)
30                     }
31                 }
32             }
33             pre = cur
34         }
35         return pre
36     }
37     
38     func getArr(_ n:Int) -> [Int]
39     {
40         var n = n
41         var result:[Int] = [Int](repeating:0,count:8)
42         for i in (0...7).reversed()
43         {
44             let num:Int = Int(pow(2, Double(i)))
45             if n >= num
46             {
47                 result[i] = 1
48                 n -= num
49             }
50         }
51         return result
52     }
53     
54     func getSum(_ arr:[Int])->Int
55     {
56         var result:Int = 0
57         for  i in 0...7
58         {
59             if arr[i] == 1
60             {
61                 result += Int(pow(2, Double(i)))
62             }
63         }
64         return result
65     }
66 }

24ms
 1 class Solution {
 2     func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
 3         if N == 0 { return cells }
 4         var cells = cells
 5         var copy1day: [Int] = []
 6         var newDays = -1
 7         for i in 1...N {
 8             var prev = -1
 9             for i in 0..<7 {
10                 if cells[i + 1] == prev {
11                     prev = cells[i]
12                     cells[i] = 1
13                 } else {
14                     prev = cells[i]
15                     cells[i] = 0
16                 }
17             }
18             cells[7] = 0
19             //print("\(i): \(cells)")
20             if i == 1 {
21                 copy1day = cells
22             } else if copy1day == cells {
23                 let cycle = i - 1
24                 newDays = (N - 1) % cycle
25                 //print(cycle)
26                 //print(newDays)
27                 break
28             }
29         }
30         guard newDays >= 0 else { return cells }
31         for i in 0..<newDays {
32             var prev = -1
33             for i in 0..<7 {
34                 if cells[i + 1] == prev {
35                     prev = cells[i]
36                     cells[i] = 1
37                 } else {
38                     prev = cells[i]
39                     cells[i] = 0
40                 }
41             }
42         }
43         
44         return cells
45     }
46 }

36ms

 1 class Solution {
 2     func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
 3         let seq = sequence(first: cells, next: next)
 4         return seq.extrapolate(to: N)
 5     }
 6 }
 7 
 8 func next(_ cells: [Int]) -> [Int] {
 9     var result = Array(repeating: 0, count: cells.count)
10     
11     for (index, equal) in zip(1..., zip(cells, cells.dropFirst(2)).lazy.map(==)) {
12         result[index] = equal ? 1 : 0
13     }
14     
15     return result
16 }
17 
18 extension Sequence where Element: Hashable {
19     func extrapolate(to targetIndex: Int) -> Element {
20         precondition(targetIndex >= 0)
21         
22         var indices: [Element: Int] = [:]
23         var elements: [Element] = []
24         
25         for (index, element) in enumerated() {
26             if index == targetIndex {
27                 return element
28             } else if let previous = elements.lastIndex(of: element) {
29                 let cycle = index - previous
30                 let remaining = (targetIndex - index) % cycle
31                 return elements[previous + remaining]
32             } else {
33                 indices[element] = index
34                 elements.append(element)
35             }
36         }
37         
38         preconditionFailure("sequence terminated too early")
39     }
40 }

64ms

 1 class Solution {
 2     func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
 3         var currentDay = processDay(cells)
 4         var originalCells = currentDay
 5         var count = 0
 6 
 7         repeat { 
 8             currentDay = processDay(currentDay)
 9             count += 1
10         } while currentDay != originalCells
11         
12         let cyclesToComplete = (N-1)%count
13         
14         if cyclesToComplete == 0 {
15             return currentDay
16         } else {
17             for _ in 1...cyclesToComplete {
18                 currentDay = processDay(currentDay)
19             }        
20         }
21         
22         return currentDay
23     }
24     
25     func processDay(_ cells: [Int]) -> [Int] {
26         var newCells = [Int]()
27         newCells.append(0)
28         for index in 1..<cells.count-1 {
29             newCells.append(cells[index-1] == cells[index+1] ? 1 : 0)
30         }
31         newCells.append(0)
32         print(newCells)
33         return newCells
34     }
35 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode130. 被围绕的区域 | Surrounded Regions发布时间:2022-07-13
下一篇:
Swift中的Optional类型发布时间: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