LeetCode 445 Add Two Numbers II
链接：https://leetcode.com/problems/add-two-numbers-ii/
方法：双指针
时间复杂度：O(n)
想法：这个其实就是双指针的那种技巧性非常强的题...可能都不是很容易应用到其他题目上。但不管怎么样，这道题，想法是别管怎么样，先把各个对应的节点加起来，哪怕加起来的数超过9，比方说l1 = [7,2,4,3], l2 = [5,6,4]，别管三七二十一，先加出一个[7,7,10,7]。这样加完之后得到了一个新链表，然后开始处理这个链表。先用一个指针p，然后用一个指针q从p.next开始，扫过所有值为9的地方，那如果扫完一片9，最后一个数字超过了9，我们就知道，这个地方应该进位，进位的结果就是前面所有的9全变0，最前面也就是p那个地方加1，实现上就是p一路挪过来，挪到q的位置。如果扫过一片9之后q到达的位置比9小，那直接把p挪到这里来，说明这一段没有进位，不用处理。
代码：
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;
}
}
LeetCode 340 Longest Substring with At Most K Distinct Characters
链接：https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
方法：滑动窗口
时间复杂度：O(n)
想法：这个题倒是比较基本，就是滑动窗口的模板题。外面一个for，里面一个while。唯一要注意的就是滑动j的条件。在我的滑动窗口的模板中，i指的是滑动窗口的左端点，j指的是右端点右边一个的那个不合法的位置，所以在while里面j滑到这个地方就停。因为j指向的是第一个不合法的位置，因此j的判断条件需要是while (j < n && (cnt < k || (cnt == k && map[s.charAt(j)] > 0)))。
代码：
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;
}
}
LeetCode 312 Burst Balloons
链接：https://leetcode.com/problems/burst-balloons/
方法：DP
时间复杂度：O(n3)
想法：经典区间型DP。用dp[i][j]代表打掉(i,j)开区间内的所有气球拿到的最大钱数（把i-j中间的气球全部打掉，只剩下i和j）。因为题目当中说原数组的两边相当于有两个1在旁边，所以干脆听他的直接改数组，就在前面后面各放一个1，这样在循环的时候就不用写各种if了。然后dp[i][j]，我们可以想象中间有个k，在分割这个区间，把区间(i, j)分成(i, k), k, (k, j)三部分，然后打出dp[i][j]的最后一步是打气球k，在此之前把左右两个区间内的气球全打没了，所以最后一步的收益是A[i] * A[k] * A[j]。这样的话我们通过枚举k就能得到dp[i][j]的所有可能的值，当然也能得到最大值。那么dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])。
代码：
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];
}
}
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown
链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
方法：DP
时间复杂度：O(n)
想法：买卖股票大家族的其中一道题，有机会可以把这个系列全写一遍。这个题主要是分析状态转化。其中有一些空间复杂度上的简化可以做，但写一个O(n)时间复杂度的算法还是并不难。先放一种最直观的想法，就是sell、buy和cooldown数组的第i个元素分别表示在第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]))。
代码：
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]));
}
}
继续观察可知，cooldown[i] = sell[i-1]，因为cooldown[i]代表在第i天以及它之前，最后一次操作为啥也不干的最大收益，既然最后一次操作是啥也不干，那其实就是说这次操作之前的那次操作是卖股票。那卖股票最晚发生在i-1处，所以cooldown[i] = sell[i-1]。带入之后可以把三个数组化简为两个数组。
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]);
}
}
然后继续观察发现数组当中i这个下标的值仅与i-1和i-2两个状态有关，这类问题全都可以将空间复杂度再往下压一维，就是滚动数组。
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);
}
}
LeetCode 300 Longest Increasing Subsequence
链接：https://leetcode.com/problems/longest-increasing-subsequence/
方法：DP + 贪心 + 二分
时间复杂度：O(nlogn)
想法：经典题目，简称LIS，后续在一些hard的题目当中又作为解题的关键步骤。我之前想出了那个n平方的DP做法，这种nlogn的没想出来，是看的别人做的。这个DP的巧妙之处在于，用一个列表dp，这里面第i个元素代表是：在所有长度为i的LIS中，结尾的元素最小的那个LIS，它的结尾元素的值是多少。我们为什么只关心结尾元素最小的LIS呢？因为比方说我有两个长度为2的LIS，分别是[1,2]和[3,4]，那么当求长度为3的LIS的时候，所有元素都更容易放在[1,2]后面产生长度为3的LIS。比方有一个元素是3，3可以跟[1,2]形成[1,2,3]，但就没法放到第二个序列。所以这里使用贪心，贪结尾元素最小。
然后根据上述的DP规则，可以发现DP列表是一个单调递增的列表。当我们遍历到一个原数组的元素的时候，如果它可以跟之前的一些元素形成最长的increasing subsequence的话，它就应该去找DP列表中第一个>=它的元素，因为在这个元素的左边都是严格小于它的，那它组成的LIS就会是最后一个严格小于它的这个地方代表的长度+1，也就是第一个>=它的元素代表的长度。这个时候更新这个地方结尾的最小元素为当前元素。当然如果DP列表中根本找不到>=它的，那说明最后一个小于它的就是DP列表的最后一个元素，他就跟这个长度的sequence合起来形成LIS。
代码：
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;
}
}
