島問題

感染過程：遍歷矩陣過程中死宣，找到1后，將其相連的1變?yōu)?碴开，找到1個島毅该，依次直至遍歷完矩陣，感染幾次潦牛，則有幾個島眶掌。

并查集

支持集合合并非常快速的結(jié)構(gòu)
在一些有N個元素的集合應(yīng)用問題中巴碗，我們通常是在開始時讓每個元素構(gòu)成一個單元素的集合畏线，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個元素在哪個集合中良价。
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)寝殴，用于處理一些不相交集合（disjoint sets）的合并及查詢問題。常常在使用中以森林來表示明垢。

KMP解決的問題

時間復(fù)雜度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的時間復(fù)雜度是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數(shù)組

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數(shù)組的位置
    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算法主要是處理字符串中關(guān)于回文串的問題的

偽代碼

滑動窗口

左右指針
雙端對列

單調(diào)棧結(jié)構(gòu)

找一個數(shù)組中痊银，求某個數(shù)組其左右兩側(cè)離該數(shù)最近的最大/最小的數(shù)抵蚊。
以求該數(shù)離其最近的最大的數(shù)為例：

• 沒有重復(fù)數(shù)值
  棧中數(shù)值保證從大到小，依次遍歷數(shù)組，如果遍歷的數(shù)字小于棧頂數(shù)值贞绳，直接入棧谷醉，如果大于棧頂數(shù)值，彈出棧頂元素冈闭，則棧頂數(shù)值的右側(cè)離其最近的最大數(shù)為當(dāng)前數(shù)值俱尼，左側(cè)離其最近的最大數(shù)為新的棧頂元素。
• 有重復(fù)數(shù)值
  重復(fù)數(shù)值以類似鏈表的形式存儲在棧中萎攒，在java中可以用LinkList或者ArrayList存儲遇八。

樹形dp

二叉樹結(jié)點間的最大距離

從二叉樹的節(jié)點a出發(fā)，可以向上或者向下走耍休，但沿途的節(jié)點只能經(jīng)過一次刃永，到達節(jié)點b時路徑上的節(jié)點個數(shù)叫做a到b的距離，那么二叉樹任何兩個節(jié)點之間都有距離羊精，求整棵樹的最大距離

分析：

• 頭節(jié)點不參與參與情況下
  左子樹的最大距離
  右子樹的最大距離

  
  
• 頭節(jié)點參與情況下整棵樹的最大距離
  左子樹距離頭節(jié)點最遠的節(jié)點A和右子樹距離頭節(jié)點最遠的節(jié)點B斯够，A和B之間的距離,其結(jié)果為左樹的高度+1+右樹的高度

