300+弱鸡重刷leetcode（附题目总结）

这两天有点忙，没打卡。今天补上。

## 5. Longest Palindromic Substring

Given a string **s**, find the longest palindromic substring in **s**. You may assume that the maximum length of **s** is 1000.

**Example 1:**

```
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
```

**Example 2:**

```
Input: "cbbd"
Output: "bb"
```



### Solution

先讲讲开始的思路

- dp\[i][j]:  s[i:j+1] 是否为回文串

- 状态转换方程：两种情况，一种是dp\[i][j-1] 是回文串，另一种也就是不是回文串。对于是回文串的，就需要考虑s[i-1]是否和s[j]相等。不是回文串的，可以看s[i]是否和s[j]相等，然后再看dp\[i+1][j]是否为True.

- 初始状态：dp\[i][i]=True

```python
class Solution:
    # wrong
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ''
        if len(set(s))==1:
            return s
        dp = [[False for _ in s] for _ in s]
        for i in range(len(s)):
            dp[i][i] = True
        ret = (0,0)
        for j in range(0,len(s)):
            for i in range(0,j):
                if dp[i][j-1] == True and i-1>=0:
                    dp[i][j] = dp[i][j-1] and s[i-1]==s[j]
                if dp[i][j-1] == False or i==j-1:
                    if i==j-1:
                        dp[i][j] = s[i]==s[j]
                    else:
                        dp[i][j] = dp[i+1][j-1] and s[i]==s[j]
                if dp[i][j] and (ret[1]-ret[0])<j-i:
                    ret = (i,j)
        return s[ret[0]:ret[1]+1]
```



但是这样的解法是有问题的，一开始以为是`dp[i][j] ← dp[i+1][j-1]` 这一块出了问题，请教了群里的小伙伴，小伙伴提出是不是状态转换对应的DAG有环的问题。第一次听说状态转换和DAG的关系，但真的很精巧，这或许就是DP的本质？如果DAG有环，则无法完成拓扑排序，也就是无法用先前处理完成的状态来推导后续状态，则DP不成立！从这个角度入手，进行了一波探索。



`dp[i][j-1]→dp[i][j]`  and `dp[i+1][j-1]→dp[i][j]` 两个转换方向，对应的就是图上的虚线和实线。从图来看，要保证在计算任一状态时，其所需的前置状态都已经被计算完成，那么就应该以j为外循环，i为内循环。这样的顺序既满足了无环，也满足了状态递推。

经过这样的分析，发现问题是出在了状态转换方程上：`dp[i][j] = dp[i][j-1] and s[i-1]==s[j]`

`dp[i][j]`就该是判断s[i]到s[j]，而我这边引入了s[i-1]，实际上相当于判断了s[i-1]到s[j]

代码修改后如下，但由于转换思路比较差，所以时间复杂度达到了$O(n^3)$

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if not s:
            return ''
        if len(set(s))==1:
            return s
        dp = [[False for _ in s] for _ in s]
        for i in range(len(s)):
            dp[i][i] = True
        ret = (0,0)
        for j in range(0,n):
            for i in range(0,j):
                if dp[i][j-1] == True and i-1>=0:
                    if len(set(s[i:j]))==1 and s[i]==s[j]:
                        dp[i][j]=True
                    else:
                        dp[i][j] = False
                if dp[i][j-1] == False or i==j-1:
                    if i==j-1:
                        dp[i][j] = s[i]==s[j]
                    else:
                        dp[i][j] = dp[i+1][j-1] and s[i]==s[j]
                if dp[i][j] and (ret[1]-ret[0])<j-i:
                    ret = (i,j)
        return s[ret[0]:ret[1]+1]
```



别人的思路如下：

```python
    def longestPalindrome(self, s):
        n = len(s)
        if n<=1:
            return s
        dp = [[False for _ in range(n)] for _ in range(n)]
        idx = (0,0)
        for i in range(n):
            dp[i][i] = True
        for j in range(n):
            for i in range(0, j):
                if s[i] != s[j]:
                    continue
                if j-i+1<=3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and j-i>idx[1]-idx[0]:
                    idx = (i,j)
        return s[idx[0]:idx[1]+1]
