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

## 41. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

**Example 1:**

```
Input: [1,2,0]
Output: 3
```

**Example 2:**

```
Input: [3,4,-1,1]
Output: 2
```

**Example 3:**

```
Input: [7,8,9,11,12]
Output: 1
```

**Note:**

Your algorithm should run in *O*(*n*) time and uses constant extra space.

---

### Solution

难点在于不使用额外空间啊

1. 直观的想法：将对应数值移动对应位置，如 3  -> A[2]。最后从前往后遍历判断。

   > We visit each number once, and each number will be put in its right place at most once, so it is O(n) + O(n). Although there are two nesting of cyclic (for and while), but its time complexity is still O(n).

   ```python
       def firstMissingPositive(self, nums):
           n = len(nums)
           for i in range(n):
               # Need loop, because after swap, former A[i] is in right place,
               # but the one swapped at i is not sure.
               while(nums[i]>0 and nums[i]<=n and nums[nums[i]-1]!=nums[i]):
                   nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
           for i in range(n):
               if nums[i] != i+1:
                   return i+1
           return n+1
   ```

   

2. 很tricky的方法。以数组下标为hash，存储值的出现频次，最后也是从前往后遍历判断，哪个数组元素的出现频次小于1，就是缺失的那个正数。以A=[1,3,4,5,6]为例：

   

   ```python
       def firstMissingPositive(self, nums: List[int]) -> int:
           nums.append(0)
           n = len(nums)
           for i,num in enumerate(nums):
               if num>=n or num<0:
                   nums[i] = 0
           for i in range(n):
               nums[nums[i]%n] += n
           for i in range(1, n):
               if nums[i]//n==0:
                   return i
           return n
   ```

   

## 42. Trapping Rain Water

Given *n* non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. **Thanks Marcos** for contributing this image!

**Example:**

```
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
```

---

### Solution

1. 找到最高的海拔高度的对应下标k个，将地图分隔开来，前k-1块可以用naive的贪心去算积水量（从前往后碰到更高的就加总更新），最后一块反过来算

   ```python
   class Solution:
       def trap(self, h: List[int]) -> int:
           if not h:
               return 0
           def helper(h, l, r, step):
               max_h = h[l]
               tmp = 0
               res = 0
               l+= step
               while((l<=r and step>0) or (l>=r and step<0)):
                   if h[l]>=max_h:
                       res += tmp
                       max_h = h[l]
                       tmp = 0
                   else:
                       tmp += max_h - h[l]
                   l+= step
               return res
           maxi = [0]
           n = len(h)
           for i in range(n):
               if h[i]>h[maxi[0]]:
                   maxi = [i]
               elif h[i] == h[maxi[0]]:
                   maxi.append(i)
           res = 0
           pre = 0
           for i in maxi:
               res += helper(h, pre, i, 1)
               pre = i
           res += helper(h, n-1, maxi[-1], -1)
           return res
   ```

2. 同样的思路，但是别人的贼精简orz

   ```python
       def trap(self, h):
           n = len(h)
           a,b = 0,n-1
           leftmax,rightmax = 0,0
           res = 0
           while(a<b):
               leftmax = max(leftmax, h[a])
               rightmax = max(rightmax, h[b])
               if leftmax<=rightmax:
                   res += leftmax - h[a]
                   a += 1
               else:
                   res += rightmax - h[b]
                   b -= 1            
           return res
   ```

   

## 138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a [**deep copy**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the list.

The Linked List is represented in the input/output as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where:

- `val`: an integer representing `Node.val`
- `random_index`: the index of the node (range from `0` to `n-1`) where random pointer points to, or `null` if it does not point to any node.



**Example 1:**


```
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
```

**Example 2:**


```
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
```

**Example 3:**

****

```
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
```

**Example 4:**

```
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
```



**Constraints:**

- `-10000 <= Node.val <= 10000`
- `Node.random` is null or pointing to a node in the linked list.
- Number of Nodes will not exceed 1000.

---

### Solution

1. 直觉的做法：先复制，再分配。需要借助hashmap来存储对应的idx和点的映射关系

```
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        curr = head
        p= q = o =  Node(head.val, head.next)
        curr = curr.next
        lookup = {0:p}
        relookup = {head:0}
        idx = 0
        l = 1
        while(curr):
            idx += 1
            l += 1
            node = Node(curr.val, curr.next)
            lookup[idx] = node
            relookup[curr] = idx
            p.next = node
            curr = curr.next
            p = p.next
        lookup[l] = None
        curr = head
        while(curr):
            if not curr.random:
                idx = l
            else:
                idx = relookup[curr.random]
            q.random = lookup[idx]
            q = q.next
            curr  = curr.next
        return o
```

这是别人写的...差距啊...

```python
    def copyRandomList(self, head):
        if not head:
            return head
        d = dict()
        a = b = head
        while(a):
            d[a] = Node(a.val)
            a = a.next
        cnt = 0
        while(b):
            # when b.next or b.random is None, it fails because None cannot be key.
            # So use d.get
            d[b].next = d.get(b.next)
            d[b].random = d.get(b.random)
            b = b.next
        return d[head]
```



2. tricky的做法。把复制的节点插在被复制的节点后面。贴个链接吧

   https://leetcode.com/problems/co ... -space-complexity-O(1)-and-linear-time-complexity-O(N)

   

## 11. Container With Most Water

