[Swift]LeetCode975.奇偶跳|OddEvenJump

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

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

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

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

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallestsuch index j.
(It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

Example 1:

Input: [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can jump to i = 2 (since A[2] is the smallest among A[1], A[2], A[3], A[4] that is greater or equal to A[0]), then we can't jump any more.
From starting index i = 1 and i = 2, we can jump to i = 3, then we can't jump any more.
From starting index i = 3, we can jump to i = 4, so we've reached the end.
From starting index i = 4, we've reached the end already.
In total, there are 2 different starting indexes (i = 3, i = 4) where we can reach the end with some number of jumps.

Example 2:

Input: [2,3,1,1,4]
Output: 3
Explanation: 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:

During our 1st jump (odd numbered), we first jump to i = 1 because A[1] is the smallest value in (A[1], A[2], A[3], A[4]) that is greater than or equal to A[0].

During our 2nd jump (even numbered), we jump from i = 1 to i = 2 because A[2] is the largest value in (A[2], A[3], A[4]) that is less than or equal to A[1].  A[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3.

During our 3rd jump (odd numbered), we jump from i = 2 to i = 3 because A[3] is the smallest value in (A[3], A[4]) that is greater than or equal to A[2].

We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.

In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indexes (i = 1, i = 3, i = 4) where we can reach the end with some number of jumps.

Example 3:

Input: [5,1,3,4,2]
Output: 3
Explanation: 
We can reach the end from starting indexes 1, 2, and 4.

Note:

1 <= A.length <= 20000
0 <= A[i] < 100000

给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。

你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：

在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] => A[j]，A[j] 是可能的最大值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
（对于某些索引 i，可能无法进行合乎要求的跳跃。）

如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。

返回好的起始索引的数量。

示例 1：

输入：[10,13,12,14,15]
输出：2
解释： 
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 2：

输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：

在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。

在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。

在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。

我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。

类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 3：

输入：[5,1,3,4,2]
输出：3
解释： 
我们可以从起始索引 1，2，4 出发到达数组末尾。

提示：

1 <= A.length <= 20000
0 <= A[i] < 100000

Runtime: 224 ms

Memory Usage: 22.1 MB

 1 class Solution {
 2     func oddEvenJumps(_ A: [Int]) -> Int {
 3         var A = A
 4         let maxNum:Int = rerange(&A)
 5         var map:[Int] = [Int](repeating:0,count:maxNum + 1)
 6         var res:Int = 1
 7         let N:Int = A.count
 8         map[A[N-1]] = N-1
 9         var odds:[Bool] = [Bool](repeating:false,count:N)
10         var evens:[Bool] = [Bool](repeating:false,count:N)
11         odds[N-1] = true
12         evens[N-1] = true
13         for i in stride(from:N - 2,through:0,by: -1)
14         {
15             let key:Int = A[i]
16             let minGE:Int = ceilingIndex(map,key)
17             let maxLE:Int = floorIndex(map,key)
18             if minGE != 0 && evens[minGE]
19             {
20                 res += 1
21                 odds[i] = true
22             }
23             if maxLE != 0 && odds[maxLE]
24             {
25                 evens[i] = true
26             }
27             map[key] = i
28         }
29         return res
30     }
31     
32     func rerange(_ A:inout [Int]) -> Int {
33         var minNum:Int = A[0]
34         var maxNum:Int = A[0]
35         for v in A
36         {
37             if v < minNum {minNum = v}
38             if v > maxNum {maxNum = v}
39         }
40         var map:[Int] = [Int](repeating:0,count:maxNum - minNum + 1)
41         for v in A
42         {
43             map[v - minNum] = 1
44         }
45         var ix:Int = 0
46         for i in 0..<map.count
47         {
48             if map[i] != 0
49             {
50                 ix += 1
51                 map[i] = ix
52             }
53         }
54         for i in 0..<A.count
55         {
56             A[i] = map[A[i] - minNum]
57         }
58         return ix
59     }
60     
61     func ceilingIndex(_ map:[Int],_ v:Int) -> Int
62     {
63          var v = v
64         while(v < map.count)
65         {
66             if map[v] != 0
67             {
68                 return map[v]
69             }
70             v += 1
71         }
72         return 0
73     }
74     
75     func floorIndex(_ map:[Int],_ v:Int) -> Int
76     {
77         var v = v
78         while(v > 0)
79         {
80             if map[v] != 0
81             {
82                 return map[v]
83             }
84             v -= 1
85         }
86         return 0
87     }
88 }

428ms

 1 class Solution {
 2     func oddEvenJumps(_ A: [Int]) -> Int {
 3         var nextHigher = Array(repeating: 0, count: A.count)        
 4         var stack = [Int]()
 5         for (i, a) in ((A.enumerated()).sorted { $0.1 < $1.1 }) {
 6             while !stack.isEmpty && stack.last! < i {
 7                 nextHigher[stack.removeLast()] = i
 8             }
 9             stack.append(i)
10         }
11                 
12         var nextLower = Array(repeating: 0, count: A.count)
13         stack = []
14         for (i, a) in ((A.enumerated()).sorted { $0.1 > $1.1 }) {
15             while !stack.isEmpty && stack.last! < i {
16                 nextLower[stack.removeLast()] = i
17             }
18             stack.append(i)
19         }
20         
21         var higher = Array(repeating: 0, count: A.count)
22         var lower = Array(repeating: 0, count: A.count)
23         higher[A.count-1] = 1
24         lower[A.count-1] = 1
25         for i in (0..<(A.count - 1)).reversed() {
26             higher[i] = lower[nextHigher[i]]
27             lower[i] = higher[nextLower[i]]
28         }
29         
30         return higher.reduce(0, +)
31     }
32 }

444ms

 1 class Solution {
 2     func oddEvenJumps(_ A: [Int]) -> Int {
 3         guard A.count > 1 else { return A.count }
 4         
 5         var map = [(Int, Int)]()
 6         for (index, item) in A.enumerated() {
 7             map.append((item, index))
 8         }
 9         
10         let nextHeigher = generateNextHeigher(map)
11         let nextLower = generateNextLower(map)
12         
13         var heigher = Array(repeating: 0, count: A.count)
14         var lower = Array(repeating: 0, count: A.count)
15         heigher[A.count - 1] = 1
16         lower[A.count - 1] = 1
17         
18         for i in (0..<A.count - 1).reversed() {
19             heigher[i] = lower[nextHeigher[i]]
20             lower[i] = heigher[nextLower[i]]
21         }
22         
23         return heigher.reduce(0, +)
24         
25     }
26     
27     func generateNextHeigher(_ map: [(Int, Int)]) -> [Int] {
28         let map = map.sorted {
29             if $0.0 == $1.0 { return $0.1 < $1.1 }
30             return $0.0 < $1.0
31         }
32         
33         var nextHeigher = Array(repeating: 0, count: map.count)
34         var stack = [Int]()
35         
36         for (item, index) in map {
37             while stack.count > 0 && stack.last! < index {
38                 nextHeigher[stack.popLast()!] = index
39             }
40             stack.append(index)
41         }
42         
43         return nextHeigher
44     }
45     
46     func generateNextLower(_ map: [(Int, Int)]) -> [Int] {
47         let map = map.sorted {
48             if $0.0 == $1.0 { return $0.1 < $1.1 }
49             return $0.0 > $1.0
50         }
51         
52         var nextLower = Array(repeating: 0, count: map.count)
53         var stack = [Int]()
54         
55         for (item, index) in map {
56             while stack.count > 0 && stack.last! < index {
57                 nextLower[stack.popLast()!] = index
58             }
59             stack.append(index)
60         }
61         
62         return nextLower
63     }
64 }

800ms

  1 class Solution {
  2     private struct Record: CustomStringConvertible {
  3         var oddFeasible: Bool
  4         var evenFeasible: Bool
  5         
  6         init() {
  7             self.oddFeasible = false
  8             self.evenFeasible = false
  9         }
 10         
 11         var description: String {
 12             return "\(oddFeasible) + \(evenFeasible)"
 13         }
 14     }
 15     
 16     func oddEvenJumps(_ A: [Int]) -> Int {
 17         let path = searchPath(A)
 18         var records = [Record]()
 19         
 20         var lastRecord = Record()
 21         lastRecord.oddFeasible = true
 22         lastRecord.evenFeasible = true
 23         records.append(lastRecord)
 24         
 25         for idx in stride(from: A.count-1, to: 0, by: -1) {
 26             var record = Record()
 27             
 28             let nextJumpByOdd = path.oddPath[idx-1]
 29             if nextJumpByOdd >= 0 {
 30                 record.oddFeasible = records[A.count - 1 - nextJumpByOdd].evenFeasible
 31             } else {
 32                 record.oddFeasible = false
 33             }
 34             
 35             let nextJumpByEven = path.evenPath[idx-1]
 36             if nextJumpByEven >= 0 {
 37                 record.evenFeasible = records[A.count - 1 - nextJumpByEven].oddFeasible
 38             } else {
 39                 record.evenFeasible = false
 40             }
 41             
 42             records.append(record)
 43         }
 44         
 45         return records.reduce(0) {
 46             if $1.oddFeasible {
 47                 return $0 + 1
 48             } else {
 49                 return $0
 50             }
 51         }
 52     }
 53     
 54     struct Path {
 55         var evenPath: [Int]
 56         var oddPath: [Int]
 57         
 58         init() {
 59             oddPath = []
 60             evenPath = []
 61         }
 62     }
 63     
 64     struct Node: Comparable, Equatable {
 65         let num: Int
 66         let idx: Int
 67         
 68         static func <(_ lhs: Node, _ rhs: Node) -> Bool {
 69             return lhs.num < rhs.num
 70         }
 71         
 72         static func ==(_ lhs: Node, _ rhs: Node) -> Bool {
 73             return lhs.num == rhs.num
 74         }
 75     }
 76     
 77     private func searchPath(_ A: [Int]) -> Path {
 78         var path = Path()
 79         var sortedSuffix = [Node]()
 80         
 81         for idx in stride(from: A.count, to: 0, by: -1) {
 82             let node = Node(num: A[idx-1], idx: idx-1)
 83             let index = sortedSuffix.sortedInsert(node)
 84             if index < sortedSuffix.count-1 {
 85                 let rightNode = sortedSuffix[index+1]
 86                 path.oddPath.insert(rightNode.idx, at: 0)
 87                 if rightNode == node {
 88                     path.evenPath.insert(rightNode.idx, at: 0)
 89                     continue
 90                 }
 91             } else {
 92                 path.oddPath.insert(-1, at: 0)
 93             }
 94             
 95             if index > 0 {
 96                 let leftVal = sortedSuffix[index - 1]
 97                 var leftIdx = index - 2
 98                 while leftIdx >= 0 && leftVal == sortedSuffix[leftIdx] {
 99                     leftIdx = leftIdx - 1
100                 }
101                 
102                 let leftNode = sortedSuffix[leftIdx + 1]
103                 path.evenPath.insert(leftNode.idx, at: 0)
104             } else {
105                 path.evenPath.insert(-1, at: 0)
106             }
107         }
108         
109         return path
110     }
111 }
112 
113 extension Array where Element: Comparable {
114     mutating func sortedInsert(_ elm: Element) -> Int {
115         if count == 0 {
116             append(elm)
117             return 0
118         }
119         
120         if count == 1 {
121             if elm <= self[0] {
122                 insert(elm, at: 0)
123                 return 0
124             } else {
125                 append(elm)
126                 return 1
127             }
128         }
129         
130         if count > 1 {
131             if elm <= self[0] {
132                 insert(elm, at: 0)
133                 return 0
134             } else if elm > self[count-1] {
135                 insert(elm, at: count)
136                 return count-1
137             }
138         }
139         
140         let idx = binarySearch(elm, 0, count-1)
141         insert(elm, at: idx)
142         return idx
143     }
144     
145     // Invariant: start < elm, end >= elm, end != start
146     private func binarySearch(_ elm: Element, _ start: Int, _ end: Int) -> Int {
147         if end - start == 1 {
148             return end
149         }
150         
151         let mid: Int = (start + end) / 2
152         if self[mid] < elm {
153             return binarySearch(elm, mid, end)
154         } else if self[mid] > elm {
155             return binarySearch(elm, start, mid)
156         } else {
157             return mid
158         }
159     }
160 }

2328ms

  1 class Solution {
  2     func oddEvenJumps(_ A: [Int]) -> Int {
  3         guard A.count > 0 else { return 0 }
  4         
  5         var map = [Int: Int]()
  6         
  7         let tree = AVLTree<Int>()
  8         
  9         var minMaxArr: [Int?] = Array(repeating: nil, count: A.count)
 10         var maxMinArr: [Int?] = Array(repeating: nil, count: A.count)
 11         
 12         var i = A.count - 1
 13         while i >= 0 {
 14             let this = A[i]
 15             
 16             if let node = tree.root?.find(to: this, rule: .closestRight) {
 17                 minMaxArr[i] = map[node.value]
 18  
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