```

### Description:

House Robber

Easy

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight **without alerting the police**.

**Example 1:**

```
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
```

**Example 2:**

```
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.
```

### Solution

dp[i] = max(dp[i-1], dp[i-2]+nums[i])

秒了, \(^o^)/~

```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums)==1:
            return nums[0]
        dp = [0 for _ in nums]
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        return dp[-1]
```

## 206 翻转链表

### Description

Reverse a singly linked list.

**Example:**

```
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
```

**Follow up:**

A linked list can be reversed either iteratively or recursively. Could you implement both?

### Solution

- 递归

递归的方法非常的精巧～

注意两点：1. 递归的返回值是末节点  2. 通过head.next.next这样的形式来修改链表指向，不要去影响返回值node

```python
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node
```

- 迭代

  其实迭代也挺精巧的，这是官方解，自己写的就没这么好看了～

```python
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        curr = head
        while(curr):
            nextTmp = curr.next
            curr.next = pre
            pre = curr
            curr = nextTmp
        return pre
```

## 91. Decode Ways

A message containing letters from `A-Z` is being encoded to numbers using the following mapping:

```
'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Given a **non-empty** string containing only digits, determine the total number of ways to decode it.

**Example 1:**

```
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
```

**Example 2:**

```
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```



### Solution:

这道题恶心人啊...一个"0"的特判搞死人。u1s1，下次遇到肯定还要出篓子。

注意这些： "3022", "00", "20201"

另外状态转换方程也需要注意一下，s[i]不能和s[i-1]组合，那就dp[i]=dp[i-1]，能组合，注意了，是dp[i] = max(dp[i-1], dp[i-1]+dp[i-2])。

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == "0":
            return 0
        if n == 1:
            return 1
        dp = [0 for _ in range(n)]
        dp[0] = 1
        if int(s[:2])>26 and s[1]=="0":
            return 0
        else:
            dp[1] = 2 if int(s[:2]) <= 26 and s[1] != "0" else 1
        
        for i in range(2, n):
            if s[i] == "0":
                if int(s[i - 1]) > 2 or s[i-1]=="0":
                    return 0
                dp[i] = dp[i - 2]
            else:
                dp[i] = max(
                    dp[i - 1],
                    dp[i - 1] + dp[i - 2]
                    if (s[i - 1] != "0" and int(s[i - 1 : i + 1]) <= 26)
                    else float("-inf"),
                )
        return dp[-1]
```

## 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

**Example:**

```
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```

**Note:**

- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(*n2*) complexity.

**Follow up:** Could you improve it to O(*n* log *n*) time complexity?

### Solution:

$O(n^2)$解法

教训是不要把`__main__`给提交了！

dp[i] 以nums[i] 为最末元素的最长子序列的长度

```python
class Solution:
    def lengthOfLIS(self, nums) -> int:
        n = len(nums)

        if n<=1:
            return n
        dp =[1 for _ in range(n)]
        ret = 0
        for i in range(1, n):
            for j in range(0, i):
                dp[i] = max(dp[i], dp[j]+1 if nums[i]>nums[j] else 1)
            ret = max(ret, dp[i])
        return ret
