Leetcode

2136. Earliest Possible Day of Full Bloom Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Greedy、Sorting 一、題目 You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed take time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each: plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total. growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever. From the beginning of day 0, you can plant the seeds in any order. Return the earliest possible day where all seeds are blooming. Example 1: ...

難度分: 2063 這題是 rolling hash，同樣樣到 sliding window 的概念，由左至右需要處理除法問題，會使問題的難度增加，所以這題逆其道而行，從右至左，那就可以把除法問題變成乘法問題了。 在處理商數時，要小心處理負數，由於商數 d 必定介於 0~k之間，可以利用 $$ \boxed{\mod(\mod(a)-\mod(b)+k)} $$ 證明： $$ \boxed{ \begin{array}{ll} 0\le\mod(a)<k \\ 0\le\mod(b)<k \\ -k<\mod(a)-\mod(b)<k & 在取 \mod 前先整理成正數\\ 0<\mod(a)-\mod(b)+k< 2k \\ 0<\mod(\mod(a)-\mod(b)+k) < k \end{array} } $$ 令 str = dcba，k = 3，已知 curr = mod(ap^2+bp+c, m) 求 mod(bp^2+cp+d, m) \(\mod(bp^2+cp+d)\) \(\quad = \mod((ap^2+bp+c)\times p +d-ax^3)\) \(\quad = \mod(\mod(ap^2+bp+c)\times p +d+m-\mod(ax^3))\) \(\quad = \mod(\text{curr}\times p +d+m-\mod(ax^3))\) class Solution { public: string subStrHash(string s, int p, int mod, int k, int val) { int n = s.size(); long pk = 1, curr = 0; for (int i = 0; i < k; i++) { curr = (curr * p + (s[n-1-i]-'a'+1)) % mod; pk = (pk * p) % mod; } int j = n-k; for (int i = k; i < n; i++) { curr = (curr * p + (s[n-1-i]-'a'+1) + mod - ((s[n-1-i+k]-'a'+1) * pk) % mod) % mod; if (curr == val) j = n-1-i; } return s.substr(j, k); } };

18. 4Sum Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Two Pointer、Sorting 一、題目 Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order. Example 1: Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Example 2: ...

17. Letter Combinations of a Phone Number Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Hash Table,String,Backtracking 一、題目 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example 1: Input: digits = “23” Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] Example 2: ...

no. </strong> <ul> <li>Hardness: \(\color{orange}\textsf{Medium}\)</li> <li>Ralated Topics: <code>Array</code>、<code>Two Pointers</code>、<code>Sorting</code></li> </ul> <hr> <h3 id="一題目">一、題目</h3> <p>Given an integer array <code>nums</code> of length <code>n</code> and an integer <code>target</code>, find three integers in <code>nums</code> such that the sum is closet to <code>target</code>. Return *the sum of the three integers`. You may assume that each input would have exactly one solution. <p><strong>Example 1:</strong> <ul> <li><strong>Input:</strong> nums = [-1,2,1,-4], target = 1</li> <li><strong>Output:</strong> 2</li> <li><strong>Explanation:</strong> The sum that is closet to the target is 2. (-1 + 2 + 1 = 2).</li> </ul> <p><strong>Example 2:</strong> ...

15. 3Sum Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Two Pointer、Sorting 一、題目 Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Example 2: ...

這一題與 567 類似，差別是將字元比較改成字串比較。 注意因為字串比較不一定是從 0 開始，所以還要多一個 for start in range(0, wordLen) 的迴圈來調整起始位置 class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { unordered_map<string, int> cnt1, cnt2; for (const auto& word : words) cnt1[word]++; int wordLen = words[0].size(); int k = words.size(); vector<int> res; if (s.size() < wordLen * k) return res; for (int start = 0; start < wordLen; start++) { cnt2.clear(); int valid = 0; for (int i = start; i < k * wordLen; i += wordLen) { string sin = s.substr(i, wordLen); if (cnt1.count(sin) && ++cnt2[sin] == cnt1[sin]) valid++; } if (valid == cnt1.size()) res.push_back(start); for (int i = start + k * wordLen; i < s.size(); i += wordLen) { string sin = s.substr(i, wordLen); if (cnt1.count(sin) && ++cnt2[sin] == cnt1[sin]) valid++; string sout = s.substr(i-k*wordLen, wordLen); if (cnt1.count(sout) && cnt2[sout]-- == cnt1[sout]) valid--; if (valid == cnt1.size()) res.push_back(i-(k-1)*wordLen); } } return res; } };

這一題與 567 類似，是找 anagram 題題目，令 p 長度為 window size，即可解。 class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> res; int k = p.size(); int n = s.size(); if (n < k) return res; unordered_map<char,int> cnt1, cnt2; for (const auto& c : p) cnt1[c]++; int valid = 0; for (int i = 0; i < k; i++) { if (cnt1.count(s[i]) && ++cnt2[s[i]] == cnt1[s[i]]) valid++; } if (valid == cnt1.size()) res.push_back(0); for (int i = k; i < n; i++) { if (cnt1.count(s[i]) && ++cnt2[s[i]] == cnt1[s[i]]) valid++; if (cnt1.count(s[i-k]) && cnt2[s[i-k]]-- == cnt1[s[i-k]]) valid--; if (valid == cnt1.size()) res.push_back(i-k+1); } return res; } };

這一題同樣是定長度的 sliding window，window size 為 s1.size() class Solution { public: bool checkInclusion(string s1, string s2) { unordered_map<char,int> map, map2; int k = s1.size(); int n = s2.size(); if (k > n) return false; int valid = 0; for (const auto& c : s1) map[c]++; for (int i = 0; i < k; i++) { if (!map.count(s2[i])) continue; if (++map2[s2[i]] == map[s2[i]]) valid++; } if (valid == map.size()) return true; for (int i = k; i < n; i++) { if (map.count(s2[i]) && ++map2[s2[i]] == map[s2[i]]) valid++; if (map.count(s2[i-k]) && map2[s2[i-k]]-- == map[s2[i-k]]) valid--; if (valid == map.size()) return true; } return false; } };

難度分: 2006 這一題如果沒有條件一，則很簡單，根據奇偶數索引位置，判斷是否要 flip 就可以了。 int minFlips(string s) { int n = s.size(); int ans1 = 0, ans2 = 0; for (int i = 0; i < n; i++) { if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1; if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2; } int ans = min(ans1, ans2); } 但這一題加上條件一，可以用很精巧的手法，把它轉成 sliding window 的問題，將字串重覆兩次，以原字串長度作為 window size，可解這題。 class Solution { public: int minFlips(string s) { int k = s.size(); s += s; int ans1 = 0, ans2 = 0; for (int i = 0; i < k; i++) { if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1; if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2; } int ans = min(ans1, ans2); for (int i = k; i < s.size(); i++) { if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1; if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2; if (((i - k) % 2 == 0 && s[i - k] != '1') || ((i - k) % 2 == 1 && s[i - k] != '0')) --ans1; if (((i - k) % 2 == 0 && s[i - k] != '0') || ((i - k) % 2 == 1 && s[i - k] != '1')) --ans2; ans = min({ans1, ans2, ans}); } return ans; } };