Skip to content

Commit 81b9209

Browse files
author
Botao Xiao
committed
[Function add]: 1. Add leetcode solutions.
1 parent 26ffd0a commit 81b9209

7 files changed

+419
-2
lines changed

‎leetcode/224. Basic Calculator.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,3 +100,45 @@ class Solution {
100100
}
101101
}
102102
```
103+
104+
### Third Time
105+
* Method 1: Recursion 99.21% Solved by myself, no reference
106+
```Java
107+
class Solution {
108+
private int index = 0;
109+
private char[] arr;
110+
public int calculate(String s) {
111+
arr = s.toCharArray();
112+
return parse();
113+
}
114+
private int parse(){
115+
int sum = 0;
116+
int sign = 1;
117+
while(index < arr.length && arr[index] != ')'){
118+
char c = arr[index];
119+
if(c == '('){
120+
index++;
121+
sum += sign * parse();
122+
}else if(Character.isDigit(c)){
123+
int temp = arr[index] - '0';
124+
index++;
125+
while(index < arr.length && Character.isDigit(arr[index])){
126+
temp = temp * 10 + arr[index] - '0';
127+
index++;
128+
}
129+
sum += sign * temp;
130+
index--;
131+
}else if(c == '+'){
132+
sign = 1;
133+
}else if(c == '-'){
134+
sign = -1;
135+
}else if(c == ')'){
136+
index++;
137+
return sum;
138+
}
139+
index++;
140+
}
141+
return sum;
142+
}
143+
}
144+
```

‎leetcode/227. Basic Calculator II.md‎

Lines changed: 45 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
### Question
44
Implement a basic calculator to evaluate a simple expression string.
55

6-
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
6+
The expression string contains only non-negative integers, 4 operators and empty spaces . The integer division should truncate toward zero.
77

88
```
99
Example 1:
@@ -98,4 +98,47 @@ class Solution {
9898
return result;
9999
}
100100
}
101-
```
101+
```
102+
103+
### Third Time
104+
* Method 1: Stack
105+
```Java
106+
class Solution {
107+
public int calculate(String s) {
108+
int len = s.length();
109+
if(len == 0) return 0;
110+
char[] arr = s.toCharArray();
111+
Stack<Integer> numbers = new Stack<>();
112+
char operators = '+';
113+
numbers.push(0);
114+
int index = 0;
115+
while(index < len){
116+
char c = arr[index];
117+
if(Character.isDigit(c)){
118+
int temp = c - '0';
119+
index++;
120+
while(index < len && Character.isDigit(arr[index])){
121+
temp = temp * 10 + arr[index] - '0';
122+
index++;
123+
}
124+
index--;
125+
if(operators == '*'){
126+
numbers.push(temp * numbers.pop());
127+
}else if(operators == '/'){
128+
numbers.push(numbers.pop() / temp);
129+
}else if(operators == '-'){
130+
numbers.push(-temp);
131+
}else numbers.push(temp);
132+
}else if(c == '+' || c == '-' || c == '*' || c == '/'){
133+
operators = c;
134+
}
135+
index++;
136+
}
137+
int sum = 0;
138+
while(!numbers.isEmpty()){
139+
sum += numbers.pop();
140+
}
141+
return sum;
142+
}
143+
}
144+
```

‎leetcode/435. Non-overlapping Intervals.md‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
## 435. Non-overlapping Intervals
2+
3+
### Question
4+
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
5+
6+
Note:
7+
8+
You may assume the interval's end point is always bigger than its start point.
9+
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
10+
11+
```
12+
Example 1:
13+
14+
Input: [ [1,2], [2,3], [3,4], [1,3] ]
15+
16+
Output: 1
17+
18+
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
19+
20+
21+
Example 2:
22+
23+
Input: [ [1,2], [1,2], [1,2] ]
24+
25+
Output: 2
26+
27+
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
28+
29+
30+
Example 3:
31+
32+
Input: [ [1,2], [2,3] ]
33+
34+
Output: 0
35+
36+
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
37+
```
38+
39+
### Solution
40+
* Method 1: Sort + Greedy
41+
```Java
42+
class Solution {
43+
public int eraseOverlapIntervals(int[][] intervals) {
44+
int len = intervals.length;
45+
if(len == 0) return 0;
46+
Arrays.sort(intervals, (a, b)->{
47+
return a[1] - b[1];
48+
});
49+
int end = intervals[0][1];
50+
int count = 1;
51+
for(int i = 1; i < len; i++){
52+
if(intervals[i][0] >= end){
53+
end = intervals[i][1];
54+
count++;
55+
}
56+
}
57+
return len - count;
58+
}
59+
}
60+
```

‎leetcode/452. Minimum Number of Arrows to Burst Balloons.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
## 452. Minimum Number of Arrows to Burst Balloons
2+
3+
### Question
4+
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
5+
6+
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
7+
8+
```
9+
Example:
10+
11+
Input:
12+
[[10,16], [2,8], [1,6], [7,12]]
13+
14+
Output:
15+
2
16+
17+
Explanation:
18+
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
19+
```
20+
21+
### Solutions
22+
* Method 1: Greedy
23+
```Java
24+
class Solution {
25+
public int findMinArrowShots(int[][] points) {
26+
int len = points.length;
27+
if(len == 0) return 0;
28+
Arrays.sort(points, (a, b)->{
29+
return a[1] - b[1];
30+
});
31+
int end = points[0][1];
32+
int count = 1;
33+
for(int i = 1; i < len; i++){
34+
if(points[i][0] > end){
35+
end = points[i][1];
36+
count ++;
37+
}
38+
}
39+
return count;
40+
}
41+
}
42+
```

