刷题记录帖子

Lc 11        Container With Most Water        Medium       

Tow pointers, Moving Shorter one to make the area bigger

LeetCode 784 Letter Case Permutation

啊，实在是脑子 what 了，居然没做出来， sigh！

参考这个帖子，可以硬上，https://maxming0.github.io/2021/02/16/Letter-Case-Permutation/

也可以用递归做，https://zxi.mytechroad.com/blog/ ... r-case-permutation/
花花也有很好的一个讲解题，https://youtu.be/LJifc-ehvBM
DFS + Recurrsion

1249. Minimum Remove to Make Valid Parentheses

基本都是 用 stack

LeetCode 413. Arithmetic Slices

还是很经典的答案总结，特别是 dp 的时候，dp[i] 代表以 i 结尾的 seq 数，那么多一个数字就会+2个答案。

https://leetcode.com/problems/arithmetic-slices/

当然也可以用我自己的解法，找到 seq 的长度然后发现数目。

13. Roman to Integer

Easy 题，只要处理好如何处理 edge case 即可。

1. class Solution:
   
2.     def romanToInt(self, s: str) -> int:
   
3.         ans = 0
   
4.         i = 0
   
5.         while i < len(s):
   
6.             # I can be placed before V (5) and X (10) to make 4 and 9.
   
7.             if i + 1 < len(s) and s[i] == 'I' and s[i+1] == 'V':
   
8.                 ans -= 1
   
9.             elif i + 1 < len(s) and s[i] == 'I' and s[i+1] == 'X':
   
10.                 ans -= 1
    
11.             # X can be placed before L (50) and C (100) to make 40 and 90.
    
12.             elif i + 1 < len(s) and s[i] == 'X' and s[i+1] == 'L':
    
13.                 ans -= 10
    
14.             elif i + 1 < len(s) and s[i] == 'X' and s[i+1] == 'C':
    
15.                 ans -= 10
    
16.             # C can be placed before D (500) and M (1000) to make 400 and 900.
    
17.             elif i + 1 < len(s) and s[i] == 'C' and s[i+1] == 'D':
    
18.                 ans -= 100
    
19.             elif i + 1 < len(s) and s[i] == 'C' and s[i+1] == 'M':
    
20.                 ans -= 100
    
21.             else:
    
22.                 if s[i] == 'I': ans += 1
    
23.                 if s[i] == 'V': ans += 5
    
24.                 if s[i] == 'X': ans += 10
    
25.                 if s[i] == 'L': ans += 50
    
26.                 if s[i] == 'C': ans += 100
    
27.                 if s[i] == 'D': ans += 500
    
28.                 if s[i] == 'M': ans += 1000
    
29.             i += 1
    
30.         return ans
    
31.                

复制代码

LeetCode 991.Broken-Calculator (Python)

这道题目，从答案看很简单，但是从思考来看其实很不简单，从这个帖子，https://github.com/wisdompeak/Le ... 1.Broken-Calculator ，得到启发。

贪心算法！

首先，当X>Y时，容易判断出我们只有对X持续地减一才能实现Y。

当X<Y时，我们也容易判断出，如果Y是奇数，那么最后一步操作一定是-1（否则x2是得不到奇数的），所以我们只需要递归考虑brokenCalc(X,Y+1)即可。

那么如果Y是偶数呢？我们将任意从X变换成Y的过程，可以分为两个大类：第一类是最后若干步是-1，第二类是最后若干步是x2。这两类方法可以分别写作：

(a) X ... [x2 x2 ... x2][-1 -1 ... -1] = Y
(b) X ... [-1 -1 ... -1][x2 x2 ... x2] = Y
注意，我们并不关心“最后若干步”具体是有多少步。所以上面的两种方法就可以代表任意从X到Y的变换过程。其中，第一种方法最后的若干步-1一定是偶数次，假设是2k。我们容易看出第一种方法其实是不高效的，因为通过简单的分解就可以看出X ... [x2 x2 ... x2][-1 -1 ... -1]{2k个}等效于X ... [x2 x2 ...][-1 -1 ... -1]{k个} x2。而前者最后需要1+2k步，而后者只需要k+1步。

所以结论是，当Y>X并且Y是偶数的时候，方法(a)是不高效的，不如等效的方法(b)。也就是说，从X到Y最高效的变化方法，最后一步应该是x2而不是-1.因此下一步我们只需要递归考虑brokenCalc(X,Y/2)即可。

当然你也可以参考官方解答的思路，https://leetcode.com/problems/broken-calculator/solution/

Approach 1: Work Backwards
Intuition

Instead of multiplying by 2 or subtracting 1 from X, we could divide by 2 (when Y is even) or add 1 to Y.

The motivation for this is that it turns out we always greedily divide by 2:

If say Y is even, then if we perform 2 additions and one division, we could instead perform one division and one addition for less operations [(Y+2) / 2 vs Y/2 + 1].

If say Y is odd, then if we perform 3 additions and one division, we could instead perform 1 addition, 1 division, and 1 addition for less operations [(Y+3) / 2 vs (Y+1) / 2 + 1].

Algorithm

While Y is larger than X, add 1 if it is odd, else divide by 2. After, we need to do X - Y additions to reach X.

524. Longest Word in Dictionary through Deleting

排序 + Two Pointer 比较 word 是不是 in string

74. Search a 2D Matrix
240. Search a 2D Matrix II

Binary Search Plus

74 是把 matrix 转成 1D array

240 是从 右上 或者 左下 出发，进行  Binary Search

LeetCode 856. Score of Parentheses

真是经典的题目，虽然是 medium 但是其实用到的知识还是很深刻的。参考花花的解答， https://www.bilibili.com/video/B ... 1786526661555307833

Recursion

Counting Cores

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. 
    

复制代码