1851. Minimum Interval to Include Each Query
題目網址：https://leetcode.cn/problems/minimum-interval-to-include-each-query/
題意：給一個二維整數 array intervals, 其中 intervals[i] = [left_i, right_i] 表示第 i 個區間開始於 left_i、結束於 right_i。
定義 intervals[i] 的長度為 right_i - left_i + 1。
再給一整數 array queries, 第 j 個查詢的答案是滿足 left_i ≤ queries[j] ≤ right_i 的最小區間 i 之長度。若不存在這樣的區間, 則答案為 -1。
以 array 的形式返回對應查詢的所有答案。
Solution：
想法：利用 offline 算法 + Min Heap + Greedy, 先將所有滿足 interval.left ≤ query 的區間加到 pq 中, 再判斷 pq 中的這些 interval 是否滿足 interval.right ≥ query
offline 算法：
將 queries 由 ...
41. First Missing Positive
題目網址：https://leetcode.cn/problems/first-missing-positive/
題意：給一未排序的整數 array nums, 返回其中未出現的最小正整數。
必須設計 $O(n)$ time 且 $O(1)$ space 的演算法。
Solution 1：
想法：利用 hash table, 首先 hash table 儲存出現過的數, 然後再從 1 開始遍歷到 n。若其中有不在 hash table 中的, 則直接返回該數。否則, 返回 n + 1
class Solution {public: int firstMissingPositive(vector<int>& nums) { const int n = nums.size(); unordered_set<int> s(nums.begin(), nums.end()); for (int i = 1; i <= n; ++i) { if (s ...
37. Sudoku Solver
題目網址：https://leetcode.cn/problems/sudoku-solver/
題意：寫一程式, 可填充空格來解決數獨問題。
數獨的解法需遵從以下規則：
數字 1-9 在每一行只能出現一次
數字 1-9 在每一列只能出現一次
數字 1-9 在每一個以粗實線分隔的 3x3 九宮格內只能出現一次
數獨部分空格已填入數字, 而空格用 '.' 來表示。
Solution：
想法：利用 DFS + Backtracking
class Solution {public: void solveSudoku(vector<vector<char>>& board) { fill(board, 0, 0); }private: // y 為 row, x 為 col bool fill(vector<vector<char>>& board, int y, int x){ // 代表 0 ~ 8 列所有 ...
632. Smallest Range Covering Elements from K Lists
題目網址：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/
題意：給一包含 k 個非遞減排列整數 array 的 list nums。找到一最小區間, 使得每個 array 中皆至少有一個整數包含在該區間中。
定義區間 [a, b] < [c, d], 滿足下列其中一個條件便成立：
b-a < d-c
b-a == d-c 且 a < c
Solution 1：
想法：利用 Sliding Window, 類似 76. Minimum Window Substring
首先, 取出每個 array 中的最小值, 並加入到 set 中
取出 set 中最大、最小的值, 並計算出 newRange
若 newRange < range, 則更新 range 和最小區間
移除 set 中的最小元素, 並將 insert 其所對應的 array 之下一個元素若該元素為不存在, 則直接返回
e.g. nums = [[4,10,15,24,26], [0,9 ...
759. Employee Free Time
題目網址： https://leetcode.cn/problems/employee-free-time/
題意：給一員工的 schedule 列表, 表示每個員工的工作時間。
每個員工都有一個非重疊的時段 Intervals 列表, 這些時段皆已由小到大排序。
返回這些員工共同、為正數長度的有限時段列表, 需由小到大排序。
注意：類似 [5, 5] 這樣的時段不能成為答案, 因為長度為 0, 而非正數
Solution 1：
想法：先將所有 intervals flatten 成一維, 再將這些 intervals 由小到大進行排序
若 intervals[i - 1].end < intervals[i].start 代表兩個區間沒重疊, 須將 Interval(intervals[i - 1].end, intervals[i].start) 加入到 res 中
若 intervals[i - 1].end >= intervals[i].start 代表兩個區間有重疊
須更新 end = max(intervals[i - 1].end, interval ...