LeetCode 445 Add Two Numbers II

Link: leetcode.com/problems/ad…

Method: double pointer

Time complexity: O(n) Idea: This is actually a two-pointer kind of tricky problem… They may not be easy to apply to other topics. For example, l1 = [7,2,4,3], l2 = [5,6,4], ignore the three seven twenty-one, first add one [7,7,10,7]. And then you get a new list, and then you start working on that list. With a pointer to the first p, then use a pointer q from p.n ext, swept all the value of 9, that if finish cleaning a 9, the last number more than 9, we know that this place should carry, carry all the result is that all previous 9 0, the front is where p plus 1, implementation is p moved all the way, Let’s move it to q. If you sweep a 9 and q gets to a position less than 9, then you just move p over here, which means there’s no carry, so you don’t have to deal with that. Code:

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int n1 = getLength(l1), n2 = getLength(l2); int s = Math.max(n1, n2); ListNode dummy = new ListNode(0); ListNode p = dummy; while (s > 0) { p.next = new ListNode(0); p = p.next; if (s <= n1) { p.val += l1.val; l1 = l1.next; } if (s <= n2) { p.val += l2.val; l2 = l2.next; } s--; } p = dummy; while (p ! = null) { ListNode q = p.next; while (q ! = null && q.val == 9) { q = q.next; } if (q ! = null && q.val > 9) { while (p ! = q) { p.val++; p = p.next; p.val -= 10; } } else { p = q; } } if (dummy.val > 0) { return dummy; } return dummy.next; } private int getLength(ListNode l) { int res = 0; while (l ! = null) { res++; l = l.next; } return res; }}Copy the code

LeetCode 340 Longest Substring with At Most K Distinct Characters

Link: leetcode.com/problems/lo…

Method: Slide window

Time complexity: O(n) Idea: This is a basic sliding window template. A “for” on the outside and a “while” on the inside. The only thing to notice is the condition for sliding j. In my sliding window template, I refers to the left end of the sliding window, and J refers to the illegal position of the one to the right of the right end, so in the while J slides to this place and stops. Because j point was the location of the first illegal, so j judgement conditions need to be a while (j < n && (CNT < k | | (CNT = = k && map [s.c harAt (j)] > 0))). Code:

class Solution { public int lengthOfLongestSubstringKDistinct(String s, int k) { int res = 0, n = s.length(), i = 0, j = 0, cnt = 0; int[] map = new int[256]; for (; i < n; i++) { while (j < n && (cnt < k || (cnt == k && map[s.charAt(j)] > 0))) { map[s.charAt(j)]++; if (map[s.charAt(j)] == 1) { cnt++; } j++; } res = Math.max(res, j - i); map[s.charAt(i)]--; if (map[s.charAt(i)] == 0) { cnt--; } } return res; }}Copy the code

LeetCode 312 Burst Balloons

Link: leetcode.com/problems/bu…

Methods: the DP

Time complexity: O(N3) Idea: classical interval DP. Use dp[I][j] to represent the maximum amount of money to be made by blowing all the balloons in the open interval (I,j) (all balloons between i-j are dropped, leaving only I and j). So we can just change the array and put a 1 in front and a 1 in back, so that we don’t have to write ifs when we loop through. Then dp[I][j], we can imagine that there is a k in the middle, divide the interval (I, j) into three parts (I, k), K, (k, j), and then beat out DP [I][j]. The last step is to beat out balloon K, and before that, all balloons in the left and right intervals are destroyed. So the payoff of the last step is A[I] * A[k] * A[j]. This way we can get all possible values of dp[I][j] by enumerating k, and of course get the maximum. So dp [I] [j] = math.h Max (dp [I] [j], dp [I] [k] + dp [k] [j] + [I] A * A * [k] A [j]). Code:

class Solution { public int maxCoins(int[] nums) { int n = nums.length; n += 2; int[] A = new int[n]; A[0] = 1; A[n - 1] = 1; for (int i = 1; i < n - 1; i++) { A[i] = nums[i - 1]; } int[][] dp = new int[n][n]; for (int len = 3; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; for (int k = i + 1; k < j; k++) { dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]); } } } return dp[0][n - 1]; }}Copy the code

LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

Link: leetcode.com/problems/be…

Methods: the DP

