Leetcode

198. House Robber Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Dynamic Programming 一、題目 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. ...

947. Most Stones Removed with Same Row or Column Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Depth-First Search、Union Find、Graph 一、題目 On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed. ...

151. Reverse Words in a String Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Two Pointers、String 一、題目 Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces. ...

23. Merge k Sorted Lists Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Linked List、Divide and Conquer、Heap (Priority Queue)、Merge Sort 一、題目 You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 Example 2: ...

22. Generate Parentheses Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: String、Dynamic Programming、Backtracking 一、題目 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Example 2: Input: n = 1 Output: ["()"] Constraints: 1 <= n <= 8 二、分析 DFS 演算法是在遍歷「節點」，而回溯法是在遍歷「樹枝」。站在一個節點上，需思考三個問題： 路徑(PATH)：已做出的選擇。 選項(OPTION)：當前可以做的選擇。 終止條件(TERMINATE)：到達決策樹的底層，無法再做其它選擇。 以下為回溯法的框架： vector<PATH> res; void backtrack(PATH, OPTION) { if (TERMINATE) { res.push_back(PATH); return; } for (CHOICE : OPTION) { DO OPTION; backtrack(PATH, OPTION); CANCEL OPTION; } } 本題的終止條件是當 path 的長度為 2n 的時候。 而選項是增加左括號 ( 與增加右括號 )。 加上兩個子節點的條件便完成， 左節點需滿足 left < n。 右節點需滿足 right < n && right < left。 DP 動態規劃則需觀察轉移方程式。 dp[0] base case： `` dp[1] 很容易得到：() dp[2] 也不難：()()、(()) 接下來觀察 dp[3]，可以分解為下面三個： ( + dp[0] + ) + dp[2]：()()()、()(()) ( + dp[1] + ) + dp[1]：(())() ( + dp[2] + ) + dp[0]：(()())、((())) 換句話說，轉移方程式可以寫成：dp[i] = "(" + dp[j] + ")" + dp[i-j-1] 三、解題 1. Backtrack Time complexity: \(O(2^{2n})\)，Wiki - Catalan number Space complexity: \(O(n)\) vector<string> generateParenthesis(int n) { string path; vector<string> res; backtrack(n, 0, 0, res, path); return res; } void backtrack(int n, int left, int right, vector<string>& res, string& path) { // terminate if (path.length() == 2*n) { res.push_back(path); return; } // select if (left < n) { path.push_back('('); backtrack(n, left+1, right, res, path); path.pop_back(); } if (right < n && right < left) { path.push_back(')'); backtrack(n, left, right+1, res, path); path.pop_back(); } } 2. Dynamic Programming Time complexity: \(O(n^4)\) Space complexity: \(O(n)\) vector<string> generateParenthesis(int n) { vector<vector<string>> dp(n+1); dp[0] = {""}; for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ vector<string> left = dp[j]; vector<string> right = dp[i-j-1]; for(int k=0;k<left.size();k++){ for(int l=0;l<right.size();l++){ dp[i].push_back("(" + left[k] + ")" + right[l]); } } } } return dp[n]; } 回目錄 Catalog ...

21. Merge Two Sorted Lists Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Linked List、Recursion 一、題目 You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. Example 1: Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Example 2: ...

1047. Remove All Adjacent Duplicates In String Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: String、Stack 一、題目 You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique. ...

901. Online Stock Span Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Stack、Design、Monotonic Stack、Data Stream 一、題目 Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day. The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today’s price. ...

1544. Make The String Great Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: String、Stack 一、題目 Given a string s of lower and upper case English letters. A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where: 0 <= i <= s.length - 2 s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa. To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good. Return the string after making it good. The answer is guaranteed to be unique under the given constraints. Notice that an empty string is also good. Example 1: ...

2463. Minimum Total Distance Traveled Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Dynamic Programming、Sorting \(\color{blue}\textsf{Weekly Contest 318}\) 一、題目 There are some robots and factories on the X-axis. You are given an integer array robot where robot[i] is the position of the ith robot. You are also given a 2D integer array factory where factory[j] = [positionj, limitj] indicates that positionj is the position of the jth factory and that the jth factory can repair at most limitj robots. ...