算法编程技巧

一.双指针（常见于对数组和链表的操作）

1.快慢指针(常用于解决链表问题）
[1] 判定链表中是否有环

• 思路：快指针每次走两步，慢指针每次走一步，如果快慢指针相遇，则表示有环

[2]寻找链表的中点

• 思路：快指针每次走两步，慢指针每次走一步，当快指针走到尽头的时候，慢指针指向的就是中间位置

[3]寻找链表的倒数第K个元素

• 思路：快指针先走K步，然后快慢指针一起走，当快指针到尽头的时候，慢指针指向的就是倒数第K个元素

[4] 移动零

• 思路：快慢指针，循环遍历，当快指针遇到非零元素，则将值赋值给慢指针，然后快指针赋值为0，慢指针加1

[5]删除排序数组重复元素

• 思路：快慢指针，循环遍历，当快指针和慢指针指向的元素不同的时候，将快指针指向的值赋值给慢指针，慢指针加1

2.左右指针（常见于二分查找，反转数组）
[1] 二分查找

• 思路：左右指针，while循环，不断更新左右指针的值

[2]两数之和

• 思路：先进行升序排列，while循环，左右指针求和，直到找到目标值
• 备注：三数之和也可以按类似的方法进行求解，遍历其中一个，另外两个从左右指针开始

[3]反转数组

• 思路：左右指针进行元素对换，更新左右指针

[4]盛最多水的容器

• 思路：左右指针 循环遍历，判断左右位置的高度，从而计算面积

[5]合并两个有序链表
*思路：初始化三个指针，分别是两个链表的头节点，新的头节点，最后将剩下的链表直接加到后面

[6]合并两个有序数组
*思路：从后往前进行比较，初始化三个指针，从后往前进行赋值，最后将剩下不为空的数组元素直接加到后面

二.滑动窗口(子串问题）

1.算法思路
[1]初始化双指针为0
[2]不断增加右指针扩大窗口，直到窗口里面的字符串符合要求
[3]停止增加右指针，不断增加左指针缩小窗口，直到窗口中的字符串不再符合要求
[4]重复步骤2，3直到右指针到达字符串的末尾

2.常见问题
[1]最小覆盖子串：找出一个字符串里面包含另一个字符串所有字符的最小子串

• 思路：代码同上，右指针移动找到满足条件的，左指针收缩，不断缩小找到最优解，判断是否收缩的条件为vaild是否等于需要的字符个数

[2]字符串排列：判断一个字符串是否包含宁一个字符串的排列

• 思路：同上，窗口左侧开始收缩的条件改为rigth-left >=len(t) 因为排列的长度肯定和字符串本身一样，如果vaild==len(need)，则直接返回true

[3]找到字符串中所有字母异位词：在一个字符串S中找出所有是t的字母异位词的子串(字母相同，但是排列不同的字符串）
*思路：同上，滑动窗口解决，将所有满足条件的子串的起始位置加入结果列表即可

[4]最长无重复子串：找出一个字符串中不含有重复字符的最长子串的长度
*思路：一个字符串，不需要使用need，只需要构建窗口window，收缩的条件为窗口内某个字符出现的次数大于1，然后更新子串的长度

三.栈和队列

1.栈：先进后出
[1]有效的括号
*思路：构建右括号和左括号组成的键值对字典，遍历字符串里面每个括号，
如果是右括号，则和栈顶元素进行匹配，如果匹配不成功直接返回False，匹配成功则弹出栈顶元素
否则如果是左括号则直接入栈

[2]柱状图中最大的矩形面积
*思路：找到每个柱子的左右边界(第一个小于他的高度的柱子），维护一个单调递增的栈，栈底元素为-1，新加入的元素大于栈顶元素则直接入栈，小于则表示找到了右边界，开始计算栈顶元素的面积

def largestRectangleArea(heights):
    #解法二：使用递增的栈来获取每个元素的左右边界
    heights = [0] + heights + [0]
    res = 0
    stack = []
    for i in range(len(heights)):
        #栈里面存放的是每个元素的索引 新加入的元素小于栈顶元素，开始计算栈顶元素所能构成的矩形的最大面积
        while stack and heights[stack[-1]] > heights[i]:
            #记录栈顶元素的索引
            tmp = stack.pop()
            #根据左右边界计算对应的面积
            res = max(res,(i-stack[-1]-1)*tmp)
        #如果大于栈顶元素则直接入栈
        stack.append(i)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[3]接雨水
*思路：找到每个位置的左右边界

2.队列：先进先出
[1]滑动窗口的最大值
*思路：单调递减队列实现，将元素的下标加入队列，新加入的元素比队尾元素大，则删除队尾元素，将该元素往前移动，否则直接加入队尾，这样保证了最大的元素始终是在队头

import collections
#11.滑动窗口最大值
def maxSlidingWindow(nums,k):
    #采用双端队列
    if len(nums) < 2:
        return nums
    queue = collections.deque()
    res = []
    for i in range(len(nums)):
        #将元素加入双端队列，保证从大到小排序，新加入的如果比队尾元素大，则删除队尾元素，加入新得元素
        while queue and nums[queue[-1]] < nums[i]:
            queue.pop()
        #当队列为空，或加入的元素比队尾元素小，则直接加入队列
        queue.append(i)
        #判断队首是否在窗口内部
        if queue[0] <= i - k:
            queue.popleft()
        #当窗口长度为k时加入队首元素到结果列表
        if i + 1 >= k:
            res.append(nums[queue[0]])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三.哈希表

1.主要是通过哈希映射构建字典
[1]有效的字母异位词（每个字符的个数一样，但是顺序不一样）
*思路：统计其中一个字符串里面每个字符的个数构建hashmap，
遍历另一个字符串，将hashmap里面对应字符的个数减一，最后判断hashmap里面是否所有的值都为0

[2]两数之和
*思路：不需要进行排序，直接通过Hash查找，遍历每个元素的下标和值，将值为键，索引为值加入hashmap，然后判断另一个元素是否在hashmap中，在的话直接返回两个数的索引

四.二叉树

1.树的问题一般都是用递归解决
2.树的遍历：根据根节点的位置不同分为前序，中序，后序遍历

#中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode):
        #解法一：递归解决 时间复杂度为O(n) n为节点个数   空间复杂度为O(h) h为树的深度
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
1
2
3
4
5
6
7

#N叉树的前序遍历
    def preorder(self, root: 'Node'):
        # 解法一：递归 根左右的方式加入结果列表
        if not root:
            return []
        res = [root.val]
        for child in root.children:
            res.extend(child.val)
        return res
1
2
3
4
5
6
7
8
9

3.树的优先搜索算法：BFS和DFS
4.验证二叉搜索树

def isValidBST(self, root: TreeNode) -> bool:
    #递归判断每个节点的值是否在正确的范围内
    def helper(root,left,right):
        if not root:
            return True

        if (root.val > left) and (root.val < right):
            return helper(root.left,left,root.val) and helper(root.right,root.val,right)
        else:
            return False
    return helper(root,-float('inf'),float('inf'))
1
2
3
4
5
6
7
8
9
10
11

5.二叉树的最近公共祖先
6.前序遍历和中序遍历构建二叉树

五.递归

1.递归模板
[1]递归终止条件
[2]处理当前层的逻辑
[3]递归下一层

2.常见题目
[1]树的问题一般都是用递归解决
[2]括号生成
*思路：每个位置可以根据条件选择生成左括号或者右括号

def generateParenthesis(n):
    #递归
    stack = [('',0,0)]  #栈里面的元素分别表示当前的括号字符串，左括号的个数，右括号的个数
    res = []
    while stack:
        p,left,right = stack.pop()
        #终止条件
        if left == right == n:
            res.append(p)
            continue
        #每次只将符合条件的括号加入
        if left < n:
            stack.append((p + '(',left+1,right))
        if right < n and right < left:
            stack.append((p + ')',left,right+1))
    #栈为空的时候退出循环得到所有的括号
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

[3]二叉树的最大深度

class Solution:
    #二叉树的最大深度
    def maxDepth(self, root: TreeNode) -> int:
        #解法一：递归，最大深度等于左子树和右子树的最大深度加1
        if not root:
            return 0
        left_height = self.maxDepth(root.left)
        right_height = self.maxDepth(root.right)
        return max(left_height,right_height) + 1
1
2
3
4
5
6
7
8
9

[4]翻转二叉树

 def invertTree(self, root: TreeNode) -> TreeNode:
      if not root:
          return root
      #左子树翻转后的结果
      left = self.invertTree(root.left)
      right = self.invertTree(root.right)
      root.left = right
      root.right = left
      return root
1
2
3
4
5
6
7
8
9

六.分治

1.分治模板
[1]递归终止条件
[2]将问题分解成多个子问题
[3]递归解决子问题
[4]通过子问题的结果生成最终的结果

2.常见题目
[1]求x的n次幂

def myPow(x,n):
   #使用分治求解 自顶向下将大问题逐步分解成小的子问题
   def helper(n):
       #终止条件
       if n == 0:
           return 1
       #当前层的逻辑处理n //2 递归子问题
       y = helper(n // 2)
       #合并结果进行返回
       return y * y if n % 2 == 0 else y * y * x
   return helper(n) if n >= 0 else 1.0 / helper(-n)
1
2
3
4
5
6
7
8
9
10
11

七.回溯

1.思路：类似于多叉树的遍历，只需要在前序遍历和后序遍历的地方做一些操作即可,
三个关键点：结束条件，选择列表，路径
2.回溯模板（和一般的递归模板一样）

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10

3.常见题目
[1]全排列

def permutation(nums):
    res = []
    def helper(nums,track):
        #递归结束条件 当路径上原始的个数等于原始数组元素个数
        if len(nums) == len(track):
            res.append(track)
            return

        #遍历选择列表
        for i in range(len(nums)):
            #排除不合法的选择
            if nums[i] in track:
                continue
            #做出选择
            track.append(nums[i])
            #进入下一层决策树
            helper(nums,track.copy())
            #回到当前层，撤销当前做的选择
            track.pop()
    helper(nums,[])
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

[2] N皇后

def solveNQueens(n):
    cols = []
    pie = []
    na = []
    #递归每一行，记录可以存放的列
    def helper(ans,n,row,tmp):
        #递归终止条件
        if row >= n:
            ans.append(tmp)
            return

        #处理当前层的逻辑，即找出可以放皇后的列，并且将下一层不能放的位置都添加到对应的列表
        for col in range(n):
            if col in cols or row+col in pie or row-col in na:
                continue

            #否则,找到可以放的列
            cols.append(col)
            pie.append(row+col)
            na.append(row-col)

            #递归到下一行
            helper(ans,n,row+1,tmp.copy() + [col])

            #清除当前层的状态
            cols.pop()
            pie.pop()
            na.pop()
    ans = []
    helper(ans,n,0,[])

    result = []
    for item_lst in ans:
        sub_lst = []
        for i in item_lst:
            sub_lst.append('.'*i + 'Q' + '.'*(n-i-1))
        result.append(sub_lst)
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

[3]子集

 递归 类似于括号生成的问题，对于每个数字，每次可以选或不选
    def helper(ans, nums, list, index):
        # 递归终止条件
        if index == len(nums):
            ans.append(list)
            return

        # 处理当前层，选或不选，递归子问题。这里的只有选或不选两种结果，不需要遍历递归
        helper(ans, nums, list.copy(), index + 1)  # 不添加元素到list
        list.append(nums[index])  # 添加元素到List
        helper(ans, nums, list.copy(), index + 1)

        # 每个子问题处理之后需要将list面元素去掉
        list.pop()
    ans = []
    helper(ans, nums, [], 0)
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

[4]电话号码的字母组合

 def letterCombinations(digits):
     phoneMap = {
         "2": "abc",
         "3": "def",
         "4": "ghi",
         "5": "jkl",
         "6": "mno",
         "7": "pqrs",
         "8": "tuv",
         "9": "wxyz",
     }
     #创建递归函数
     def helper(i,digits,ans,tmp):
         """
         :param i: 表示第几个数字
         :param digits: 原始输入数字字符串
         :param ans: 结果列表
         :param tmp: 可能的字符列表
         :return:
         """
         #递归终止条件
         if i == len(digits):
             ans.append(''.join(tmp))
             return

         #处理当前层的逻辑 遍历每次可以选择的选择列表
         for ch in phoneMap[digits[i]]:
             tmp.append(ch)
             #递归处理子问题
             helper(i + 1,digits,ans,tmp.copy())
             tmp.pop()

     ans = []
     helper(0,digits,ans,[])
     return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

八.贪心

1.概念
是一种在每一步都选择当前最优的，从而希望达到全局最优解，和动态规划的区别是选择后不能回退，动态规划每次会保存之前最优的结果。

2.常见题目
[1]换零钱：可以换的零钱相互之前是倍数关系，可以考虑使用贪心法从最大的开始匹配
[2]分发饼干：饼干满足小孩胃口最多的数量
*思路：两个数组从小到大进行排序，双指针while循环判断当前位置的饼干能否满足当前位置的小孩

def findContentChildren(self, g: List[int], s: List[int]) -> int:
 #思路：将两个数组进行从小到大的排序，用最小的饼干去尽可能的满足他可以满足的小孩胃口
 g.sort()
 s.sort()
 i,j = 0,0
 res = 0
 while i < len(g) and j < len(s):
     #可以满足
     if g[i] <= s[j]:
         res += 1
         i += 1
         j += 1
     else: #不能满足,用下一块饼干
         j += 1
 return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[3]买卖股票的最佳时机，可以多次进行交易，使利益最大化

def maxProfit(self, prices: List[int]) -> int:
   #使用贪心算法，只要后一天的价格比前一天大就卖出
   profit = 0
   for i in range(len(prices)-1):
       if prices[i+1] > prices[i]:
           profit += prices[i+1] - prices[i]
   return profit
1
2
3
4
5
6
7

[4]跳跃问题：数组里面每个元素表示该位置最多可以跳的步数
*思路：从后往前遍历，不断更新可以最后的点的下标，最后判断这个下标是否为零

def canJump(self, nums: List[int]) -> bool:
   #贪心算法，从后往前遍历，找出可以到达的点，看最后是否为起始位置
   if len(nums) < 1:
       return False
   enableIndex = len(nums) - 1
   for i in range(len(nums)-1,-1,-1):
       #如果当前点的索引加上最大可以跳的步数大于当前点，则更新
       if nums[i] + i >= enableIndex:
           enableIndex = i
   return enableIndex == 0
1
2
3
4
5
6
7
8
9
10

九.动态规划

1.和递归分治的区别主要是看有无最优子结构，共性都是找重复子问题
2.步骤
[1]定义状态数组dp，明确里面元素的含义
[2]状态初始值
[3]状态递推关系

3.状态数组常见的初始化方式

dp = [0] * m
dp = [[0] * m for j in range(m+1)]  m行n列
1
2

4.常见题目
[1] 含有障碍物的不同路径的总数

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
  # 定义状态数组，dp[i][j]表示第(i,j)个位置的路径数量
  m = len(obstacleGrid)
  n = len(obstacleGrid[0])
  dp = [[0 for i in range(n)] for j in range(m)]
  # 状态初始化
  if obstacleGrid[0][0] == 1:
      dp[0][0] = 0
  else:
      dp[0][0] = 1
  #只有一列的时候
  for i in range(1,m):
      #当前格子不是障碍物，并且前一个也是有值的
      if (obstacleGrid[i][0] == 0 and dp[i-1][0] == 1):
          dp[i][0] = 1

  #只有一行的时候
  for j in range(n):
      if (obstacleGrid[0][j] == 0 and dp[0][j-1] == 1):
          dp[0][j] = 1

  #状态递推
  for i in range(1,m):
      for j in range(1,n):
          if obstacleGrid[i][j] == 0:
              dp[i][j] = dp[i-1][j] + dp[i][j-1]
          else:
              dp[i][j] = 0
  return dp[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

[2]返回两个字符串的最长公共子序列(不要求连续)

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
   #将两个字符串转换为二维矩阵
   m = len(text1)
   n = len(text2)
   #初始化状态数组 dp[i][j]表示text1 前i个字符和 text2前j个字符的最长公共子序列的长度
   #将行和列都加1，可以直接让下标从1开始
   dp = [[0] * (n + 1) for i in range(m+1)]
   for i in range(1,m+1):
       for j in range(1,n+1):
           if text1[i-1] == text2[j-1]:
               dp[i][j] = dp[i-1][j-1] + 1
           else:
               dp[i][j] = max(dp[i-1][j],dp[i][j-1])
   return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

[3] 三角形最小路径和

def minimumTotal(self, triangle: List[List[int]]) -> int:
     #从倒数第2行开始向上计算每个位置的路径最小值
     #定义状态数组，并初始化
     dp = triangle
     #状态递推 从下往上进行
     for i in range(len(triangle)-2,-1,-1):
         for j in range(len(triangle[i])):
             dp[i][j] += min(dp[i+1][j],dp[i+1][j+1])
     return dp[0][0]
1
2
3
4
5
6
7
8
9

[4]最大子序列和：求连续子数组的最大和

def maxSubArray(self, nums: List[int]) -> int:
     #动态规划 定义状态数组 dp[i]表示以第i个元素结尾的最大子串的和
     m = len(nums)
     dp = [0] * m
     #初始化
     dp[0] = nums[0]
     #递推公式
     for i in range(1,len(nums)):
         #如果以第i-1个元素结尾的最大子串和为正，则当前的为dp[i-1]+nums[i],如果为负数，则直接就是当前元素
         dp[i] = max(dp[i-1],0) + nums[i]
     return max(dp)
1
2
3
4
5
6
7
8
9
10
11

[5]乘积最大的数组

  def maxProduct(self, nums: List[int]) -> int:
      #定义状态数组 需定义两个，分别表示以当前元素结尾的连续子串的最大乘积和最小乘积
      m = len(nums)
      dp_max = [1] * m
      dp_min = [1] * m
      #初始化状态数组
      dp_max[0] = dp_min[0] = nums[0]
      #递推公式
      for i in range(1,m):
          dp_max[i] = max(max(dp_max[i-1] * nums[i],dp_min[i-1] * nums[i]),nums[i])
          dp_min[i] = min(min(dp_max[i-1] * nums[i],dp_min[i-1] * nums[i]),nums[i])
      return max(dp_max)
1
2
3
4
5
6
7
8
9
10
11
12

[6]零钱兑换

def coinChange(self, coins: List[int], amount: int) -> int:
   #定义状态数组dp[i]表示筹够面值i需要的硬币数量
   MAX = float('inf')
   dp = [0] + [MAX]*amount
   
   #递推
   for i in range(1,amount+1):
       #循环遍历每一种可能的硬币面值
       for j in range(len(coins)):
           if coins[j] <= i:
               dp[i] = min(dp[i],dp[i-coins[j]] + 1)
   return -1 if dp[amount] == MAX else dp[amount]
1
2
3
4
5
6
7
8
9
10
11
12

[7]打家劫舍
*思路：新增一个维度表示该房子是否偷，每个房子记录偷与不偷的利润

  def rob(self, nums: List[int]) -> int:
      #动态规划，初始化状态数组，有两个维度 第一个维度表示第几个房子 第二个维度表示偷或不偷
      m = len(nums)
      if m < 1:
          return 0
      dp = [[0]*2 for i in range(m)]

      #状态初始化
      dp[0][0] = 0
      dp[0][1] = nums[0]

      #递推公式也可以不用新增维度 直接根据前一个是否被偷 dp[i] = max(dp[i-1],dp[i-2]+nums[i])
      for i in range(1,m):
          dp[i][0] = max(dp[i-1][0],dp[i-1][1])
          dp[i][1] = dp[i-1][0] + nums[i]

      return max(dp[m-1][0],dp[m-1][1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

[8]股票买卖问题
*状态方程
dp[i][k][0 or 1]
每个状态对应的选择有买入，卖出和持有
dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k-1][1] + prices[i])
解释：第i天不持有股票
[1]前一天就不持有股票，今天什么也没做
[2]前一天持有股票，今天选择卖出

dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])
解释：第i天持有股票
[1]前一天就持有股票，今天什么也没做
[2]前一天不持有股票，今天选择买入

初始化
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

[9]编辑距离

def minDistance(self, word1: str, word2: str) -> int:
   #动态规划 里面每个元素表示第一个单词前i个字符和第2个单词前j个字符的编辑距离
   m = len(word1)
   n = len(word2)
   dp = [[0]*(n+1) for i in range(m+1)]
   #初始化，当其中一个为空的时候
   for i in range(m+1):
       dp[i][0] = i
   for j in range(n + 1):
       dp[0][j] = j
   #递推
   for i in range(1,m+1):
       for j in range(1,n+1):
           if word1[i-1] == word2[j-1]:
               dp[i][j] = dp[i-1][j-1]
           else:
               dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + 1
   return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[10] 最长上升子序列

def lengthOfLIS(self, nums: List[int]) -> int:
   #不要求连续
   dp = [1] * len(nums)

   for i in range(len(nums)):
       for j in range(i):
           if nums[j] < nums[i]:
               dp[i]  = max(dp[i],dp[j] + 1)
   return max(dp)
1
2
3
4
5
6
7
8
9

十.字典树

1.字典树即Trie树，也称字典树。每个节点是一个字符，每条路径是一个单词，常用于统计和排序大量的字符串，所以经常被搜索引擎用于文本词频统计，优点是单词查找次数就是单词的长度，查询效率比哈希表高

2.常见题目
[1]单词搜索

3.代码模板

#Trie树代码模板
class Trie(object):
  def __init__(self):
      self.root = {}
      self.end_of_word = '#'

  #插入单词，构建前缀树
  def insert(self,word):
      node = self.root #是一个字典，键是当前节点，值是下一层所有的子节点列表
      for char in word:
          node = node.setdefault(char,{})
      node[self.end_of_word] = self.end_of_word

  #搜索某给单词
  def search(self,word):
      node = self.root
      for char in word:
          if char not in node:
              return False
          #得到搜索的最后的单词字符
          node = node[char]
      return self.end_of_word in node

  #判断字典树里面是否存在某个前缀字符串
  def satrtsWith(self,prefix):
      node = self.root
      for char in prefix:
          if char not in node:
              return False
          node = node[char]
      return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

十一.并查集

1.解决组团和配对问题（判断两个人是否是朋友）

2.常见的操作
[1]makeSet(s)：建立一个新的并查集，其中包含s个单元素集合
[2]unionSet(x,y)：将元素x和元素y所在得集合合并，要求x和y所在的集合不相交
[3]find(x)：找到元素x所在的集合，也可以判断两个元素是否位于同一集合

3.常见题目
[1]朋友圈
[2]岛屿数量
[3]被围绕的区域

4.代码模板

class unionFind(object):
  def __init__(self,n):
      #创建一个并查集 p[i] = i
      self.p = [i for i in range(n)]

  #查找并查集上i的领头节点
  def parent(self,p,i):
      root = i
      while p[root] != root:
          root = p[root]

      while p[i] != i: #路径压缩
          x = i
          i = p[i]
          p[x] = root
      return root

  def union(self,p,i,j):
      p1 = self.parent(p,i) #找到i的领头节点
      p2 = self.parent(p,j) #找到j的领头节点
      p[p1] = p2 #将P1的partent指向p2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

十二.高级搜索

1.在一般搜索的基础上优化的方式主要有不重复，剪枝，和方向
2.AVL
3.红黑树

十三.位运算

1.位运算存在的原因
计算机里面数字的表示和信息的存储都是二进制形式

2.常见的位运算
[1]与 & 有一个为0则为0
[2]或 | 有一个为1则为1
[3]按位取反 ~ 0变成1，1变成0
[4]异或 ^ 相同取0，不同取1

3.异或常见的操作
[1]任何数与0的异或还是为原值
[2]任何数与本身的异或为0
[3]任何数与1的异或为原值取反
[4]任何数与其取反的数进行异或为1

4.指定位置的位运算
[1]将x最右边的n位清零 x & (~0 < [2]获取x的第n位值 （x>>n) & 1
[3]获取x第n位的幂值 x & (1<

5.位运算实战要点
[1]判断奇偶（直接通过最后一位与1来判断）
奇数：x&1 == 1
偶数：x&1 == 0
[2]求平均(直接通过右移1位来表示）
mid = (left + right)>>n
[3]将最低位的1变成0
X = X&(X-1)
[4]得到最低位的1
X&-X（-X表示所有位置取反加1）
[5]清零
X&~X

6.实战题目
[1]位1的个数

 def hammingWeight(self, n: int) -> int:
      #解法一：直接使用X&(X-1) 清零最低位的1来进行计数
      count = 0
      while (n > 0):
          count += 1
          n = n & (n - 1)
      return count
1
2
3
4
5
6
7

[2]判断一个数是否是2的幂（表示二进制仅有一个1）

def isPowerOfTwo(self, n: int) -> bool:
    #仅仅只有以恶搞二进制位为1 则用X&(X-1)去掉最低位的1之后该数变为0
    return (n != 0 and n&(n-1) == 0)
1
2
3

[3]颠倒二进制数

def reverseBits(self, n: int) -> int:
    #直接for循环移动 ,每次通过n&1找到最低位
    ans = 0
    for i in range(31,-1,-1):
        ans += (n&1) << i
        n >>= 1
    return ans
1
2
3
4
5
6
7

十一.布隆过滤器和LRU缓存

1.布隆过滤器
[1]一个很长的二进制向量和一系列的随机函数，用于检索一个元素是否在集合中，空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率
[2]到布隆过滤器里面查新元素的索引，如果有一个为0，则这个元素肯定不在里面，但是如果都为1，只能说这个元素可能在里面

2.LRU Cach
[1]一般是用一个哈希表和一个双向链表实现，查询，修改和更新的时间复杂度为O(1)
[2]least recently used 是一种更新的方式 最近被使用过的元素放到上面

十二.排序算法

https://www.cnblogs.com/onepixel/p/7674659.html
1.比较类排序
通过比较来决定元素间的相对次序，因为时间复杂度不能突破O(nlogn)，因此也称非线性时间比较类排序
[1]交换排序
A.冒泡排序（O(n^2))
思路：双层循环，每次相邻的两个元素之间进行比较，将较大的后移

B.快速排序 O(nlogn)
思路：数组取标杆pivot，将小于pivot的放到左边，大于的放到右边，然后依次对左右两边的进行快排，已达到整个序列有序

def quick_sort(nums):
   #递归终止条件
   if len(nums) < 2:
       return nums
   
   #处理当前层
   pivot = nums[0]
   left = [i for i in nums[1:] if i < pivot]
   right = [i for i in nums[1:] if i >= pivot]
   
   #递归处理
   return quick_sort(left) + [pivot] + quick_sort(right)
1
2
3
4
5
6
7
8
9
10
11
12

[2]插入排序
A.简单插入排序 （O(n^2))
思路：for+while双层循环，for遍历每个元素，while用于比较待插入的元素和已经有的元素进行比较，然后将比他大的往后移动，找到合适的位置进行插入

B.希尔排序

[3]选择排序
A.简单选择排序 （O(n^2))
思路：双重循环，依次将前面的数和后面所有的数进行比较，每次将最小的放到前面的位置，实现从小到大的排序

B.堆排序 O(nlogn) 堆插入O(logn) 取最大/最小 O(1)
思路：数组元素依次建立小根堆；然后依次取出堆顶元素，并删除

import heapq
def heap_sort(nums):
    #构建一个小根堆
    heapq.heapify(nums)
    #初始化一个结果列表
    heap = []
    while nums:
        #依次将堆顶的元素加入到列表
        heap.append(heapq.heappop(nums))
    nums[:] = heap
    return nums
1
2
3
4
5
6
7
8
9
10
11

[4]归并排序 O(nlogn)
思路：先将序列分成两个子序列，对两个子序列分别采用归并排序，然后将排好序的子序列进行合并

#递归将序列分成子序列
def merge_sort(nums,left,right):
   if right <= left:
       return
   mid = (left + right) >> 1
   #分别对子序列进行排序
   merge_sort(nums,left,mid)
   merge_sort(nums,mid + 1,right)
   #将左右两边的子序列进行合并
   return merge(nums,left,mid,right)

#将两个有序的子序列进行合并
def merge(nums,left,mid,right):
   i = left
   j = mid + 1
   tmp = []
   while i <= mid and j <= right:
       if nums[i] <= nums[j]:
           tmp.append(nums[i])
           i += 1
       else:
           tmp.append(nums[j])
           j += 1
   #将剩下不为空的数组直接添加到后面
   while i <= mid:
       tmp.append(nums[i])
       i += 1
   while j <= right:
       tmp.append(nums[j])
       j += 1
   nums[left:right+1] = tmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.归并和快排的比较：
[1]归并排序：先排序左右子数组，然后再合并两个有序子数组
[2]快速排序：先根据基准值分出左右子数组，然后对子数组进行排序

3.非比较类排序
不通过比较来决定元素间的相对次序，可以突破比较类排序算法的时间复杂度下限，以线性时间运行（缺点是一般只能用于整型数据的排序），因此也称线性非比较类排序
[1]计数排序
计数排序要求输入的数据必须是有确定范围的整数，将输入的数据值转化为键存储在额外开辟的数组空间中，然后依次把计数大于1的填充回原数组

[2]桶排序
假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序

[3]基数排序
按低位先排序，然后收集，再按高位进行排序，再收集，依次类推，可以都映射到0-9区间范围内

4.实战题
[1]合并区间：合并所有重叠的区间
*思路：先对二维列表按左边界进行排序，然后再判断右边界的值

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
   if len(intervals) == 0:
       return intervals

   #初始化存放结果的数组
   res = []
   intervals.sort(key=lambda x:x[0])
   for inter in intervals:
       #如果新加入的数组的左边界大于最后一个数组的右边界，说明不存在重复，直接添加到数组即可
       if len(res) == 0 or (res[-1][1] < inter[0]):
           res.append(inter)
       else: #有重复的话直接更新最后一个数组的右边界
           res[-1][1] = max(res[-1][1],inter[1])
   return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

[2]逆序对

十.框架思维系列

1.n数之和

• 主要思路：递归+双指针

def nSumTarget(nums,n,start,target):
    res = []
    length = len(nums)
    if length < 2 or n < 2:
        return []
    if n == 2:
        #采用双指针解法
        l,r = start,length-1
        while (l < r):
            sum = nums[l] + nums[r]
            left = nums[l]
            right = nums[r]
            if (sum < target):
                while(l < r and nums[l] == left): #去重
                    l += 1
            elif (sum > target):
                while(l < r and nums[r] == right):
                    r -= 1
            else:
                res.append([left,right])
                #继续查找
                while (l < r and nums[l] == left):  # 去重
                    l += 1
                while (l < r and nums[r] == right):
                    r -= 1
    else:#大于2的情况  3数之和  4数之和 递归计算（n-1）的和
        for i in range(start,length):
            #对第一个元素进行去重
            if i > 0 and nums[i] == nums[i-1]:
                continue
            sub = nSumTarget(nums,n-1,i+1,target-nums[i])
            #当前元素加入到结果列表
            for arr in sub:
                arr.insert(0,nums[i])
                res.append(arr)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2.递归思维：n个一组反转链表

• 思路：先反转以head开头的K个元素，然后将第k+1个元素作为head递归调用反转函数，最后将两个过程的结果连接起来

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def reverse(a,b):
    pre = None
    cur = a
    while (cur != b):
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

#按k个一组进行反转链表
def reverseKGroup(head,k):
    a = b = head
    for i in range(k):
        if b == None:
            return head
        b = b.next
    #反转前k个元素
    newHead = reverse(a,b)
    #递归反转后面的，并且和前面反转的结果进行连接
    a.next = reverseKGroup(b,k)
    return newHead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.滑动窗口问题

• 思路：双指针 注意何时收缩窗口

def minWindow(s,t):
    #初始化两个字典，分别用于存放T里面所有字符和窗口里面所有的字符
    need = {}
    window = {}
    for c in t:
        if c in need.keys():
            need[c] += 1
        else:
            need[c] = 1

    #初始化双指针
    left = right = 0
    #初始化满足条件的最小字符串的长度
    start = 0
    max_len = len(s)
    #初始化窗口里面满足条件的字符个数
    vaild = 0
    #开始进行窗口操作
    while (right < len(s)):
        c = s[right]
        right += 1
        #进行窗口内数据更新
        if (c in need):
            #满足要求的加入窗口
            if c in window.keys():
                window[c] += 1
            else:
                window[c] = 1

            #如果窗口里面某个字符的个数满足需求则vaild需加1
            if window[c] == need[c]:
                vaild += 1

        #判断左侧是否需要收敛 左侧是否需要收缩的条件
        while(vaild == len(need)):
            #更新最小覆盖子串
            if (right - left < max_len):
                start = left
                max_len = right - left
            #将移出的字符
            d = s[left]
            left += 1
            #进行窗口内更新
            if d in need.keys():
                #vaild 需要减1
                if window[d] == need[d]:
                    vaild -= 1
                #该字符需要移出窗口
                window[d] -= 1
    #返回最小覆盖子串
    if len == max_len:
        return ''
    else:
        return s[start:right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54