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

## 72. Edit Distance

Given two words *word1* and *word2*, find the minimum number of operations required to convert *word1* to *word2*.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

**Example 1:**

```
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
```

**Example 2:**

```
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
```

---

Solution

竟然秒了...变强了吗？

```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        dp = [[float("inf") for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        for i in range(1, m+1):
            for j in range(1,n+1):
                a = 0 if word1[i-1]==word2[j-1] else 1
                dp[i][j] = min(dp[i-1][j-1]+a, dp[i-1][j]+1, dp[i][j-1]+1)
        return dp[-1][-1]
```

## 647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

**Example 1:**

```
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
```



**Example 2:**

```
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
```



**Note:**

1. The input string length won't exceed 1000.

---

### Solution

惊了 一发dp过了，本来感觉还会卡一会的呢。。。

```python
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)        
        dp = [[False for _ in range(n)] for _ in range(n)]
        res = n
        for i in range(n):
            dp[i][i] = True
            if i<n-1:
                dp[i][i+1] = s[i]==s[i+1]
                res += 1 if dp[i][i+1] else 0
        for j in range(n-2):
            for i in range(n):
                if 2+i+j<n:
                    dp[i][2+i+j] = dp[i+1][2+i+j-1] and s[i]==s[2+i+j]
                    res += 1 if dp[i][2+i+j] else 0
                else:
                    break
        return res
```

看了下别人的，dp顺序搞复杂了...这样就ok

```c
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++)
```

## 239. Sliding Window Maximum

Given an array *nums*, there is a sliding window of size *k* which is moving from the very left of the array to the very right. You can only see the *k* numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

**Example:**

```
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7
```

**Note:**
You may assume *k* is always valid, 1 ≤ k ≤ input array's size for non-empty array.

**Follow up:**
Could you solve it in linear time?

---

### Solution

1. Brute Force

2. MaxHeap

3. 双端队列。看了题解的思路后写的。

   ```python
       def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
           if not nums or k==0:
               return []
           if k==1:
               return nums
           n = len(nums)
           def clear(d, i, nums, k):
               if d and d[0]==i-k:
                   d.popleft()
               while(d and nums[i]>nums[d[-1]]):
                   d.pop()
           # Initialize deque
           t = float("-inf")
           d = deque()
           for i in range(k):
               clear(d, i, nums, k)
               d.append(i)
           res = []
           for i in range(k, n):
               res.append(nums[d[0]])
               clear(d, i, nums, k)
               d.append(i)
           res.append(nums[d[0]])
           return res
   ```

   后来其实核心在于利用单调递减的双端队列。滑动窗口最大值，最小值，用单调双端队列是一个思考方向。

   ```python
   class Monoqueue:
       def __init__(self):
           self.mq = deque()
      
       def push(self, n):
           while(self.mq and self.mq[-1]<n):
               self.mq.pop()
           self.mq.append(n)
      
       def pop(self):
           self.mq.popleft()
   
       @property   
       def front(self):
           return self.mq[0]
           
   class Solution:
       def maxSlidingWindow(self, nums, k):
           mq = Monoqueue()
           n = len(nums)
           res = []
           for i in range(n):
               # 注意下是i<k-1，对应后面的push,res.append顺序
               if i<k-1:
                   mq.push(nums[i])
                   continue
               mq.push(nums[i])
               res.append(mq.front)
               if nums[i-k+1]==mq.front:
                   mq.pop()
           return res
   ```

   

## 122. Best Time to Buy and Sell Stock II

Say you have an array for which the *i*th element is the price of a given stock on day *i*.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

**Note:** You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

**Example 1:**

```
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
```

**Example 2:**

```
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
```

**Example 3:**

```
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
```

---

### Solution

贪心吧

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        res = 0
        n = len(prices)
        i = 0
        t = prices[0]
        while(i<n-1):
            if prices[i+1]>=prices[i]:
                i+=1
            else:
                res += prices[i]-t
                t = prices[i+1]
                i+=1
        if prices[i]>=prices[i-1]:
            res += prices[i]-t
        return res
```

代码可简化。eg: 1,2,5,7 原思路为1处买7处卖，但其实可以直接将每次增长的值都加进去，省了不少判断逻辑。

```python
    def maxProfit(self, prices):
        if not prices:
            return 0
        res = 0
        for i in range(len(prices)-1):
            if prices[i+1]-prices[i]>0:
                res+= prices[i+1]-prices[i]
        return res
