Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite521827

Browse files
authored
Sri Hari: Batch-4/Neetcode-250/Added-articles (neetcode-gh#3781)
* Batch-4/Neetcode-250/Added-articles* Batch-4/Neetcode-250/Added-articles* Batch-4/Neetcode-250/Added-articles* Batch-4/Neetcode-250/Added-articles* Batch-4/Neetcode-250/Added-articles
1 parentde6c6a9 commite521827

26 files changed

+10686
-19
lines changed

‎articles/asteroid-collision.md

Lines changed: 239 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,239 @@
1+
##1. Stack
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defasteroidCollision(self,asteroids: List[int]) -> List[int]:
8+
stack= []
9+
for ain asteroids:
10+
while stackand a<0and stack[-1]>0:
11+
diff= a+ stack[-1]
12+
if diff<0:
13+
stack.pop()
14+
elif diff>0:
15+
a=0
16+
else:
17+
a=0
18+
stack.pop()
19+
if a:
20+
stack.append(a)
21+
return stack
22+
```
23+
24+
```java
25+
publicclassSolution {
26+
publicint[]asteroidCollision(int[]asteroids) {
27+
Stack<Integer> stack=newStack<>();
28+
for (int a: asteroids) {
29+
while (!stack.isEmpty()&& a<0&& stack.peek()>0) {
30+
int diff= a+ stack.peek();
31+
if (diff<0) {
32+
stack.pop();
33+
}elseif (diff>0) {
34+
a=0;
35+
}else {
36+
a=0;
37+
stack.pop();
38+
}
39+
}
40+
if (a!=0) {
41+
stack.add(a);
42+
}
43+
}
44+
return stack.stream().mapToInt(i-> i).toArray();
45+
}
46+
}
47+
```
48+
49+
```cpp
50+
classSolution {
51+
public:
52+
vector<int> asteroidCollision(vector<int>& asteroids) {
53+
vector<int> stack;
54+
for (int& a : asteroids) {
55+
while (!stack.empty() && a < 0 && stack.back() > 0) {
56+
int diff = a + stack.back();
57+
if (diff < 0) {
58+
stack.pop_back();
59+
} else if (diff > 0) {
60+
a = 0;
61+
} else {
62+
a = 0;
63+
stack.pop_back();
64+
}
65+
}
66+
if (a != 0) {
67+
stack.push_back(a);
68+
}
69+
}
70+
return stack;
71+
}
72+
};
73+
```
74+
75+
```javascript
76+
class Solution {
77+
/**
78+
* @param {number[]} asteroids
79+
* @return {number[]}
80+
*/
81+
asteroidCollision(asteroids) {
82+
const stack = [];
83+
for (let a of asteroids) {
84+
while (stack.length && a < 0 && stack[stack.length - 1] > 0) {
85+
const diff = a + stack[stack.length - 1];
86+
if (diff < 0) {
87+
stack.pop();
88+
} else if (diff > 0) {
89+
a = 0;
90+
} else {
91+
a = 0;
92+
stack.pop();
93+
}
94+
}
95+
if (a !== 0) {
96+
stack.push(a);
97+
}
98+
}
99+
return stack;
100+
}
101+
}
102+
```
103+
104+
::tabs-end
105+
106+
###Time & Space Complexity
107+
108+
* Time complexity: $O(n)$
109+
* Space complexity: $O(n)$
110+
111+
---
112+
113+
##2. Without Stack
114+
115+
::tabs-start
116+
117+
```python
118+
classSolution:
119+
defasteroidCollision(self,asteroids: List[int]) -> List[int]:
120+
n=len(asteroids)
121+
j=-1
122+
123+
for ain asteroids:
124+
while j>=0and asteroids[j]>0and a<0:
125+
if asteroids[j]>abs(a):
126+
a=0
127+
break
128+
elif asteroids[j]==abs(a):
129+
j-=1
130+
a=0
131+
break
132+
else:
133+
j-=1
134+
if a:
135+
j+=1
136+
asteroids[j]= a
137+
138+
return asteroids[:j+1]
139+
```
140+
141+
```java
142+
publicclassSolution {
143+
publicint[]asteroidCollision(int[]asteroids) {
144+
int n= asteroids.length;
145+
int j=-1;
146+
147+
for (int a: asteroids) {
148+
while (j>=0&& asteroids[j]>0&& a<0) {
149+
if (asteroids[j]>Math.abs(a)) {
150+
a=0;
151+
break;
152+
}elseif (asteroids[j]==Math.abs(a)) {
153+
j--;
154+
a=0;
155+
break;
156+
}else {
157+
j--;
158+
}
159+
}
160+
if (a!=0) {
161+
asteroids[++j]= a;
162+
}
163+
}
164+
165+
returnArrays.copyOfRange(asteroids,0, j+1);
166+
}
167+
}
168+
```
169+
170+
```cpp
171+
classSolution {
172+
public:
173+
vector<int> asteroidCollision(vector<int>& asteroids) {
174+
int n = asteroids.size();
175+
int j = -1;
176+
177+
for (int& a : asteroids) {
178+
while (j >= 0 && asteroids[j] > 0 && a < 0) {
179+
if (asteroids[j] > abs(a)) {
180+
a = 0;
181+
break;
182+
} else if (asteroids[j] == abs(a)) {
183+
j--;
184+
a = 0;
185+
break;
186+
} else {
187+
j--;
188+
}
189+
}
190+
if (a !=0) {
191+
asteroids[++j] = a;
192+
}
193+
}
194+
195+
asteroids.resize(j + 1);
196+
return asteroids;
197+
}
198+
};
199+
```
200+
201+
```javascript
202+
classSolution {
203+
/**
204+
*@param{number[]}asteroids
205+
*@return{number[]}
206+
*/
207+
asteroidCollision(asteroids) {
208+
let n=asteroids.length;
209+
let j=-1;
210+
211+
for (let aof asteroids) {
212+
while (j>=0&& asteroids[j]>0&& a<0) {
213+
if (asteroids[j]>Math.abs(a)) {
214+
a=0;
215+
break;
216+
}elseif (asteroids[j]===Math.abs(a)) {
217+
j--;
218+
a=0;
219+
break;
220+
}else {
221+
j--;
222+
}
223+
}
224+
if (a!==0) {
225+
asteroids[++j]= a;
226+
}
227+
}
228+
229+
returnasteroids.slice(0, j+1);
230+
}
231+
}
232+
```
233+
234+
::tabs-end
235+
236+
###Time & Space Complexity
237+
238+
* Time complexity: $O(n)$
239+
* Space complexity: $O(n)$ for the output array.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp