• 
  
• 为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？

  从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k type_size但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)type_size对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

• 散列表

散裂冲突？

1. 开放寻执法
   1. 线性寻找
   2. 二次寻找
   3. 二次散裂
2. 链表法 - bucket

• 分治算法是一种处理问题的思想，递归是一种编程技巧。

实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

1. 分解：将原问题分解成一系列子问题
2. 解决：递归地求解各个子问题，若子问题足够小，则直接求解
3. 合并：将子问题的结果合并成原问题。

Math & Bit

不用加号的加法 & ^ <<

class Solution:
    def add(self, a: int, b: int) -> int:
      while b:
        a, b = a& 0xFFFFFFFF ^ b& 0xFFFFFFFF, (a&b)<<1 & 0xFFFFFFFF
      return a if a < 0x80000000 else ~(a^0xFFFFFFFF)

埃拉托斯特尼筛法求素数

import math
def prime(L):
    arr = list(range(2,L))
    for i in range(math.ceil(math.sqrt(len(arr)))+1):
        if arr[i] == 0:
            continue
        for j in range(i+1, len(arr)):
            if arr[j]!= 0 and arr[j]%arr[i]==0:
                arr[j]=0
    return [i for i in arr if i!=0]

一个一个筛选，能整除的肯定不是素数

1. 当n是2的次幂, 那么 x%n == x & (n-1) 用位运算代替求模运算，可以提升效率
2. 异或运算可以用来找出唯一不重复的数字
3. & 1 可以用来做奇偶判断
4. pow(x,n)可以把n转换为二进制，每次& 1来连乘

   剑指 Offer 56 - I. 数组中数字出现的次数

   https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

   class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        for num in nums:
            res ^= num
        mask = 1
        while res & mask == 0:
            mask <<= 1
        a, b = 0, 0
        for num in nums:
            if num & mask:
                a ^= num
            else:
                b ^= num
        return [a,b]

   169. 多数元素

   https://leetcode-cn.com/problems/majority-element/

   class Solution {
   public:
    int majorityElement(vector<int>& nums) {
    int res = 0;
    for(int i = 0 ; i < 32; ++i)
    {
        int ones = 0;
        for(int n : nums)
            ones += (n >> i) & 1;              //位运算法统计每个位置上1出现的次数，每次出现则ones+1
        res += (ones > nums.size()/2) << i;    //如果1出现次数大于1/2数组的长度，1即为这个位置的目标数字
    }
    return res;
    }
   };

   Sort

   冒泡排序

   每次都从数组最开始循环, 遇到前一个大于后一个的, 就把大的挪到后面, 所以一次循环之后,最大的元素会被放到最后

   def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

   选择排序

   每次循环找到最小的那个元素的index, 然后把它放到最前面

   def select(arr):
   for i in range(len(arr)):
    min_idx = i
    for j in range(i+1, len(arr)):
      if arr[j] < arr[min_idx]:
        min_idx = j
    if min_idx != i:
      arr[min_idx], arr[i] = arr[i], arr[min_idx]
   return arr

   插入排序

   每次循环从当前元素往前找, 把它插入到合适的位置

   def insert_sort(arr):
   for i in range(len(arr)):
    j = i
    while j > 0:
      if arr[j] < arr[j-1]:
        arr[j], arr[j-1] = arr[j-1], arr[j]
      j -= 1
   return arr

   快速排序

   分两部分
   递归函数是quick sort自身, 提供一个array, 提供一个low一个high, 把这个范围里的做个divide, 然后一边小于pivot, 一边大于pivot, 这个事情具体由partition函数来做, shuffle之后, 取第一个元素为pivot (也可以是最后一个,也可以是随机找的一个), 循环, 双指针: 如果小于pivot, 不操作, 左指针++, 如果大于pivot, 左右指针指向的元素调换, 右指针— ```python def partition(arr, low, high): pivot = arr[low] i = low + 1 j = high while i <= j: if arr[i] < pivot: i += 1 else: arr[i], arr[j] = arr[j], arr[i] j -= 1 arr[low], arr[j] = arr[j], arr[low] return j

def quick_sort(arr, low, high): if low < high: pivot = partition(arr, low, high) quick_sort(arr, low, pivot-1) quick_sort(arr, pivot+1, high) return arr

<a name="XHPP9"></a>
### 堆排序
- 堆排序是利用 **堆**进行排序的
- **堆**是一种完全二叉树
- **堆**有两种类型: **大根堆** **小根堆**
- 两种类型的概念如下：<br />大根堆：每个结点的值都大于或等于左右孩子结点<br />小根堆：每个结点的值都小于或等于左右孩子结点
![image.png](https://cdn.nlark.com/yuque/0/2021/png/12408325/1611127316880-fc0ed86e-35bc-471a-8bfe-646efd618bc2.png#height=97&id=a1uox&margin=%5Bobject%20Object%5D&name=image.png&originHeight=290&originWidth=1154&originalType=binary&ratio=1&size=37884&status=done&style=none&width=384.6666666666667)<br />Find the maximum element and place the maximum element at the end.<br />a binary heap is a complete binary tree.
1. build a max heap from the input data
1. at this point, the largest item is stored at the root of the heap, replace it with the last item of the heap followed by reducing the size of heap by 1. finally heapify the root of the tree.
1. repeat step 2 while size of heap is greater than 1.
```python
import time
def heapify(arr,n, i):
    largest = i
    l = i*2 + 1
    r = i*2 + 2
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest!=i:
        arr[largest], arr[i] = arr[i], arr[largest]
        heapify(arr,n,largest)
