岛问题

感染过程：遍历矩阵过程中，找到1后，将其相连的1变为2，找到1个岛，依次直至遍历完矩阵，感染几次，则有几个岛。

并查集

支持集合合并非常快速的结构
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

KMP解决的问题

时间复杂度O(N)
字符串s1和s2,s1是否包含s2,如果包含返回s2在s1中开始的位置。

KMP算法

def kmp(str1, str2):
    if not str1 or not str2 or len(str2) < 1 or len(str1) < len(str2):
        return -1
    i1, i2 = 0, 0
    next = next_array(str2)
    # while的时间复杂度是O(n)
    while i1 < len(str1) and i2 < len(str2):
        if str1[i1] == str2[i2]:
            i1 += 1
            i2 += 1
        elif i2 == 0: # next[i2] == -1 # i1和i2位置字符不相等且比较到s2的最开始位置
            i1 += 1
        else:  # i1和i2字符位置不相等
            i2 = next[i2] 
    # i1或者i2越界
    # i2越界，说明找到字符串匹配
    if i2 == len(str2):
        return i1 - i2
    else: # 未找到匹配字符串
        return -1

求next数组

def next_array(li):
    if len(li) == 1:
        return [-1]
    next = [0] * len(li)
    next[0] = -1
    next[1] = 0
    cn = 0
    i = 2  # next数组的位置
    while i < len(next):
        if li[i-1] == li[cn]:
            cn += 1
            next[i] = cn
            i += 1
        elif cn > 0:  
            cn = next[cn]
        else:
            next[i] = 0
            i += 1
    return next

if __name__ == '__main__':
    str2 = 'abbstabbs'  # 8
    print(next_array(str2))
    

Manachar算法

manachar算法主要是处理字符串中关于回文串的问题的

伪代码

滑动窗口

左右指针
双端对列

单调栈结构

找一个数组中，求某个数组其左右两侧离该数最近的最大/最小的数。
以求该数离其最近的最大的数为例：

• 没有重复数值
  栈中数值保证从大到小，依次遍历数组，如果遍历的数字小于栈顶数值，直接入栈，如果大于栈顶数值，弹出栈顶元素，则栈顶数值的右侧离其最近的最大数为当前数值，左侧离其最近的最大数为新的栈顶元素。
• 有重复数值
  重复数值以类似链表的形式存储在栈中，在java中可以用LinkList或者ArrayList存储。

树形dp

二叉树结点间的最大距离

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫做a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树的最大距离

分析：

• 头节点不参与参与情况下
  左子树的最大距离
  右子树的最大距离

  
  
• 头节点参与情况下整棵树的最大距离
  左子树距离头节点最远的节点A和右子树距离头节点最远的节点B，A和B之间的距离,其结果为左树的高度+1+右树的高度

"""
首先定义函数的返回值
左右子树均需要返回树的最大高度和最大距离
max_distance = 0# 树的最大距离
heigh = 0# 树的最大高度
"""
def process(Node root) {
    if not root:
        return 0, 0 # 最大距离和最大高度
    left_max_dis, left_max_height = process(root.left)
    right_max_dis, right_max_height = process(root.right)
    p3 = left_max_height + 1 + right_max_height
    return max(left_max_dis, right_max_dis, p3), max(left_max_height, right_max_height) + 1
        
}

code

派对的最大快乐值

image.png

列出可能性

对于某一个节点X

• X参与
  则其直接下级都不参与，例如X有直接下级有[a,...]
  所以派对最大的快乐值=X快乐值 + X各个直接下级不参与的条件下，以其直接下级为父节点的各个子树的最大快乐值之和
  res = X快乐值+以a为头节点的子树 在a不参与的条件下 的最大快乐值+...
• X不参与
  X有直接下级有[a,...]
  得到的X的快乐值为0，X不参与则其直接下级可能参与，也可能不参与，则派对最大的快乐值=a参与的情况下其子树的最大快乐值与a不参与的情况下其子树的最大快乐值，2者中选出最大的值,...
  res = 0 + max{a参与下子树的最大快乐值，a不参与下子树的最大快乐值} + ...

