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

### [4. 寻找两个有序数组的中位数](https://leetcode-cn.com/problems ... arrays/description/)

时间复杂度要求O(log(m+n))

#### 解法一：

我自己想到的解法就是以两数组a,b 中所有元素的最小值和最大值为范围，在这个范围中二分搜索，每找到一个数k就判断一下是不是中位数。 这个判断的过程也就是 a,b中在找不大于k的元素个数之和是否等于  

- (m+n+1)//2  对于a，b数组个数和为奇数
- (m+n+1)//2 or (m+n+2)//2   对于....偶数（有左中位数和右中位数）

那么怎么找不大于k的元素个数呢，其实可以转化为   二分查找   在数组中找>k的下界，所得left(第一个≥k的元素下标)即为数组中不大于k的元素个数。

总结一下，也就是两次二分，一次二分取值范围进行猜测(logK)，另一次对值利用二分进行判断(log(mn))， 所以总的复杂度至少是

logK ·log(mn)， 哇，惊人的复杂度...但是竟然还过了？？？

#### 解法二：

在题解中找到一份不错的[正确解法](https://leetcode-cn.com/problems ... -cheng-zhong-zhao-/)，主要是利用了边界线的思想，这是条什么样的边界线呢？这条边界线将这两个数组各自分成了左右两部分， a,b左边部分的元素数量之和就是(m+n+1)/2，对于奇数数量的数组来说，第(m+n+1)/2个元素就是中位数，对于偶数数量的数组，是左中位数，别忘了还有右中位数。非常有意思的一条边界线，找到了它也就找到了中位数！

那怎样才能找到这样的边界线呢？由于a,b左边部分的元素数量之和就是(m+n+1)/2， 所以其实只要确定边界线在a中的索引，b自然确定， 那问题就转化成在数组中找索引，log(m+n)? 二分go!

大概知道二分还不够， 毕竟还是不知道具体怎么找orz...

接着分析， 从这条边界线在两个数组中的位置我们可以发现，这条边界线满足这样的性质：

1. 边界线左边的所有数都小于等于右边的所有数
2. - a,b元素和为奇数时, size左 = size右+1
   - ...................偶数...., size左 = size右

性质2可以用 i+j=(m+n+1)//2 表示

性质1 就可以用来调整二分搜索的left right了，借用题解的图来表示一下逻辑


那这搜索的逻辑代码也就相应得出了：

```python
left = 0
right = m
while(left<right):
    i = left + (right-left)//2
    j = (m+n+1)//2 - i
    if nums1[i] < nums[j-1]:
        left = i+1
    else:
        right = i
```

所得 left 即为边界线

以为这样就完了吗？No！边界条件！如果边界线一侧是空集怎么办！

其实也可以处理， 先回想下，我们的边界线将两个数组分成两部分，左边一部分的元素的数量和是(m+n+1)/2，如果是m+n是奇数，那么就拿这第(m+n+1)/2个数，如果是偶数，那拿这个数和恰好比这个数大的那个数。

注意，是i+j=(m+n+1)/2，所以这第(m+n+1)/2个数是哪个呢？a在边界线左边的第一个数，还是b呢？对，比较一下这两个数谁大就行了，所以空集怎么处理也显而易见了吧，反正不可能选空集，那就把边界线左侧出现的空集表示成-inf。同样的逻辑，对于第(m+n+1)//2个数后的一个数，取边界线右侧a,b中更小的那个，出现空集就表示成inf

```python
        nums1LeftMax = float("-inf") if i == 0 else nums1[i - 1]
        nums1RightMin = float("inf") if i == len(nums1) else nums1[i]

        nums2LeftMax = float("-inf") if j == 0 else nums2[j- 1]
        nums2RightMin = float("inf") if j == len(nums2) else nums2[j]

        if (len(nums1) + len(nums2)) & 1:
            return max(nums1LeftMax, nums2LeftMax)
        else:
            return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin))/2
```

至此，就解决了这个问题～




补充内容 (2020-2-4 02:09):
如果觉得楼主哪里写的有问题的话，欢迎指出噢～

## 10. Regular Expression Matching

Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for `'.'` and `'*'`.

```
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
```

The matching should cover the **entire** input string (not partial).

**Note:**

- `s` could be empty and contains only lowercase letters `a-z`.
- `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`.

**Example 1:**

```
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

**Example 2:**

```
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
```

**Example 3:**

```
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
```

**Example 4:**

```
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
```

**Example 5:**

```
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
```

---

### Solution

1. 回溯。Emmmmm交了6发才A了，总之就是各种判断...       

```python
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # Generate Patterns.
        pattern = []
        for i in range(len(p)):
            if p[i]!="*":
                if i==len(p)-1 or p[i+1]!="*": pattern.append((p[i],"#"))
                else: pattern.append((p[i], "*"))
            else:
                if i<len(p)-1 and p[i+1]=="*":
                    return False
               
        self.flag = False
        def dfs(s, pattern):
            if self.flag:
                return True
            if not s:
                if not pattern:
                    self.flag = True
                elif pattern[0][1]=="*":
                    self.flag = dfs(s[:], pattern[1:])
                else:
                    self.flag = False
                return self.flag
            if not pattern:
                return False
            pt, sign = pattern[0]
            flag = False
            if pt==".":
                if sign=="*":
                    for i in range(len(s)+1):
                        flag = flag or dfs(s[i:], pattern[1:])
                else:
                    flag = flag or dfs(s[1:], pattern[1:])
            else:
                if s[0]!=pt and sign!="*":
                    flag = False
                else:
                    if sign=="*":
                        for i in range(len(s)+1):
                            if i==1:
                                print(s)
                            if i==0:
                                flag = flag or dfs(s[:], pattern[1:])
                            else:
                                if s[i-1]!=pt:
                                    break
                                flag = flag or dfs(s[i:], pattern[1:])
                    else:
                        flag = flag or dfs(s[1:], pattern[1:])
            return flag
        return dfs(s, pattern)
```

2. dp。这个dp好难啊...

   ```python
       def isMatch(self, s: str, p: str) -> bool:
           n = len(s)
           m = len(p)
           dp = [[False for _ in range(m+1)] for _ in range(n+1)]
           dp[0][0] = True
           # Update the corner case of when s is an empty string but p is not.
           for j in range(1,m+1):
               if p[j-1] == "*":
                   dp[0][j] = dp[0][j-2]
   
           for i in range(1, n+1):
               for j in range(1, m+1):
                   if s[i-1]==p[j-1] or p[j-1]==".":
                       dp[i][j] = dp[i-1][j-1]
                   elif p[j-1]=="*":
                       a = b = False
                       # 0 occurence. 相当于 x* 这个pattern不用，所以看去掉这段pattern后，之前所计算出的结果
                       a = dp[i][j-2]
                       # >=1 occurences. 相当于 x* 这个pattern至少匹配了一个字符，匹配成功的前提条件就是：
                       # 'x' 和当前s[i-1]相同/ 'x'='.'，当前位匹配成功了，那决定dp[i][j]的就是dp[i-1][j]（这是难点，想想为啥是                                        i-1，而不是改变j：因为x*可以匹配多个。）
                       # 如果前提条件不满足，就归到最后一个else了。
                       if p[j-1-1]==s[i-1] or p[j-1-1]==".":
                           b = dp[i-1][j]
                       dp[i][j] = a or b
                   else:
                       dp[i][j]==False
                  
           return dp[-1][-1]
   ```

   

## 621. Task Scheduler

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval **n** that means between two **same tasks**, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the **least** number of intervals the CPU will take to finish all the given tasks.



**Example:**

```
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
```



**Note:**

1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

------

这题一开始的想法是贪心，拿尽可能多的不同task归到一组里面，然后再搞下一组。某个task用完了就从可用task中移除。如果某一组的数量小于n+1，就拿idle去填充。不知道这样贪有没有问题，但就是wa了。

```python
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0:
            return len(tasks)
        hm = {}
        t = 0
        for task in tasks:
            hm[task] = hm.get(task, 0) + 1
            t = max(t, hm[task])
        print(hm)
        counts = sorted(hm.values(), reverse=True)

        ret = 0
        while counts:
            if len(counts) - 1 >= n:
                t = counts.pop(-1)
                ret += t * (len(counts))
                _counts = []
                for i in range(len(counts)):
                    counts[i] -= t
                    if counts[i] > 0:
                        _counts.append(counts[i])
                counts = _counts
            else:
                i = 0
                while i < len(counts) - 1:
                    if counts[i] == counts[i + 1]:
                        i = i + 1
                    else:
                        break
                ret += (counts[0] - 1) * (n + 1) + i + 1
                break
        return ret
```

后来看有人用优先队列解的，但是python中的heapq是没有decreasekey这个操作的，然后就去找怎么搞。最后弄出来这么个优先队列的类。

```python
from typing import List
from collections import Counter
import heapq
from itertools import count
import collections

REMOVED = "<removed-task>"


class PriorityQueue:
    def __init__(self):
        self.pq = []
        self.entryFinder = {}
        self._counter = count()
        self.size = 0

    def addTask(self, task, priority=0):
        if task in self.entryFinder and self.entryFinder[task][-1] != REMOVED:
            self.remove_task(task)
        count = next(self._counter)
        entry = [priority, count, task]
        self.entryFinder[task] = entry
        self.size += 1
        heapq.heappush(self.pq, entry)

    def removeTask(self, task):
        self.size -= 1
        entry = self.entryFinder[task]
        entry[-1] = REMOVED

    def popTask(self):
        while self.pq:
            priority, count, task = heapq.heappop(self.pq)
            if task is not REMOVED:
                self.size -= 1
                del self.entryFinder[task]
                return task, priority
        raise KeyError("pop from an empty priority queue")

    def findMin(self):
        while self.pq:
            if self.pq[0][-1] == REMOVED:
                heapq.heappop(self.pq)
            else:
                return self.pq[0][-1], self.pq[0][0]
        raise KeyError("The priority queue is empty")

    @property
    def isEmpty(self):
        return self.size == 0
   
    def __repr__(self):
        s = [f"{i[2]}:{i[0]}" for i in self.pq]
        return ",".join(s)


class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        pq = PriorityQueue()
        counts = collections.Counter(tasks)
        for key, val in counts.items():
            pq.addTask(key, -val)
        count= 0
        while not pq.isEmpty:
            # print(pq)
            interval = n + 1
            _pq = []
            while interval > 0 and not pq.isEmpty:
                task, cnt = pq.popTask()
                if task==REMOVED:
                    continue
                _pq.append([task, cnt + 1])
                interval -= 1
                count += 1
            for task, cnt in _pq:
                if cnt < 0:
                    pq.addTask(task, cnt)
            if pq.isEmpty:
                break
            # print(f"interval:{interval}, cnt:{cnt}")
            count += interval
        return count
```

## 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]
```

## 142 环形链表II  (链表寻找环入口)

### Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

To represent a cycle in the given linked list, we use an integer `pos` which represents the position (0-indexed) in the linked list where tail connects to. If `pos` is `-1`, then there is no cycle in the linked list.

**Note:** Do not modify the linked list.



**Example 1:**

```
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
```


**Example 2:**

```
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
```


**Example 3:**

```
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
```




**Follow-up**:
Can you solve it without using extra space?



### Solution

这道题很有代表性了，链表找环入口。算法也比较精巧，更巧的是，又忘了怎么证明的了

算法过程：

1. fast, slow 从head 出发，fast速率为2， slow速率为1，直至两点相遇，若fast遇到None，则说明无环
2. a从head出发，b从相遇点出发，速率都为1，直至a,b相遇，相遇点即为环入口

证明如下：

给个思路吧，假设有环，环前距离为a，环长度为b，那么slow到达环入口时，此时fast在环上的什么位置呢？fast比slow要多走一个a，所以$h= a\mod b$

接着走，直到fast和slow相遇，要走多远呢，走  b-h！

slow走了b-h，到了环上的b-h处；fast走了2(b-h)，加上原来走的那一段距离 $2b-2h+h=2b-h$，又套圈了，去掉个b，就是b-h，两点恰好相遇在b-h处！

最后a从head出发，b从相遇点出发，相遇于环入口



代码很短，但是坑却不少，主要在第一个while上，开始写成了`while(fast and fast.next and slow!=fast)`。1. 初始化时fast和slow都指向了head，导致不进入循环体....   2. 考虑只有一个节点的特例。while中的fast.next直接隔断循环体，跳到下面去了，然后就把这个节点给输出了，明明是没有环的...

```python
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while(True):
            if not fast or not fast.next:
                return None
            slow = slow.next
            fast = fast.next.next
            if slow==fast: break
        a = head
        b = fast
        while(a!=b):
            a = a.next
            b = b.next
        return a
```



还有一题找数组重复数可以用到类似的思路

https://leetcode.com/problems/find-the-duplicate-number/

把数组中的元素看为链表中的节点。 元素下标是链表节点值， 元素值是节点的next。找重复元素也就转化为了找链表的环入口

##  3. Longest Substring Without Repeating Characters(滑动窗口经典问题)

Given a string, find the length of the **longest substring** without repeating characters.

**Example 1:**

```
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```

**Example 2:**

```
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
```

**Example 3:**

```
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
```



### Solution

一看就知道是滑动窗口的题，但就是写不对，各种边界可搞死我了orz

直接上代码吧，注释写挺清楚了。

```python
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right = 0, 0
        n = len(s)
        tmp = {}
        local, ret = 0, 0
        # 第一个while中维护一个循环不变量：$[left, right)$间元素都已经被计入，且无重复元素。
        # 也就是说s[left]到s[right-1]间都被加入了tmp， 而tmp[s[right]]一定为False.
        while left <= right and left < n and right < n:
            # right一直向后探索，直到触底或者遇到重复元素
            while right < n and (s[right] not in tmp or tmp[s[right]] == False):
                tmp[s[right]] = True
                right += 1
            ret = max(ret, right - left)
            # 触底
            if right == n:
                continue
            # 遇到重复元素，为了维护循环变量的性质，那就要删去原来的，加入新的
            # while 寻找旧的重复元素位置，同时移出tmp
            while left < n and s[left] != s[right]:
                tmp[s[left]] = False
                left += 1
            # 此时s[left],s[right]指向的元素相等，就是重复元素
            # 下面两步很重要
            tmp[s[right]] = False   #维护[left, right)，所以right此时不能加入tmp
            left += 1   # left要指向旧的重复元素的后一位
        return ret
```

## 76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

### Solution

又是滑动窗口的问题，这题有点搞噢。

对于输入的T没有考虑周到，没想到会输入多个相同的，一开始就用了set去存。后来发现有相同值，就得改成{key: cnt}的形式来做了。

最终代码如下：

```python
import collections
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)
        target = collections.defaultdict(int)
        for w in t:
            target[w] += 1
        left, right = 0, 0  
        self.ret, self._global = "", float("inf")
        cntMap = collections.defaultdict(int)
        while left < n and right < n:
            while right < n and not self.contains(target, cntMap):
                if s[right] in target:
                    cntMap[s[right]] += 1
                right += 1
         
            # unable to find all： 两种情况，一种是到底了都没有合适的，一种是之前有合适的，但是作啊，不要，left继续往后，然后就找不到合适的了。这两种情况都直接输出ret就行。
            if not self.contains(target, cntMap):
                return self.ret
            self.judge(s, left, right)
            # remove elements to make lookup<target
            # 此处循环不变量为 s[left,right) 包含T的所有字母
            while left < n:
                tmp = s[left]
                if tmp in target:
                    cntMap[tmp] -= 1
                    if not self.contains(target, cntMap):
                        left += 1
                        break
                # 于此处进行紧缩
                left += 1
                self.judge(s, left, right)
        return self.ret

    def judge(self,s, left, right):
        if self._global > right - left:
            self._global = right - left
            self.ret = s[left:right]
   
    def contains(self, target, source):
        for key,val in target.items():
            if key not in source or val>source[key]:
                return False
        return True
```

题目要求是O(n)， 我瞄一眼就觉得这不是O(n)... 毕竟contains的复杂度是O(k)的，k是target的长度，循环里一直在调用contains......怎么说，但还是过了。明天瞅瞅别人的题解吧。

补充内容 (2020-1-26 04:51):
今天看了下，完全可以把contains优化掉：
用一个match变量标识已被匹配的数量，用match和target的所含元素数进行比较（需要注意的是t="aa"，那target={"a":2}，也就是match等于1就满足条件了）代码贴不下就不贴了

给楼主点个赞

## 55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

**Example 1:**

```
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
```

**Example 2:**

```
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.
```



### Solution:

哎，为什么我这么菜啊

第一反应dfs，好的超时， 发现其实只要idx+val的值大过end就可以了，优化下，emmm还是超时，真的难顶，放代码

```python
    def canJump(self, nums: List[int]) -> bool:
        if not nums:
            return False
        vis = [0 for _ in nums]
        m = len(nums)
        if m==1:
            return True

        def dfs(pos, nums):
            flag = False
            for i in reversed(range(nums[pos])):
                j = pos+i+1
                if j>=m-1:
                    return True
                if j<m and not vis[j]:
                    vis[j] = 1
                    flag = flag or dfs(j, nums)
                    if flag:
                        return flag
            return flag
        return dfs(0, nums)
```

接着想，利用idx+val>end，试试看贪心？

```python
    def canJump(self, nums: List[int]) -> bool:
        idx = 0
        if len(nums)==1:
            return True
        while(True):
            t = idx
            for i in range(nums[idx]):
                pos = idx +i+1
                if pos>=len(nums)-1 or pos+nums[pos]>=len(nums)-1:
                    return True
                t = max(pos+nums[pos], t)
            if t==idx:
                return False
            idx = t
```

nice 样例[5,9,3,2,1,0,2,3,3,1,0,0]跑不通（微笑脸）

结果我没细想为什么不通，直接以为贪心有问题？？？跑去写dp？？？

写的dp简直是傻吊，我直接把题意给扭曲了，以为上一次剩下的步数还可以存储到下一次，那这样的话dp[i] 为移动到i时所剩的最大步数，那只要dp[-1]>=0即可。递推式就是：dp[i] = max(dp[j]-(i-j)+nums[j]  if i-j<=dp[j], dp[i]), j=0...i-1。O(n^2)，像模像样，宛若智障。

受不了了，去看了别人的题解，一口老血。

```python
    def canJump(self, nums):
        max_i = 0
        for i,val in enumerate(nums):
            if max_i<i:
                return False
            if i+val>max_i:
                max_i = i+val
        return max_i>=len(nums)-1
```

直接维护当前所能到达的最远处 max_i。

当时的贪心为什么错呢？想了想，贪过头了。我是以i 为基准，找从i出发能到达的点中最远的一个，然后再拿最远的这个点去探索。所以这样的样例：[5,9,3,2,1,0,2,3,3,1,0,0]就跑不通了，基本功不扎实啊...稳扎稳打，每个idx都去瞅一眼，看看能不能到这个idx，再看看这个idx+nums[idx]能到哪，比max_i大就更新了，这也就是O(n)的复杂度...

吸取教训，谨记。

## 1335. Minimum Difficulty of a Job Schedule

You want to schedule a list of jobs in `d` days. Jobs are dependent (i.e To work on the `i-th` job, you have to finish all the jobs `j` where `0 <= j < i`).

You have to finish **at least** one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the `d` days. The difficulty of a day is the maximum difficulty of a job done in that day.

Given an array of integers `jobDifficulty` and an integer `d`. The difficulty of the `i-th` job is `jobDifficulty[i]`.

Return *the minimum difficulty* of a job schedule. If you cannot find a schedule for the jobs return **-1**.



**Example 1:**


```
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
```

**Example 2:**

```
Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
```

**Example 3:**

```
Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.
```

**Example 4:**

```
Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15
```

**Example 5:**

```
Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843
```



**Constraints:**

- `1 <= jobDifficulty.length <= 300`
- `0 <= jobDifficulty[i] <= 1000`
- `1 <= d <= 10`

### Solution

周赛最后一题，dp数组，转换关系思路都是对的，死在了边界条件，真的菜

```python
    def minDifficulty(self, jobs, d: int) -> int:
        if d>len(jobs):
            return -1
        dp = [[float("inf") for _ in range(len(jobs))] for _ in range(d)]
        dp[0][0] = jobs[0]
        for i in range(1,len(jobs)):
            dp[0][i] = max(dp[0][i-1], jobs[i])
        for i in range(1,d):
            for j in range(1,len(jobs)):
                local = jobs[j]
                for k in reversed(range(i,j+1)):
                    local = max(local, jobs[k])
                    dp[i][j] = min(dp[i][j], dp[i-1][k-1]+local)
        return dp[-1][-1]
```

## 152.  Maximum Product Subarray

Given an integer array `nums`, find the contiguous subarray within an array (containing at least one number) which has the largest product.

**Example 1:**

```
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
```

**Example 2:**

```
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
```



### Solution:

dp老大难啊....

一开始想的是用dp\[i][j]来表示从nums[i]到nums[j]间的最大乘积，然后犯了两个错误。

1. 没有考虑到负数成负数的情况，只用一个dp表示最大乘积并不够，还要保存最小乘积
2. 根本没必要开二维dp，直接dp[i]表示nums[:i+1]间的最大乘积即可

经过修改写出了下面的代码

```python
from typing import List
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        if not nums:
            return 0
        dp  = [1 for _ in range(n)]
        dp_min  = [1 for _ in range(n)]
        ret = float("-inf")
        for i in range(n):
            dp[i] = max(dp[i-1]*nums[i], dp_min[i-1]*nums[i],nums[i])
            dp_min[i] = min(dp[i-1]*nums[i], dp_min[i-1]*nums[i],nums[i])
            ret = max(ret, dp[i])
        return ret
```

但其实，空间复杂度还可以优化，因为dp转化方程只用到前一位，比如dp[i] 只会和dp[i-1]，dp_min[i-1]打交道，所以只需要使用maxDp, minDp两个变量就可以了。

```python
    def maxProduct(self, nums):
        n = len(nums)
        if n==0:
            return 0
        if n==1:
            return nums[0]
        maxDp = nums[0]
        minDp = nums[0]
        #对于[2,-1,1,1]的形式，如果ret= -inf，就会出错。
        # 其实也的确应该是nums[0]，因为maxDp,minDp已经取了nums[0]，相当于已经判断过idx=0，那么ret也得对应补上
        ret = nums[0]        
        for i in range(1, n):
            t = maxDp                # 注意此处，maxDp会先改变，所以需要存储
            maxDp = max(maxDp*nums[i], minDp*nums[i], nums[i])
            minDp = min(t*nums[i], minDp*nums[i], nums[i])
            ret = max(ret, maxDp)
        return ret
```

状态有点不对，各种细节处理不当。

## 172. Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

**Example 1:**

```
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
```

**Example 2:**

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

### Solution:

两种方法，一种常规，维护idx之前最小的price，每次和price[idx]比较下更新ret即可

```python
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n<=1:
            return 0
        _min = prices[0]
        ret = 0
        for i in range(1, n):
            if prices[i]>_min:
                ret = max(ret, prices[i]-_min)
            else:
                _min = prices[i]
        return ret
```



另外一种是...DP，没想到吧，这种解法真的很美

将求原数组两个元素的最大差   转化为  求差值数组的最大子序列和

```python
    def maxProfit(self, prices):
        n = len(prices)
        if n<=1:
            return 0
        diff = [prices[i+1]-prices[i] for i in range(n-1)]
        dp = [0 for i in range(n-1)]
        dp[0] = max(diff[0], 0)
        ret = max(dp[0], 0)
        for i in range(1,n-1):
            dp[i] = max(dp[i-1]+diff[i], 0)
            ret = max(dp[i], ret)
        return ret
```

> 牛顿莱布尼茨公式：
>
> $\int_{a}^{b} f(x) \mathrm{d} x=\left.F(x)\right|_{a} ^{b}=F(b)-F(a)$
>
> **区间和可以转换成求差的问题，求差问题，也可以转换成区间和的问题**。

dp数组和diff数组也可以优化掉...

https://leetcode-cn.com/problems ... hi-ji-dp-7-xing-ji/

## 139 Word Break

Given a **non-empty** string *s* and a dictionary *wordDict* containing a list of **non-empty** words, determine if *s* can be segmented into a space-separated sequence of one or more dictionary words.

**Note:**

- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.

**Example 1:**

```
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
```

**Example 2:**

```
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
```

**Example 3:**

```
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
```



### Solution

有点感觉了，感觉卡的点就在dp递推式上，两个for，下标范围取多少，对应的递推式dp下标怎么取，这一块是大有问题的。这题做的时候，想不大明白，就写了两三个具体的递推式，然后才发现下标该怎么取的。不知道有没有更好的办法。

```python
class Solution:
    def wordBreak(self, s: str, wordDict) -> bool:
        n = len(s)
        dp = [False for i in range(n+1)]
        # 为了考虑将s[:i+1]整个字符串拿去看在不在wordDict中的情况，所以要设置dp[0] = True
        # 也是为了后面递推的方便
        dp[0] = True
        dp[1] = s[0] in wordDict
        for i in range(1, n+1):
            for j in range(1,i+1):
                dp[i] = dp[i] or (dp[j-1] and s[j-1:i] in wordDict)
        return dp[-1]
```