def heapSort(arr):
    n = len(arr)
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0,-1):
        arr[i], arr[0] = arr[0], arr[i]
        # heapify until i, because the rest have been sorted and removed from the heap
        heapify(arr,i,0)
    return arr

Sliding Window

2021-02是滑动窗口月, 开一篇单独的题解来记录二月份的滑动窗口

480. 滑动窗口中位数

https://leetcode-cn.com/problems/sliding-window-median/
相比滑动窗口的最大值, 维护一个当前窗口的最大值, 这道题就变成了要维护一个有序数组(因为要找中位数), 然后用二分法进行查找.

import bisect
class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        res = []
        window = []
        left = 0
        for right in range(len(nums)):
            bisect.insort(window, nums[right])
            if right >= k-1:
                if k & 1:
                    res.append(window[k//2])
                else:
                    res.append((window[k//2]+window[(k-1)//2])/2.0)
                window.pop(bisect.bisect_left(window, nums[left]))
                left += 1
        return res

上面的题解主要是关于bisect的使用, 但是由于window.pop()的操作时间复杂度依然为O(k)

Design

146. LRU 缓存机制

https://leetcode-cn.com/problems/lru-cache/
关键点在于每次的挪动，删除，增加的操作要记得同时更新哈希表和链表
LRU:

1. key-value的保存，O(1) search, then HashMap - > key-ListNode(value)
2. Double LinkedList, first in will be put in the front
   1. add a node at the end ( the latest used one and new coming)
   2. delete a node from the front ( full capacity)
   3. move a random node at the end ( refresh a node)

What do we need?

1. class LinkedList - > key, value, next, prev
2. a HashMap -> key - ListNode(key,value)
3. def get - > if not in HashMap, return -1, if in HashMap, (1) refresh the corresponding key’s value in the HashMap (2) move the key to the tail of LinkedList, at the end return the value
4. def put ->
   if in HashMap -> move it to the tail of LinkedList,
   if not in HashMap -> if capacity full, remove head.next from HashMap and remove head.next from LinkedList, then add the new one to HashMap, add the new one to the tail of LinkedList ```python class ListNode: def init(self,key=None, val=None):

    self.key=key
    self.val=val
    self.next = None
    self.prev = None

class LRUCache:

def __init__(self, capacity: int):
    self.HashMap = {}
    self.capacity = capacity
    self.head = ListNode()
    self.tail = ListNode()
    self.head.next, self.tail.prev = self.tail, self.head
def move_to_tail(self, key):
    # 从自己所在位置拿出来
    node = self.HashMap[key]
    node.prev.next = node.next
    node.next.prev = node.prev
    # 放到tail之前
    self.add_to_tail(node)
def remove_from_head(self):
    # delete from HashMap
    # 链表里存了key就为了这个时候反向定位，从hashmap弹出
    self.HashMap.pop(self.head.next.key)
    # delete from the LinkList
    self.head.next = self.head.next.next
    self.head.next.prev = self.head
def add_to_tail(self, node):
    # node 的前后
    node.prev = self.tail.prev
    node.next = self.tail
    # assign node to its prev's next and next's prev
    self.tail.prev.next = node
    self.tail.prev = node
def get(self, key: int) -> int:
    if key not in self.HashMap:
        return -1
    else:
        self.move_to_tail(key)
        return self.HashMap[key].val
def put(self, key: int, value: int) -> None:
    if key in self.HashMap:
        self.HashMap[key].val = value # update HashMap
        self.move_to_tail(key)  # update the LinkedList
    else:
        if len(self.HashMap)==self.capacity:  # check capacity
            self.remove_from_head()
        newNode = ListNode(key,value)
        self.HashMap[key]=newNode
        self.add_to_tail(newNode)

<a name="5CKDu"></a>
#### [716. 最大栈](https://leetcode-cn.com/problems/max-stack/)
[https://leetcode-cn.com/problems/max-stack/](https://leetcode-cn.com/problems/max-stack/)<br />两个栈解决，time complexity O(n)<br />每次两个栈都压入，区别是max_stack是用来存放当前stack里最大value的，如果push的value大于max_stack[-1]，那么压入value， 如果小于，那么把max_stack[-1]再压入一次
```python
class MaxStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.max_stack = []
    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.max_stack:
            self.max_stack.append(x)
        else:
            self.max_stack.append(max(self.max_stack[-1],x))
    def pop(self) -> int:
        if self.stack:
            self.max_stack.pop()
            return self.stack.pop()
        else:
            return -1
    def top(self) -> int:
        return self.stack[-1]
    def peekMax(self) -> int:
        return self.max_stack[-1]
    def popMax(self) -> int:
        tmp = []
        while self.stack and self.stack[-1]!=self.max_stack[-1]:
            tmp.append(self.stack.pop())
            self.max_stack.pop()
        res = self.stack.pop()
        self.max_stack.pop()
        while tmp:
            self.push(tmp.pop())
        return res

难点在于popMax(), O(logN)需要用到二叉搜索树+双向链表

实现哈希表
https://leetcode-cn.com/problems/design-hashmap/

class LinkedNode:
    def __init__(self, key=0,val=0, next=None):
        self.key = key
        self.val = val
        self.next = next
class HashMap:
    def __init__(self):
        self.capacity = 1<<3
        self.loader_factor = 0.75
        self.arr = [None]*self.capacity
        self.count = 0
    def reset(self):
        self.capacity = self.capacity << 1
        self.tmp_arr = self.arr[:]
        self.arr = [None]*self.capacity
        for node in self.tmp_arr:
            while node:
                self.put(node.key, node.value)
                node = node.next
    def get(self,key):
        hash_key = self.get_hash_key(key)
        if self.arr[hash_key]:
            head = self.arr[hash_key]
            while head:
                if head.key == key:
                    return head.val
                head = head.next
            # if not find
        return
    def get_hash_key(self, key):
        return key & (self.capacity -1)
    def put(self,key,value):
        if self.count > self.capacity*self.loader_factor:
            self.reset()
        hash_key = self.get_hash_key(key)
        if not self.arr[hash_key]:
            self.arr[hash_key] = LinkedNode(key=key,val=value)
            self.count+=1
        else:
            head = self.arr[hash_key]
            while head:
                if head.key == key:
                    head.val = value
                    break
                if not head.next:
                    head.next = LinkedNode(key=key,val=value)
                    self.count+=1
                head = head.next

Stack

面试题 03.02. 栈的最小值

https://leetcode-cn.com/problems/min-stack-lcci/
维护一个最小值stack，每个元素对应当前位置下往前所有元素的最小值

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.sorted_stack = []
        self.min_value = float('inf')
    def push(self, x: int) -> None:
        self.stack.append(x)
        if x < self.min_value:
            self.sorted_stack.append(x)
            self.min_value=x
        else:
            self.sorted_stack.append(self.min_value)
    def pop(self) -> None:
        if not self.stack:
            return None
        res = self.stack.pop()
        self.sorted_stack.pop()
        if res == self.min_value:
            self.min_value = float('inf') if not self.sorted_stack else self.sorted_stack[-1]
        return res
    def top(self) -> int:
        if self.stack:
            return self.stack[-1]
        else:
            return None
    def getMin(self) -> int:
        if self.sorted_stack:
            return self.sorted_stack[-1]
        else:
            return None

剑指 Offer 59 - II. 队列的最大值

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

from queue import Queue,deque
class MaxQueue:
    def __init__(self):
        self.queue = Queue()
        self.deque = deque()
    def max_value(self) -> int:
        if self.deque:
            return self.deque[0]
        else:
            return -1
    def push_back(self, value: int) -> None:
        while self.deque and self.deque[-1]<value:
            self.deque.pop()
        self.deque.append(value)
        self.queue.put(value)
    def pop_front(self) -> int:
        if not self.deque:
            return -1
        res = self.queue.get()
        if res == self.deque[0]:
            self.deque.popleft()
        return res

剑指 Offer 31. 栈的压入、弹出序列

https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
场景还原:
新建一个临时stack，按照压栈顺序压入,每次压入后判断临时stack的最后一位和出栈序列的第一位是否相等，相等的话说明该弹出了，就持续弹出符合条件的元素，等循环结束后，如果临时stack和弹出序列都是空，那么就说明符合

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        if not pushed and not popped:
            return True
        stack = list()
        while pushed:
            num = pushed.pop(0)
            stack.append(num)
            while stack and popped:
                if stack[-1] == popped[0]:
                    popped.pop(0)
                    stack.pop()
                else:
                    break
        return not popped and not stack

331. 验证二叉树的前序序列化

https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
栈的消消乐

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        stack = []
        for node in preorder.split(","):
            stack.append(node)
            while len(stack) > 2 and stack[-1]=='#' and stack[-2]=='#' and stack[-3].isdigit():
                for i in range(3):
                    stack.pop()
                stack.append('#')
        return True if stack ==['#'] else False

入度和出度

UnionFind

放两个模板
模版一：
初始化状态下，每个节点都不在子集合里，根节点的parent是None

class UnionFind:
    def __init__(self):
        """
        记录每个节点的父节点
        """
        self.father = {}
    def find(self,x):
        """
        查找根节点
        路径压缩
        """
        root = x
        while self.father[root] != None:
            root = self.father[root]
        # 路径压缩
        while x != root:
            original_father = self.father[x]
            self.father[x] = root
            x = original_father
        return root
    def merge(self,x,y,val):
        """
        合并两个节点
        """
        root_x,root_y = self.find(x),self.find(y)
        if root_x != root_y:
            self.father[root_x] = root_y
    def is_connected(self,x,y):
        """
        判断两节点是否相连
        """
        return self.find(x) == self.find(y)
    def add(self,x):
        """
        添加新节点
        """
        if x not in self.father:
            self.father[x] = None

模板二：
初始状态下所有节点的parent是他自己，所有没有了add函数，而且在find root函数里判断条件不是parent为None,而是parent为自身

1202. 交换字符串中的元素

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        root = x
        while self.parent[root]!=root:
            root = self.parent[root]
        while x!=root:
            self.parent[x],x, = root ,self.parent[x]
        return root
    def union(self,x,y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x!=root_y:
            self.parent[root_x]=root_y
from collections import defaultdict
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        uf = UnionFind(len(s))
        for i,j in pairs:
            uf.union(i,j)
        children = defaultdict(lambda: set())
        for i,j in pairs:
            root = children[uf.find(i)]
            root.add(i)
            root.add(j)
        arr = list(s)
        for v in children.values():
            for i,j in zip(sorted(v),sorted([arr[i] for i in v])):
                arr[i]=j
        return "".join(arr)

200. 岛屿数量

https://leetcode-cn.com/problems/number-of-islands/
岛屿的数量还是用DFS写起来好理解一些

1319. 连通网络的操作次数

https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/

1. n台计算机至少需要n-1条线才能全部联通
2. 用并查集计算有多少个cluster，那么至少需要cluster-1条多余的连接线才可以做到全连通

3. 如何计算多余的线？ 其实并不需要计算，因为如果两个cluster之间没有足够的线把他们链接起来，那么就已经不满足第一个条件了

   class UnionFind:
    def __init__(self, n):
        self.family = [i for i in range(n)]
        self.redundant = 0
    def find(self,x):
        root = x
        while self.family[root]!=root:
            root = self.family[root]
        while root!=x:
            self.family[x], x = root, self.family[x]
        return root
    def union(self,x,y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x!=root_y:
            self.family[root_x] = root_y
    def is_connected(self,x,y):
        return self.find(x) == self.find(y)
   class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n-1:
            return -1
        uf = UnionFind(n)
        for a,b in connections:
            if uf.is_connected(a,b):
                uf.redundant+=1
            uf.union(a, b)
        clusters = 0
        for i in range(n):
            if uf.family[i]==i:
                clusters+=1
        if uf.redundant < clusters-1:
            return -1
        else:
            return clusters-1

   LinkedList

   24. 两两交换链表中的节点

   https://leetcode-cn.com/problems/swap-nodes-in-pairs/
   链表操作时尽量使用dummy节点
   注意post节点更新的时机

   class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        while head and head.next:
            post = head.next
            # swap
            head.next = post.next
            post.next = head
            pre.next = post
            # update pointer
            pre = head
            head = head.next
        return dummy.next

   206. 反转链表

   https://leetcode-cn.com/problems/reverse-linked-list/
   迭代

   class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = None
        while head:
            tmp = head.next
            head.next = cur
            cur = head
            head = tmp
        return cur

   递归
   

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

   92. 反转链表 II

   https://leetcode-cn.com/problems/reverse-linked-list-ii/
   第一个版本写的比较丑，一个指针指向m的pre，一个指针指向n，一直把pre_m.next移动到n的后面就可以了
   这种情况需要特殊考虑当m是1的时候，也就是要从第头指针开始反转的情况
   第二种： 其实没有必要找到n点，只需要每次把m.next挪到m之前, pre_m之后即可

   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        i = 0
        while i < m-1:
            pre = pre.next
            i += 1
        pre_m = pre
        while i < n:
            pre = pre.next
            i += 1
        node_n = pre
        i = 0
        while i < n - m :
            # 从前面拿出来
            node = pre_m.next
            pre_m.next = pre_m.next.next
            # 放到后面去
            tmp = node_n.next
            node_n.next = node
            node.next = tmp
            i += 1
        return dummy.next

   只需要找到反转的起始位置, 使用头插法
   用一个守卫节点指向反转起始位置,设为g
   起始位置为p, 每次将p.next放到g.next. 循环m-n次

   class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if left == right:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        i = 0
        while i < left-1:
            pre = pre.next
            i += 1
        g = pre
        p = g.next
        for i in range(right-left):
            tmp = p.next
            p.next = tmp.next
            tmp.next = g.next
            g.next = tmp
        return dummy.next

   445. 两数相加 II

   https://leetcode-cn.com/problems/add-two-numbers-ii/

   class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack_l1 = []
        stack_l2 = []
        while l1:
            stack_l1.append(l1.val)
            l1 = l1.next
        while l2:
            stack_l2.append(l2.val)
            l2 = l2.next
        carry = 0
        while stack_l2 or stack_l1 or carry:
            a = stack_l2.pop() if stack_l2 else 0
            b = stack_l1.pop() if stack_l1 else 0
            summary = a+b+carry
            node = ListNode(summary%10)
            carry = summary//10
            node.next = head
            head = node
        return head

   21. 合并两个有序链表

   https://leetcode-cn.com/problems/merge-two-sorted-lists/
   迭代

   class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        res = dummy
        while l1 and l2:
            if l2.val<l1.val:
                res.next = l2
                l2 = l2.next
            else:
                res.next = l1
                l1 = l1.next
            res = res.next
        res.next = l1 if l1 else l2
        return dummy.next

   递归

   class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:return l2
        if not l2:return l1
        if l1.val<l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

   23. 合并K个升序链表

   https://leetcode-cn.com/problems/merge-k-sorted-lists/
   21的升级版

4. 循环遍历k个链表， python会TLE

   class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return
        dummy = ListNode(0)
        res = dummy
        size = len(lists)
        while True:
            minNode = None
            minPointer = -1
            for i in range(len(lists)):
                if not lists[i]:
                    continue
                if not minNode or lists[i].val < minNode.val:
                    minNode = lists[i]
                    minPointer = i
            if minPointer==-1:
                break
            res.next = minNode
            res = res.next
            lists[minPointer] = lists[minPointer].next
        return dummy.next

   分治， 归并排序应用于链表

   class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return
        def mergeTwoLists(l1,l2):
            dummy = ListNode(-1)
            res = dummy
            while l1 and l2:
                if l2.val<l1.val:
                    res.next = l2
                    l2 = l2.next
                else:
                    res.next = l1
                    l1 = l1.next
                res = res.next
            res.next = l1 if l1 else l2
            return dummy.next
        def merge(lists, lo, hi):
            if lo==hi:
                return lists[lo]
            mid = lo + (hi-lo)//2
            l1 = merge(lists, lo, mid)
            l2 = merge(lists, mid+1, hi)
            return mergeTwoLists(l1,l2)
        return merge(lists, 0 , len(lists)-1)

   拍案叫绝，给ListNode class增加lt方法， 就可以用来比较大小

   class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def __lt__(self, other):
            return self.val < other.val
        ListNode.__lt__ = __lt__
        import heapq
        heap = []
        dummy = ListNode(-1)
        p = dummy
        for l in lists:
            if l:
                heapq.heappush(heap, l)
        while heap:
            node = heapq.heappop(heap)
            p.next = ListNode(node.val)
            p = p.next
            if node.next:
                heapq.heappush(heap, node.next)
        return dummy.next

   25. K 个一组翻转链表

   https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
   一旦看到翻转顺序， 请第一时间先想到stack！

   160. 相交链表

   https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
   我一开始想到的是用哈希表，两个链表都往哈希表里存，如果一个链表存的时候发现已经存在了，那么肯定是另外一个链表存进去的，此时返回这个节点
   但是这样空间复杂度太高， 这道题可以用空间复杂度为0(1)的解法， 也就是长短链表拼接，假设两个链表相交，那么相交的部分长度是相等的，我们分为一个长链表一个短链表， 两个链表从表头开始循环，如果长的走完了，那么就走短的，如果短的走完了，那么就走长的； 如果有交点，那么他们会同时抵达交点，此刻走过的路程都是等于 长+短+相交， 顺序是 长+相交+短 和 短+相交+长。
   这里最巧妙的地方在于边界条件的处理，要把最后一个节点之后的None也加到循环中来， 这样如果两个链表不相交，那么最终会在等于None的地方相交（满足退出条件）

   class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        ha, hb = headA, headB
        while ha!=hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

   138. 复制带随机指针的链表

   https://leetcode-cn.com/problems/copy-list-with-random-pointer/ ```python “””

   Definition for a Node.

   class Node: def init(self, x: int, next: ‘Node’ = None, random: ‘Node’ = None):

    self.val = int(x)
    self.next = next
    self.random = random

   “””

class Solution: def copyRandomList(self, head: ‘Node’) -> ‘Node’: lookup = {} if not head: return None p = head while p: lookup[p] = Node(p.val) p = p.next p = head while p: lookup[p].next = lookup[p.next] if p.next else None p = p.next p = head while p: lookup[p].random = lookup[p.random] if p.random else None p = p.next return lookup[head]

<a name="1lT4Q"></a>
#### [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
[https://leetcode-cn.com/problems/palindrome-linked-list/](https://leetcode-cn.com/problems/palindrome-linked-list/)<br />简单的题不简单的做,  涉及快慢指针, 链表反转<br />用快慢指针找到链表的中间位置 ( 注意链表长度的奇偶分别判断)<br />反转链表后半部分<br />此时两个指针分别指向链表的开头 和 链表中间(后半部分已经翻转)<br />逐个对比, 判断回文
```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        fast,slow = head,head
        # fast pointer is twice faster than slow pointer
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # if fast pointer is not None, it means the length of linkedlist is odd
        if fast:
            slow = slow.next
        # reverse the linkedlist leading by slow pointer
        pre = ListNode(-1)
        pre.next = slow
        while slow.next:
            post = slow.next
            slow.next = post.next
            post.next = pre.next
            pre.next = post
        slow = pre.next
        # compare from head
        while head and slow:
            if head.val!=slow.val:
                return False
            head = head.next
            slow = slow.next
        return True

DFS&BFS

200. 岛屿数量

https://leetcode-cn.com/problems/number-of-islands/
This question can be solved by DFS, BFS, Union-Find, I only practiced DFS and Union-Find
这道题也可以不用visited函数，在原来grid上修改，但是如果面试中，需要询问是否可以修改原数组

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        if rows==0:
            return 0
        cols = len(grid[0])
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
        count = 0
        def isArea(x,y):
            return x>=0 and y>=0 and x<=rows-1 and y<=cols-1
        def dfs(i,j):
            visited[i][j] = True
            for k in range(4):
                x = i + DIRECTION[k][0]
                y = j + DIRECTION[k][1]
                if isArea(x,y) and not visited[x][y] and grid[x][y]=='1':
                    dfs(x,y)
        for i in range(rows):
            for j in range(cols):
                if not visited[i][j] and grid[i][j]=='1':
                    dfs(i,j)
                    count+=1
        return count

BFS
主函数差不多，遍历函数用一个队列来维护了和当前岛屿连接的岛屿，注意DFS只需要向下或者向右，BFS需要把上下左右都加进来查看

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows =len(grid)
        cols =len(grid[0])
        DIRECTION = ((1,0),(0,1),(-1,0),(0,-1))
        count=0
        def inArea(x,y):
            return x>=0 and y>=0 and x<rows and y<cols
        def bfs(x,y):
            queue = deque()
            queue.append([x,y])
            while queue:
                i,j = queue.popleft()
                if inArea(i,j) and grid[i][j]=='1':
                    grid[i][j]='0'
                    for k in range(4):
                        queue.append([i+DIRECTION[k][0],j+DIRECTION[k][1]])
        for i in range(rows):
            for j in range(cols):
                if grid[i][j]=='1':
                    bfs(i,j)
                    count+=1
        return count

22. 括号生成

https://leetcode-cn.com/problems/generate-parentheses/
left和right从n开始递减，表示还剩多少个括号留下没用

    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        cur_str = ''
        def dfs(cur_str, left, right):
            '''
            params:
                cur_str,  the string from root to leaf
                left,  how many left ( left
                right, how many right ) left
            '''
            if left==0 and right==0:
                res.append(cur_str)
                return
            if right<left:
                return
            if left > 0:
                dfs(cur_str+'(', left-1,right)
            if right >0:
                dfs(cur_str+')', left, right-1)
        dfs(cur_str, n,n)
        return res

left和right从0开始，逐渐增加，注意判断条件变成了right要严格小于left，如果大于了就要return

    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        cur_str = ''
        def dfs(cur_str, left, right):
            '''
            params:
                cur_str,  the string from root to leaf
                left,  how many left ( left
                right, how many right ) left
            '''
            if left==n and right==n:
                res.append(cur_str)
                return
            if right>left:
                return
            if left < n:
                dfs(cur_str+'(', left+1,right)
            if right < n:
                dfs(cur_str+')', left, right+1)
        dfs(cur_str, 0,0)
        return res

剑指 Offer 12. 矩阵中的路径

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

329. 矩阵中的最长递增路径

https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
拓扑排序， 课程表是为了找环，如果有环，说明无法学完全部课程，因为有的课程互为先决条件，导致有环出现。
这道题以数字大小来作为出度入度，是肯定没有环的，要计算的最长路径，那么就是每次把入度为0的作为一层，将这一层点挪去之后，还剩下的入度为0的点就是下一次，加入队列进入下一次循环， 经过多少次循环后再也没有入度为0的点就得到了最长递增路径

from collections import deque
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
        # indegrees每个坐标上的值，是matrix对应坐标位置的入度
        indegrees = [[0 for _ in range(cols)] for _ in range(rows)]
        def inArea(x,y):
            return x>=0 and y>=0 and x<rows and y<cols
        # calculate the indegrees
        for i in range(rows):
            for j in range(cols):
                for k in range(4):
                    new_x = i + DIRECTION[k][0]
                    new_y = j + DIRECTION[k][1]
                    if inArea(new_x, new_y) and matrix[i][j] > matrix[new_x][new_y]:
                        indegrees[i][j]+=1
        queue = deque()
        # 入度为0的坐标进入队列
        for i in range(rows):
            for j in range(cols):
                if indegrees[i][j] == 0:
                    queue.append((i,j))
        res = 0
        while queue:
            # 每一层遍历 res+1
            res += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for k in range(4):
                    new_x = x + DIRECTION[k][0]
                    new_y = y + DIRECTION[k][1]
                    if inArea(new_x,new_y) and matrix[x][y] < matrix[new_x][new_y]:
                        indegrees[new_x][new_y] -= 1
                        if indegrees[new_x][new_y] == 0:
                            queue.append((new_x,new_y))
        return res

从最小的数字开始，遍历每个点附近的四个点， 取这四个点里（1.没有出界，2.值比当前点小）的当前路径最长的，然后这个点的路径就是那个附近最长路径+1， 如果附近四个点都比当前点大，那么这个点就是一个起始点，最长路径为1

from collections import deque
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
        dp = [[0]*cols for _ in range(rows)]
        def inArea(x,y):
            return x>=0 and y>=0 and x<rows and y<cols
        points = sorted([[matrix[i][j], (i,j)] for i in range(rows) for j in range(cols)])
        res = 0
        for point in points:
            value = point[0]
            x, y = point[1]
            max_path = 0
            for k in range(4):
                new_x = x + DIRECTION[k][0]
                new_y = y + DIRECTION[k][1]
                if inArea(new_x, new_y) and matrix[new_x][new_y] < value:
                    max_path = max(max_path, dp[new_x][new_y])
            dp[x][y] = max_path+1
            res = max(res, dp[x][y])
        return res