Bîn-hiân ê 演算法練習

856. Score of Parentheses

2022年11月17日 · 閱讀時間約 1 分鐘

/*
 * @lc app=leetcode id=856 lang=cpp
 *
 * [856] Score of Parentheses
 *
 * https://leetcode.com/problems/score-of-parentheses/description/
 *
 * algorithms
 * Medium (63.90%)
 * Likes:    5526
 * Dislikes: 229
 * Total Accepted:    205.7K
 * Total Submissions: 322.7K
 * Testcase Example:  '"()"'
 *
 * Given a balanced parentheses string s, return the score of the string.
 *
 * The score of a balanced parentheses string is based on the following
 * rule:
 *
 *
 * "()" has score 1.
 * AB has score A + B, where A and B are balanced parentheses strings.
 * (A) has score 2 * A, where A is a balanced parentheses string.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: s = "()"
 * Output: 1
 *
 *
 * Example 2:
 *
 *
 * Input: s = "(())"
 * Output: 2
 *
 *
 * Example 3:
 *
 *
 * Input: s = "()()"
 * Output: 2
 *
 *
 *
 * Constraints:
 *
 *
 * 2 <= s.length <= 50
 * s consists of only '(' and ')'.
 * s is a balanced parentheses string.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int scoreOfParentheses(string s) {
        int res = 0;
        stack<int> stk;
        for (auto c : s) {
            if(c == '(') {
                stk.push(res);
                res = 0;
            } else {
                if (res == 0) {
                    res = 1 + stk.top();
                } else {
                    res = res * 2 + stk.top();
                }
                stk.pop();
            }
        }
        return res;
    }
};
// @lc code=end

826. Most Profit Assigning Work

2022年10月26日 · 閱讀時間約 1 分鐘

工人派遣工作，一人只能被指派一個工作，但是一個工作可以被做很多遍。
初始化 {difficulty, profit} pair jobs。
排序 worker, jobs。
雙指針法搭配 Greedy 找最大獲利。

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker)
    {
        int n = difficulty.size();

        // {difficulty, profit} pair
        vector<pair<int, int>> jobs;

        for (int i = 0; i < n; ++i)
        {
            jobs.push_back({difficulty[i], profit[i]});
        }

        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());

        // 雙指針法
        int res = 0;
        int i = 0;
        int cur = 0;
        for (auto w : worker)
        {
            while (i < n && w >= jobs[i].first)
            {
                cur = max(cur, jobs[i++].second);
            }
            res += cur;
        }
        return res;
    }
};

T: $O(n \cdot \log n + m \cdot \log m)$
S: $O(n)$

783. Minimum Distance Between BST Nodes

2022年10月21日 · 閱讀時間約 1 分鐘

Hint

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int> v;
public:
    int minDiffInBST(TreeNode* root)
    {
        dfs(root);
        sort(v.begin(), v.end());
        int minDiff = INT_MAX;
        for (int i = 1; i < v.size(); i++)
        {
            minDiff = min(minDiff, v[i] - v[i - 1]);
        }
        return minDiff;
    }
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
};

T: $O()$
S: $O()$

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]

Constraints:

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st;
        vector<int> res(n);
        for(int i = 0; i < n; i++) {
            // 當遇到溫度是比較高的時候
            while(!st.empty() && temperatures[i] > temperatures[st.top()]) {
                // 拿到前一天的 index
                int previousDay = st.top(); st.pop();

                // 計算 index 差，也就是差幾天
                int dayDiff = i - previousDay;

                // 將結果存到 res
                res[previousDay] = dayDiff;
            }
            // 將 index 存到 stack
            st.push(i);
        }
        return res;
    }
};

T: $O(N)$
S: $O(N)$

733. Flood Fill

2022年10月4日 · 閱讀時間約 1 分鐘

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        int originalColor = image[sr][sc];
        if (color == originalColor) return image;
        dfs(image, sr, sc, color, originalColor);
        return image;
    }

    void dfs(vector<vector<int>>& image, int i, int j, int color, int originalColor)
    {
        if (i < 0 || j < 0 || i >= image.size() || j >= image[0].size() || image[i][j] == color || image[i][j] != originalColor)
            return;

        image[i][j] = color;

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (const auto& dir : directions)
        {
            dfs(image, i + dir[0], j + dir[1], color, originalColor);
        }
    }
};

T: $O(m \cdot n)$。
S: $O(1)$。

856. Score of Parentheses

846. Hand of Straights

844. Backspace String Compare

840. Magic Squares In Grid

826. Most Profit Assigning Work

783. Minimum Distance Between BST Nodes

746. Min Cost Climbing Stairs

739. Daily Temperatures

733. Flood Fill