Leetcode

1293. Shortest Path in a Grid with Obstacles Elimination Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Breadth-First Search、Matrix 一、題目 You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacles). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right conrer m-1, n-1 given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1. ...

難度分: 2449 這題是一個定長的 sliding window，比較難想的是 window size 是 k * 1, k * 2, … 到 k * 26，因為只有 26 個英文字母，所以最多只可能到 26 * k 的長度。 額外需要檢查相鄰的字母是否距離 <= 2，我使用的方法是找到一個 j 記錄最大的不符合的索引值，所以直要 window 不包含該 j，window 內的所字元都會滿足。 所以 pesudo code 會是 for (int c = 1; c <= 26; i++) { // window size int windowSize = c * k; // construct window for (int i = 0; i < windowSize; i++) { // 處理 j // 計算進入 window } // 確認初始的 window 是否滿足 // rolling windo for (int i = windowSize; i < n; i++) { // 處理 j // 計算進入 window // 計算離開 window // 確認 window 是否滿足 } } class Solution { public: int countCompleteSubstrings(string s, int k) { int n = s.size(); int res = 0; for (int idx = 1; idx <= 26 && idx * k <= n; idx++) { int len = idx * k; int j = -1; vector<int> cnt(26, 0); int valid = 0; for (int i = 0; i < len; i++) { if (i > 0 && abs(s[i] - s[i-1]) > 2) { j = i-1; } if (++cnt[s[i]-'a'] == k) valid++; } if (valid == idx && j < 0) { res++; } for (int i = len; i < n; i++) { if (abs(s[i] - s[i-1]) > 2) { j = i-1; } if (++cnt[s[i]-'a'] == k) valid++; if (cnt[s[i-len]-'a']-- == k) valid--; if (valid == idx && i-len >= j) { res++; } } } return res; } };

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