Stack

Sujinยท2022๋…„ 12์›” 2์ผ
0

LeetCode

๋ชฉ๋ก ๋ณด๊ธฐ
4/24
post-thumbnail
post-custom-banner

๐Ÿ’ก 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;
    }
};
profile
๋ฉ‹์ฐ ๋‚˜ ,,(๊ฐ€ ๋˜๊ณ ํ”ˆ)
post-custom-banner

0๊ฐœ์˜ ๋Œ“๊ธ€