分析

代码

image.png

递归代码

(x.nexts.isEmpty()==True)节点x的直接下级为空时,说明x是叶子节点，则若x来则快乐值为x.happy,若x不来，则快乐值为0。

image.png

Morris遍历

一种遍历二叉树的方式，并且时间复杂度O(N),空间复杂度O(1).
通过利用原树中大量空闲指针的方式，达到节省空间的目的

Morris遍历细节

假设来到当前节点cur，开始时cur来到头节点位置

1.如果cur没有左孩子，cur向右移动（cur=cur.right）

2.如果cur没有左孩子，找到左子树上最右的节点mostRright:

       a.如果mostRright的右指针指向空，让其指向cur,然后cur向左移动（cur=cur.left）

      b.如果mostRright的右指针指向cur,让其指向null，然后cur向右移动（cur=cur.right）

3.cur为空时停止遍历

java code

python code

def morris(head):
  if not head:
    return
  cur = head
  while cur: # cur为空时停止遍历
    most_right = cur.left
    if most_right:# 当前节点有左子树
      while most_right.right and most_right.right != cur:
      # 找到最子树的最右节点
        most_right = most_right.right
      if most_right.right is None: # 最右节点的右指针为空
        most_right.right = cur # 让最右节点的右指针指向当前节点
        cur = cur.left # 当前节点左移
        continue # 跳出本轮遍历
      else: # 最右节点的右指针指向当前节点cur
        most_right.right = None # 恢复最右节点的右指针指向
    # cur节点没有左子树
    cur = cur.right    

分析：

每个节点如果有左子树都要遍历找左子树的最右节点，是否会增加时间复杂度？No
所有节点遍历左子树右边界的代价

需要遍历的所有节点都是不重复的

先序遍历

• 一个节点只遍历一次，直接打印
• 一个节点遍历2次，第一次打印

def morris_pre(head):
  if not head:
    return
  cur = head
  while cur: # cur为空时停止遍历
    most_right = cur.left
    if most_right:# 当前节点有左子树
      while most_right.right and most_right.right != cur:
      # 找到最子树的最右节点
        most_right = most_right.right
      if most_right.right is None: # 最右节点的右指针为空
        print("=========")
        print(cur.value) # 回来到cur2次，在第一次来到时打印
        most_right.right = cur # 让最右节点的右指针指向当前节点
        cur = cur.left # 当前节点左移
        continue # 跳出本轮遍历
      else: # 最右节点的右指针指向当前节点cur
        most_right.right = None # 恢复最右节点的右指针指向
    else: # cur节点没有左子树
      print("==========")
      print(cur.value)  # 来到cur节点一次，直接打印
   cur = cur.right  

image.png

中序遍历

• 一个节点只遍历一次，直接打印
• 一个节点遍历2次，第二次打印

def morris_in(head):
  if not head:
    return
  cur = head
  while cur: # cur为空时停止遍历
    most_right = cur.left
    if most_right:# 当前节点有左子树
      while most_right.right and most_right.right != cur:
      # 找到最子树的最右节点
        most_right = most_right.right
      if most_right.right is None: # 最右节点的右指针为空
        most_right.right = cur # 让最右节点的右指针指向当前节点
        cur = cur.left # 当前节点左移
        continue # 跳出本轮遍历
      else: # 最右节点的右指针指向当前节点cur
        most_right.right = None # 恢复最右节点的右指针指向
    # cur节点没有左子树
    print("==========")
    print(cur.value)  # 来到cur节点一次，直接打印
    cur = cur.right  

后序遍历

• 一个节点只遍历一次，什么也不做
• 一个节点遍历2次，第二次逆序打印该节点的左树的最右边界

• 最后单独打印整颗树的最右边界（逆序）

  
  
  
  
  
  
  
  

搜索二叉树BST

根据moris遍历得到搜索二叉树BST的最优解
修改moris中序遍历的代码
BST是空树，如果其左子树不为空则左子树上所有节点的值都小于根节点的值。