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

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

原作者: [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:

cells.length == 8
cells[i] is in {0, 1}
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]

提示：

cells.length == 8
cells[i] 的值为 0 或 1
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 }