Given a string s containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
'()[]{}'
.class Solution {
public:
bool isValid(string s) {
vector<char> stack; //or use stack<char>
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
stack.push_back(s[i]);
} else {
if (stack.size() == 0) return false;
if (s[i] == ')' && stack.back() != '(') return false;
else if (s[i] == ']' && stack.back() != '[') return false;
else if (s[i] == '}' && stack.back() != '{') return false;
else stack.pop_back();
}
}
if (stack.size() == 0) return true;
else return false;
}
};
Given the head
of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
[0, 5000]
.5000 <= Node.val <= 5000
์ ๋ฉ๋ชจ๋ฆฌ ์๋ฌ ๊ณ์ ๋๋๊ฒ stack.pop()
์ด๋ vector.pop_back()
์ ํด๋น object์ destructor๋ฅผ ๋ถ๋ฅด๋๊ตฌ๋,,
์ซ์๋ง ๋ณด๊ดํด์ ์๋ก Node๋ฅผ ์์ฑํด์ผ๊ฒ ๋ค
node๋ฅผ ์ฌ์ฌ์ฉํ๋ค๋ฉด ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋ฉด์์ ์ข์๋ฐ,,
pop์ํด์ฃผ๋ฉด ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ฌ๋ผ์ ธ์ ์ฌ๊ธฐ์ ์ ์ฉ์ ๋ชปํ๋ค
์ค์ ์์ pop์ overrideํ์ฌ ๋ฉ๋ชจ๋ฆฌ๋ ์ง์ฐ์ง ์๊ณ size์ ๊ธธ์ด๋ง ์ค์ฌ์ค๋ค๋ฉด ๋ฉ๋ชจ๋ฆฌ ๋ฉด์์ efficient ํ๊ฒ ์ฝ๋ฉ ํ ์ ์๊ฒ ๋ค.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
stack<int> reverse;
ListNode *curr = head;
while (curr && curr->next) { //๋ง์ง๋ง node๋ push ์ํ๋๋ก
reverse.push(curr->val);
curr = curr->next;
}
head = curr;
while (!reverse.empty()) {
ListNode *new_next = new ListNode(reverse.top());
curr->next = new_next;
reverse.pop();
curr = curr->next;
}
return head;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *curr = head;
while (curr && curr->next) { //๋ง์ง๋ง node๋ push ์ํ๋๋ก
reverse.push(curr->val);
curr = curr->next;
}
return do_reverse(curr, curr);
}
private:
stack<int> reverse;
ListNode *do_reverse(ListNode *head, ListNode *curr) {
if (reverse.empty()) return head;
ListNode *new_node = new ListNode(reverse.top());
curr->next = new_node;
reverse.pop();
curr = curr->next;
return do_reverse(head, curr);
}
};
.
.
.
์ด๊ฑฐ ๋ค 1ํ๋ ๋ ํ๋๊ฑด๋ฐ ์ง์ง ๋ค์ ํ๋ ค๋๊น ๋๋ฌด ๋๊ฐ๋ฆฌ ๊นจ์ง๊ฑฐ ๊ฐ๋ค ,,,
CS136 slide ๋ค์ ๋ด์ผ๊ฒ๋ค...
Design a stack that supports push
, pop
, top
, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.
void push(int val)
pushes the element val onto the stack.
void pop()
removes the element on the top of the stack.
int top()
gets the top element of the stack.
int getMin()
retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Minstack์ด๋ผ๋ stack์ ํ๋ ๋ ์์ฑํด์
์ง๊ธ๊น์ง์ minimum value๋ฅผ keep track ํ๋ค
class MinStack {
public:
MinStack() {
}
void push(int val) {
// push to stack
stk.push(val);
if (min_stk.empty() || val < min_stk.top()) {
// need to push in the new val as minimum
min_stk.push(val);
} else {
// else just push the same minimum as before
min_stk.push(min_stk.top());
}
}
void pop() {
min_stk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
private:
stack<int> stk;
stack<int> min_stk;
};
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +
, -
, *
, and /
. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Example 1:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
์ค์ฐ ์ด๊ฑฐ 136์ธ๊ฐ์์ ํ๋๊ฑฐ๋ค
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long int> stk;
// when meet operation, pop two numbers and do the calculation
// and push the calculation result to the stack
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long int n2 = stk.top();
stk.pop();
long long int n1 = stk.top();
stk.pop();
long long int calculated = 0;
if (tokens[i] == "+") calculated = n1 + n2;
if (tokens[i] == "-") calculated = n1 - n2;
if (tokens[i] == "*") calculated = n1 * n2;
if (tokens[i] == "/") calculated = n1 / n2;
stk.push(calculated);
} else {
long long int num = stoi(tokens[i]);
stk.push(num);
}
}
return stk.top();
}
};
Given an array of integers temperatures
represents the daily temperatures, return an array answer such that answer[i]
is the number of days you have to wait after the ith
day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0
instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
// pair: [index, temp]
stack<pair<int, int>> stk;
vector<int> result(n);
for (int i = 0; i < n; i++) {
int currDay = i;
int currTemp = temperatures[i];
while (!stk.empty() && stk.top().second < currTemp) {
// ๋ฐ๋ฏํด์ก๋ค!
int prevDay = stk.top().first;
int prevTemp = stk.top().second;
stk.pop();
result[prevDay] = currDay - prevDay;
}
stk.push({currDay, currTemp});
}
return result;
}
};
There are n
cars going to the same destination along a one-lane road. The destination is target
miles away.
You are given two integer array position
and speed
, both of length n
, where position[i]
is the position of the ith
car and speed[i]
is the speed of the ith car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return the number of car fleets that will arrive at the destination.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.
Example 2:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.
Example 3:
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n = position.size();
vector<pair<int, double>> cars;
for (int i = 0; i < n; i++) {
// the time it takes to reach the destination(=target)
double time = (double) (target - position[i]) / speed[i];
cars.push_back({position[i], time});
}
// sort based on the start position of cars
sort(cars.begin(), cars.end()); // sort is done based on the first element
double maxTime = 0.0;
int result = 0;
// looping from the back
for (int i = n - 1; i >= 0; i--) {
double time = cars[i].second;
if (time > maxTime) {
// when the previous car needs less time than the next car,
// they will collide and this is the car fleet!
maxTime = time;
result++;
}
}
return result;
}
};