673. Number of Longest Increasing Subsequence
題目網址：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
題意：給一 array nums, 返回最長嚴格遞增 subsequence 的個數。
Solution：
想法：可看到下圖 5 的部分重複計算, 故利用 DP, dp[i] 代表 nums[i] 開頭的最大 LIS 長度
特殊情況: 最長的 LIS 不只一個, 則 cnt 要相加
class Solution {public: int findNumberOfLIS(vector<int>& nums) { const int n = nums.size(); vector<int> dp(n, 1) , cnt(n, 1); int maxLis = 0, res = 0; for (int i = n - 1; i >= 0; --i) { for (int j ...
698. Partition to K Equal Sum Subsets
題目網址：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
題意：給一整數 array nums 和一正整數 k, 返回是否能把 nums 拆分成 k 的非空 subset, 且每個 subset 元素總和皆相等。
注意：nums.length ≤ 16
Solution 1：
想法：總共有 n 顆球、k 個桶子, 以「球」為視角, 每顆球都有 k 個桶子可以選擇, 每個桶子的容量為 target = sum / k。
e.g. nums = [1, 2, 2, 4, 3, 3], k = 3
class Solution {public: bool canPartitionKSubsets(vector<int>& nums, int k) { const int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % k != 0) { // 無法分成 k ...
142. Linked List Cycle II
題目網址：https://leetcode.cn/problems/linked-list-cycle-ii/
題意：給一 linked list 的 head, 返回 cycle 的起點。若無 cycle, 則返回 null。
進階：設計 $O(1)$ space 的演算法
Solution：
想法：定義以下變數
L 是起始點和 cycle head 的距離
x 是 cycle head 到第一次相遇的距離
C 是整個 cycle 的長度
第一次相遇可以寫成一個等式：2(L + x) = L + nC + x其中, L + x 為烏龜走的步數, L + nC + x 為兔子走的步數nC 代表兔子率先進入 cycle, 在和烏龜第一次相遇之前可能已經繞 cycle 好幾圈了
2(L + x) = L + nC + x 可化簡成 L + x = nC
讓烏龜回到原點, 然後走 L 步抵達 cycle head
兔子則在第一次相遇的地方 (L+x) 走 L 步此時兔子的新位置在 (L + x) + L = nC + L 也就是在 cycle head(nC + L 可看成從 ...
148. Sort List
題目網址：https://leetcode.cn/problems/sort-list/
題意：給一 linked list 的起始節點 head, 返回以升序排列過的 linked list。
進階：設計 $O(n \cdot log(n))$ time 且 $O(1)$ space 的演算法
Solution 1：
想法：利用 Merge Sort (top-down)
class Solution {public: ListNode* sortList(ListNode* head) { // 0 或 1 個 node if (!head || !head->next) { return head; } // 讓 slow 指向中點; 若 n 為偶數, 則指向第一個中點 ListNode *slow = head; ListNode *fast = head->next; while (fas ...
92. Reverse Linked List II
題目網址：https://leetcode.cn/problems/reverse-linked-list-ii/
題意：給一 single linked list 的 head 和兩整數 left 和 right, 其中 left ≤ right, 反轉位置 left 到位置 right 的 node, 並返回反轉後的 linked list。
Solution:
想法：分成三步驟
將待反轉的區域反轉
將 left (leftPrev->next) 的 next 指向 cur
將 leftPre 的 next 指向 reverseHead
class Solution {public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode *dummy = new ListNode(0, head); ListNode *leftPrev = dummy, *cur = head; // l ...