268 篇文章含有標籤「leetcode」

424. Longest Repeating Character Replacement

2022年5月16日 · 閱讀時間約 1 分鐘

求最長的重複子字串，可替換 k 次。
初始化兩個指標 i 和 j 分別作為滑動視窗的左右邊界，初始時都指向字串的起始位置。
初始化一個 unordered_map<char, int> charCount。
maxCnt 變數為當前滑動視窗中出現次數最多的字元的次數，要不斷更新 maxCnt 的值。
什麼情況滑動視窗的左邊界要往右移呢？當發現滑動視窗的長度 - 出現最多頻率的字母 > 可以替換的字母 k 的時候

class Solution {
public:
    int characterReplacement(string s, int k)
    {
        int n = s.size();
        int longest = 0, maxCnt = 0;
        unordered_map<char, int> charCount;

        // i, j 分別是滑動視窗的左右邊界
        int i = 0;
        for (int j = 0; j < n; ++j)
        {
            // 右邊界的 freq + 1
            ++charCount[s[j]];

            // 更新 maxCnt 變數為當前滑動視窗中出現次數最多的字元的次數
            maxCnt = max(maxCnt, charCount[s[j]]);

            while (j - i + 1 - maxCnt > k)
            {
                // 移動左邊界
                // 左邊界字母的頻率 - 1
                --charCount[s[i]];
                ++i;
            }
            longest = max(longest, j - i + 1);
        }
        return longest;
    }
};

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

417. Pacific Atlantic Water Flow

2022年5月10日 · 閱讀時間約 3 分鐘

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below: [0,4]: [0,4] -> Pacific Ocean [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic Ocean Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]] Output: [[0,0]] Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105

class Solution {
public:
    vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        if(rows == 0 || cols == 0) return {};

        vector<vector<int>> res;

        // 分別用兩個矩陣紀錄這個格子有沒有比其他格子高
        // 起始值都是 false
        vector<vector<bool>> pacific(rows, vector<bool>(cols));
        vector<vector<bool>> atlantic(rows, vector<bool>(cols));

        // by rows 開始搜索，如果發現這個格子比周圍的格子高，就標記 true
        // 因為要找比周圍格子高的值，起始值用 INT_MIN
        for(int i = 0; i < rows; ++i) {
            dfs(heights, pacific, INT_MIN, i, 0);
            dfs(heights, atlantic, INT_MIN, i, cols - 1);
        }

        // by cols 開始搜索，如果發現這個格子比周圍的格子高，就標記 true
        // 因為要找比周圍格子高的值，起始值用 INT_MIN
        for(int j = 0; j < cols; ++j) {
            dfs(heights, pacific, INT_MIN, 0, j);
            dfs(heights, atlantic, INT_MIN, rows - 1, j);
        }

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(pacific[i][j] && atlantic[i][j]) {
                    res.push_back({i, j});
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& seen, int previous, int i, int j) {
        int rows = heights.size(), cols = heights[0].size();
        if(i < 0 || j < 0 || i >= rows || j >= cols || seen[i][j] || heights[i][j] < previous)
            return;

        // 標記這個格子比其他人高
        seen[i][j] = true;

        // 四個方向深度搜索
        for(auto& dir : directions)
            dfs(heights, seen, heights[i][j], i + dir[0], j + dir[1]);
    }
};

T: $O(M \cdot N)$
S: $O(M \cdot N)$

416. Partition Equal Subset Sum

2022年5月5日 · 閱讀時間約 2 分鐘

2D array