Given *n* non-negative integers *a1*, *a2*, ..., *an* , where each represents a point at coordinate (*i*, *ai*). *n* vertical lines are drawn such that the two endpoints of line *i* is at (*i*, *ai*) and (*i*, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

**Note:** You may not slant the container and *n* is at least 2.




The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.



**Example:**

```python
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
```

---

### Solution

双指针

```python
class Solution:
    def maxArea(self, h) -> int:
        n = len(h)
        l, r = 0, n-1
        res = 0
        while(l<r):
            if h[l]<=h[r]:
                res = max(h[l]*(r-l), res)
                l = l+1
            else:
                res = max(h[r]*(r-l), res)
                r = r-1
        return res
```

## Word Break II

Given a **non-empty** string *s* and a dictionary *wordDict* containing a list of **non-empty** words, add spaces in *s* to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

**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 = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]
```

**Example 2:**

```
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
```

**Example 3:**

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

### Solution

直接dfs会超时，需要dfs+memorization。注意是如何进行记忆化的！

```python
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        memo = {}
        def dfs(s):
            if s in memo:
                return memo[s]
            if not s:
                return []
            res = []
            for word in wordDict:
                if s.startswith(word):
                    if len(word) == len(s):
                        res.append(s)
                        continue
                    a = dfs(s[len(word):])
                    for item in a:
                        res.append(word + " " + item)
            memo[s] = res
            return res
        return dfs(s)
```

Mark一下，楼主总结的很好

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

   

## 1360. Number of Days Between Two Dates

Write a program to count the number of days between two dates.

The two dates are given as strings, their format is `YYYY-MM-DD` as shown in the examples.



**Example 1:**

```
Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1
```

**Example 2:**

```
Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15
```



**Constraints:**

- The given dates are valid dates between the years `1971` and `2100`.

---

### Solution:

计算日期的思路可以借鉴，把某一特定日期转化为从1971开始的天数和

```python
class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        def helper(date):
            months = [31,28,31,30,31,30,31,31,30,31,30,31]
            y,m,d = int(date[:4]), int(date[5:7]), int(date[8:])
            total = 0
            for i in range(1971, y):
                if i%4==0 and(i%100!=0 or i%400==0):
                    total += 366
                else:
                    total += 365
            if m>2 and (y%4==0 and (y%100!=0 or y%400==0)):
                total += 1
            for i in range(m-1):
                total += months[i]
            total += d
            return total
        return abs(helper(date1)- helper(date2))
```

## 23. Merge k Sorted Lists

Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

**Example:**

```
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
```

---

Solution

heap的板子. 需要注意的是比较类。直接用(node.val, node)会报错，因为ListNode没有 < 操作符，随后想到重写ListNode, 但是leetcode好像不支持重写这类基础数据类。所以最后还是用了Comparable类。

```python
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
   
#     def __lt__(self, other):
#         if self.val<other.val:
#             return True
#         else:
#             return False

class Comparable:
    def __init__(self, val, node):
        self.val = val
        self.node = node
   
    def __lt__(self, other):
        return self.val<other.val

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # if not lists or (not lists[0] and len(lists)==1):
        #     return None
        head = pre = ListNode(-1)
        heap = [Comparable(node.val,node) for node in lists if node]
        heapq.heapify(heap)
        while(heap):
            c = heapq.heappop(heap)
            curr = c.node
            pre.next = curr
            if curr.next:
                heapq.heappush(heap, Comparable(curr.next.val, curr.next))
            pre = curr
        return head.next
```

## 15. 3Sum

Given an array `nums` of *n* integers, are there elements *a*, *b*, *c* in `nums` such that *a* + *b* + *c* = 0? Find all unique triplets in the array which gives the sum of zero.

**Note:**

The solution set must not contain duplicate triplets.

**Example:**

```
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
```

---

Solution

一开始想岔了，想去存储两数和，但其实遍历nums，以一个数为基点，往后找满足条件的两个数即可。

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = set()
        for i in range(n-2):
            l,r = i+1,n-1
            if nums[i]>0:
                break
            # If the number is the same as the number before, we have used it as target already, continue.
            # This strategy save a lot of time.
            if i>0 and nums[i]==nums[i-1]:
                continue
            while(l<r):
                t = nums[l]+nums[r]
                if t>-nums[i]:
                    r = r-1
                elif t<-nums[i]:
                    l = l+1
                else:
                    res.add((nums[i],nums[l],nums[r]))
                    l = l+1
        res = [list(i) for i in res]
        return res
```



别人的题解，对于重复性的处理值得借鉴

```python
class Solution(object):
        def threeSum(self, nums):
                res = []
                nums.sort()
                length = len(nums)
                for i in xrange(length-2): #[8]
                        if nums[i]>0: break #[7]
                        if i>0 and nums[i]==nums[i-1]: continue #[1]

                        l, r = i+1, length-1 #[2]
                        while l<r:
                                total = nums[i]+nums[l]+nums[r]

                                if total<0: #[3]
                                        l+=1
                                elif total>0: #[4]
                                        r-=1
                                else: #[5]
                                        res.append([nums[i], nums[l], nums[r]])
                                        # We need to move the left and right pointers to the next different numbers,
                    # so we do not get repeating result. [6]
                                        while l<r and nums[l]==nums[l+1]: #[6]
                                                l+=1
                                        while l<r and nums[r]==nums[r-1]: #[6]
                                                r-=1
                                        l+=1
                                        r-=1
                return res
```