"""
首先定義函數(shù)的返回值
左右子樹均需要返回樹的最大高度和最大距離
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

列出可能性

對于某一個節(jié)點X

• X參與
  則其直接下級都不參與，例如X有直接下級有[a,...]
  所以派對最大的快樂值=X快樂值 + X各個直接下級不參與的條件下喧锦，以其直接下級為父節(jié)點的各個子樹的最大快樂值之和
  res = X快樂值+以a為頭節(jié)點的子樹 在a不參與的條件下 的最大快樂值+...
• X不參與
  X有直接下級有[a,...]
  得到的X的快樂值為0读规，X不參與則其直接下級可能參與，也可能不參與裸违，則派對最大的快樂值=a參與的情況下其子樹的最大快樂值與a不參與的情況下其子樹的最大快樂值，2者中選出最大的值,...
  res = 0 + max{a參與下子樹的最大快樂值本昏，a不參與下子樹的最大快樂值} + ...

分析

代碼

image.png

遞歸代碼

(x.nexts.isEmpty()==True)節(jié)點x的直接下級為空時,說明x是葉子節(jié)點供汛，則若x來則快樂值為x.happy,若x不來，則快樂值為0涌穆。

image.png

Morris遍歷

一種遍歷二叉樹的方式怔昨，并且時間復(fù)雜度O(N),空間復(fù)雜度O(1).
通過利用原樹中大量空閑指針的方式，達到節(jié)省空間的目的

Morris遍歷細節(jié)

假設(shè)來到當(dāng)前節(jié)點cur宿稀，開始時cur來到頭節(jié)點位置

1.如果cur沒有左孩子趁舀，cur向右移動（cur=cur.right）

2.如果cur沒有左孩子，找到左子樹上最右的節(jié)點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:# 當(dāng)前節(jié)點有左子樹
      while most_right.right and most_right.right != cur:
      # 找到最子樹的最右節(jié)點
        most_right = most_right.right
      if most_right.right is None: # 最右節(jié)點的右指針為空
        most_right.right = cur # 讓最右節(jié)點的右指針指向當(dāng)前節(jié)點
        cur = cur.left # 當(dāng)前節(jié)點左移
        continue # 跳出本輪遍歷
      else: # 最右節(jié)點的右指針指向當(dāng)前節(jié)點cur
        most_right.right = None # 恢復(fù)最右節(jié)點的右指針指向
    # cur節(jié)點沒有左子樹
    cur = cur.right    

分析：

每個節(jié)點如果有左子樹都要遍歷找左子樹的最右節(jié)點，是否會增加時間復(fù)雜度罩锐？No
所有節(jié)點遍歷左子樹右邊界的代價

需要遍歷的所有節(jié)點都是不重復(fù)的

先序遍歷

• 一個節(jié)點只遍歷一次奉狈，直接打印
• 一個節(jié)點遍歷2次，第一次打印

def morris_pre(head):
  if not head:
    return
  cur = head
  while cur: # cur為空時停止遍歷
    most_right = cur.left
    if most_right:# 當(dāng)前節(jié)點有左子樹
      while most_right.right and most_right.right != cur:
      # 找到最子樹的最右節(jié)點
        most_right = most_right.right
      if most_right.right is None: # 最右節(jié)點的右指針為空
        print("=========")
        print(cur.value) # 回來到cur2次涩惑，在第一次來到時打印
        most_right.right = cur # 讓最右節(jié)點的右指針指向當(dāng)前節(jié)點
        cur = cur.left # 當(dāng)前節(jié)點左移
        continue # 跳出本輪遍歷
      else: # 最右節(jié)點的右指針指向當(dāng)前節(jié)點cur
        most_right.right = None # 恢復(fù)最右節(jié)點的右指針指向
    else: # cur節(jié)點沒有左子樹
      print("==========")
      print(cur.value)  # 來到cur節(jié)點一次仁期，直接打印
   cur = cur.right  

image.png

中序遍歷

• 一個節(jié)點只遍歷一次，直接打印
• 一個節(jié)點遍歷2次，第二次打印

def morris_in(head):
  if not head:
    return
  cur = head
  while cur: # cur為空時停止遍歷
    most_right = cur.left
    if most_right:# 當(dāng)前節(jié)點有左子樹
      while most_right.right and most_right.right != cur:
      # 找到最子樹的最右節(jié)點
        most_right = most_right.right
      if most_right.right is None: # 最右節(jié)點的右指針為空
        most_right.right = cur # 讓最右節(jié)點的右指針指向當(dāng)前節(jié)點
        cur = cur.left # 當(dāng)前節(jié)點左移
        continue # 跳出本輪遍歷
      else: # 最右節(jié)點的右指針指向當(dāng)前節(jié)點cur
        most_right.right = None # 恢復(fù)最右節(jié)點的右指針指向
    # cur節(jié)點沒有左子樹
    print("==========")
    print(cur.value)  # 來到cur節(jié)點一次跛蛋，直接打印
    cur = cur.right  

后序遍歷

• 一個節(jié)點只遍歷一次熬的，什么也不做
• 一個節(jié)點遍歷2次，第二次逆序打印該節(jié)點的左樹的最右邊界

• 最后單獨打印整顆樹的最右邊界（逆序）

  
  
  
  
  
  
  
  

搜索二叉樹BST

根據(jù)moris遍歷得到搜索二叉樹BST的最優(yōu)解
修改moris中序遍歷的代碼
BST是空樹赊级，如果其左子樹不為空則左子樹上所有節(jié)點的值都小于根節(jié)點的值押框。