[Swift]LeetCode735.行星碰撞|AsteroidCollision

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

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

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

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

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

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

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: 
asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: 
The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.

Example 2:

Input: 
asteroids = [8, -8]
Output: []
Explanation: 
The 8 and -8 collide exploding each other.

Example 3:

Input: 
asteroids = [10, 2, -5]
Output: [10]
Explanation: 
The 2 and -5 collide resulting in -5.  The 10 and -5 collide resulting in 10.

Example 4:

Input: 
asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation: 
The -2 and -1 are moving left, while the 1 and 2 are moving right.
Asteroids moving the same direction never meet, so no asteroids will meet each other.

Note:

The length of asteroids will be at most 10000.
Each asteroid will be a non-zero integer in the range [-1000, 1000].

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1:

输入: 
asteroids = [5, 10, -5]
输出: [5, 10]
解释: 
10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。

示例 2:

输入: 
asteroids = [8, -8]
输出: []
解释: 
8 和 -8 碰撞后，两者都发生爆炸。

示例 3:

输入: 
asteroids = [10, 2, -5]
输出: [10]
解释: 
2 和 -5 发生碰撞后剩下 -5。10 和 -5 发生碰撞后剩下 10。

示例 4:

输入: 
asteroids = [-2, -1, 1, 2]
输出: [-2, -1, 1, 2]
解释: 
-2 和 -1 向左移动，而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

说明:

数组 asteroids 的长度不超过 10000。
每一颗行星的大小都是非零整数，范围是 [-1000, 1000] 。

84ms

 1 class Solution {
 2     func asteroidCollision(_ asteroids: [Int]) -> [Int] {
 3         var positiveItems = [Int]()
 4         var negativeItems = [Int]()
 5         var isAddNegative = false
 6          
 7         for asteroid in asteroids
 8         {
 9             if asteroid > 0 
10             {
11                 positiveItems.append(asteroid)
12             }
13             else
14             {
15               isAddNegative = true
16               while positiveItems.count > 0
17               {
18                   
19                 if positiveItems.last! > abs(asteroid)
20                 {
21                     isAddNegative = false
22                     break
23                 }
24                 else 
25                 {
26                     let lastPositiveItem = positiveItems.removeLast()
27 
28                     if lastPositiveItem == abs(asteroid)
29                     {
30                         isAddNegative = false
31                         break
32 
33                     }                    
34                   }
35                 }
36                 
37                 if isAddNegative
38                 {
39                      negativeItems.append(asteroid)
40                 }
41             }            
42         }
43         
44         return negativeItems + positiveItems
45         
46     }
47 }

Runtime: 88 ms

Memory Usage: 19.2 MB

 1 class Solution {
 2     struct Stack<T> {
 3         private var temperatures = [T]()
 4         mutating func push(_ item:T){
 5             self.temperatures.append(item)
 6         }
 7         
 8         mutating func pop()->T?{
 9             return self.temperatures.popLast()
10         }
11         
12         func isEmpty() -> Bool {
13             return self.temperatures.isEmpty
14         }
15         
16         func peek() -> T? {
17            return self.temperatures.last
18         }
19         
20         func contents() -> [T] {
21             return self.temperatures
22         }
23     }
24     
25         func asteroidCollision(_ asteroids: [Int]) -> [Int] {
26         
27         var stack:Stack = Stack<Int>()
28         
29         for asteroid in asteroids {
30             var isShouldPush = true
31             if asteroid < 0 {
32                 // 向左移动,碰撞检测
33                 while let peek = stack.peek(),peek > 0 {
34                     if abs(peek) <= abs(asteroid) {
35                         stack.pop()
36                         isShouldPush = abs(asteroid) - abs(peek) > 0 ? true : false
37                     }else{
38                         isShouldPush = false
39                     }
40                     
41                     if isShouldPush == false{
42                         break
43                     }
44                 }
45                 
46             }
47             
48             if isShouldPush {
49                 stack.push(asteroid)
50             }
51         }
52         return stack.contents()
53     }
54 }

88ms

 1 class Solution {
 2     func asteroidCollision(_ asteroids: [Int]) -> [Int] {
 3         var output = [Int]()
 4         
 5         for index in 0..<asteroids.count {
 6             let rock = asteroids[index]
 7             if rock > 0 {
 8                 output.append(rock)
 9                 continue
10             }
11             checkExplosion(&output, rock)
12         }
13         return output
14     }
15     
16     func checkExplosion(_ output: inout [Int], _ rock: Int) {
17         if let last = output.last {
18             if last < 0 {
19                 output.append(rock)
20             } else {
21                 output.removeLast()
22                 // Explode
23                 if abs(last) > abs(rock) {
24                     output.append(last)
25                 } else if abs(last) < abs(rock) {
26                     checkExplosion(&output, rock)
27                 }
28             }
29         } else {
30             output.append(rock)
31         }
32     }
33 }

96ms

 1 class Solution {
 2     func asteroidCollision(_ asteroids: [Int]) -> [Int] {
 3         var positives = [Int]()
 4         var negatives = [Int]()
 5         
 6         for asteroid in asteroids {
 7             if asteroid > 0 {
 8                 positives.append(asteroid)
 9             } else {
10                 var shouldAppendToNegative = true
11                 
12                 while positives.count > 0 {
13                     if positives.last! > -asteroid {
14                         shouldAppendToNegative = false
15                         break
16                     } else {
17                         let last = positives.removeLast()
18                         
19                         if -asteroid == last {
20                             shouldAppendToNegative = false
21                             break
22                         }
23                     }
24                 }
25                 
26                 if shouldAppendToNegative {
27                     negatives.append(asteroid)
28                 }
29             }
30         }
31         
32         return negatives + positives
33     }
34 }

100ms

 1 class Solution {
 2     func asteroidCollision(_ asteroids: [Int]) -> [Int] {
 3         var goR = [Int]()
 4         var result = [Int]()
 5         
 6         for ast in asteroids {
 7             if ast < 0 {
 8                 var astExploded = false
 9                 while !goR.isEmpty && !astExploded {
10                     if let prev = goR.last {
11                         if prev.magnitude == ast.magnitude {
12                             goR.removeLast()
13                             astExploded = true
14                         } else if prev.magnitude < ast.magnitude {
15                             goR.removeLast()
16                         } else {
17                             astExploded = true
18                         }
19                     } else {
20                         result.append(ast)
21                     }
22                 }
23                 if !astExploded {
24                     result.append(ast)
25                 }
26             } else {
27                 goR.append(ast)
28             }
29         }
30 
31         if !goR.isEmpty {
32             result.append(contentsOf: goR)
33         }
34         return result
35     }
36 }

112ms

 1 class Solution {
 2     func asteroidCollision(_ asteroids: [Int]) -> [Int] {
 3     guard asteroids.count > 1 else{
 4         return asteroids
 5     }
 6     
 7     var stack : [Int] = []
 8     
 9     outerLoop: for asteroid in asteroids{
10         while !stack.isEmpty && stack.last! >= 0 && asteroid < 0{
11             if stack.last! + asteroid == 0{
12                 stack.removeLast()
13                 continue outerLoop
14             }else if stack.last! + asteroid > 0 {
15                 continue outerLoop
16             }else{
17                 stack.removeLast()
18             }
19         }
20         stack.append(asteroid)
21         
22     }
23     return stack
24   }
25 }