```



$O(n\log n)$

这解法我是肯定想不出了，精巧orz

> 依然是着眼于一个上升子序列的结尾元素。思路是这样的：
>
> 如果已经得到的上升子序列的结尾的数越小，遍历的时候后面接上一个数，就会有更大的可能性构成一个更长的上升子序列。
>
> 说明：
>
> 1、在最开始，我们强调了子序列的定义，必须保持子序列中的元素在原始数组中的相对顺序。因此，通过从左向右遍历得到一个上升子序列，这个方法是合理的；
>
> 2、既然结尾越小越好，可以如下定义状态。为了与之前的状态区分，这里将状态数组命名为 tail。
>
> 第 1 步：定义新的状态。
> $tail[i]$ 表示长度为 i + 1 的所有最长上升子序列的结尾的最小值。
>
> 说明：
>
> 1、状态定义其实也描述了状态转移方程；
>
> 2、以题目中的示例为例 [10, 9, 2, 5, 3, 7, 101, 18] 中，容易发现长度为 2 的所有上升子序列中结尾最小的是子序列 [2, 3] ，因此 tail[1] = 3。
>
> 第 2 步：思考状态转移方程。状态转移方程其实也包含在状态的定义中。从直觉上看，数组 tail 也是一个严格上升数组。
> 下面证明：即对于任意的索引 i < j ，都有 tail[i] < tail[j]。
>
> 使用反证法：
>
> 假设对于任意的索引 i < j ，存在某个 tail[i] >= tail[j]。
>
> 对于此处的 $tail[i]$ 而言，对应一个上升子序列$[a_0,a_1,\ldots, a_i]$，依据定义 $tail[i] = a_i$；
> 对于此处的 $tail[j]$ 而言，对应一个上升子序列 $[b_0, b_1, ..., b_i, ... , b_j]$，依据定义 $tail[j] = b_j$ ；
>
> 由于 $tail[i] >= tail[j]$ ，等价于 $a_i \ge b_j$  ，而在上升子序列 $[b_0, b_1, ..., b_i, ... , b_j]$ 中，$b_i$严格小于 $b_j$ ，故有 $a_i \ge b_j > b_i$ ，则上升子序列 $[b_0, b_1, ..., b_i]$是一个长度也为 i + 1 但是结尾更小的数组，与 $a_i$的最小性矛盾。因此原命题成立。（证完）
>
> 因此，我们只需要维护有序数组 tail，它的长度就是最长上升子序列的长度。
>
> 下面说明如何在遍历中维护有序数组 tail 的定义：
>
> 算法的执行流程：
>
> 1、设置一个有序数组 tail，初始时为空；
>
> 注意：有序数组 tail 虽然有“上升”的性质，但它不是每时每刻都表示问题中的“最长上升子序列”（下文还会强调），不能命名为 LIS，有序数组 tail 只是用于求解 LIS 问题的辅助数组。
>
> 2、在遍历数组 nums 的过程中，每来一个新数 num，如果这个数严格大于有序数组 tail 的最后一个元素，就把 num 放在有序数组 tail 的后面，否则进入第 3 点；
>
> 注意：这里的大于是“严格”大于，不包括等于的情况。
>
> 3、在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；
>
> 如果有序数组 tail 中存在等于 num 的元素，什么都不做，因为以 num 结尾的最短的“上升子序列”已经存在；
> 如果有序数组 tail 中存在大于 num 的元素，找到第 1 个，让它变小，这样我们就找到了一个“结尾更小”的“相同长度”的上升子序列。
> 说明：我们再看一下数组 tail[i] 的定义：长度为 i + 1 的所有最长上升子序列的结尾的最小值。因此，在遍历的过程中，我们试图让一个大的值变小是合理的。
>
> 这一步可以认为是“贪心算法”，总是做出在当前看来最好的选择，当前“最好的选择”是：试图让第 1 个严格大于 nums[i] 的数变小，变成 nums[i]，这一步操作是“无后效性”的。
>
> 这一步是在有序数组中的操作，因此可以使用“二分查找法”。
>
> 4、遍历新的数 num ，先尝试上述第 2 点，第 2 点行不通则执行第 3 点，直到遍历完整个数组 nums，最终有序数组 tail 的长度，就是所求的“最长上升子序列”的长度。
>
>

https://leetcode-cn.com/problems ... -tan-xin-suan-fa-p/

```python
    def lengthOfLIS(self, nums):
        n = len(nums)
        if not nums:
            return 0
        tails = [nums[0]]
        for num in nums[1:]:
            if num>tails[-1]:
                tails.append(num)
                continue
            l, r = 0, len(tails)-1
            while(l<r):
                mid = l+(r-l)//2
                if tails[mid]<num:
                    l = mid+1
                else:
                    r = mid
            tails[l]=num
        return len(tails)
