Loss on training data large: model bias -> add features optimization -> change optimization methods small: loss on testing data large: overfitting: (1) more training data, data augmentation (2) make model simpler small: mismatch
題號 題目 類別 題解 1 Two Sum Hash Table Hash Table 2 Add Two numbers Linked List Recursion 201 Bitwise AND of Numbers Range Bitwise Operation Lowbit = x&(~x+1) 204 Count Primes Math Thetory The Sieve of Eratosthenes 408 Valid Word Abbreviation Two Pointers 字串轉數字
132. Palindrome Partitioning II Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: string, dynamic programming 一、題目 Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example 1: Input: s = “aab” Output: 1 Explanation: The palindrome partitioning [“aa”, “b”] could be produced using 1 cut. Example 2: Input: s = “a” Output: 0 Example 3: Input: s = “ab” Output: 1 Constraints:...
一、分治法 分治法，簡而言之就是分而治之，把複雜的問題分成兩個或更多個相似或相似的子問題，直到子問題可以直接求解，最後再將子問題的解做合併。 三步驟：Divide、Conquer、Merge 以 pseudo code 來表示大概像： void func(collection set) { // 子問題求解 if (base_case) { // 根據要求將子問題解合併成母問題解 do_something return; } // 將母問題分解成子問題 for (collection subset : set) { func(subset); } } graph LR; 母問題-->子問題1; 母問題-->子問題2; subgraph Divide 子問題1-->最小子問題1; 子問題1-->最小子問題2; 子問題2-->最小子問題3; 子問題2-->最小子問題4; end subgraph Conquer 最小子問題1-->最小子問題解1; 最小子問題2-->最小子問題解2; 最小子問題3-->最小子問題解3; 最小子問題4-->最小子問題解4; end subgraph Merge 最小子問題解1-->合併; 最小子問題解2-->合併; 最小子問題解3-->合併; 最小子問題解4-->合併; end 合併-->母問題解 舉例說明，河內塔遊戲： 河內塔是由三根桿子以大小不同碟片所組成的遊戲，僧人一次可以從一根桿子移動一個碟片到另一根桿子，但是小的碟片若放憂大的碟片下面會使得小的碟片裂開(也就是碟片只能由上而下從小排到大)，試問將一座塔從一根桿子完整的移動到另一根桿子需要移動多少次。 思考上面的情形，以三個碟片為例，若我們要從 A 到 C 移動一座塔，我們可以將之分解成「如何把上面兩個碟片移動到 B」，因為剩下的一個大碟片，可以很簡單的從 A 移動到 C。也就是說 f3(A->C) = f2(A->B) + f1(A->C) + f2(B->C)。 再更進一步，f2(A->B) 和 f2(B->C) 其實就是移動兩個碟片到另一座塔，所以可以分解成 f2(A->C) = f1(A->B) + f1(A->C) + f1(B->C)，至此，我們已經把 f3 都分解成可以代表一次移動的最小子問題的解 f1 了： graph TD; A[f3,A->C] B[f2,A->B] C[f1,A->C] D[f2,B->C] E[f1,A->C] F[f1,A->B] G[f1,C->B] H[f1,B->A] I[f1,B->C] J[f1,A->C] A-->B A--->C A-->D B-->E B-->F B-->G D-->H D-->I D-->J 故我們可以以數學方式證明：...
491. Non-decreasing Subsequences Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Hash Table、Backtracking、Bit Manipulation 一、題目 Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order. Example 1: Input: nums = [4,6,7,7] Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] Explanation: Example 2: Input: nums = [4,4,3,2,1] Output: [[4,4]] Constraints: <= nums.length <= 15 -100 <= nums[i] <= 100 二、分析 這一很典型的是一個 backtrack 的問題，只要熟悉回溯法的框架並注意終止條件與處理重覆子序列即可。 終止條件為 i == nums....