‎leetcode/716. Max Stack.md‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
## 716. Max Stack
2+
3+
### Question
4+
Design a max stack that supports push, pop, top, peekMax and popMax.
5+
6+
push(x) -- Push element x onto stack.
7+
pop() -- Remove the element on top of the stack and return it.
8+
top() -- Get the element on the top.
9+
peekMax() -- Retrieve the maximum element in the stack.
10+
popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
11+
12+
```
13+
Example 1:
14+
MaxStack stack = new MaxStack();
15+
stack.push(5);
16+
stack.push(1);
17+
stack.push(5);
18+
stack.top(); -> 5
19+
stack.popMax(); -> 5
20+
stack.top(); -> 1
21+
stack.peekMax(); -> 5
22+
stack.pop(); -> 1
23+
stack.top(); -> 5
24+
```
25+
26+
Note:
27+
1. -1e7 <= x <= 1e7
28+
2. Number of operations won't exceed 10000.
29+
3. The last four operations won't be called when stack is empty.
30+
31+
### Solutions
32+
* Method 1: LinkedList + PriorityQueue
33+
```Java
34+
class MaxStack {
35+
private PriorityQueue<Integer> pq;
36+
private LinkedList<Integer> values;
37+
/** initialize your data structure here. */
38+
public MaxStack() {
39+
this.pq = new PriorityQueue<>(new Comparator<Integer>(){
40+
@Override
41+
public int compare(Integer a, Integer b){
42+
return b - a;
43+
}
44+
});
45+
this.values = new LinkedList<>();
46+
}
47+
48+
public void push(int x) {
49+
this.values.addFirst(x);
50+
this.pq.offer(x);
51+
}
52+
53+
public int pop() {
54+
Integer first = this.values.pollFirst();
55+
pq.remove(first);
56+
return first;
57+
}
58+
59+
public int top() {
60+
return this.values.get(0);
61+
}
62+
63+
public int peekMax() {
64+
return this.pq.peek();
65+
}
66+
67+
public int popMax() {
68+
Integer max = pq.poll();
69+
this.values.remove(max);
70+
return max;
71+
}
72+
}
73+
74+
/**
75+
* Your MaxStack object will be instantiated and called as such:
76+
* MaxStack obj = new MaxStack();
77+
* obj.push(x);
78+
* int param_2 = obj.pop();
79+
* int param_3 = obj.top();
80+
* int param_4 = obj.peekMax();
81+
* int param_5 = obj.popMax();
82+
*/
83+
```

‎leetcode/735. Asteroid Collision.md‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
## 735. Asteroid Collision
2+
3+
### Question
4+
We are given an array asteroids of integers representing asteroids in a row.
5+
6+
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.
7+
8+
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.
9+
10+
```ample 1:
11+
Input:
12+
asteroids = [5, 10, -5]
13+
Output: [5, 10]
14+
Explanation:
15+
The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
16+
17+
Example 2:
18+
Input:
19+
asteroids = [8, -8]
20+
Output: []
21+
Explanation:
22+
The 8 and -8 collide exploding each other.
23+
24+
Example 3:
25+
Input:
26+
asteroids = [10, 2, -5]
27+
Output: [10]
28+
Explanation:
29+
The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
30+
31+
Example 4:
32+
Input:
33+
asteroids = [-2, -1, 1, 2]
34+
Output: [-2, -1, 1, 2]
35+
Explanation:
36+
The -2 and -1 are moving left, while the 1 and 2 are moving right.
37+
Asteroids moving the same direction never meet, so no asteroids will meet each other.
38+
```
39+
40+
Note:
41+
1. The length of asteroids will be at most 10000.
42+
2. Each asteroid will be a non-zero integer in the range [-1000, 1000]..
43+
44+
### Solutions
45+
* Method 1: Stack
46+
```Java
47+
class Solution {
48+
public int[] asteroidCollision(int[] asteroids) {
49+
Stack<Integer> stack = new Stack<>();
50+
LABEL:
51+
for(int a : asteroids){
52+
if(stack.isEmpty()){
53+
stack.push(a);
54+
}else{
55+
if((stack.peek() * a > 0) || (stack.peek() < 0 && a > 0)){
56+
stack.push(a);
57+
}else{
58+
while(!stack.isEmpty() && stack.peek() * a < 0 && Math.abs(stack.peek()) <= Math.abs(a)){
59+
if(Math.abs(stack.peek()) == Math.abs(a)){
60+
stack.pop();
61+
continue LABEL;
62+
}else{
63+
stack.pop();
64+
}
65+
}
66+
if(stack.isEmpty() || stack.peek() * a > 0 || (stack.peek() * a < 0 && Math.abs(stack.peek()) < Math.abs(a))) stack.push(a);
67+
}
68+
}
69+
}
70+
int[] result = new int[stack.size()];
71+
int count = 0, size = stack.size() - 1;
72+
while(!stack.isEmpty()){
73+
result[size--] = stack.pop();
74+
}
75+
return result;
76+
}
77+
}
78+
```

0 commit comments

Comments
 (0)