```

赶 due，都忘了打周赛......明天我要刷十题！！！

明天要pre和quiz，完不成10道的flag了orz。
但是！312这题是真的好啊，我觉得我变强了！


## 312. Burst Balloons

Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by array `nums`. You are asked to burst all the balloons. If the you burst balloon `i` you will get `nums[left] * nums[i] * nums[right]` coins. Here `left` and `right` are adjacent indices of `i`. After the burst, the `left` and `right` then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

**Note:**

- You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.
- 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100

**Example:**

```
Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
```



### Solution

首先学到了一个tip，这也是为什么dp大多都要写bottom-up的吧

>递归调用的效率是很低的，因为牵扯到大量的函数调用，即栈帧的创建与释放。而且由于临时变量的存在以及需要保存之前栈帧的esp、程序计数器等寄存器值，在递归层数加深时会占用大量的栈空间，非常容易引起爆栈。这样的代码是绝对不可以放到生产环境上的

再看题目本身吧。这题的状态定义是真的很妙了。

首先，这道题直觉上可以用搜索暴力解决。每一层选个没被戳爆的气球，戳爆它！左右找到最近的没被戳爆的气球，算出赚到的coin，然后再继续往下探索。第一层n，第二层戳爆了一个，n-1，第三层, n-2....总复杂度$O(n!)$，绝壁超时

那么，想一下这题能不能用分治呢。分治法的核心问题在于如何使用子问题的解来表示原问题的解，也就是子问题该怎么划分才能够用来解决原问题。

设想这样一种划分方式，先戳爆一个气球，这个气球为边界，再把气球数组分成了两部分继续戳。设戳爆区间i，j内的所有气球能获得的最大coins为`def(i,j)`。设戳爆气球k时，左右两区间所能获得的最大coin为 `def(i+1,k-1)` `def(k+1,j-1)`，这两个子问题需要继续计算。问题来了，这两个子问题独立吗？不独立！因为这两个子问题中，在k被戳爆后，左右两部分直接相邻了，那你先计算左边的子问题还是右边的子问题，会得到不同的结果。

那咋搞呢？如果说我们**反着想**，把k当做最后一个被戳爆的气球呢？左右两边的子问题相应独立了！因为k是最后爆的，左右两个区间不会在k爆前相邻了！

最后状态是如何转换的呢？`def(i,j)= def(i,k-1)+def(k+1,j)+nums[i-1]*nums[j+1]*nums[k]`.  

那接下来无论是记忆话递归，还是dp都可以做了。

`dp[i][j]`： 戳爆区间i,j间所有气球能获得的最大coins，注意，不包含i,j

`dp[i][j] = dp[i][k]+dp[k][j]+nums[i]*nums[j]*nums[k]`，其中k指的是区间i,j内最后被戳爆的气球

顺序可以用之前的画图法来推导得出。

```python
class Solution:
    def maxCoins(self, nums)-> int:
        n = len(nums)
        nums = [1]+nums+[1]
        dp = [[0 for i in range(n+2)] for j in range(n+2)]

        for i in reversed(range(0, n)):
            for j in range(i+2, n+2):
                for k in range(i+1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+nums[i]*nums[j]*nums[k])
        return dp[0][-1]
```

哎 load好大啊...
570这是在飙车啊，两节课Prim, Kruskal, Huffman, Djikstra...算法和时间复杂度分析倒是还好，但是这个证明，要我狗命啊，让我想我肯定想不出这么证啊orz

### Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.



**Example:**

```
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.
```



### Solution

解法一：

一开始想的方法是一个stack存储原始的数据，另一个双向链表存储升序的数据节点 ```Node: val, next, pre, cnt```

由于我是在push时对链表进行排序操作，而且排序又就是从前往后的简单的遍历，所以当push进来的数据特别多,如n个且按降序排列时，需要的操作数就是 0+1+2+3+4+...+n-1 = log(n2),虽然题目没有限制push的复杂度， 但 n一大还是玩球了。

```python
class Node:
    def __init__(self, val=None):
        self.val = val
        self.next = None
        self.pre = None
        self.cnt = 1
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.dummy = Node(float("-inf"))
        self.hashmap = {}
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if x in self.hashmap:
            node = self.hashmap[x]
            node.cnt += 1
            return
        node = Node(x)
        curr = self.dummy
        while(curr.next and curr.next.val<node.val):
            curr = curr.next
        node.next = curr.next
        node.pre = curr
        if curr.next:
            curr.next.pre = node
        curr.next = node
        self.hashmap[x] = node

    def pop(self) -> None:
        x = self.stack.pop()
        node = self.hashmap[x]
        if node.cnt>1:
            node.cnt-=1
            return
        self.hashmap.pop(x)
        node.pre.next = node.next
        if node.next:
            node.next.pre = node.pre
        
        

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.dummy.next.val
```



解法二：

这是看了别人的题解才想起来以前做过这样的类似题目orz...

思路是一个栈stack存储原始元素， 另一栈helper存储当前的最小值，辅助栈和数据栈不同步

    # 关键 1：辅助栈的元素空的时候，必须放入新进来的数
    # 关键 2：新来的数小于或者等于辅助栈栈顶元素的时候，才放入（特别注意这里等于要考虑进去）
    # 关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了

当push时，if helper[-1]>=x，那helper.append(x)，也就是当前位置的最小值更新为x,  当pop时，判断if stack.pop()==helper[-1]， 如果等于，那就说明被pop出去的恰好是最小值，最小值需要更新一下 helper.pop()

```python
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.helper = []


    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.helper or self.helper[-1]>=x:
            self.helper.append(x)

    def pop(self) -> None:
        x = self.stack.pop()
        if x==self.helper[-1]:
            self.helper.pop()
        
    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.helper[-1]

```