Questions ================== Maximum Number of Points with Cost ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score where abs(x) is x's absolute value. Return the maximum number of points you can achieve. Example 1: Input: points = [[1,2,3],[1,5,1],[3,1,1]] Output: 9 Explanation: The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0). You add 3 + 5 + 3 = 11 to your score. However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score. Your final score is 11 - 2 = 9. Example 2: Input: points = [[1,5],[2,3],[4,2]] Output: 11 Explanation: The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0). You add 5 + 3 + 4 = 12 to your score. However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score. Your final score is 12 - 1 = 11 ---- After selecting the cell in each row in turn, the obtained score is actually only related to the total score obtained after selecting the cell in the previous row, so it can be solved by dynamic programming. Design an array dp[i], which represents the maximum score when the i-th cell of the current row is selected. If the total score of the corresponding position of the previous line is lastLine[i], then ``dp[i] = max(lastLine[j] - |i - j|) + points[line][i]``, 0 <= j < n . In order to simplify the solution, the dynamic programming method can be further optimized to preprocess the calculation of the highest score that can be obtained by selecting the left and right cells of the previous row at each position. Finally, dp[i] is the highest score obtained when cell i in the last row is selected, and the maximum value is the solution. It should be noted that the data range of this question may exceed MAX_INT. .. literalinclude:: maximum_number_of_points_with_cost_test.cpp :linenos: :lines: 6-33 :emphasize-lines: 5-7, 9-10 :caption: Maximum Number of Points with Cost :name: maximum_number_of_points_with_cost_test .. only:: html - https://leetcode.com/problems/maximum-number-of-points-with-cost/ .. _regex_match: Regular Expression Matching ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Implement regular expression matching with support for "." and "*". "." Matches any single character. "*" Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: ``bool match(const string& s, const string& p)`` Examples: .. code-block:: none match("aa", "a") → false match("aa", "aa") → true match("aaa","aa") → false match("aa", "a*") → true match("aa", ".*") → true match("ab", ".*") → true because ".*" can be explained as "..", and ".." matches "ab". match("aab","c*a*b") → true Without star, the problem is very simple. The only tricky thing is the star. This problem can be solved with a recursive function. :numref:`regex_matching_rec` is a implementation with recursion from head to tail. You can also implement another version with recursion from tail to head, but the code ``s.substr(0, s.size()-2)`` will be more lengthy than ``s.substr(2)``. .. literalinclude:: regex_matching.h :linenos: :lines: 68-79 :emphasize-lines: 5-7, 9-10 :caption: A Simple Recursion Approach :name: regex_matching_rec Adding a cache to the recursive approach, we can have a top-down dynamic programming with memoization implementation :numref:`regex_matching_td`. .. literalinclude:: regex_matching.h :linenos: :lines: 81-98 :emphasize-lines: 3-13 :caption: Top-Down Dynamic Programing :name: regex_matching_td We can try bottom-up approach as :numref:`regex_matching_bu`. .. literalinclude:: regex_matching.h :linenos: :lines: 101-121 :emphasize-lines: 3-7, 13-15 :caption: Bottom-Up Dynamic Programing :name: regex_matching_bu The time complexity is O(M*N), where M and N are the length of string s and p respectively. But which method is the fastest? :numref:`regex_matching_test` has two test cases with profiling code. .. literalinclude:: regex_matching_test.cpp :linenos: :lines: 7-19 :emphasize-lines: 2 :caption: Bottom-Up Dynamic Programing :name: regex_matching_test We can see, from :numref:`regex_matching_test_result`, the top-down approach actually is the fastest, and bottom-up is the slowest. The reason is because, in this problem, top-down approach doesn't calculate all the subproblems in the subproblem space. It only calculatea the necessary nodes in the subproblem graph. In this specific case, only the 10% and 80% subproblems are calculated in the first and second test cases respectively. This is the advantage of recursion and top-down approaches over bottom-up approach. However, if, in other problems, all the subproblems need to be calculated, the bottom-up approach will be normally faster since it has less overhead like function call. .. code-block:: none :name: regex_matching_test_result :caption: Performance Test Result recursive : 1665 us top-down : 441 us bottom-up : 2440 us .. only:: html - https://leetcode.com/problems/regular-expression-matching Wildcard Matching ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '\*' where: '?' Matches any single character. '\*' matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). s contains only lowercase English letters. p contains only lowercase English letters, '?' or '\*'. |:bulb:| The biggest difference between wild card matching and regular matching is in the rules for the use of stars. For regular matching, the star cannot exist alone, and there must be a character in front of it, and the meaning of the star is to indicate the number of characters in front of it. The number can be any number, including 0, so it doesn't matter even if the previous character does not appear in s, as long as the latter can be matched. This is not the case for wild card matching. The star has nothing to do with the previous characters in wildcard matching. If the previous characters do not match, then return false directly, and don't care about the star at all. The role of the star is that it can represent any string, of course, only when the matching string is missing some characters. When the matching string contains characters that the target string does not have, it will not match successfully. .. literalinclude:: wildcard_matching.h :linenos: :lines: 68-79 :emphasize-lines: 3,4,8 :caption: Recursive Approach :name: wild_card_rec 💣 line 4: to match empty s, p could be empty or a sequence of continuous stars. We can add cache to recursive solution to get the top-down dynamic programming solution. The same as the :numref:`regex_match`, this problem doesn't need the entire subproblem space being solved. Tthe top-down dynamic programming code is as :numref:`wild_card_td`. It is just some base cases plus recursion logic with results being cached. You even don't have to think about the meaning of the cache. But if you have to, cache[i][j] means the result of `match(s[i:], p[j:])`. .. literalinclude:: wildcard_matching.h :linenos: :lines: 81-99 :caption: Top-Down Dynamic Programing :name: wild_card_td To have a bottom-up solution, you have to define the cache thoughtfully. The the bottom-up solution is :numref:`wild_card_bu`. .. literalinclude:: wildcard_matching.h :linenos: :lines: 102-120 :caption: Bottom-Up Dynamic Programing :name: wild_card_bu In the bottom-up approach, cache[i][j] means `s[0:i) matches p[0:j)`, so i and j are equivalent to the string length. .. only:: html - https://leetcode.com/problems/wildcard-matching Subsequence Number ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given two strings, find the number of times the second string occurs in the first string, whether continuous or discontinuous. Longest Increasing Subsequence(LIS) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. |:alien:| Could you improve it to :math:`O(NlogN)` time complexity? Number of Longest Increasing Subsequence(LIS) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Longest Common Subsequence ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Edit Distance (Levenshtein distance) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. math:: f(i,j)= \begin{cases} min(f(i-1,j-1),f(i-1,j),f(i,j-1))+1, & A[i-1] \neq B[j-1] \\ f(i-1,j-1), & A[i-1] = B[j-1] \\ \end{cases} Burst Balloons ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Paint House ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ House Robber ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Dungeon Game ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Target Sum ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Maximal Square ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Count Subarrays With More Ones Than Zeros ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Longest String Chain ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given an array of words where each word consists of lowercase English letters. wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB. For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad". A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1. Return the length of the longest possible word chain with words chosen from the given list of words. Example 1: Input: words = ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: One of the longest word chains is ["a","ba","bda","bdca"]. Example 2: Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] Output: 5 Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"]. Example 3: Input: words = ["abcd","dbqca"] Output: 1 Explanation: The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed. ---- .. literalinclude:: code/longest_string_chain_test.cpp :linenos: Warehouses In Villages ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ There are several villages on a one-dimensional axis, and several warehouses can be built in the axis. The cost of each village is the square of the distance from the village to its nearest warehouse. Find the minimum sum of cost of building k warehouses in between u villages. ---- .. only:: html - http://web.engr.oregonstate.edu/~xfern/classes/cs434/slides/clustering2-16.pdf - https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5148156/#!po=95.5882 .. _dp_max_profit_job_scheduling: Maximum Profit in Job Scheduling ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that starts at time X. Example 1: Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70. Example 2: Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60. Example 3: Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6 ---- Maintain a increasing max-profit-til-time sequence(using list or map), so we can do binary search. .. code-block:: none end3 ..._________| end2 ..._______| |____________| (start4) (end4) <------------------ We need to find the end time which is `the last less than or equal to` start4 (end3 in this case). ``upper_bound`` is used to find the last of less-than-or-equal-to element. .. literalinclude:: code/job_scheduling_max_profit_test.cpp :linenos: :language: c++ .. only:: html - upper_bound(:numref:`lower_upper_bound`) - https://leetcode.com/problems/maximum-profit-in-job-scheduling/ - https://www.youtube.com/watch?v=3kU7VYcmffU .. _dp_lis: Longest Increasing Subsequence(LIS) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given an unsorted array of integers, find the length of longest increasing subsequence. For example, given [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(N\^2) complexity. Follow up: Could you improve it to O(NLogN) time complexity? ---- There are two solutions for LIS: DP and patience sort. For DP, the recurrence function is: dp[x] = max(dp[x], dp[y] + 1) where y < x and nums[y] < nums[x] Patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array. https://en.wikipedia.org/wiki/Patience_sorting Take array {6, 3, 5, 10, 11, 2, 9, 14, 13, 7, 4, 8, 14} as an example. .. figure:: lis_patience_0.png :align: center :name: Patience Sort with Binary Search Patience Sort with Binary Search .. figure:: lis_patience.png :align: center :name: Patience Sort Patience Sort with TC: O(NLogN) The number of the piles is the longest increasing subsequence. .. literalinclude:: code/lis_test.cpp :linenos: :language: c++ .. only:: html - https://leetcode.com/problems/longest-increasing-subsequence/ - lower_bound(:numref:`lower_upper_bound`) .. _russian_doll: Russian Doll Envelopes ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope. One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height. Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other). Note: You cannot rotate an envelope. .. code-block:: none Example 1: Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]). Example 2: Input: envelopes = [[1,1],[1,1],[1,1]] Output: 1 ---- The problem boils down to a two dimensional version of the longest increasing subsequence problem (LIS). We must find the longest sequence seq such that the elements in seq[i+1] are greater than the corresponding elements in seq[i] (this means that seq[i] can fit into seq[i+1]). The problem we run into is that the items we are given come in arbitrary order - we can't just run a standard LIS algorithm because we're allowed to rearrange our data. How can we order our data in a way such that our LIS algorithm will always find the best answer? We answer the question from the intuition by sorting. Let's pretend that we found the best arrangement of envelopes. We know that each envelope must be increasing in w, thus our best arrangement has to be a subsequence of all our envelopes sorted on w. After we sort our envelopes, we can simply find the length of the longest increasing subsequence on the second dimension (h). Note that we use a clever trick to solve some edge cases: Consider an input [[1, 3], [1, 4], [1, 5], [2, 3]]. If we simply sort and extract the second dimension we get [3, 4, 5, 3], which implies that we can fit three envelopes (3, 4, 5). The problem is that we can only fit one envelope, since envelopes that are equal in the first dimension can't be put into each other. In order fix this, we don't just sort increasingly in the first dimension - we also sort decreasingly on the second dimension, so two envelopes that are equal in the first dimension can never be in the same increasing subsequence. Now when we sort and extract the second element from the input we get [5, 4, 3, 3], which correctly reflects an LIS of one. .. literalinclude:: code/russian_doll_test.cpp :linenos: :language: c++ .. only:: html - https://leetcode.com/problems/russian-doll-envelopes/ - https://leetcode.com/problems/maximum-height-by-stacking-cuboids/ - Stacking Boxes(https://leetcode.com/discuss/interview-question/1431204) - lower_bound(:numref:`lower_upper_bound`) Maximum Height by Stacking Cuboids ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed). Choose a subset of cuboids and place them on each other. You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j. You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid. Return the maximum height of the stacked cuboids. .. code-block:: none Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]] Output: 190 Explanation: Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95. Cuboid 0 is placed next with the 45x20 side facing down with height 50. Cuboid 2 is placed next with the 23x12 side facing down with height 45. The total height is 95 + 50 + 45 = 190. ---- .. literalinclude:: code/stacking_cuboids_test.cpp :linenos: :language: c++ .. only:: html - https://leetcode.com/problems/maximum-height-by-stacking-cuboids/ - https://www.youtube.com/watch?v=nyJe6_4_MTs