```

## 739. Daily Temperatures

Given a list of daily temperatures `T`, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put `0` instead.

For example, given the list of temperatures `T = [73, 74, 75, 71, 69, 72, 76, 73]`, your output should be `[1, 1, 4, 2, 1, 1, 0, 0]`.

**Note:** The length of `temperatures` will be in the range `[1, 30000]`. Each temperature will be an integer in the range `[30, 100]`.

---

### Solution

要找递增，用单调递减栈。

```python
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = deque()
        res = [0 for _ in range(len(T))]
        for i in range(len(T)):
            while(stack and stack[-1][0]<T[i]):
                _, idx = stack.pop()
                res[idx] = i-idx
            stack.append((T[i], i))
        while(stack):
            _, idx = stack.pop()
            res[idx] = 0
        return res
```

## 84. Largest Rectangle in Histogram

Given *n* non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.



Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.



The largest rectangle is shown in the shaded area, which has area = `10` unit.



**Example:**

```
Input: [2,1,5,6,2,3]
Output: 10
```

---

### Solution

思路： max(以第i根柱子为最矮柱子向两端延伸所能覆盖的最短面积 $S_i$)---> 找左边第一个比h[i]矮的柱子，找右边第一个比h[i]矮的柱子。朴素的想法，很容易就会得到Brute Force的解法，O(n^2)复杂度。

Q: 如何优化呢？是否存在某种方法，可以在常数时间内获取到第i根柱子两端更矮的index?

A: 单调栈。维护单调递增栈。对于栈中任意一根柱子，其下面一根柱子就是小于当前柱子的最近的那根。当右侧出现比栈顶柱子还要矮的柱子时，说明即可计算以栈顶为基准的$S_i$。

每根柱子入栈出栈各一次，Amortised Cost = O(n)

```python
from typing import List
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        heights  = [0]+heights + [0]
        res = 0
        for i in range(len(heights)):
            while(stack and heights[i]<heights[stack[-1]]):
                width = i-stack[-2]-1
                res = max(width*heights[stack[-1]], res)
                stack.pop()
            stack.append(i)
        return res
```

## 1368. Minimum Cost to Make at Least One Valid Path in a Grid

Given a *m* x *n* `grid`. Each cell of the `grid` has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of `grid[i][j]` can be:

- **1** which means go to the cell to the right. (i.e go from `grid[i][j]` to `grid[i][j + 1]`)
- **2** which means go to the cell to the left. (i.e go from `grid[i][j]` to `grid[i][j - 1]`)
- **3** which means go to the lower cell. (i.e go from `grid[i][j]` to `grid[i + 1][j]`)
- **4** which means go to the upper cell. (i.e go from `grid[i][j]` to `grid[i - 1][j]`)

Notice that there could be some **invalid signs** on the cells of the `grid` which points outside the `grid`.

You will initially start at the upper left cell `(0,0)`. A valid path in the grid is a path which starts from the upper left cell `(0,0)` and ends at the bottom-right cell `(m - 1, n - 1)` following the signs on the grid. The valid path **doesn't have to be the shortest**.

You can modify the sign on a cell with `cost = 1`. You can modify the sign on a cell **one time only**.

Return *the minimum cost* to make the grid have at least one valid path.



**Example 1:**


```
Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.
```

**Example 2:**


```
Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).
```

**Example 3:**


```
Input: grid = [[1,2],[4,3]]
Output: 1
```

**Example 4:**

```
Input: grid = [[2,2,2],[2,2,2]]
Output: 3
```

**Example 5:**

```
Input: grid = [[4]]
Output: 0
```



**Constraints:**

- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 100`

---

### Solution

离AK最近的一次了，哎...因为BFS对于VIS的判断遗漏而导致的超时，有点不甘心。

1. BFS+PriorityQueue

   ```python
   import heapq
   from collections import deque
   class Solution:
       def minCost(self, grid: List[List[int]]) -> int:
           d = {1: [0, 1], 2: [0, -1], 3: [1, 0], 4: [-1, 0]}
           q = [(0,0,0)]
           m = len(grid)
           n = len(grid[0])
           vis = [[0 for _ in range(n)] for _ in range(m)]
           while(q):
               cost, i, j = heapq.heappop(q)
               if i==m-1 and j==n-1:
                   return cost
               #  就是因为没有加这个vis[i][j]=1超时了！！！还是bfs没有理解透彻啊，哎。。。
               if vis[i][j]:
                   continue
               vis[i][j] = 1
               for k,v in d.items():
                   r,c = i+d[k][0],j+d[k][1]
                   if r<0 or r>=m or c>0 or c>=n or (r,c) or vis[r][c]:
                       continue
                   _cost = cost + 1 if grid[i][j]!=k else cost
                   heapq.heappush(q, (_cost, r, c))
   ```