厦门过路费网站,福建省建设执业资格注册中心网站,企业怎样建立自己的网站,个人网站制作的主要内容其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 什么情况会用到栈
2.2 方法一#xff1a;模拟 栈
三、代码
3.1 方法一#xff1a;模拟 栈
四… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 什么情况会用到栈
2.2 方法一模拟 栈
三、代码
3.1 方法一模拟 栈
四、复杂度分析
4.1 方法一模拟 栈 前言
这是力扣的 735 题难度为中等解题方案有很多种本文讲解我认为最奇妙的一种。
慢慢开始栈的模块了这道题是一道非常好的栈的例题很有代表性。 一、题目描述
给定一个整数数组 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 。提示
2 asteroids.length 104-1000 asteroids[i] 1000asteroids[i] ! 0 二、题解 2.1 什么情况会用到栈
栈是一种数据结构其特点是后进先出Last In First OutLIFO。在算法中栈在很多情况下是非常有用的下面是一些常见的情况
括号匹配当你有一个包含括号的字符串并且你想要检查这个字符串中的括号是否匹配你可以使用栈。从左到右扫描字符串如果遇到左括号如“(”“{”或“[”则将其压入栈。如果遇到右括号则从栈顶弹出一个元素并检查它们是否匹配。如果它们不匹配那么这个字符串就不是有效的。深度优先搜索DFS在图的遍历中栈经常被用于实现深度优先搜索。首先将起始节点压入栈。然后当栈不为空时弹出栈顶元素并访问它。对于每个刚刚访问过的节点将其未被访问过的邻居节点压入栈。函数调用在计算机程序的执行中函数调用通常使用栈来管理。当一个函数被调用时它的参数和局部变量被压入栈。当函数执行结束时这些数据从栈中弹出。文本编辑器中的撤销/重做功能许多文本编辑器使用撤销/重做功能来允许用户撤销他们最近所做的更改。这些功能通常使用一个操作栈每个操作例如插入或删除文本都被压入栈。用户可以多次撤销每次撤销都从栈中弹出并反转一个操作。解析语法在编译原理中栈被广泛用于解析语法。例如在解析一个算术表达式时你可以使用栈来保持追踪括号和操作符的优先级。
这只是栈在算法中的一些应用实际上还有很多其他的应用场景。
2.2 方法一模拟 栈
思路与算法
由于碰撞抵消总是从相邻行星之间发生我们可以使用「栈」来模拟该过程。 从前往后处理所有的 asteroids[i] 使用栈存储当前未被抵消的行星当栈顶元素方向往右当前 asteroids[i] 方向往左时会发生抵消操作抵消过程根据规则进行即可。
用到变量 ok 的 true 和 false 来表示待插入栈的元素是否还大于栈顶元素。
最后把栈内元素再放入 int[] 中。 三、代码
3.1 方法一模拟 栈
Java版本
class Solution {public static int[] asteroidCollision(int[] asteroids) {ArrayDequeInteger deque new ArrayDeque();for (int i : asteroids) {boolean ok true;while (ok !deque.isEmpty() deque.peekLast() 0 i 0) {int a deque.peekLast(), b -i;if (a b) deque.pollLast();if (a b) ok false;}if (ok) deque.addLast(i);}int n deque.size();int[] res new int[n];while(!deque.isEmpty()) res[--n]deque.pollLast();return res;}
}
C版本
class Solution {
public:static vectorint asteroidCollision(vectorint asteroids) {dequeint deque;for (int i : asteroids) {bool ok true;while (ok !deque.empty() deque.back() 0 i 0) {int a deque.back(), b -i;if (a b) deque.pop_back();if (a b) ok false;}if (ok) deque.push_back(i);}vectorint res(deque.begin(), deque.end());return res;}
};Python版本
from collections import dequeclass Solution:def asteroidCollision(self, asteroids: List[int]) - List[int]:deque deque()for i in asteroids:ok Truewhile ok and deque and deque[-1] 0 and i 0:a, b deque[-1], -iif a b: deque.pop()if a b: ok Falseif ok: deque.append(i)return list(deque)Go版本
package mainimport fmtfunc asteroidCollision(asteroids []int) []int {var stack []intfor _, i : range asteroids {ok : truefor ok len(stack) 0 stack[len(stack)-1] 0 i 0 {a, b : stack[len(stack)-1], -iif a b {stack stack[:len(stack)-1]}if a b {ok false}}if ok {stack append(stack, i)}}return stack
}func main() {asteroids : []int{5, 10, -5}fmt.Println(asteroidCollision(asteroids))
}四、复杂度分析
4.1 方法一模拟 栈
时间复杂度O(n)。空间复杂度O(n)。
