刷题记录帖子

516. Longest Palindromic Subsequence

经典的 DP 题目，还是非常需要理解的。参考了huahua 的解法 https://www.youtube.com/watch?v=OZX1nqaQ_9M，当然还有这个视频的解答, https://www.bilibili.com/video/BV1po4y1R738。 第二个视频还介绍了 Python @lru_cache() 高级了，直接暴力记忆函数不同参数调用的次数。

空间未优化版本

空间优化版本

1. 
   
2. 
   
3. class Solution:
   
4.     def longestPalindromeSubseq(self, s: str) -> int:
   
5.         n = len(s)
   
6.         # Processing edge cases
   
7.         if n == 1: return 1
   
8.         if n == 2:
   
9.             if s[0] == s[1]: return 2
   
10.             else: return 1
    
11.         """
    
12.         dp_x[i]:max Palindromic Subsequence starts from i with length x
    
13.         
    
14.         in detail:
    
15.         dp0:
    
16.             current_len substring,starts from length 2 substring, to be updated
    
17.         dp1:
    
18.             current_len-1 substring, starts from length 1 substring, so initialized all to 1
    
19.         dp2:
    
20.             current_len-2 substring, starts from length 2 substring, so initialized all to 0         
    
21.         """     
    
22.         dp0 = [0] * n
    
23.         dp1 = [1] * n
    
24.         dp2 = [0] * n
    
25.         
    
26.         for ll in range(2, n+1): # substring len 2 to n
    
27.             for i in range(0, n-ll+1):
    
28.                 j = i + ll - 1
    
29.                 if s[i] == s[j]:
    
30.                     dp0[i] = dp2[i+1] + 2
    
31.                 else:
    
32.                     dp0[i] = max(dp1[i+1], dp1[i])
    
33.             dp2 = dp1.copy()
    
34.             dp1 = dp0.copy()
    
35.         return dp0[0]
    
36. 
    

复制代码

581 Shortest Unsorted Continuous Subarray (Python)

O（nlogn）

单调栈可以做到 O（N），题目的答案有更加全面的解释, https://leetcode.com/problems/sh ... -subarray/solution/。

Approach 4: Using Stack
Algorithm

The idea behind this approach is also based on selective sorting. We need to determine the correct position of the minimum and the maximum element in the unsorted subarray to determine the boundaries of the required unsorted subarray.

To do so, in this implementation, we make use of a stackstack. We traverse over the numsnums array starting from the beginning. As we go on facing elements in ascending order(a rising slope), we keep on pushing the elements' indices over the stackstack. This is done because such elements are in the correct sorted order(as it seems till now). As soon as we encounter a falling slope, i.e. an element nums[j]nums[j] which is smaller than the element on the top of the stackstack, we know that nums[j]nums[j] isn't at its correct position.

In order to determine the correct position of nums[j]nums[j], we keep on popping the elemnents from the top of the stackstack until we reach the stage where the element(corresponding to the index) on the top of the stackstack is lesser than nums[j]nums[j]. Let's say the popping stops when the index on stackstack's top is kk. Now, nums[j]nums[j] has found its correct position. It needs to lie at an index k + 1k+1.

We follow the same process while traversing over the whole array, and determine the value of minimum such kk. This marks the left boundary of the unsorted subarray.

Similarly, to find the right boundary of the unsorted subarray, we traverse over the numsnums array backwards. This time we keep on pushing the elements if we see a falling slope. As soon as we find a rising slope, we trace forwards now and determine the larger element's correct position. We do so for the complete array and thus, determine the right boundary.

We can look at the figure below for reference. We can observe that the slopes directly indicate the relative ordering. We can also observe that point bb needs to lie just after index 0 marking the left boundary and the point aa needs to lie just before index 7 marking the right boundary of the unsorted subarray.

楼主一直在坚持。想问下楼主是在上学还是已经工作。上岸了吗？

946. Validate Stack Sequences
Greedy

LeetCode 29. Divide Two Integers (Python)

还是很经典的题目，有两点，一个是 log N 的优化，一个是边界条件处理，我个人不太喜欢 bitwise 操作，当然还是理解为什么用的。感觉还是可以的。

895. Maximum Frequency Stack

多重 stack 来解决，一个 dict 记录 freq 一个 维持插入的 order。

575. Distribute Candies

Easy

其实是抽屉原理

645. Set Mismatch

Using Constant Space to record the showing of the array

LeetCode 268. Missing Number  Easy 题

235        Lowest Common Ancestor of a Binary Search Tree
236        Lowest Common Ancestor of a Binary Tree

这个两题需要放到一起，学习下如何做递归的基本方法。

推荐这个视频，讲解的真好！

https://www.youtube.com/watch?v= ... upszWcA&index=2

通过 Base Case， 空 + root==p + root == q 来解决这个问题 ，然后递归求解，答案在左子树或者右子树的情况，

左右子树的返回值，都不空，就是 root 自己；
一个空，一个不空，答案是那个不空。
都空就没找到 LCA，当然这个答案不合法，因为题目保证了存在。