💡 Valid Parentheses

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
• s consists of parentheses only '()[]{}'.

Solution

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;
    }
};

💡 Reverse Linked List

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:

• The number of nodes in the list is the range [0, 5000].
• 5000 <= Node.val <= 5000

Solution

1. iteratively

아 메모리 에러 계속 나던게 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;
        
    }
};

2. recursively

/**
 * 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 다시 봐야겟다...

---

💡 Min Stack

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.

Solution

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 Reverse Polish Notation

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

Solution

오우 이거 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();
    }
};

---

💡 Daily Temperatures

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]

Solution

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;
    }
};

---

💡 Car Fleet

There are ncars 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.

Solution

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;
    }
};