Time complexity: O(n) Idea: One of the problems of buying and selling stock family, have the chance to write the whole series. This problem is mainly analyzing state transitions. There’s some space simplification that can be done, but it’s not too hard to write an O(n) time algorithm. To put this in perspective, the i-th element of the Sell, Buy, and CoolDown arrays represents the maximum return on the last operation, sell, buy, and stay until day I, respectively. Buy [I] = Math. Max (buy[I], buy[I] + price), buy[I] = Math. Max (buy[I], cooldown[I] -price), Cooldown [I] = math.max (sell[i-1], math.max (buy[i-1], CoolDown [i-1])). Code:

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] sell = new int[n]; int[] buy = new int[n]; int[] cooldown = new int[n]; buy[0] = -prices[0]; for (int i = 1; i < n; i++) { int price = prices[i]; sell[i] = Math.max(sell[i - 1], buy[i - 1] + price); buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - price); cooldown[i] = Math.max(sell[i - 1], Math.max(buy[i - 1], cooldown[i - 1])); } return Math.max(sell[n - 1], Math.max(buy[n - 1], cooldown[n - 1])); }}Copy the code

Cooldown [I] = sell[i-1], because cooldown[I] represents the maximum return on the last operation that did nothing on day I and before it. So cooldown = sell[i-1]. You can simplify three groups of numbers into two arrays.

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] sell = new int[n + 1]; int[] buy = new int[n + 1]; sell[0] = 0; buy[0] = 0; sell[1] = 0; buy[1] = -prices[0]; for (int i = 2; i <= n; i++) { sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i - 1]); buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i - 1]); } return Math.max(sell[n], buy[n]); }}Copy the code

And then you look and you see that the value of the subscript I in the array is only related to the two states i-1 and I-2, and all of these kinds of problems can push the spatial complexity down one dimension, which is scrolling arrays.

class Solution { public int maxProfit(int[] prices) { int preBuy = 0, preSell = 0, sell = 0, buy = Integer.MIN_VALUE; for (int price : prices) { preBuy = buy; buy = Math.max(preSell - price, preBuy); preSell = sell; sell = Math.max(preSell, preBuy + price); } return Math.max(sell, buy); }}Copy the code

LeetCode 300 Longest Increasing Subsequence

Link: leetcode.com/problems/lo…

Method: DP + greedy + binary

A) LIS b) LIS C) LIS D) LIS I came up with the n squared DP method, but I didn’t come up with the nlogn method, but I watched somebody else do it. The trick of this DP is to use a list DP, in which the ith element represents: among all LIS of length I, the LIS with the smallest ending element has the value of its ending element. Why do we care only about LIS with the smallest ending element? For example, I have two LIS with length 2, [1,2] and [3,4] respectively, so when finding LIS with length 3, it is easier for all elements to be placed after [1,2] to produce LIS with length 3. Let’s say you have an element 3 that can form [1,2,3] with [1,2], but you can’t put it in the second sequence. So we use greed, the least greedy element. Then, according to the DP rule above, you can see that the DP list is a monotonically increasing list. When we iterate over an element of the original array, if it can form the longest increasing subsequence with the preceding elements, it should go to the first element in the DP list >= it, because the element on the left is strictly smaller than it, And then its constituent LIS is going to be the last one that’s strictly smaller than this plus one, which is the length of the first one that’s greater than or equal to it. This time updates the smallest element at the end of the place to the current element. Of course, if there is no >= in the DP list at all, it means that the last element smaller than it is the last element in the DP list, which is combined with the sequence of this length to form LIS. Code:

class Solution { public int lengthOfLIS(int[] nums) { List<Integer> dp = new ArrayList<>(); for (int num : nums) { int index = firstGreaterOrEqual(dp, num); if (index == -1) { dp.add(num); } else { dp.set(index, num); } } return dp.size(); } private int firstGreaterOrEqual(List<Integer> dp, int target) { if (dp.size() == 0) { return -1; } int left = 0, right = dp.size() - 1; while (left + 1 < right) { int mid = left + (right - left) / 2; int cur = dp.get(mid); if (cur >= target) { right = mid; } else { left = mid; } } if (dp.get(left) >= target) { return left; } if (dp.get(right) >= target) { return right; } return -1; }}Copy the code