/*
 * @lc app=leetcode id=416 lang=cpp
 *
 * [416] Partition Equal Subset Sum
 *
 * https://leetcode.com/problems/partition-equal-subset-sum/description/
 *
 * algorithms
 * Medium (46.89%)
 * Likes:    12640
 * Dislikes: 260
 * Total Accepted:    1M
 * Total Submissions: 2.1M
 * Testcase Example:  '[1,5,11,5]'
 *
 * Given an integer array nums, return true if you can partition the array into
 * two subsets such that the sum of the elements in both subsets is equal or
 * false otherwise.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,5,11,5]
 * Output: true
 * Explanation: The array can be partitioned as [1, 5, 5] and [11].
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1,2,3,5]
 * Output: false
 * Explanation: The array cannot be partitioned into equal sum subsets.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int n = nums.size();
        int subset_sum = sum / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(subset_sum + 1));
        dp[0][0] = true;

        for (int i = 1; i <= n; i++)
        {
            int cur = nums[i - 1];
            for(int j = 0; j <= subset_sum; j++) {
                if(j < cur) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] || (dp[i - 1][j - cur]);
            }
        }
        return dp[n][subset_sum];
    }
};
// @lc code=end

T: $O(M \cdot N)$：N 是 array 長度，M 代表 subset sum 的大小。
S: $O(M \cdot N)$，M 代表 subset sum 的大小。

DP improved

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int target = sum >> 1;
        vector<bool> dp(target + 1);
        dp[0] = true;

        for (int num : nums)
        {
            for (int i = target; i >= num; --i)
            {
                dp[i] = dp[i] || dp[i - num];
                if (dp[target])
                {
                    return dp[target];
                }
            }
        }
        return dp[target];
    }
};

T: $O(M \cdot N)$：N 是 array 長度，M 代表 subset sum 的大小。
S: $O(M)$，M 代表 subset sum 的大小。

409. Longest Palindrome

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

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a" Output: 1 Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints:

1 <= s.length <= 2000
s consists of lowercase and/or uppercase English letters only.

回傳最長迴文的長度

注意題目的字母是 case sensitive，aA 不被視為迴文

class Solution {
public:
    int longestPalindrome(string s) {
        int mid = 0, res = 0;
        unordered_map<char, int> freq;
        for(auto& c : s) ++freq[c];
        for(auto& f : freq) {
            res += f.second;
            if(f.second % 2 == 1) {
                --res;
                mid = 1;
            }
        }
        return (mid == 1) ? ++res : res;
    }
};

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

399. Evaluate Division

2022年4月24日 · 閱讀時間約 3 分鐘

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

**Note:**The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000] Explanation: Given: a / b = 2.0, b / c = 3.0 queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? return: [6.0, 0.5, -1.0, 1.0, -1.0 ] note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits.

class Solution {
public:
    // 用 map 儲存 a/b, b/c 和結果的關係
    // 以 graph 的題目來說，會有一點類似 adjacencyt list 的感覺
    // {
    //   {"a", {"b": 2.0}},
    //   {"b", {"a": 1/2.0}},
    //   {"b", {"c": 3.0}},
    //   {"c", {"b": 1/3.0}},
    // }
    unordered_map<string, unordered_map<string, double>> graph;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); ++i) {
            string A = equations[i][0];
            string B = equations[i][1];
            graph[A][B] = values[i];
            graph[B][A] = 1.0 / values[i];
        }

        vector<double> res;

        for (auto q : queries) {
            // 如果沒在分母或分子的話，返回 -1.0
            if(!graph.count(q[0]) || !graph.count(q[1])) {
                res.push_back(-1.0);
                continue;
            }
            // 每次的 query，都要新的 seen hashset
            unordered_set<string> seen;
            res.push_back(dfs(q[0], q[1], seen));
        }
        return res;
    }
    double dfs(string up, string down, unordered_set<string>& seen) {
        // 如果在 graph 看到有對應的值，直接返回值是多少
        if (graph[up].count(down))
            return graph[up][down];

        // iterate graph 的分子
        for (auto a : graph[up]) {
            // 如果已經走訪過的，略過
            if (seen.count(a.first)) continue;

            // 將走訪的值插入到 set 裡
            seen.insert(a.first);

            // d = C / B
            double t = dfs(a.first, down, seen);
            // A / B = C / B * A / C
            if (t > 0.0) return t * a.second;
        }
        return -1.0;
    }
};

T: $O(M \cdot N)$
S: $O(N)$

392. Is Subsequence

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

Given two strings s and t, return trueif s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc" Output: true

Example 2:

Input: s = "axc", t = "ahbgdc" Output: false

Constraints:

0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

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

383. Ransom Note

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

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        vector<int> freq(26);

        for(auto& c : magazine) ++freq[ c - 'a'];

        for(int i = 0; i < ransomNote.size(); i++)
        {
            int c = ransomNote[i] - 'a';
            if (--freq[c] < 0) return false;
        }
        return true;
    }
};

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

380. Insert Delete GetRandom O(1)

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

class RandomizedSet {
private:
    unordered_map<int, int> m;
    vector<int> nums;
public:
    RandomizedSet() {}

    bool insert(int val)
    {
        if(m.count(val)) return false;

        nums.push_back(val);

        m[val] = nums.size() - 1;

        return true;
    }

    bool remove(int val)
    {
        if (!m.count(val)) return false;

        int lastElement = nums.back();

        nums[m[val]] = lastElement;
        m[lastElement] = m[val];

        nums.pop_back();
        m.erase(val);
        return true;
    }

    int getRandom()
    {
        return nums[rand() % nums.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

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

350. Intersection of Two Arrays II

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

這道題目要求我們找出兩個整數數列的交集，包括重複元素。具體來說:

給定兩個整數數列 nums1 和 nums2。
返回一個數列，包含兩個數列的交集元素。
結果中每個元素出現的次數，應該與它在兩個數列中出現次數的最小值一致。
結果可以按任意順序返回。

例如: 輸入: nums1 = [1,2,2,1], nums2 = [2,2] 輸出: [2,2]

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 輸出: [4,9] 或 [9,4]

解決這個問題的一種常見方法是使用 HashMap 來記錄元素出現的次數。基本步驟如下:

走訪 nums1，用 HahsMap 記錄每個元素出現的次數。
走訪 nums2，檢查每個元素是否在 HashMap 中，如果在且次數大於 0，則加入結果數列,並將 HashMap 中該元素的計數減 1。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        if (nums1.size() > nums2.size()) return intersect(nums2, nums1);

        unordered_map<int, int> m;

        for (int num : nums1) ++m[num];
        int k = 0;
        for (int num : nums2)
        {
            if (m.count(num) && m[num] >= 1)
            {
                --m[num];
                nums1[k++] = num;
            }
        }
        return vector<int>{nums1.begin(), nums1.begin() + k};
    }
};

T: $O(n + m)$
S: $O(min(n, m))$
Sort

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int i = 0, j = 0, k = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1[i] < nums2[j])
            {
                ++i;
            }
            else if (nums1[i] > nums2[j])
            {
                ++j;
            }
            else
            {
                nums1[k++] = nums1[i++];
                ++j;
            }

        }
        return vector<int>{nums1.begin(), nums1.begin() + k};
    }
};

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