[Swift Weekly Contest 119]LeetCode975. 奇偶跳 | Odd Even Jum
You are given an integer array? You may from index?
A starting index is?good?if,starting from that index,you can reach the end of the array (index? 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,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[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[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,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,2]
Output: 3 Explanation: We can reach the end from starting indexes 1,2,and 4.?
Note:
给定一个整数数组? 你可以按以下方式从索引?
如果从某一索引开始跳跃一定次数(可能是 0 次或多次),就可以到达数组的末尾(索引? 返回好的起始索引的数量。? 示例 1: 输入:[10,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,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 = 4)出发,通过一定数量的跳跃到达数组末尾。 示例 3: 输入:[5,2] 输出:3 解释: 我们可以从起始索引 1,2,4 出发到达数组末尾。? 提示:
超出时间限制 1 class Solution { 2 func oddEvenJumps(_ A: [Int]) -> Int { 3 var n:Int = A.count 4 var res:Int = 1 5 var higher:[Bool] = [Bool](repeating:false,count:n) 6 var lower:[Bool] = [Bool](repeating:false,count:n) 7 higher[n - 1] = true 8 lower[n - 1] = true 9 var map:[Int:Int] = [Int:Int]() 10 map[A[n - 1]] = n - 1 11 for i in stride(from:n - 2,through:0,by:-1) 12 { 13 var hi:Int? = nil 14 for num in map.keys 15 { 16 if num >= A[i] 17 { 18 if hi == nil 19 { 20 hi = num 21 } 22 else 23 { 24 if num < hi! 25 { 26 hi = num 27 } 28 } 29 } 30 } 31 var lo:Int? = nil 32 for num in map.keys 33 { 34 if num <= A[i] 35 { 36 if lo == nil 37 { 38 lo = num 39 } 40 else 41 { 42 if num > lo! 43 { 44 lo = num 45 } 46 } 47 } 48 } 49 if hi != nil && map[hi!] != nil 50 { 51 higher[i] = lower[map[hi!]!] 52 } 53 54 if lo != nil && map[lo!] != nil 55 { 56 lower[i] = higher[map[lo!]!] 57 } 58 if higher[i] 59 { 60 res += 1 61 } 62 map[A[i]] = i 63 } 64 return res 65 } 66 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |