Leetcode

題號 題目 類別 題解 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: ...

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.size()，此時將遍歷過的 path 加入 res，但要注意題目有規定至少要 2 個元素的子序列，故需要再加入前做確認。 注意題目傳回的子序列不可重覆，故需要額外做處理。 三、解題 1. Backtracking Time complexity: \(O(2^n)\) Space complexity: \(O(n)\) vector<vector<int>> findSubsequences(vector<int>& nums) { vector<vector<int>> res; vector<int> path; dfs(nums, 0, path, res); sort(res.begin(), res.end()); // 先做排序後 for (int i = res.size()-1; i >= 1; i--) { // 從後面往前迭代 if (res[i] == res[i-1]) { res.erase(res.begin()+i); // 刪除重覆的序列 } } return res; } void dfs(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) { if (i == nums.size()) { // 終止條件 if (path.size() > 1) { // 滿足子序列元素大於等於2個，則加入答案 res.push_back(path); } return; } if (path.size() == 0 || nums[i] >= path.back()) { // 注意需滿足題意為上升序列 path.push_back(nums[i]); // 加入子序列 dfs(nums, i+1, path, res); path.pop_back(); // 回溯法需將元素 pop 掉 } dfs(nums, i+1, path, res); // 跳過不取 } 2. Backtracking(optimized) Time complexity: \(O(2^n)\) Space complexity: \(O(n)\) vector<vector<int>> findSubsequences(vector<int>& nums) { vector<vector<int>> res; vector<int> path; dfs(nums, 0, path, res); return res; } void dfs(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) { if (i == nums.size()) { if (path.size() > 1) { res.push_back(path); } return; } if (path.size() == 0 || nums[i] >= path.back()) { path.push_back(nums[i]); dfs(nums, i+1, path, res); path.pop_back(); } if (path.size() == 0 || nums[i] != path.back()) { // 處理重覆子序列 dfs(nums, i+1, path, res); } } 回目錄 Catalog ...

974. Subarray Sums Divisible by K Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Hash Table、Prefix Sum 一、題目 Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k. A subarray is a contiguous part of an array. Example 1: Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by k = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] Example 2: ...

53. Maxmimum Subarray Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Divide and Conquer、Dynamic Programming 一、題目 Given an integer array num, find the subarray with the largest sum, and return its sum. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1. Example 3: Input: [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. Constraints: ...

918. Maximum Sum Circular Subarray Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Divide and Conquer、Dynamic Programming、Queue、Monotonic Queue 一、題目 Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums. A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n]. A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n. ...

926. Flip String to Monotone Increasing Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: String、Dynamic Programming 一、題目 A binary string is monotone increasing if it consists of some number of 0’s (possibly none), followed by some number of 1’s (also possibly none). You are given a binary string s. You can flip s[i] changing 0 to 1 or from 1 to 0. Return the minimum number of flips to make s monotone increasing. Example 1: ...

1519. Number of Nodes in the Sub-Tree With the Same Level Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Hash Table、Tree、Depth-First Search、Breadth-First Search、Counting 一、題目 You are given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]). The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree. Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i. A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes. ...

100. Same Tree Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Tree、Depth-First Search、Breadth-First Search、Binary Tree 一、題目 Given the roots of two binary tree p and q, write a function to check if they are the same or not. Two binary tree are considered the same if they are structurally iedntical, and the nodes have the same value. Example 1: Input: p = [1,2,3], q = [1,2,3] Output: true Example 2: Input: p = [1,2], q = [1,null,2] Output: false Example 3: ...

149. Max Points on a Line Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Hash Table、Math、Geometry 一、題目 Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -10^4 <= xi, yi <= 10^4 All the points are unique. 二、分析 若干點在同一條線上，表示這些點的斜率都相同，注意題目有提示不會有相同的點，故兩點間必定有斜率。 特別注意當分母為 0 時要特別處理。 題目有限制 -10^4 <= xi, yi <= 10^4，故斜率最大 10^8，所以我們可以將分母為零的斜率暫定為 INT_MAX(2147483647)。 遍歷每個點，並統計該點與其它點之間的斜率，將斜率用 unordered_map 記錄下來，其每個斜率的直線上總共會有 m+1 (加上自己)。 三、解題 1. Time complexity: \(O(n^2)\) Space complexity: \(O(n)\) int maxPoints(vector<vector<int>>& points) { int n = points.size(); int res = 0; for (int i = 0; i < n; i++) { int& x0 = points[i][0]; int& y0 = points[i][1]; unordered_map<double,int> map; for (int j = 0; j < n; j++) { if (i == j) continue; // 若等於自己則跳過 int& x1 = points[j][0]; int& y1 = points[j][1]; if (x0 == x1) { // 當分母為 0 時特別處理 int& cnt = ++map[INT_MAX]; res = max(res, cnt); } else { double m = (y1-y0)/(1.0*(x1-x0)); // 注意將斜率轉成 double int& cnt = ++map[m]; res = max(res, cnt); } } } return res + 1; // 答案記得加 1，加上自己 } 回目錄 Catalog ...