mysql视频 django 分布式调度 USB串口通信 xpath vue异步加载组件 网站后台管理模板 ppt视频教程下载 ajax的get请求 jquery移除子元素 linux查看mysql进程 js回调函数写法 java 数据分析 mysql新增用户和权限 爬虫数据清洗 python入门 python安装mysql python条件判断 python安装环境变量 java获取当前年份 java实用教程 java时间格式 java时间戳转日期 java的框架 linux用户管理 linux云服务器 pascal教程 骁龙660和625 dg分区 c语言代码表白 begininvoke 手机模拟器下载 vfloppy 魔兽地图七个人 刷声望 dll下载 显示器面板类型 古风头像女动漫 js跳出for循环 有线网卡驱动下载
当前位置: 首页 > 学习教程  > 编程语言

【栈】B031_LC_行星碰撞(模拟碰撞+处理特殊情况)

2020/8/11 19:13:35 文章标签:

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

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

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

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

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

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

方法一:

思路

这题核心逻辑是需要一直模拟碰撞过程,而不是逐个添加;

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& A) {
        int n=A.size();
    	stack<int> st;

    	for (int w : A) {
    		if (w < 0) {
    			while (!st.empty() && st.top()>0 && st.top()<-w) st.pop();
                if (!st.empty() && st.top()+w==0) st.pop();
                else if (st.empty() || st.top()<0) st.push(w);
    		} else {
    			st.push(w);
    		}
    	}
    	vector<int> ans(st.size());
    	int i=st.size()-1;
    	while (!st.empty()) ans[i--]=st.top(), st.pop();
    	return ans;
    }
};

复杂度分析

  • TimeO(n)O(n)
  • SpaceO(n)O(n)

本文链接: http://www.dtmao.cc/news_show_100091.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?