252. Meeting Rooms
題目網址:https://leetcode.cn/problems/meeting-rooms/
題意:給定一包含開始時間和結束時間的 intervals, 其中intervals[i] = [starti, endi], 返回一個人是否可以參加所有會議。
注意:(0,8)、(8,10) 並不衝突
Solution:
想法:先將 intervals 根據 interval.start 進行排序, 然後判斷當前 interval[i - 1].end 是否大於 interval[i].start。若是的話, 代表會衝突到
class Solution {public: bool canAttendMeetings(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); for (int i = 1; i < intervals.size(); ++i) { if ...
617. Merge Two Binary Trees
題目網址:https://leetcode.cn/problems/merge-two-binary-trees/
題意:給兩棵 BT, 請合併它們。
如果兩個節點重疊, 則將節點值相加作為合併節點的新值。
否則, 不為 NULL 的節點將作為新樹的節點。
Solution:
想法:利用 DFS
class Solution {public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (!root1) { return root2; } if (!root2) { return root1; } // root1, root2 皆存在 root1->val += root2->val; root1->left = mergeTrees(root1->left, root ...
876. Middle of the Linked List
題目網址:https://leetcode.cn/problems/middle-of-the-linked-list/
題意:返回 linked list 的中點, 若 linked list 的 node 數為偶數, 則返回第二個中點。
Solution:
想法:利用 Two Pointersslow 一次走一步, fast 一次走兩步, 當 fast 走到 NULL 時, slow 剛好走到中點
class Solution {public: ListNode* middleNode(ListNode* head) { ListNode *slow = head, *fast = head; // 當 n 為偶數時, 跳出迴圈是因為 fast == NULL // 當 n 為奇數時, 跳出迴圈是因為 fast->nxt = NULL while (fast && fast->next) { slow = slow->next; ...
21. Merge Two Sorted Lists
題目網址:https://leetcode.cn/problems/merge-two-sorted-lists/
題意:給兩個 sorted linked list: list1 和 list2, 將兩個合併成一個 sorted linked list。
Solution:
想法:利用 dummy node, 其中 tail 指向當前 val 較小的 list node
class Solution {public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *dummy = new ListNode(), *tail = dummy; while (list1 && list2) { if (list1->val < list2->val) { tail->next = list1; ...
155. Min Stack
題目網址:https://leetcode.cn/problems/min-stack/
題意:設計一個支持 push、pop、top 操作, 並且能在 $O(1)$ time 得到最小元素的 stack。
實作 MinStack class:
MinStack():初始化 instance
void push(int val):將 val push 到 stack 中
void pop():移除 stack 頂端元素
void top():得到 stack 頂端元素
int getMin():得到 stack 中的最小元素
Solution:
想法:利用兩個 Stack, 其中 stack stk 紀錄元素 push / pop 的過程, 另一個 stack minStk.top() 紀錄每一次 push 元素到 stk 後, 當前 stk 中的的最小值
class MinStack {public: MinStack() { // 讓 minStk 初始有一個最大值, 這樣後續 push 時 minStk 一定有 top ...