算法笔记

发表于 2026/09/21

作者 Guanlong Ma

176 分钟 阅读

算法笔记

一、数据结构

(零)数字、列表、字符串、集合、字典

数字

  
# ============================================================
# Python 数字常用操作速查
# ============================================================
   
   
# ------------------------------------------------------------
# 1. 取整
# ------------------------------------------------------------
   
round(nums)
# 四舍五入到最接近的整数
# 注意：Python 对正好 x.5 的情况采用“取偶数”
   
round(2.4)       # 2
round(2.6)       # 3
round(2.5)       # 2
round(3.5)       # 4
   
   
int(nums)
# 向 0 取整，也可以理解为“直接去掉小数部分”
int(3.9)         # 3
int(-3.9)        # -3
   
   
# ------------------------------------------------------------
# 2. 进制转换：字符串 -> 整数
# ------------------------------------------------------------
   
int('255')        # 十进制字符串 -> 255
int('FF', 16)     # 十六进制 -> 255
int('ff', 16)     # 十六进制大小写都可以 -> 255
int('1010', 2)    # 二进制 -> 10
int('777', 8)     # 八进制 -> 511
int('001')        # 十进制，前导 0 自动忽略 -> 1
   
   
# ------------------------------------------------------------
# 3. 进制转换：整数 -> 字符串
# ------------------------------------------------------------
   
bin(10)
# -> '0b1010'
# 0b 表示二进制前缀
   
   
oct(8)
# -> '0o10'
# 0o 表示八进制前缀
   
   
hex(255)
# -> '0xff'
# 0x 表示十六进制前缀
   
   
# ---------- 格式化写法 ----------
   
f'{255:b}'        # '11111111'  二进制
f'{255:o}'        # '377'       八进制
f'{255:x}'        # 'ff'        小写十六进制
f'{255:X}'        # 'FF'        大写十六进制
   
# 如果不想要 0b / 0o / 0x 前缀，通常格式化写法更方便：
   
number = 10
   
f'{number:b}'     # '1010'
f'{number:o}'     # '12'
f'{number:x}'     # 'a'
f'{number:X}'     # 'A'
   
   
# ------------------------------------------------------------
# 4. 整除 / 取余 / divmod
# ------------------------------------------------------------
   
# ---------- // 整除 ----------
   
a // b
# // 是向下取整，不是向 0 取整
   
17 // 5           # 3
-17 // 5          # -4
   
# ---------- % 取余 ----------
   
a % b
   
   
# ---------- divmod：同时求商和余数 ----------
   
q, r = divmod(a, b)
   
   
   
# ------------------------------------------------------------
# 5. 用取模 % 实现循环 / 环形
# ------------------------------------------------------------
   
# 核心思想：x % n 的结果一定在：0 ~ n-1，所以特别适合处理循环下标、方向、周期问题。
   
   
# ---------- 例 1：循环取字符 ----------
   
chars[(cnt - 1) % len(chars)]
   
   
# ---------- 例 2：方向循环 ----------
# 假设：
# 0 = 上，1 = 右，2 = 下，3 = 左
direction = (direction + 1) % 4 # 右转
direction = (direction - 1) % 4 # 左转
   
# ---------- 例 3：环形数组下标 ----------
   
next_index = (i + 1) % n
# 到最后一个位置后，下一个自动回到 0
prev_index = (i - 1) % n
# 在 0 的前一个位置自动回到 n-1
   
# ---------- 例 4：周期结束位置 ----------
best_end = (best_start + max_length - 1) % n
   
   
   

列表

  
   
   
# ------------------------------------------------------------
# 总原则：列表是可变类型：append / extend / insert / remove / pop / sort 等，会直接修改原列表。
# ------------------------------------------------------------
   
   
   
# ------------------------------------------------------------
# 1. 查找 / 统计
# ------------------------------------------------------------
   
nums = [10, 20, 30, 20]
   
   
# ---------- index：查找元素第一次出现的位置 ----------
   
nums.index(20)
   
# 注意：列表没有 find() 方法！index() 找不到元素时会报 ValueError， 如果不确定元素是否存在，可以先用 in：
   
if 20 in nums:
    index = nums.index(20)
   
# ---------- count：统计出现次数 ----------
nums.count(20)
   
# ---------- 最大值 / 最小值 ----------
max(nums)
min(nums)
   
# 最大小值所在的位置：注意：如果最大值出现多次，index() 只返回第一次出现的位置。
nums.index(max(nums))
nums.index(min(nums))
   
# ------------------------------------------------------------
# 2. 增加元素
# ------------------------------------------------------------
# ---------- append：末尾追加一个元素 ----------
a.append(4)
   
# ---------- extend：末尾追加多个元素 ----------
a.extend([3, 4])
   
# ---------- insert：指定位置插入 ----------
a.insert(0, 100)  # a.insert(index, element)
   
# ------------------------------------------------------------
# 3. 删除元素
# ------------------------------------------------------------
   
# ---------- remove：按“值”删除 ----------
a.remove(20) # 如果有多个相同元素，只删除第一个。元素不存在时会报 ValueError
   
# ---------- pop：按“索引”删除，并返回被删除元素 ----------
x = a.pop(1) # 不写索引：默认删除最后一个元素
   
# ---------- del：按索引直接删除 ----------
   
del a[1]
del a[1:3]
   
   
# ------------------------------------------------------------
# 4. 列表反转
# ------------------------------------------------------------
   
a.reverse()
b = a[::-1]
   
   

字符串

  
# ============================================================
# Python 字符串常用操作速查
# ============================================================
   
# ------------------------------------------------------------
# 总原则：字符串是不可变类型
# ------------------------------------------------------------
   
# 字符串方法通常不会修改原字符串，而是返回一个新字符串。所以很多操作都要用变量接收返回值。
   
line = "   hello"
line.lstrip()            # 原 line 不会改变
line = line.lstrip()     # 正确
   
   
# ------------------------------------------------------------
# 1. 大小写转换
# ------------------------------------------------------------
   
s = "i Love YOU"
   
s.lower()          # 全部小写 -> 'i love you'
s.upper()          # 全部大写 -> 'I LOVE YOU'
s.swapcase()       # 大小写互换 -> 'I lOVE you'
s.capitalize()     # 整个字符串首字符大写，其余变小写 -> 'I love you'
s.title()          # 每个单词首字母大写 -> 'I Love You'
   
   
# ------------------------------------------------------------
# 2. 查找 / 统计
# ------------------------------------------------------------
   
s = "sdfWFSDss"
   
s.find('s')        # 第一个 's' 的索引；找不到返回 -1
s.rfind('s')       # 最后一个 's' 的索引；找不到返回 -1
s.index('s')       # 和 find 类似，但找不到会报 ValueError
s.count('s')       # 统计 's' 出现次数
   
   
# ------------------------------------------------------------
# 3. 替换
# ------------------------------------------------------------
   
s.replace('s', 'b')          # 将所有 's' 替换为 'b'
s.replace('s', 'b', 1)       # 只替换前 1 个
   
text = "1,2,3"
text = text.replace(',', ' ') # '1 2 3'
   
   
# ------------------------------------------------------------
# 4. 去除首尾空白 / 指定字符
# ------------------------------------------------------------
   
line = "   hello   "
   
line = line.lstrip()     # 去左侧空白
line = line.rstrip()     # 去右侧空白
line = line.strip()      # 去两侧空白
   
"00032".lstrip('0')      # '32'
"-3".lstrip('-')         # '3'
   
# 注意：
# strip / lstrip / rstrip 中传入的是“字符集合”，不是完整前后缀
   
"abcahelloabc".strip('abc')   # 'hello'
   
# strip('abc') 的意思：
# 从两端不断删除 a / b / c 中的字符
   
   
# ------------------------------------------------------------
# 5. 分割 / 拼接
# ------------------------------------------------------------
   
# ---------- split：字符串 -> 列表 ----------
   
input_str = "489607   minute"
   
input_str.split()
# 无参数：
# 按任意空白切分
# 连续空白自动合并
# -> ['489607', 'minute']
   
   
item = "a|b|c|d"
   
item.split('|')
# 指定分隔符
# -> ['a', 'b', 'c', 'd']
   
   
"a||b".split('|')
# -> ['a', '', 'b']
# 指定分隔符时，连续分隔符会产生空字符串
   
   
# ---------- join：列表 -> 字符串 ----------
   
result = ['I', 'love', 'you']
   
' '.join(result)
# -> 'I love you'
   
''.join(result)
# -> 'Iloveyou'
   
   
chars = ['a', 'b', 'c']
   
''.join(chars)
# -> 'abc'
   
   
   
   
# ------------------------------------------------------------
# 6. 前缀 / 后缀判断
# ------------------------------------------------------------
   
line = "hello.py"
   
line.startswith('he')        # True
line.endswith('.py')         # True
   
# 一次判断多个后缀
line.endswith(('.jpg', '.png', '.py'))
   
   
# ------------------------------------------------------------
# 7. 字符类型判断
# ------------------------------------------------------------
   
"123".isdigit()          # 是否全部是数字 -> True
"abc".isalpha()          # 是否全部是字母 -> True
"ABC".isupper()          # 是否全部是大写字母 -> True
"abc".islower()          # 是否全部是小写字母 -> True
"   ".isspace()          # 是否全部为空白字符 -> True
   
"-3".isdigit()           # False
   
   
# 简单判断负整数
   
value = "-123"
   
value.lstrip('-').isdigit()
# True
   
   
# 注意：
"--3".lstrip('-').isdigit()
# True
   
# 因为 lstrip('-') 会删除左侧所有 '-'
# 所以这种方法只是简单判断，并不完全严谨
   
   
# 更严谨：
try:
    int(value)
    is_integer = True
except ValueError:
    is_integer = False
   
   
# ------------------------------------------------------------
# 8. 字符 <-> Unicode 编码
# ------------------------------------------------------------
   
ord('A')             # 字符 -> Unicode 码点，例如 65
chr(65)              # Unicode 码点 -> 字符，例如 'A'
   
ord('中')            # 中文也可以
chr(ord('中'))       # '中'
   
   
# ------------------------------------------------------------
# 9. 补齐 / 对齐
# ------------------------------------------------------------
   
# ---------- zfill：左侧补 0 ----------
   
'1010'.zfill(8)      # '00001010'
'1010'.zfill(4)      # '1010'
'1010'.zfill(2)      # '1010'，不会截断
'5'.zfill(3)         # '005'
   
# zfill 会特殊处理正负号
'-3'.zfill(5)        # '-0003'
   
   
# ---------- rjust：右对齐，左侧填充 ----------
   
'7'.rjust(3, '0')    # '007'
'x'.rjust(3, '-')    # '--x'
   
# rjust 不特殊处理负号
'-3'.rjust(5, '0')   # '000-3'
   
   
# ---------- ljust：左对齐，右侧填充 ----------
   
'7'.ljust(3, '0')    # '700'
   
   
# ---------- center：居中填充 ----------
   
'7'.center(3, '0')   # '070'
'abc'.center(7, '-') # '--abc--'
   
   
   
   

  
f"{变量:[填充][对齐][宽度][.精度][类型]}"
   
# [填充]：任意单字符，如 0、*、-、空格
# [对齐]：< 左对齐，> 右对齐，^ 居中，= 符号后填充
# [宽度]：最小总宽度，如 5、8、10
# [.精度]：主要配合浮点数使用，表示保留几位小数
#          .2f -> 保留 2 位小数
#          .3f -> 保留 3 位小数
#          例如：f"{3.14159:.2f}" -> '3.14'
#
# [类型]：
# d   十进制整数
# b   二进制
# o   八进制
# x   十六进制小写
# X   十六进制大写
# f   普通小数，通常配合 .精度 使用
# e/E 科学计数法
# %   百分比，通常配合 .精度 使用
   
   
# 例：
f"{7:05d}"          # '00007'
f"{10:08b}"         # '00001010'
f"{255:04X}"        # '00FF'
   
f"{3.14159:.2f}"    # '3.14'
f"{3.14159:8.2f}"   # '    3.14'  总宽度 8，保留 2 位小数
f"{0.2567:.2%}"     # '25.67%'

集合

  
   
s = set(numbers)                 # 列表去重
array = list(set(array_a + array_b))    # 并集去重（顺序会打乱）
vowels = set('aeiouAEIOU')       # 字符串 → 集合，查找 O(1)
x in s                           # O(1) 判断存在
s.add(x) / s.remove(x)           # 增删
`set` 元素必须**可哈希**：`list` 不能放进去，要转 `tuple`。

字典

  
# ============================================================
# Python 字典 dict
# ============================================================
   
   
# ------------------------------------------------------------
# 1. 基础创建
# ------------------------------------------------------------
d = {}
d = dict()
   
# ------------------------------------------------------------
# 2. 访问
# ------------------------------------------------------------
d['a']                  # 取值；key 不存在会 KeyError
d.get('a')              # key 不存在返回 None
d.get('a', 0)           # key 不存在返回默认值 0
   
# ------------------------------------------------------------
# 3. 遍历
# ------------------------------------------------------------
   
# 同时遍历 key 和 value
for key, value in my_dict.items():
    print(key, value)
# 只遍历 key
for key in my_dict:
    print(key)
for key in my_dict.keys():
    print(key)
# 只遍历 value
for value in my_dict.values():
    print(value)
   
# 值求和
sum(my_dict.values())
   
   
# ------------------------------------------------------------
# 4. 遍历时删除
# ------------------------------------------------------------
   
# 不能一边直接遍历字典，一边修改字典大小，推荐先转成 list：
for key, value in list(d.items()):
    if value == 0:
        del d[key]
   
   
# ------------------------------------------------------------
# 5. 删除
# ------------------------------------------------------------
   
# ---------- del ----------
del d[key]
   
# ---------- pop ----------
value = d.pop(key)
value = d.pop(key, None)
   
   
# ------------------------------------------------------------
# 6. 判断 key 是否存在
# ------------------------------------------------------------
if key in d:
if key not in d:
   
   
   
# ------------------------------------------------------------
# 7. 用字典计数 / 累加
# ------------------------------------------------------------
counter = {}
   
if x not in counter:
    counter[x] = 0
counter[x] += 1
   
from collections import defaultdict
counter = defaultdict(int)
counter[x] += 1
   
# ------------------------------------------------------------
# 8. 字典排序
# ------------------------------------------------------------
   
# 按 (key, value) 排序，默认先按 key：
   
sorted(dic.items())
   
# ---------- 按 key 排序 ----------
sorted(dic.items(), key=lambda x: x[0])
   
# ---------- 按 value 排序 ----------
sorted(dic.items(), key=lambda x: x[1])
   
   
   
# ============================================================
# defaultdict
# ============================================================
   
from collections import defaultdict
# ---------- 默认空列表 ----------
d = defaultdict(list)
# ---------- 默认整数 0 ----------
counter = defaultdict(int)
# ---------- 默认自定义值 ----------
log = defaultdict(lambda: [0, 0])
   
   
# ============================================================
# Counter
# ============================================================
   
from collections import Counter
want = Counter(favorites)
   
# 直接取某元素次数，不存在的 key返回0
want[1]
# 所有计数之和：
sum(want.values())
   
   
cnt = Counter("aabccc")
# {'c': 3, 'a': 2, 'b': 1}
cnt.most_common()
# [('c', 3), ('a', 2), ('b', 1)]
cnt.most_common(2)
# 出现次数最多的前 2 个
   

(一)链表

单向链表

  
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
           
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = nextclass SingleLinkList:   
    def __init__(self,node=None):
        self.__head=node        
    #链表是否为空
    def is_empty(self):
        return self.__head==None        
    #链表长度
    def length(self):
        point=self.__head
        count=0
        while point != None:
            count+=1
            point=point.next
        return count                    
    #遍历链表
    def travel(self):
        point=self.__head
        while point != None:
            print(point.val)
            point=point.next                   
    #头部添加元素
    def add(self, item):
        node=ListNode(item)
        node.next=self.__head
        self.__head=node    
    #尾部添加元素
    def append(self, item):
        node=ListNode(item)
        point = self.__head
        if self.is_empty():
            self.__head=node
        else:
            while point.next != None:
                point=point.next
            point.next=node            
    #在指定位置添加元素
    def insert(self,pos,item):
        node=ListNode(item)
        point=self.__head
        if pos<=0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            for i in range(0,pos-1):
                point=point.next
            node.next=point.next
            point.next=node      
    #删除节点
    def remove(self,item):
        point=self.__head
        while point.next!=None:
            if point.next.val==item:
                point.next=point.next.next
                break
            else:
                point=point.next
    #判断节点是否存在
    def search(self, item):
        point=self.__head
        while point!=item:
            if point!=item:
                return True
            else:
                point=point.next
        return False

双向链表

  
class ListNode: 
    def __init__(self, val=0, next=None,prev=None):
        self.val = val
        self.next = next
        self.prev = prev
class DoubleLinkList():    
    def __init__(self,node=None):
        self.__head=node              
    #链表是否为空
    def is_empty(self):
        return self.__head is None        
    #链表长度
    def length(self):
        point=self.__head
        count=0
        while point != None:
            count+=1
            point=point.next
        return count                    
    #遍历链表
    def travel(self):
        point=self.__head
        while point != None:
            print(point.val)
            point=point.next                    
    #头部添加元素
    def add(self, item):
        node=ListNode(item)
        node.next=self.__head
        self.__head=node
        node.next.prev=node            
    #尾部添加元素
    def append(self, item):
        node=ListNode(item)
        point = self.__head
        if self.is_empty():
            self.__head=node
        else:
            while point.next != None:
                point=point.next
            point.next=node
            node.prev=point            
    #在指定位置添加元素
    def insert(self,pos,item):
        node=ListNode(item)
        point=self.__head
        if pos<=0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            for i in range(0,pos-1):
                point=point.next
            node.next=point.next
            node.next.perv=node
            point.next=node
            node.prev=point      
    #删除节点
    def remove(self,item):
        point=self.__head
        while point.next!=None:
            if point.next.val==item:
                point.next=point.next.next
                point.next.prev=point
                break
            else:
                point=point.next
    #判断节点是否存在
    def search(self, item):
        point=self.__head
        while point!=item:
            if point!=item:
                return True
            else:
                point=point.next
        return False

单项循环链表

(二)栈、队列

  
from collections import deque

q = deque()      					# 从列表构造双端队列
q.pop()           				# 右侧弹出
q.popleft()               # 左侧弹出 O(1)（list.pop(0) 是 O(n)）
q.append(x)               # 右侧入队
q.appendleft(x)           # 左侧入队
q[0]                      # 查看队首/栈顶（不弹出）

FILO栈

  
stack = [1,2.3]
stack.append(x)  # 入栈操作
stack.pop()  # 出栈操作，默认末尾元素出栈
print(stack[-1])  # 获取栈顶元素
   
class Stack:
    def __init__(self):
        self._stack = deque()
   
    def push(self, item):
        self._stack.append(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Popping from an empty stack")
        return self._stack.pop()
   
    def is_empty(self):
        return len(self._stack) == 0
   
    def size(self):
        return len(self._stack)

单调栈

  
class MonotonicStack:
    def __init__(self):
        self._stack = deque()
   
    def push(self, item):
        # 将栈中比当前元素小的元素全部弹出
        while self._stack and self._stack[-1] < item:
            self._stack.pop()
        self._stack.append(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Popping from an empty stack")
        return self._stack.pop()
   
    def top(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack[-1]
   
    def is_empty(self):
        return len(self._stack) == 0
   
    def size(self):
        return len(self._stack)

FIFO队列

  
queue = [1,2.3]
queue.append(x)  # 入队操作
queue.pop(0)  # 出队操作，默认末尾元素出栈
   
class FIFO:
    def __init__(self):
        self._queue = deque()
   
    def push(self, item):
        self._queue.append(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Dequeuing from an empty queue")
        return self._queue.popleft()
   
    def is_empty(self):
        return len(self._queue) == 0
   
    def size(self):
        return len(self._queue)

双端队列

  
class Deque:
    def __init__(self):
        self._deque = deque()
   
    def append(self, item):
        self._deque.append(item)
   
    def appendleft(self, item):
        self._deque.appendleft(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Popping from an empty deque")
        return self._deque.pop()
   
    def popleft(self):
        if self.is_empty():
            raise IndexError("Popping from an empty deque")
        return self._deque.popleft()
   
    def is_empty(self):
        return len(self._deque) == 0
   
    def size(self):
        return len(self._deque)

单调队列

  
class MonotonicQueue: #单调队列(从大到小)
    def __init__(self):
        self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时
       
    #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    #同时pop之前判断队列当前是否为空。
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()
               
    #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    #这样就保持了队列里的数值是单调从大到小的了。
    def push(self, value):
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
           
    #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    def front(self):
        return self.queue[0]
    def is_empty(self):
        return len(self._queue) == 0
    def size(self):
        return len(self._queue)

(四)堆

堆的存储
堆一般用列表存储
节点下标为\(i\)
左子节点小标\(2i+1\)
右子节点下标\(2i+1\)

堆的操作

上滤：堆尾添加新元素，复杂度\(O(logN)\),\(N\)是堆的层数

  
def heapify_up(heap, index):
    """
    - heap: A list representing the heap.
    - index: The index of the element to be heapified up.
    """
    parent_index = (index - 1) // 2
    while index > 0 and heap[index] > heap[parent_index]:
        # Swap the element with its parent if it's greater
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        # Update the index and parent_index for the next iteration
        index = parent_index
        parent_index = (index - 1) // 2
             
# Example usage:
heap = [10, 8, 7, 6, 5, 3, 2, 1]
new_element = 9
heap.append(new_element)  # Add the new element to the end of the heap
heapify_up(heap, len(heap) - 1)  # Perform heapify-up operation on the new element

下滤：堆首添加新元素，复杂度\(O(logN)\),\(N\)是堆的层数

  
def heapify_down(heap, index):
    # Get the indices of the left and right children
    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2
         
    # Find the parent element among the current node and its children
    parent_index = index
         
    if left_child_index < len(heap) and heap[left_child_index] > heap[parent_index]:
        parent_index = left_child_index
         
    if right_child_index < len(heap) and heap[right_child_index] > heap[parent_index]:
        parent_index = right_child_index
         
    # If the parent element is not the current node, swap it with the parent child and sift down
    if parent_index != index:
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        heapify_down(heap, parent_index)
     
# Example usage
heap = [1, 7, 6, 4, 5, 1, 2]  # Example heap
print("Before sift down:", heap)
heapify_down(heap, 0)  # Perform sift down operation

建堆

自上而下建堆：复杂度\(O(NlogN)\)

  
def heapify_up(heap, index):
         
    parent_index = (index - 1) // 2
         
    while index > 0 and heap[index] > heap[parent_index]:
        # Swap the element with its parent if it's greater
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        # Update the index and parent_index for the next iteration
        index = parent_index
        parent_index = (index - 1) // 2
             
def setup_heapify(arr):
    for i in range(0,len(arr)):
        heapify_up(arr, i)
     
nums=[3,4,5,6,1,7,8]
setup_heapify(nums)

自下而上建堆：复杂度\(O(N)\)

  
def heapify_down(heap, index):
    # Get the indices of the left and right children
    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2
         
    # Find the parent element among the current node and its children
    parent_index = index
         
    if left_child_index < len(heap) and heap[left_child_index] > heap[parent_index]:
        parent_index = left_child_index
         
    if right_child_index < len(heap) and heap[right_child_index] > heap[parent_index]:
        parent_index = right_child_index
         
    # If the parent element is not the current node, swap it with the parent child and sift down
    if parent_index != index:
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        heapify_down(heap, parent_index)
     
def setup_heapify(arr):
    n = len(arr)
    # 从最后一个非叶子节点开始，逐个向上进行下滤操作
    for i in range(n // 2 - 1, -1, -1):
        heapify_down(arr, i)
     
nums=[3,4,5,6,1,7,8]
setup_heapify(nums)

堆排序：见排序3

(五)哈希表

哈希表结构的选择
数组作为哈希表：数组的大小是受限的，对于有限的key用数组做hashtable最合适
set作为哈希表：没有限制数值的大小，就无法使用数组来做哈希表了。主要原因：
- 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
- 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
map作为哈希表：使用数组和set来做哈希法的局限
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key

数之和

两数之和(使用哈希表)

  
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashtable=dict()
    for i, num in enumerate(nums):
        if target-num in hashtable:
            return [hashtable[target-num],i]
        else:
            hashtable[num]=i
                     

三数之和(使用双指针)

  
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans=[]
        for i in range(len(nums)):
            if nums[i]>0:return ans
            if i>0 and nums[i]==nums[i-1]:
                continue
            left=i+1
            right=len(nums)-1
            while right>left:
                sum=nums[i]+nums[left]+nums[right]
                if sum>0:
                    right-=1
                elif sum<0:
                    left+=1
                else:
                    ans.append([nums[i],nums[left],nums[right]])
                    left+=1
                    right-=1
                    while  right>left and nums[right]==nums[right+1]:
                        right-=1
                    while  right>left and nums[left]==nums[left-1]:
                        left+=1
                             
        return ans

四数之和(使用双指针)

  
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans=[]
        n=len(nums)
        for k in range(n):
            if target>0 and nums[k]>target:# 剪枝
                break
            if k>0 and nums[k]==nums[k-1]:
                continue
            for i in range(k+1,n):
                if target>0 and nums[i]+nums[k]>target:# 剪枝
                    break 
                if i>k+1 and nums[i]==nums[i-1]:  
                    continue
                left=i+1
                right=n-1
                while right>left:
                    sum=nums[k]+nums[i]+nums[left]+nums[right]
                    if sum>target:
                        right-=1
                    elif sum<target:
                        left+=1
                    else:
                        ans.append([nums[k],nums[i],nums[left],nums[right]])
                        right-=1
                        left+=1
                        while right>left and nums[right]==nums[right+1]:
                            right-=1
                        while right>left and nums[left]==nums[left-1]:
                            left+=1
        return ans

(六)二叉树

基础概念

专业术语	中文	描述
Root	根节点	一棵树的顶点
Child	孩子结点	一个结点含有的子树的根节点称为该结点的子节点
Leaf	叶子结点	没有孩子的节点
Degree	度	一个节点包含子树的数量
Edge	边	一个节点与另外一个节点的连接
Depth	深度	根节点到这个节点经过边的数量
Height	节点高度	从当前节点到叶子节点形成路径中边的数量
Level	层级	节点到根节点最长路径的边的总和
Path	路径	一个节点和另一个节点之间经过的边和Node的序列

满二叉树（Full Binary Tree）：满二叉树是一种特殊的二叉树，除了叶子节点外，每个节点都有两个子节点，并且所有叶子节点都在同一层上。

完全二叉树（Complete Binary Tree）：完全二叉树是一种二叉树，除了最后一层外，其他层的节点都是满的，并且最后一层的节点都靠左排列。（满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树）

二叉搜索树（Binary Search Tree）：二叉搜索树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树

平衡二叉树（Balanced Binary Tree）：平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不超过1，以保持树的平衡性。

Huffman树（Huffman Tree）：Huffman树是一种特殊的二叉树，用于数据压缩算法中的Huffman编码。这些是二叉树的一些常见分类，每种分类都有其特定的性质和应用场景。

红黑树

节点是红色或黑色。
根节点是黑色。
所有的叶子节点都是黑色。
每个红色节点必须有两个黑色的子节点。（不能出现两个连续的红色节点）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

二叉树的性质

性质1：二叉树的第i层上至多有\(2^{(i-1)}\) 个节点\((i>0)\)

性质2：深度为h的二叉树中至多含有\(2^{h}-1\)个节点

性质3：若在任意一棵二叉树中，有\(N_0\)个叶子节点，有\(N_2\)个度为2的节点，则必有\(N_0=N_2+1\)

性质4：具有n个节点的满二叉树深为\(\log_2(n+1)\)

性质5：若对一棵有完全二叉树进行顺序编号\((1≤i≤n)\)，那么，对于编号为\(i\)的节点：左孩子为\(2i\)；右孩子为\(2i+1\) ；父节点为\(i//2\)

二叉树的构建

  
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None        

层次遍历结果建立二叉树(层次遍历可以确定一棵树)

  
class Tree():    
    def __init__(self):        
        self.root=None
    #二叉树构建
    def add(self,item):
        node=TreeNode(item)
        queue=[self.root]
        if self.root is None:
            self.root = node
            return
        while queue:
            cur_node=queue.pop(0)
            if cur_node.left is None:
                cur_node.left = node
                return
            else:
                queue.append(cur_node.left)
            if cur_node.right is None:
                cur_node.right = node
                return
            else:
                queue.append(cur_node.right)

先序、中序、后序左右根建立二叉树（知道其[中序]+[先序or后序]才能遍历可以确定一棵树）

二叉树遍历

广度优先遍历：层次遍历

  
 #广度优先遍历
def breadth_travel(self):
    if self.root is None:
        return
    queue=[self.root]
    while queue:
        cur_node=queue.pop(0)
        print(cur_node.val,end=' ')
        if cur_node.left is not None:
            queue.append(cur_node.left)
        if cur_node.right is not None:
            queue.append(cur_node.right)
#方便每行操作
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = collections.deque([root])
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level)
        return result

深度优先遍历

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

  
递归法
#深度优先遍历——先序遍历
def preorder_travel(self, node):
    if node is None:
        return
    print(node.val,end=' ')
    self.preorder_travel(node.left)
    self.preorder_travel(node.right)
#深度优先遍历——中序遍历
def inorder_travel(self, node):
    if node is None:
        return
    self.inorder_travel(node.left)
    print(node.val,end=' ')        
    self.inorder_travel(node.right)        
#深度优先遍历——后序遍历
def postorder_travel(self, node):
    if node is None:
        return
    self.postorder_travel(node.left)
    self.postorder_travel(node.right) 
    print(node.val,end=' ')
栈方法
# 前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return result
# 中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:     
                stack.append(cur)
                cur = cur.left		
            # 到达最左结点后处理栈顶结点    
            else:		
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right	
        return result
# 后序遍历
class Solution:
   def postorderTraversal(self, root: TreeNode) -> List[int]:
       if not root:
           return []
       stack = [root]
       result = []
       while stack:
           node = stack.pop()
           # 中结点先处理
           result.append(node.val)
           # 左孩子先入栈
           if node.left:
               stack.append(node.left)
           # 右孩子后入栈
           if node.right:
               stack.append(node.right)
       # 将最终的数组翻转
       return result[::-1]

二叉数的基本性质

二叉树的深度

  
#最大深度——后序遍历
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def gethight(node):
            if node is None:
                return 0
            left=gethight(node.left)
            right=gethight(node.right)
            height=1+max(left,right)
            return height
        h=gethight(root)
        return h
#精简       
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return 1+max(self.maxDepth(root.left), self.maxDepth(root.right))
#最大深度——层序遍历
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res
#最小深度——后序遍历
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        def getheight(node):
            if node is None:
                return 0
            left=getheight(node.left)
            right=getheight(node.right)
            if node.left is None and node.right is not None:
                return 1+right
            if node.left is not None and node.right is None:
                return 1+left
            else:
                height=1+min(left,right)
                return height
        return getheight(root)
#最小深度——层序遍历
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0
        queue = collections.deque([root])        
        while queue:
            depth += 1 
            for _ in range(len(queue)):
                node = queue.popleft()                
                if not node.left and not node.right:
                    return depth            
                if node.left:
                    queue.append(node.left)                    
                if node.right:
                    queue.append(node.right)
        return depth 

完全二叉树节点的数量

  
class Solution: # 利用完全二叉树特性
    def countNodes(self, root: TreeNode) -> int:
        if not root: return 0
        count = 1
        left = root.left; right = root.right
        while left and right:
            count+=1
            left = left.left; right = right.right
        if not left and not right: # 如果同时到底说明是满二叉树，反之则不是
            return 2**count-1
        return 1+self.countNodes(root.left)+self.countNodes(root.right)

总结
- 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
- 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
- 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。
- 注意在普通二叉树的属性中，我用的是一般为后序，例如单纯求深度就用前序，二叉树：找所有路径也用了前序，这是为了方便让父节点指向子节点。

二、基础算法

(零)Python常用

(一)排序

sord的常规用法

  
# ============================================================
# Python 排序 sort() / sorted() 速查
# ============================================================
   
   
# ------------------------------------------------------------
# 1. sort() 和 sorted()
# ------------------------------------------------------------
nums.sort() # 直接修改原列表
new_nums = sorted(nums)# 不修改原列表
   
   
# ------------------------------------------------------------
# 2. 升序 / 降序
# ------------------------------------------------------------
nums.sort()
nums.sort(reverse=False)     # 升序，默认
nums.sort(reverse=True)      # 降序
   
# ------------------------------------------------------------
# 3. key：指定“按什么排序”
# ------------------------------------------------------------
   
# key 可以理解为：先把每个元素转换成一个“排序值”，再按这个值排序。可以理解为是一个函数，sort() 会对每个元素调用一次 key
# 按长度
words.sort(key=len)
# 按绝对值
nums.sort(key=abs)
   
# lambda 写 key
# 按第 1 个元素排序
data.sort(key=lambda x: x[0])
# key1 升序，key2 升序
data.sort(key=lambda x: (x[0], x[1]))
# key1 升序，key2 降序
data.sort(key=lambda x: (x[0], -x[1]))
   
# 字符串忽略大小写排序
words.sort(key=str.lower)
# 同字母，小写优先
chars.sort(key=lambda x: (x.lower(), x.isupper()))
# 同字母，大写优先
chars.sort(key=lambda x: (x.lower(), x.islower()))
# 所有小写优先
chars.sort(key=lambda x: (x.isupper(), x.lower()))
# 所有大写优先
chars.sort(key=lambda x: (x.islower(), x.lower()))
   
   
# 字符串混合升降序，如果第二个条件是字符串，不能写：-x[1]，可以利用 Python 的“稳定排序”：先排次要条件，再排主要条件。
# 要求：key1 升序，key2 降序
   
data.sort(key=lambda x: x[1], reverse=True)   # 次要条件
data.sort(key=lambda x: x[0])                 # 主要条件
   

  
# ============================================================
# zip / enumerate / range / map 速查
# ============================================================
   
# 1. zip：并行遍历 / 配对
[x + y for x, y in zip(a, b)]
pairs = list(zip(a, b))
zip(*matrix)                  # 矩阵转置
# 注意：以最短序列为准
   
   
# 2. enumerate：同时取下标和值
for i, value in enumerate(a):
    ...
   
# i：下标
# value：元素
   
   
# 3. range：生成整数序列
range(n)                      # 0 ~ n-1
range(start, end)             # start ~ end-1
range(start, end, step)       # 指定步长
range(len(a) - 1, -1, -1)    # 倒序
   
   
# 4. map：批量对元素执行函数
map(int, a)                   # 每个元素转 int
map(str, a)                   # 每个元素转 str
   
nums = list(map(int, input().split()))
# 输入多个整数常用写法

冒泡排序

  
#%%冒泡排序
def bubble_sort(arr):
    n = len(arr)
    # 遍历数组元素
    for i in range(n):
        # 每次遍历都会将当前最大的元素移动到数组末尾
        for j in range(0, n-i-1): 
            # 如果当前元素大于下一个元素，则交换它们
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  
#%%优化冒泡排序
def bubble_sort1(arr):
    n = len(arr)
    # 遍历数组元素
    exc=n-1
    for i in range(n):
        if exc==0:
            break
        for j in range(0, exc): 
            # 如果当前元素大于下一个元素，则交换它们
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                exc=j
            if exc==n-1:
                exc=0

冒泡排序优化

  
#%%优化冒泡排序
def bubble_sort_opt(arr):
    n = len(arr)
    # 遍历数组元素
    exc=n-1
    for i in range(n):
        if exc==0:
            break
        for j in range(0, exc): 
            # 如果当前元素大于下一个元素，则交换它们
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                exc=j
            if exc==n-1:
                exc=0

选择排序

  
#%%选择排序
def selection_sort(arr):
    n = len(arr)
    # 遍历数组
    for i in range(n-1, 0, -1):
        # 寻找未排序部分的最大元素的索引
        max_index = i
        for j in range(i):
            if arr[j] > arr[max_index]:
                max_index = j
        # 将最大元素与未排序部分的末尾交换
        arr[i], arr[max_index] = arr[max_index], arr[i]

堆排序

  
#%%堆排序    
def heapdown(arr, n, i):
    '''
    构建大根堆函数
    Parameters
    ----------
    arr : list
        堆
    n : int
        堆长度
    i : int
        下滤节点索引
    '''
    largest = i  # 将最大元素的索引初始化为根节点
    l = 2 * i + 1  # 左子节点的索引
    r = 2 * i + 2  # 右子节点的索引
   
    # 如果左子节点存在且大于根节点，则更新最大元素的索引
    if l < n and arr[l] > arr[largest]:
        largest = l
   
    # 如果右子节点存在且大于根节点，则更新最大元素的索引
    if r < n and arr[r] > arr[largest]:
        largest = r
   
    # 如果最大元素的索引不等于根节点，则交换它们，并递归调用heapify
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapdown(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    # 构建大根堆
    for i in range(n // 2 - 1, -1, -1):
        heapdown(arr, n, i)
    # 逐步将最大元素移到数组末尾
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 将当前根节点（最大元素）与末尾元素交换
        heapdown(arr, i, 0)  # 重新构建最大堆，注意数组长度减小 

插入排序

  
#%%插入排序
def insertion_sort(arr):
    n = len(arr)
    # 从第二个元素开始，将每个元素插入到已排序序列的适当位置
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 将 arr[i] 向左移动，直到找到比它小的元素或者到达数组的起始位置
        while key < arr[j] and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        # 将 key 插入到正确的位置
        arr[j + 1] = key

插入排序优化

  
#%%优化插入排序（二分法）
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
   
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
       
    return left  # 如果没有找到目标元素，返回插入位置
   
def insertion_sort1_opt(arr):
    n = len(arr)
    # 从第二个元素开始，将每个元素插入到已排序序列的适当位置
    for i in range(1, n):
        key = arr[i]
        j = binary_search(arr[0:i],key)
        del arr[i]
        arr.insert(j, key)

归并排序

  
#%%归并排序 
def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
       
    # 比较左右两半的元素，并按顺序合并到结果数组中
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
   
    # 将剩余的元素添加到结果数组中
    result.extend(left[left_idx:])
    result.extend(right[right_idx:])
       
    return result     
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
       
    # 将数组分成两半
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
   
    # 递归地对左右两半进行归并排序
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
   
    # 合并已排序的左右两半
    return merge(left_half, right_half)

快速排序

  
#%%快速排序 
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
       
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准值
    left = [x for x in arr if x < pivot]  # 比基准值小的元素放在左边
    middle = [x for x in arr if x == pivot]  # 等于基准值的元素放在中间
    right = [x for x in arr if x > pivot]  # 比基准值大的元素放在右边
       
    return quick_sort(left) + middle + quick_sort(right)

希尔排序

  
#%%希尔排序 
def stepsequence(n):
    k=0
    step=0
    sequence=[]
    while True:
        if k%2==0:
            step=9*(pow(2,k)-pow(2,k/2))+1
        else:
            step=8*pow(2,k)-6*pow(2,(k+1)/2)+1
        if step>=n:
            break
        sequence.append(int(step))
        k+=1
    return sequence[::-1]
               
def shell_sort(arr):
    n = len(arr)
    sequence=stepsequence(n)
    for gap in sequence:
        # 对每个间隔进行插入排序
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 对间隔为 gap 的子数组进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp

计数排序

  
#%%计数排序
def counting_sort(arr):
    # 找到待排序数组中的最大值和最小值
    min_val = min(arr)
    max_val = max(arr)
   
    # 初始化计数数组，长度为 (max_val - min_val + 1)，并将每个计数初始化为 0
    count = [0] * (max_val - min_val + 1)
   
    # 统计每个元素出现的次数
    for num in arr:
        count[num - min_val] += 1
   
    # 根据计数数组将元素放置到正确的位置上
    sorted_arr = []
    for i in range(min_val, max_val + 1):
        sorted_arr.extend([i] * count[i - min_val])
   
    return sorted_arr

基数排序

  
#%%基数排序
def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
   
    # 统计每个元素出现的次数
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
   
    # 将计数数组转换为位置数组
    for i in range(1, 10):
        count[i] += count[i - 1]
   
    # 构造输出数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
   
    # 将输出数组复制到原始数组中
    for i in range(n):
        arr[i] = output[i]
   
def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

(二)递归

解决的问题：

①数据的定义是按递归定义的，如斐波拉契数、阶乘；

②问题解法按递归算法实现，如最大公约数、汉诺塔问题、爬楼梯、放苹果；

③数据的结构形式是按递归定义的，如二叉树深度优先

回溯、深度优先也是递归的一种

伪代码模板

  
def recursion():
    if 结束条件:
        记录答案
        return
    动作          #递的过程中做动作，先序遍历
    recursion(新的遍历)
    动作          #归的过程中做动作，后序遍历

斐波拉契数

  
class Solution:
    def fib(self, n: int) -> int:        
        def recursion(n):
            if n<=1:
                return n
            return recursion(n-1)+recursion(n-2)
        return recursion(n)

阶乘

  
def recursion(n):
    if n==1:
        return 1
    return n*recursion(n-1)

最大公约数
辗转相除：先将两个数中的较大数除以较小数，得到余数，再将较小数和余数作为新的被除数和除数，继续进行计算，直到余数为零为止。此时，最后一次除法中的除数即为最大公约数
1 2 3 4 5 6 7 def recursion(a,b): if a<b: a,b=b,a y=a%b if y==0: return b return recursion(b, y)
更相减损：先将两个数的绝对值进行相减，得到差值，然后将差值与较小的数进行比较。如果差值小于较小的数，则将差值和较小的数作为新的被减数和减数，继续进行计算；如果差值大于或等于较小的数，则停止计算，此时的较小的数即为最大公约数。
1 2 3 4 5 6 7 def recursion(a,b): if a<b: a,b=b,a diff=a-b if diff==0: return b return recursion(b,diff)

汉诺塔

  
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
    n = len(A)        
    def recursion(n,A,B,C):
        if n==1:
            C.append(A.pop())
            return
        recursion(n-1, A, C, B)
        C.append(A.pop())
        recursion(n-1, B, A, C)

放苹果

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

  
'''
放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
即求(m-n，n)
'''
m,n=map(int,input().split())
def recursion(m,n):
    if m < 0 or n < 0:
        return 0
    elif m == 1 or n == 1:
        return 1
    else:
        return recursion(m,n-1)+recursion(m-n,n)
ans=recursion(m,n)
print(ans)

(三)回溯

经常和递归组合使用，是一种纯暴力搜索

解决的问题：组合、排列、子集、切割、棋盘

所有的回溯算法都可抽象为树结构

伪代码模板

  
path=[]
ans=[]
def backtracking(参数startindex,index等):
    （剪枝）
    if（终止条件）：
        存放结果
        return
    for i in (选择：本层集合中可选择的元素数量(剪枝)):
        path.append()处理节点
        backtracking()##递归
        path.pop()回溯，撤销处理结果
    return

示例

  
#组合总和
def combinationSum(candidates,target):
    path = []
    ans = []
    def backtracking(target,candidates,start_index):
        if sum(path)>target:return
        if sum(path)==target:
            ans.append(path.copy())
            return
        for i in range(start_index,len(candidates)):
            path.append(candidates[i])
            backtracking(target,candidates,i)
            path.pop()
        return
    backtracking(target,candidates,0)
    return ans
start_index是为了控制排列、组合，有start_index是组合，没有start_index是排列
对于组合来说：i和i+1是为了控制元素能否被多次使用，i表示可以多次使用，i+1表示只能使用一次去，去重要先排序然后跳过
对于排列来说：使用uesd数组控制元素能否被多次使用
def permute(self, nums: List[int]) -> List[List[int]]:
    path = []
    ans = []
    used = [False]*len(nums)
    def backtracking(nums):
        if len(path) == len(nums):
            ans.append(path.copy())
        if len(path) > len(nums): return
        for i in range(0, len(nums)):
            if used[i]:continue
            path.append(nums[i])
            used[i] = True
            backtracking(nums)
            used[i] = False
            path.pop()
        return
    backtracking(nums)
    return ans

(四)贪心问题

话贪心算法并没有固定的套路，唯一的难点就是如何通过局部最优，推出整体最优，最好的方法就是尝试

基本步骤：

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解。

常见的贪心问题

背包问题、区间覆盖问题、活动安排问题、价格变动利润问题、多机调度问题

(五)动态规划

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

常见的贪心问题：背包问题、打家劫舍、股票问题、子序列问题

动态规划五部曲
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组初始化
- 确定遍历顺序
  如果问题是求背包能装的最大物品价值或者能不能在装满背包，那么“先背包，后物品”或”先物品，后背包“都可以，因为他求的是结果，不要求过程
  如果问题是求背包能装的方法，那么组合是”先背包，后物品“；排列是”先物品，后背包“，因为他求的是过程
  完全背包从小到大遍历，0-1背包从大到小遍历
- 举例推导dp数组（打印dp数组）

背包问题

01背包

N种物品，每种物品只有一个

二维dp数组：\(dp[i][j]\)表示从下标为[0-i]的物品里任意取，放进剩余容量为j的背包，价值总和最大是多少

dp数组初始化：背包容量为0：\(dp[:][0] = 0\)，物品1重量：\(dp[0][weight[0]: bagweight + 1] = 0\)

动态方程：\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\)

确定遍历顺序：先遍历物品，后遍历背包or先遍历背包，后遍历物品，都可以

  
def test_2_wei_bag_problem1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
     
    # 二维数组
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]
     
    # 初始化
    for j in range(weight[0], bagweight + 1):
        dp[0][j] = value[0]
     
    # weight数组的大小就是物品个数
    for i in range(1, len(weight)):  # 遍历物品
        for j in range(bagweight + 1):  # 遍历背包容量
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
     
    return dp[-1][-1]

一维滚动dp数组：一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

dp数组初始化：物品价值都是大于0的，所以dp数组初始化的时候，都初始为0

动态方程：\(dp[j] = max(dp[j], dp[j - weight[i]] + value[i])\)

确定遍历顺序：背包倒序遍历保证物品i只被放入一次

  
def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
     
    # 初始化
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
     
    return dp[-1]

完全背包

N种物品，每种物品有无限个

二维dp数组：\(dp[i][j]\)表示从下标为[0-i]的物品里任意取，放进剩余容量为j的背包，价值总和最大是多少

dp数组初始化：背包容量为0：\(dp[:][0] = 0\)，物品1重量：按重量初始化

动态方程：\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\)

确定遍历顺序：先遍历物品，后遍历背包or先遍历背包，后遍历物品，都可以

def test_2_wei_bag_problem1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
     
    # 二维数组
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]
     
    # 初始化
    for j in range(weight[0], bagweight + 1):
        dp[0][j] = j//weight[0]*value[0]
     
    # weight数组的大小就是物品个数
    for i in range(1, len(weight)):  # 遍历物品
        for j in range(bagweight + 1):  # 遍历背包容量
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
     
    return dp[-1][-1]

一维滚动dp数组：一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

dp数组初始化：物品价值都是大于0的，所以dp数组初始化的时候，都初始为0

动态方程：\(dp[j] = max(dp[j], dp[j - weight[i]] + value[i])\)

确定遍历顺序：背包正序遍历保证物品i只被放入多次

  
def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    # 初始化
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(bagWeight, weight[i] - 1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
     
    return dp[-1]

多重背包
N种物品，每种物品数量不同，每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题

背包问题变体

背包加附件（牛客HJ16）

  
N, m = map(int, input().split())
value = []
importance = []
zhufu = []
       
for i in range(m):
    v, p, q = map(int, input().split())
    value.append([v])
    importance.append([p * v])
    zhufu.append(q)
for i in range(m):
    if zhufu[i]!=0:
        if len(value[zhufu[i]-1])==1:
            value[zhufu[i]-1].append(value[zhufu[i]-1][0]+value[i][0])
            importance[zhufu[i]-1].append(importance[zhufu[i]-1][0]+importance[i][0])
        elif len(value[zhufu[i]-1])==2:
            value[zhufu[i]-1].append(value[zhufu[i]-1][0]+value[i][0])
            importance[zhufu[i]-1].append(importance[zhufu[i]-1][0]+importance[i][0])
                   
            value[zhufu[i]-1].append(value[zhufu[i]-1][1]+value[i][0])
            importance[zhufu[i]-1].append(importance[zhufu[i]-1][1]+importance[i][0])
                   
for i in range(m-1,0,-1):
    if zhufu[i]!=0:
        del value[i]
        del importance[i]
       
#dp数组
dp=[[0]*int(N/10+1) for _ in range(len(value))]
       
#初始化
for k in range(len(value[0])):
    for i in range(value[0][k]//10,N//10+1):
        dp[0][i]=importance[0][k]
#遍历
for i in range(1,len(value)):
    for j in range(0,N//10+1):
        for k in range(len(value[i])):
            if j*10<value[i][k]:
                dp[i][j]=max(dp[i][j],dp[i-1][j])
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j],dp[i-1][j-value[i][k]//10]+imortance[i][k])
print(dp[-1][-1])
               

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  
#打家劫舍1
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)<=2:
            return max(nums)
        dp=[0]*len(nums)
        dp[0]=nums[0]
        dp[1]=max(nums[1],nums[0])
        for i in range(2,len(nums)):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[-1]

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

  
#打家劫舍2
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)<=2:
            return max(nums)
        dp1=[0]*(len(nums)-1)
        dp1[0]=nums[0]
        dp1[1]=nums[0]
        for i in range(2,len(nums)-1):
            dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i])
        dp2=[0]*len(nums)
        dp2[0]=0
        dp2[1]=nums[1]
        for i in range(2,len(nums)):
            dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i])
   
        return max(dp1[-1],dp2[-1])  

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

  
#打家劫舍3
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        # dp数组（dp table）以及下标的含义：
        # 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
        # 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱
        dp = self.traversal(root)
        return max(dp)
    # 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算
    def traversal(self, node):       
        # 递归终止条件，就是遇到了空节点，那肯定是不偷的
        if not node:
            return (0, 0)
        left = self.traversal(node.left)
        right = self.traversal(node.right)
        # 不偷当前节点, 偷子节点
        val_0 = max(left[0], left[1]) + max(right[0], right[1])
        # 偷当前节点, 不偷子节点
        val_1 = node.val + left[0] + right[0]
        return (val_0, val_1)

股票问题

二维dp数组：\(dp[i][j]\)表示第i天交易完成后的最大利润，其中j表示当前是否持有股票，持有时j=0，不持有j=1。

dp数组初始化：初始状态为 \(dp[0][0]=−prices[0]\)，其余状态均为 0。

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

  
#买卖股票的最佳时机1
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        dp = [[0] * 2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, length):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        return dp[-1][1]

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的最大利润 。

  
#买卖股票的最佳时机2
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        return dp[-1][-1]

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  
#买卖股票的最佳时机3
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        if n<=1:
            return 0
        dp=[[0]*4 for _ in range(n)]
        dp[0][0]=-prices[0]
        dp[0][2]=-prices[0]
        for i in range(1,n):
            dp[i][0]=max(dp[i-1][0],-prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i])
            dp[i][3]=max(dp[i-1][3],dp[i-1][2]+prices[i])
        return dp[-1][-1]

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  
#买卖股票的最佳时机4
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n=len(prices)
        if n<=1:
            return 0
        dp=[[0]*k*2 for _ in range(n)]
        for i in range(0,2*k,2):
            dp[0][i]=-prices[0]
        for i in range(1,n):
            dp[i][0]=max(dp[i-1][0],-prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
            for j in range(2,2*k-1,2):
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
                dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]+prices[i])
        return dp[-1][-1]

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

  
#买卖股票的最佳时机(含冷冻期)
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 2][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        return dp[-1][-1]

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

  
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]-fee)
        return dp[-1][-1]

子序列

(六)双指针

左右双指针

两个指针一个从前面往后遍历，一个从后面往前遍历，两个指针同时向中间移动

两数之和(使用哈希表)

  
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashtable=dict()
    for i, num in enumerate(nums):
        if target-num in hashtable:
            return [hashtable[target-num],i]
        else:
            hashtable[num]=i
                     

三数之和(使用双指针)

  
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans=[]
        for i in range(len(nums)):
            if nums[i]>0:return ans
            if i>0 and nums[i]==nums[i-1]:
                continue
            left=i+1
            right=len(nums)-1
            while right>left:
                sum=nums[i]+nums[left]+nums[right]
                if sum>0:
                    right-=1
                elif sum<0:
                    left+=1
                else:
                    ans.append([nums[i],nums[left],nums[right]])
                    left+=1
                    right-=1
                    while  right>left and nums[right]==nums[right+1]:
                        right-=1
                    while  right>left and nums[left]==nums[left-1]:
                        left+=1
                             
        return ans

四数之和(使用双指针)

  
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans=[]
        n=len(nums)
        for k in range(n):
            if target>0 and nums[k]>target:# 剪枝
                break
            if k>0 and nums[k]==nums[k-1]:
                continue
            for i in range(k+1,n):
                if target>0 and nums[i]+nums[k]>target:# 剪枝
                    break 
                if i>k+1 and nums[i]==nums[i-1]:  
                    continue
                left=i+1
                right=n-1
                while right>left:
                    sum=nums[k]+nums[i]+nums[left]+nums[right]
                    if sum>target:
                        right-=1
                    elif sum<target:
                        left+=1
                    else:
                        ans.append([nums[k],nums[i],nums[left],nums[right]])
                        right-=1
                        left+=1
                        while right>left and nums[right]==nums[right+1]:
                            right-=1
                        while right>left and nums[left]==nums[left-1]:
                            left+=1
        return ans

共速双指针

两个指针都从前面往后遍历，第一个指针先走k步

删除链表倒数第k个节点

  
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        
        left = right = dummy = ListNode(next=head)
        #快指针先走n步
        for _ in range(n):
            right = right.next
        #快慢指针同时走
        while right.next:
            left = left.next
            right = right.next
        left.next = left.next.next
        return dummy.next

快慢指针

定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，在途中相遇

环形链表

  
class Solution(object):
     
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

(七)位运算

  
# ============================================================
# 位运算是在二进制上的运算
# ============================================================


# ------------------------------------------------------------
# 2. 与 &：两个位置都为 1，结果才是 1
# ------------------------------------------------------------

a = 6            # 110
b = 5            # 101
a & b            # 100 -> 4

# 常用：判断某一位是不是 1，如果结果 != 0：第 k 位是 1；如果结果 == 0：第 k 位是 0
n & (1 << k)

# ------------------------------------------------------------
# 3. 或 |：只要有一个位置为 1，结果就是 1
# ------------------------------------------------------------

a = 6            # 110
b = 5            # 101
a | b            # 111 -> 7

# 常用：把第 k 位设为 1
n = n | (1 << k)


# ------------------------------------------------------------
# 4. 异或 ^：相同为 0，不同为 1
# ------------------------------------------------------------

a = 6            # 110
b = 5            # 101
a ^ b            # 011 -> 3

# 异或满足交换律、结合律：
# a ^ b ^ a
# = a ^ a ^ b
# = b

# 常用：只有一个数出现一次，其余都出现两次
nums = [2, 3, 2, 4, 4]
ans = 0
for x in nums:
    ans ^= x

# ans -> 3


# ------------------------------------------------------------
# 5. 取反 ~
# ------------------------------------------------------------
~x
# ~x == -(x + 1)

# ------------------------------------------------------------
# 6. 左移 <<
# ------------------------------------------------------------
n << k
# 相当于：
# n * 2^k
3 << 1          # 6
3 << 2          # 12
3 << 3          # 24

# 常用：
# 1 << k 表示只有第 k 位是 1
1 << 0          # 1     -> 0001
1 << 1          # 2     -> 0010
1 << 2          # 4     -> 0100
1 << 3          # 8     -> 1000


# ------------------------------------------------------------
# 7. 右移 >>
# ------------------------------------------------------------

n >> k

# 对非负整数相当于：
# n // 2^k

20 >> 1         # 10
20 >> 2         # 5


# ------------------------------------------------------------
# 8. 判断奇偶
# ------------------------------------------------------------

n & 1

# 最低位为 1 -> 奇数
# 最低位为 0 -> 偶数

if n & 1:
    print("奇数")
else:
    print("偶数")


# ------------------------------------------------------------
# 9. 判断第 k 位
# ------------------------------------------------------------

# 注意：通常最低位记作第 0 位

if n & (1 << k):
    print("第 k 位是 1")
else:
    print("第 k 位是 0")


# 也可以：

(n >> k) & 1

# 结果：
# 1 -> 第 k 位是 1
# 0 -> 第 k 位是 0


# ------------------------------------------------------------
# 10. 把第 k 位设为 1
# ------------------------------------------------------------

n |= (1 << k)


# ------------------------------------------------------------
# 11. 把第 k 位设为 0
# ------------------------------------------------------------

n &= ~(1 << k)


# ------------------------------------------------------------
# 12. 翻转第 k 位
# ------------------------------------------------------------

n ^= (1 << k)

# 原来是 0 -> 变 1
# 原来是 1 -> 变 0


# ------------------------------------------------------------
# 13. 取最低位的 1
# ------------------------------------------------------------

lowbit = n & -n

# 例如：
#
# n = 12
# 二进制：1100
#
# n & -n -> 0100 -> 4

12 & -12        # 4

10 & -10        # 2

8 & -8          # 8


# 常用于：
# Fenwick Tree / 树状数组
# 统计二进制中 1 的个数


# ------------------------------------------------------------
# 14. 删除最低位的 1
# ------------------------------------------------------------

n = n & (n - 1)

# 例如：
#
# n = 12
# 1100
#
# n - 1
# 1011
#
# n & (n - 1)
# 1000


# 常用于统计二进制中 1 的个数：

count = 0

while n:
    n &= n - 1
    count += 1


# ------------------------------------------------------------
# 15. 判断是否是 2 的幂
# ------------------------------------------------------------

# 2 的幂二进制中只有一个 1：
#
# 1  -> 0001
# 2  -> 0010
# 4  -> 0100
# 8  -> 1000

if n > 0 and (n & (n - 1)) == 0:
    print("是 2 的幂")


# ------------------------------------------------------------
# 16. 二进制中 1 的个数
# ------------------------------------------------------------

# 方法 1：Python 内置

n.bit_count()

# 例如：

13.bit_count()
# 13 = 1101
# -> 3


# 方法 2：

count = 0

while n:
    n &= n - 1
    count += 1


# ------------------------------------------------------------
# 17. 状态压缩
# ------------------------------------------------------------

# 用一个整数的每一位表示一个状态：
#
# 第 0 位 -> 状态 0
# 第 1 位 -> 状态 1
# 第 2 位 -> 状态 2
# ...


# 判断第 i 个状态是否存在：
if state & (1 << i):
    ...
# 加入第 i 个状态：
state |= (1 << i)
# 删除第 i 个状态：
state &= ~(1 << i)
# 切换第 i 个状态：
state ^= (1 << i)
# 判断 state 中第 i 位：
if state & (1 << i):
    ...



# ============================================================
# 核心记忆
# ============================================================

# &   与：都为 1 才是 1
# |   或：有 1 就是 1
# ^   异或：不同为 1，相同为 0
# ~   取反
# <<  左移：乘 2
# >>  右移：除 2（非负整数）

# x ^ x = 0
# x ^ 0 = x

# n & 1
# 判断奇偶

# n & (1 << k)
# 判断第 k 位

# n & -n
# 取最低位的 1

# n & (n - 1)
# 删除最低位的 1

三、搜索

滑动窗口

（注：滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。）

定长滑窗：枚举所有长为固定值长度的windows

不定长滑窗：枚举所有长为可变值长度的windows求，最长子数组，求最短子数组，求子数组个数

模板：

  
#力扣438. 找到字符串中所有字母异位词
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        #建立窗口
        count_p = Counter(p)
        window_count  = Counter(s[:len(p)])
        # 检查初始窗口
        if window_count  == count_p:
            ans.append(0)
  
        for i in range(len(s)-len(p)):
            # 移除左边元素
            window_count[s[i]]-=1
            if window_count[s[i]]==0:
                del window_count[s[i]]
            # 添加新元素到窗口
            window_count[s[i+len(p)]] += 1
            # 对该窗口进行计算
            if window_count == count_p:
                ans.append(i+1)
        return ans

深度优先
广度优先

二分查找

判断能不能二分答案，最重要看三个条件：

答案是一个范围里的数
给定一个候选答案 x，能够判断 x 是否可行
这个“可行/不可行”具有单调性

“最小化最大值”或者“最大化最小值”，优先想二分答案。

第一种，找“第一个满足条件”的位置：

  
# 位置:     1  2  3  4  5  6
# check:    F  F  F  T  T  T
while left < right:
    mid = (left + right) // 2
     
    if check(mid):
        right = mid
    else:
        left = mid + 1
     
return left

第二种，找“最后一个满足条件”的位置：

  
# 位置:     1  2  3  4  5  6
# check:    T  T  T  T  F  F
while left < right:
    mid = (left + right + 1) // 2
     
    if check(mid):
        left = mid
    else:
        right = mid - 1
     
return left

四、图论

深度优先搜索

模板

  
result = []
path = []
#回溯算法
def dfs(参数):
    if（终止条件）：
        存放结果
        return
    for i in (选择：本节点所连接的其他节点):
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    return

广度优先搜索
并查集
拓扑排序
岛屿问题

路径问题

所有可能路径(适合深度优先)

  
class Solution:
    def __init__(self):
        self.result = []
        self.path = [0]
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        if not graph: return []
        self.dfs(graph, 0)
        return self.result
    def dfs(self, graph, root: int):
        if root == len(graph) - 1:  # 成功找到一条路径时
            # ***Python的list是mutable类型***
            # ***回溯中必须使用Deep Copy***
            self.result.append(self.path[:]) 
            return        
        for node in graph[root]:   # 遍历节点n的所有后序节点
            self.path.append(node)
            self.dfs(graph, node)
            self.path.pop() # 回溯

五、数论

判断素数

  
    def is_prime(self, n: int) -> bool:
        return all(n % i for i in range(2, isqrt(n) + 1))

判断闰年

  
def is_leap_year(year):
    if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
        return True
    else:
        return False

回文数Manacher 算法
前缀和

两个数的最大值

在数学上对于两个数的最大值，有下面的等式：

  
class Solution:
    def maximum(self, a: int, b: int) -> int:
        return int((sqrt(pow(a-b,2)) + a + b)/2)
#同理求最小值
class Solution:
    def maximum(self, a: int, b: int) -> int:
        return int(-(sqrt(pow(a-b,2)) + a + b)/2)

附录

输入

  
#输入一个
num=input()
#输入多个,一行
#1.一行输入多个字符
a,b=input().split()（空格隔开）
a,b=input().split(',')（',' 隔开）
#2.一行输入多个数字
a,b=map(int,input().split()) （空格隔开）
#3.列表的输入
a=list(map(int,input().split()))
import sys
#输入数组
for line in sys.stdin:
    a = line.split()

输出

  
#输出
print()
#1.sep和end的使用
#end: 默认是换行，表示两个字符串最后以什么结尾。
#sep: 默认是空格，表示两个字符串之间用什么分割。
>>print('a',end=" ")
>>print('b')
>> a b
>>print('a','b',sep=',')
>>a,b
#2.%实现多个变量的输出
>>a='闰年'
>>b=366
>>print("%s是%d天"%(a,b))
>>闰年是366天
#字符输出
’%4d’ % ( a )
输出一个4个字节宽度的整数字符串，如果整数 a 不满 4 个字节，就在左侧补上空格，即先填满右侧的位置。
’%-4d’ % ( a )
输出一个4个字节宽度的整数字符串，如果整数 a 不满 4 个字节，就在右侧补上空格，即先填满左侧的位置。
’%.4d’ % ( a ) 与 ‘%04d’ % ( a )
输出一个4个字节宽度的整数字符串，如果整数 a 不满 4 个字节，就在左侧空余位置补上0。
’%.2f’ % ( a ) 与 ‘%.02f’ % ( a )
输出一个小数位数为 2 位的浮点数字符串，如果小数位数不满 2 位，则在尾部补0。
’%4.2f’ % ( a )
输出一个总位数为 4 位，小数位数为 2 位的浮点数字符串。

时间

  
#datetime()函数
#1.赋值 
tody=datetime.date(2023,4,7)
#2.判断星期几：
week=today.weekday() 若为星期一则返回0
#3.单独获取年月日：
today.strftime("%d") 日
today.strftime('%m') 月
today.strftime('%y') 年
#4.天数加一：
delay = datetime.timedelta(days = 1)
tomorrow=today+delay

子数组、子序列、字串

子数组：一个或连续多个数组中的元素组成一个子数组（子数组最少包含一个元素）
子序列：子序列就是在原来序列中找出一部分组成的序列（子序列不一定连续）
子串定义：字符串中任意个连续的字符组成的子序列称为该串的子串（子串可以为空）

Algorithm Notes

I. Data Structures

(0) Numbers, Lists, Strings, Sets, Dictionaries

Numbers

  
# ============================================================
# Python number operations quick reference
# ============================================================


# ------------------------------------------------------------
# 1. Rounding
# ------------------------------------------------------------

round(nums)
# Round to the nearest integer
# Note: for exact x.5 cases, Python uses "round half to even"

round(2.4)       # 2
round(2.6)       # 3
round(2.5)       # 2
round(3.5)       # 4


int(nums)
# Truncate toward 0, i.e. simply drop the fractional part
int(3.9)         # 3
int(-3.9)        # -3


# ------------------------------------------------------------
# 2. Base conversion: string -> integer
# ------------------------------------------------------------

int('255')        # decimal string -> 255
int('FF', 16)     # hexadecimal -> 255
int('ff', 16)     # hex works in either case -> 255
int('1010', 2)    # binary -> 10
int('777', 8)     # octal -> 511
int('001')        # decimal, leading 0 ignored automatically -> 1


# ------------------------------------------------------------
# 3. Base conversion: integer -> string
# ------------------------------------------------------------

bin(10)
# -> '0b1010'
# 0b is the binary prefix


oct(8)
# -> '0o10'
# 0o is the octal prefix


hex(255)
# -> '0xff'
# 0x is the hexadecimal prefix


# ---------- format-string style ----------

f'{255:b}'        # '11111111'  binary
f'{255:o}'        # '377'       octal
f'{255:x}'        # 'ff'        lowercase hexadecimal
f'{255:X}'        # 'FF'        uppercase hexadecimal

# If you don't want the 0b / 0o / 0x prefix, the format style is usually more convenient:

number = 10

f'{number:b}'     # '1010'
f'{number:o}'     # '12'
f'{number:x}'     # 'a'
f'{number:X}'     # 'A'


# ------------------------------------------------------------
# 4. Floor division / modulo / divmod
# ------------------------------------------------------------

# ---------- // floor division ----------

a // b
# // rounds toward negative infinity, not toward 0

17 // 5           # 3
-17 // 5          # -4

# ---------- % modulo ----------

a % b


# ---------- divmod: quotient and remainder at once ----------

q, r = divmod(a, b)



# ------------------------------------------------------------
# 5. Using modulo % for cycles / rings
# ------------------------------------------------------------

# Core idea: x % n always falls in 0 ~ n-1, so it is perfect for cyclic indices, directions, and periodicity.


# ---------- Example 1: cycle through characters ----------

chars[(cnt - 1) % len(chars)]


# ---------- Example 2: cyclic direction ----------
# Assume:
# 0 = up, 1 = right, 2 = down, 3 = left
direction = (direction + 1) % 4 # turn right
direction = (direction - 1) % 4 # turn left

# ---------- Example 3: circular array indices ----------

next_index = (i + 1) % n
# after the last position, the next one wraps back to 0
prev_index = (i - 1) % n
# before index 0, the previous one wraps to n-1

# ---------- Example 4: end position of a period ----------

best_end = (best_start + max_length - 1) % n

Lists

  

# ------------------------------------------------------------
# General principle: lists are mutable. append / extend / insert / remove / pop / sort etc. modify the list in place.
# ------------------------------------------------------------



# ------------------------------------------------------------
# 1. Search / count
# ------------------------------------------------------------

nums = [10, 20, 30, 20]


# ---------- index: position of the first occurrence ----------

nums.index(20)

# Note: lists have no find() method! index() raises ValueError when the element is missing.
# If you are unsure whether the element exists, check with in first:

if 20 in nums:
    index = nums.index(20)

# ---------- count: number of occurrences ----------
nums.count(20)

# ---------- max / min ----------
max(nums)
min(nums)

# Position of the max/min. Note: if the max value occurs multiple times, index() returns only the first position.
nums.index(max(nums))
nums.index(min(nums))

# ------------------------------------------------------------
# 2. Adding elements
# ------------------------------------------------------------
# ---------- append: add a single element at the end ----------
a.append(4)

# ---------- extend: add several elements at the end ----------
a.extend([3, 4])

# ---------- insert: insert at a given position ----------
a.insert(0, 100)  # a.insert(index, element)

# ------------------------------------------------------------
# 3. Removing elements
# ------------------------------------------------------------

# ---------- remove: remove by value ----------
a.remove(20) # if there are duplicates, only the first is removed. Raises ValueError if absent.

# ---------- pop: remove by index and return the removed element ----------
x = a.pop(1) # no index: removes the last element by default

# ---------- del: delete by index directly ----------

del a[1]
del a[1:3]


# ------------------------------------------------------------
# 4. Reversing a list
# ------------------------------------------------------------

a.reverse()
b = a[::-1]

Strings

  
# ============================================================
# Python string operations quick reference
# ============================================================

# ------------------------------------------------------------
# General principle: strings are immutable
# ------------------------------------------------------------

# String methods usually do NOT modify the original string; they return a new string.
# So many operations require assigning the result back to a variable.

line = "   hello"
line.lstrip()            # the original line is unchanged
line = line.lstrip()     # correct


# ------------------------------------------------------------
# 1. Case conversion
# ------------------------------------------------------------

s = "i Love YOU"

s.lower()          # all lowercase -> 'i love you'
s.upper()          # all uppercase -> 'I LOVE YOU'
s.swapcase()       # swap case -> 'I lOVE you'
s.capitalize()     # first char of the whole string upper, rest lower -> 'I love you'
s.title()          # first letter of each word upper -> 'I Love You'


# ------------------------------------------------------------
# 2. Search / count
# ------------------------------------------------------------

s = "sdfWFSDss"

s.find('s')        # index of the first 's'; returns -1 if not found
s.rfind('s')       # index of the last 's'; returns -1 if not found
s.index('s')       # like find, but raises ValueError if not found
s.count('s')       # number of occurrences of 's'


# ------------------------------------------------------------
# 3. Replace
# ------------------------------------------------------------

s.replace('s', 'b')          # replace all 's' with 'b'
s.replace('s', 'b', 1)       # replace only the first 1

text = "1,2,3"
text = text.replace(',', ' ') # '1 2 3'


# ------------------------------------------------------------
# 4. Strip leading/trailing whitespace or specified characters
# ------------------------------------------------------------

line = "   hello   "

line = line.lstrip()     # strip left whitespace
line = line.rstrip()     # strip right whitespace
line = line.strip()      # strip whitespace on both sides

"00032".lstrip('0')      # '32'
"-3".lstrip('-')         # '3'

# Note:
# the argument to strip / lstrip / rstrip is a SET of characters, not a full prefix/suffix

"abcahelloabc".strip('abc')   # 'hello'

# strip('abc') means:
# keep removing any of a / b / c from both ends


# ------------------------------------------------------------
# 5. Split / join
# ------------------------------------------------------------

# ---------- split: string -> list ----------

input_str = "489607   minute"

input_str.split()
# no argument:
# split on any whitespace
# consecutive whitespace is merged
# -> ['489607', 'minute']


item = "a|b|c|d"

item.split('|')
# with a separator
# -> ['a', 'b', 'c', 'd']


"a||b".split('|')
# -> ['a', '', 'b']
# with an explicit separator, consecutive separators produce empty strings


# ---------- join: list -> string ----------

result = ['I', 'love', 'you']

' '.join(result)
# -> 'I love you'

''.join(result)
# -> 'Iloveyou'


chars = ['a', 'b', 'c']

''.join(chars)
# -> 'abc'




# ------------------------------------------------------------
# 6. Prefix / suffix checks
# ------------------------------------------------------------

line = "hello.py"

line.startswith('he')        # True
line.endswith('.py')         # True

# check several suffixes at once
line.endswith(('.jpg', '.png', '.py'))


# ------------------------------------------------------------
# 7. Character type checks
# ------------------------------------------------------------

"123".isdigit()          # all digits? -> True
"abc".isalpha()          # all letters? -> True
"ABC".isupper()          # all uppercase letters? -> True
"abc".islower()          # all lowercase letters? -> True
"   ".isspace()          # all whitespace characters? -> True

"-3".isdigit()           # False


# Simple check for a negative integer

value = "-123"

value.lstrip('-').isdigit()
# True


# Note:
"--3".lstrip('-').isdigit()
# True

# because lstrip('-') removes ALL leading '-'
# so this method is only a rough check, not fully rigorous


# More rigorous:
try:
    int(value)
    is_integer = True
except ValueError:
    is_integer = False


# ------------------------------------------------------------
# 8. Character <-> Unicode code point
# ------------------------------------------------------------

ord('A')             # char -> Unicode code point, e.g. 65
chr(65)              # code point -> char, e.g. 'A'

ord('中')            # Chinese works too
chr(ord('中'))       # '中'


# ------------------------------------------------------------
# 9. Padding / alignment
# ------------------------------------------------------------

# ---------- zfill: pad with 0 on the left ----------

'1010'.zfill(8)      # '00001010'
'1010'.zfill(4)      # '1010'
'1010'.zfill(2)      # '1010', never truncates
'5'.zfill(3)         # '005'

# zfill handles the sign specially
'-3'.zfill(5)        # '-0003'


# ---------- rjust: right align, pad on the left ----------

'7'.rjust(3, '0')    # '007'
'x'.rjust(3, '-')    # '--x'

# rjust does NOT handle the sign specially
'-3'.rjust(5, '0')   # '000-3'


# ---------- ljust: left align, pad on the right ----------

'7'.ljust(3, '0')    # '700'


# ---------- center: center align ----------

'7'.center(3, '0')   # '070'
'abc'.center(7, '-') # '--abc--'

  
f"{var:[fill][align][width][.precision][type]}"

# [fill]: any single character, e.g. 0, *, -, space
# [align]: < left, > right, ^ center, = pad after the sign
# [width]: minimum total width, e.g. 5, 8, 10
# [.precision]: mainly for floats, number of decimal places
#          .2f -> 2 decimal places
#          .3f -> 3 decimal places
#          e.g. f"{3.14159:.2f}" -> '3.14'
#
# [type]:
# d   decimal integer
# b   binary
# o   octal
# x   lowercase hexadecimal
# X   uppercase hexadecimal
# f   ordinary float, usually used with .precision
# e/E scientific notation
# %   percentage, usually used with .precision


# Examples:
f"{7:05d}"          # '00007'
f"{10:08b}"         # '00001010'
f"{255:04X}"        # '00FF'

f"{3.14159:.2f}"    # '3.14'
f"{3.14159:8.2f}"   # '    3.14'  total width 8, 2 decimals
f"{0.2567:.2%}"     # '25.67%'

Sets

  
s = set(numbers)                 # deduplicate a list
array = list(set(array_a + array_b))    # union and deduplicate (order is shuffled)
vowels = set('aeiouAEIOU')       # string -> set, O(1) lookup
x in s                           # O(1) membership test
s.add(x) / s.remove(x)           # add / remove
`set` elements must be **hashable**: a `list` cannot go in, convert it to a `tuple`.

Dictionaries

  
# ============================================================
# Python dict
# ============================================================


# ------------------------------------------------------------
# 1. Basic creation
# ------------------------------------------------------------
d = {}
d = dict()

# ------------------------------------------------------------
# 2. Access
# ------------------------------------------------------------
d['a']                  # get value; KeyError if the key is missing
d.get('a')              # returns None if the key is missing
d.get('a', 0)           # returns the default 0 if the key is missing

# ------------------------------------------------------------
# 3. Iteration
# ------------------------------------------------------------

# iterate over key and value together
for key, value in my_dict.items():
    print(key, value)
# keys only
for key in my_dict:
    print(key)
for key in my_dict.keys():
    print(key)
# values only
for value in my_dict.values():
    print(value)

# sum of values
sum(my_dict.values())


# ------------------------------------------------------------
# 4. Deleting while iterating
# ------------------------------------------------------------

# You cannot iterate a dict and change its size at the same time; convert to a list first:
for key, value in list(d.items()):
    if value == 0:
        del d[key]


# ------------------------------------------------------------
# 5. Deletion
# ------------------------------------------------------------

# ---------- del ----------
del d[key]

# ---------- pop ----------
value = d.pop(key)
value = d.pop(key, None)


# ------------------------------------------------------------
# 6. Check whether a key exists
# ------------------------------------------------------------
if key in d:
if key not in d:



# ------------------------------------------------------------
# 7. Counting / accumulating with a dict
# ------------------------------------------------------------
counter = {}

if x not in counter:
    counter[x] = 0
counter[x] += 1

from collections import defaultdict
counter = defaultdict(int)
counter[x] += 1

# ------------------------------------------------------------
# 8. Sorting a dict
# ------------------------------------------------------------

# sort by (key, value), by key by default:

sorted(dic.items())

# ---------- sort by key ----------
sorted(dic.items(), key=lambda x: x[0])

# ---------- sort by value ----------
sorted(dic.items(), key=lambda x: x[1])



# ============================================================
# defaultdict
# ============================================================

from collections import defaultdict
# ---------- default empty list ----------
d = defaultdict(list)
# ---------- default integer 0 ----------
counter = defaultdict(int)
# ---------- default custom value ----------
log = defaultdict(lambda: [0, 0])


# ============================================================
# Counter
# ============================================================

from collections import Counter
want = Counter(favorites)

# get the count of an element directly; a missing key returns 0
want[1]
# sum of all counts:
sum(want.values())


cnt = Counter("aabccc")
# {'c': 3, 'a': 2, 'b': 1}
cnt.most_common()
# [('c', 3), ('a', 2), ('b', 1)]
cnt.most_common(2)
# the 2 most common elements

(1) Linked Lists

Singly linked list

  
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
           
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = nextclass SingleLinkList:   
    def __init__(self,node=None):
        self.__head=node        
    # whether the list is empty
    def is_empty(self):
        return self.__head==None        
    # length of the list
    def length(self):
        point=self.__head
        count=0
        while point != None:
            count+=1
            point=point.next
        return count                    
    # traverse the list
    def travel(self):
        point=self.__head
        while point != None:
            print(point.val)
            point=point.next                   
    # add an element at the head
    def add(self, item):
        node=ListNode(item)
        node.next=self.__head
        self.__head=node    
    # append an element at the tail
    def append(self, item):
        node=ListNode(item)
        point = self.__head
        if self.is_empty():
            self.__head=node
        else:
            while point.next != None:
                point=point.next
            point.next=node            
    # insert an element at a given position
    def insert(self,pos,item):
        node=ListNode(item)
        point=self.__head
        if pos<=0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            for i in range(0,pos-1):
                point=point.next
            node.next=point.next
            point.next=node      
    # delete a node
    def remove(self,item):
        point=self.__head
        while point.next!=None:
            if point.next.val==item:
                point.next=point.next.next
                break
            else:
                point=point.next
    # check whether a node exists
    def search(self, item):
        point=self.__head
        while point!=item:
            if point!=item:
                return True
            else:
                point=point.next
        return False

Doubly linked list

  
class ListNode: 
    def __init__(self, val=0, next=None,prev=None):
        self.val = val
        self.next = next
        self.prev = prev
class DoubleLinkList():    
    def __init__(self,node=None):
        self.__head=node              
    # whether the list is empty
    def is_empty(self):
        return self.__head is None        
    # length of the list
    def length(self):
        point=self.__head
        count=0
        while point != None:
            count+=1
            point=point.next
        return count                    
    # traverse the list
    def travel(self):
        point=self.__head
        while point != None:
            print(point.val)
            point=point.next                    
    # add an element at the head
    def add(self, item):
        node=ListNode(item)
        node.next=self.__head
        self.__head=node
        node.next.prev=node            
    # append an element at the tail
    def append(self, item):
        node=ListNode(item)
        point = self.__head
        if self.is_empty():
            self.__head=node
        else:
            while point.next != None:
                point=point.next
            point.next=node
            node.prev=point            
    # insert an element at a given position
    def insert(self,pos,item):
        node=ListNode(item)
        point=self.__head
        if pos<=0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            for i in range(0,pos-1):
                point=point.next
            node.next=point.next
            node.next.perv=node
            point.next=node
            node.prev=point      
    # delete a node
    def remove(self,item):
        point=self.__head
        while point.next!=None:
            if point.next.val==item:
                point.next=point.next.next
                point.next.prev=point
                break
            else:
                point=point.next
    # check whether a node exists
    def search(self, item):
        point=self.__head
        while point!=item:
            if point!=item:
                return True
            else:
                point=point.next
        return False

Singly circular linked list

(2) Stacks and Queues

  
from collections import deque

q = deque()      					# build a deque from a list
q.pop()           				# pop from the right
q.popleft()               # pop from the left, O(1) (list.pop(0) is O(n))
q.append(x)               # enqueue on the right
q.appendleft(x)           # enqueue on the left
q[0]                      # peek the front/top (without popping)

FILO stack

  
stack = [1,2.3]
stack.append(x)  # push operation
stack.pop()  # pop operation, pops the last element by default
print(stack[-1])  # get the top element
   
class Stack:
    def __init__(self):
        self._stack = deque()
   
    def push(self, item):
        self._stack.append(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Popping from an empty stack")
        return self._stack.pop()
   
    def is_empty(self):
        return len(self._stack) == 0
   
    def size(self):
        return len(self._stack)

Monotonic stack

  
class MonotonicStack:
    def __init__(self):
        self._stack = deque()
   
    def push(self, item):
        # Pop all elements in the stack that are smaller than the current element
        while self._stack and self._stack[-1] < item:
            self._stack.pop()
        self._stack.append(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Popping from an empty stack")
        return self._stack.pop()
   
    def top(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack[-1]
   
    def is_empty(self):
        return len(self._stack) == 0
   
    def size(self):
        return len(self._stack)

FIFO queue

  
queue = [1,2.3]
queue.append(x)  # enqueue operation
queue.pop(0)  # dequeue operation, pops the last element by default
   
class FIFO:
    def __init__(self):
        self._queue = deque()
   
    def push(self, item):
        self._queue.append(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Dequeuing from an empty queue")
        return self._queue.popleft()
   
    def is_empty(self):
        return len(self._queue) == 0
   
    def size(self):
        return len(self._queue)

Deque

  
class Deque:
    def __init__(self):
        self._deque = deque()
   
    def append(self, item):
        self._deque.append(item)
   
    def appendleft(self, item):
        self._deque.appendleft(item)
   
    def pop(self):
        if self.is_empty():
            raise IndexError("Popping from an empty deque")
        return self._deque.pop()
   
    def popleft(self):
        if self.is_empty():
            raise IndexError("Popping from an empty deque")
        return self._deque.popleft()
   
    def is_empty(self):
        return len(self._deque) == 0
   
    def size(self):
        return len(self._deque)

Monotonic queue

  
class MonotonicQueue: # monotonic queue (from large to small)
    def __init__(self):
        self.queue = deque() # a deque is required here; using a list directly would time out
       
    # On each pop, compare whether the value to pop equals the value at the queue exit, and pop it if so.
    # Also check whether the queue is currently empty before popping.
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()# list.pop() is O(n), so collections.deque() is required here
               
    # If the pushed value is greater than the value at the entry, pop values from the back of the queue
    # until the pushed value is less than or equal to the value at the entry.
    # This keeps the queue monotonic from large to small.
    def push(self, value):
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
           
    # Query the maximum in the queue: just return the front of the queue.
    def front(self):
        return self.queue[0]
    def is_empty(self):
        return len(self._queue) == 0
    def size(self):
        return len(self._queue)

(4) Heaps

Heap storage
Heaps are usually stored as a list
For a node with index \(i\)
Left child index \(2i+1\)
Right child index \(2i+1\)

Heap operations

Sift up: append a new element at the end of the heap, complexity \(O(logN)\), where \(N\) is the number of levels

  
def heapify_up(heap, index):
    """
    - heap: A list representing the heap.
    - index: The index of the element to be heapified up.
    """
    parent_index = (index - 1) // 2
    while index > 0 and heap[index] > heap[parent_index]:
        # Swap the element with its parent if it's greater
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        # Update the index and parent_index for the next iteration
        index = parent_index
        parent_index = (index - 1) // 2
             
# Example usage:
heap = [10, 8, 7, 6, 5, 3, 2, 1]
new_element = 9
heap.append(new_element)  # Add the new element to the end of the heap
heapify_up(heap, len(heap) - 1)  # Perform heapify-up operation on the new element

Sift down: add a new element at the heap head, complexity \(O(logN)\), where \(N\) is the number of levels

  
def heapify_down(heap, index):
    # Get the indices of the left and right children
    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2
         
    # Find the parent element among the current node and its children
    parent_index = index
         
    if left_child_index < len(heap) and heap[left_child_index] > heap[parent_index]:
        parent_index = left_child_index
         
    if right_child_index < len(heap) and heap[right_child_index] > heap[parent_index]:
        parent_index = right_child_index
         
    # If the parent element is not the current node, swap it with the parent child and sift down
    if parent_index != index:
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        heapify_down(heap, parent_index)
     
# Example usage
heap = [1, 7, 6, 4, 5, 1, 2]  # Example heap
print("Before sift down:", heap)
heapify_down(heap, 0)  # Perform sift down operation

Building a heap

Top-down heap construction: complexity \(O(NlogN)\)

  
def heapify_up(heap, index):
         
    parent_index = (index - 1) // 2
         
    while index > 0 and heap[index] > heap[parent_index]:
        # Swap the element with its parent if it's greater
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        # Update the index and parent_index for the next iteration
        index = parent_index
        parent_index = (index - 1) // 2
             
def setup_heapify(arr):
    for i in range(0,len(arr)):
        heapify_up(arr, i)
     
nums=[3,4,5,6,1,7,8]
setup_heapify(nums)

Bottom-up heap construction: complexity \(O(N)\)

  
def heapify_down(heap, index):
    # Get the indices of the left and right children
    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2
         
    # Find the parent element among the current node and its children
    parent_index = index
         
    if left_child_index < len(heap) and heap[left_child_index] > heap[parent_index]:
        parent_index = left_child_index
         
    if right_child_index < len(heap) and heap[right_child_index] > heap[parent_index]:
        parent_index = right_child_index
         
    # If the parent element is not the current node, swap it with the parent child and sift down
    if parent_index != index:
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        heapify_down(heap, parent_index)
     
def setup_heapify(arr):
    n = len(arr)
    # Start from the last non-leaf node and sift down upward one by one
    for i in range(n // 2 - 1, -1, -1):
        heapify_down(arr, i)
     
nums=[3,4,5,6,1,7,8]
setup_heapify(nums)

Heap sort: see Sorting 3

(5) Hash Tables

Choosing the hash table structure
Array as a hash table: the size of an array is limited; for a limited set of keys, an array is the most suitable hash table
set as a hash table: it does not restrict the magnitude of values, so an array can no longer serve as the hash table. Main reasons:
- The size of an array is limited and constrained by system stack space (not the stack data structure).
- If the array is large enough but the hash values are few, very scattered, or span a huge range, using an array wastes a lot of space.
map as a hash table: the limitations of using arrays and sets for hashing
- The size of an array is limited, and if there are few elements but the hash values are large, memory is wasted.
- A set is a collection; the only thing it can hold as an element is a key

Sum problems

Two Sum (using a hash table)

  
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashtable=dict()
    for i, num in enumerate(nums):
        if target-num in hashtable:
            return [hashtable[target-num],i]
        else:
            hashtable[num]=i
                     

Three Sum (using two pointers)

  
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans=[]
        for i in range(len(nums)):
            if nums[i]>0:return ans
            if i>0 and nums[i]==nums[i-1]:
                continue
            left=i+1
            right=len(nums)-1
            while right>left:
                sum=nums[i]+nums[left]+nums[right]
                if sum>0:
                    right-=1
                elif sum<0:
                    left+=1
                else:
                    ans.append([nums[i],nums[left],nums[right]])
                    left+=1
                    right-=1
                    while  right>left and nums[right]==nums[right+1]:
                        right-=1
                    while  right>left and nums[left]==nums[left-1]:
                        left+=1
                             
        return ans

Four Sum (using two pointers)

  
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans=[]
        n=len(nums)
        for k in range(n):
            if target>0 and nums[k]>target:# pruning
                break
            if k>0 and nums[k]==nums[k-1]:
                continue
            for i in range(k+1,n):
                if target>0 and nums[i]+nums[k]>target:# pruning
                    break 
                if i>k+1 and nums[i]==nums[i-1]:  
                    continue
                left=i+1
                right=n-1
                while right>left:
                    sum=nums[k]+nums[i]+nums[left]+nums[right]
                    if sum>target:
                        right-=1
                    elif sum<target:
                        left+=1
                    else:
                        ans.append([nums[k],nums[i],nums[left],nums[right]])
                        right-=1
                        left+=1
                        while right>left and nums[right]==nums[right+1]:
                            right-=1
                        while right>left and nums[left]==nums[left-1]:
                            left+=1
        return ans

(6) Binary Trees

Basic concepts

Term	中文	Description
Root	根节点	The top node of a tree
Child	孩子结点	The root of a subtree contained in a node is called a child of that node
Leaf	叶子结点	A node with no children
Degree	度	The number of subtrees a node contains
Edge	边	The connection between one node and another
Depth	深度	The number of edges from the root to this node
Height	节点高度	The number of edges on the path from the current node to a leaf
Level	层级	The total number of edges on the longest path from the node to the root
Path	路径	The sequence of edges and nodes passed between one node and another

Full Binary Tree: a special binary tree in which every node except the leaves has two children, and all leaves are on the same level.

Complete Binary Tree: a binary tree in which all levels except the last are full, and the nodes of the last level are packed to the left. (A full binary tree is always complete, but a complete binary tree is not necessarily full.)

Binary Search Tree: a special binary tree in which all values in the left subtree are smaller than the root, and all values in the right subtree are larger than the root. Its left and right subtrees are also binary search trees.

Balanced Binary Tree: a special binary tree in which the height difference between the left and right subtrees is at most 1, keeping the tree balanced.

Huffman Tree: a special binary tree used by the Huffman coding algorithm for data compression. These are some common classifications of binary trees, each with its own properties and use cases.

Red-black tree

A node is red or black.
The root is black.
All leaves are black.
Every red node must have two black children. (Two consecutive red nodes cannot appear)
Every simple path from any node to each of its leaves contains the same number of black nodes.

Properties of binary trees

Property 1: The i-th level of a binary tree contains at most \(2^{(i-1)}\) nodes \((i>0)\)

Property 2: A binary tree of depth h contains at most \(2^{h}-1\) nodes

Property 3: In any binary tree with \(N_0\) leaves and \(N_2\) nodes of degree 2, we must have \(N_0=N_2+1\)

Property 4: A perfect binary tree with n nodes has depth \(\log_2(n+1)\)

Property 5: If a complete binary tree is numbered in order \((1≤i≤n)\), then for the node numbered \(i\): the left child is \(2i\); the right child is \(2i+1\); the parent is \(i//2\)

Building a binary tree

  
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None        

Build a binary tree from a level-order result (a level-order traversal uniquely determines a tree)

  
class Tree():    
    def __init__(self):        
        self.root=None
    # build the binary tree
    def add(self,item):
        node=TreeNode(item)
        queue=[self.root]
        if self.root is None:
            self.root = node
            return
        while queue:
            cur_node=queue.pop(0)
            if cur_node.left is None:
                cur_node.left = node
                return
            else:
                queue.append(cur_node.left)
            if cur_node.right is None:
                cur_node.right = node
                return
            else:
                queue.append(cur_node.right)

Build a binary tree from pre-order / in-order / post-order “left-right-root” sequences (only [in-order] + [pre-order or post-order] together uniquely determine a tree)

Binary tree traversal

Breadth-first traversal: level-order traversal

  
 # breadth-first traversal
def breadth_travel(self):
    if self.root is None:
        return
    queue=[self.root]
    while queue:
        cur_node=queue.pop(0)
        print(cur_node.val,end=' ')
        if cur_node.left is not None:
            queue.append(cur_node.left)
        if cur_node.right is not None:
            queue.append(cur_node.right)
# convenient for per-level processing
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = collections.deque([root])
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level)
        return result

Depth-first traversal

Pre-order traversal: root, left, right

In-order traversal: left, root, right

Post-order traversal: left, right, root

  
Recursive approach
# depth-first traversal - pre-order
def preorder_travel(self, node):
    if node is None:
        return
    print(node.val,end=' ')
    self.preorder_travel(node.left)
    self.preorder_travel(node.right)
# depth-first traversal - in-order
def inorder_travel(self, node):
    if node is None:
        return
    self.inorder_travel(node.left)
    print(node.val,end=' ')        
    self.inorder_travel(node.right)        
# depth-first traversal - post-order
def postorder_travel(self, node):
    if node is None:
        return
    self.postorder_travel(node.left)
    self.postorder_travel(node.right) 
    print(node.val,end=' ')
Stack approach
# pre-order
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # return an empty list if the root is empty
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # process the middle node first
            result.append(node.val)
            # push the right child first
            if node.right:
                stack.append(node.right)
            # push the left child afterwards
            if node.left:
                stack.append(node.left)
        return result
# in-order
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # the root cannot be pushed into stack in advance
        result = []
        cur = root
        while cur or stack:
            # first iterate down to the deepest left subtree node
            if cur:     
                stack.append(cur)
                cur = cur.left		
            # once the leftmost node is reached, process the stack top    
            else:		
                cur = stack.pop()
                result.append(cur.val)
                # take the right child of the stack top
                cur = cur.right	
        return result
# post-order
class Solution:
   def postorderTraversal(self, root: TreeNode) -> List[int]:
       if not root:
           return []
       stack = [root]
       result = []
       while stack:
           node = stack.pop()
           # process the middle node first
           result.append(node.val)
           # push the left child first
           if node.left:
               stack.append(node.left)
           # push the right child afterwards
           if node.right:
               stack.append(node.right)
       # reverse the resulting array
       return result[::-1]

Basic properties of binary trees

Depth of a binary tree

  
# maximum depth - post-order traversal
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def gethight(node):
            if node is None:
                return 0
            left=gethight(node.left)
            right=gethight(node.right)
            height=1+max(left,right)
            return height
        h=gethight(root)
        return h
# concise       
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return 1+max(self.maxDepth(root.left), self.maxDepth(root.right))
# maximum depth - level-order traversal
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res
# minimum depth - post-order traversal
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        def getheight(node):
            if node is None:
                return 0
            left=getheight(node.left)
            right=getheight(node.right)
            if node.left is None and node.right is not None:
                return 1+right
            if node.left is not None and node.right is None:
                return 1+left
            else:
                height=1+min(left,right)
                return height
        return getheight(root)
# minimum depth - level-order traversal
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0
        queue = collections.deque([root])        
        while queue:
            depth += 1 
            for _ in range(len(queue)):
                node = queue.popleft()                
                if not node.left and not node.right:
                    return depth            
                if node.left:
                    queue.append(node.left)                    
                if node.right:
                    queue.append(node.right)
        return depth 

Number of nodes in a complete binary tree

  
class Solution: # exploit the properties of a complete binary tree
    def countNodes(self, root: TreeNode) -> int:
        if not root: return 0
        count = 1
        left = root.left; right = root.right
        while left and right:
            count+=1
            left = left.left; right = right.right
        if not left and not right: # both reaching the bottom means it is a perfect binary tree, otherwise not
            return 2**count-1
        return 1+self.countNodes(root.left)+self.countNodes(root.right)

Summary
- When constructing a binary tree, whether an ordinary binary tree or a binary search tree, pre-order is always used, constructing the middle node first.
- To compute the properties of an ordinary binary tree, post-order is usually used, generally computing through the return value of the recursive function.
- To compute the properties of a binary search tree, in-order must be used, otherwise its ordering is wasted.
- Note that for the properties of an ordinary binary tree I generally use post-order; for example, when simply finding depth I use pre-order, and for “binary tree: find all paths” I also use pre-order, which conveniently lets the parent node point to the child node.

II. Basic Algorithms

(0) Common Python

(1) Sorting

Common usage of sort

  
# ============================================================
# Python sorting sort() / sorted() quick reference
# ============================================================


# ------------------------------------------------------------
# 1. sort() and sorted()
# ------------------------------------------------------------
nums.sort() # modifies the original list in place
new_nums = sorted(nums)# does not modify the original list


# ------------------------------------------------------------
# 2. Ascending / descending
# ------------------------------------------------------------
nums.sort()
nums.sort(reverse=False)     # ascending, default
nums.sort(reverse=True)      # descending

# ------------------------------------------------------------
# 3. key: specify "what to sort by"
# ------------------------------------------------------------

# key can be understood as: first convert each element into a "sort value", then sort by that value.
# It is a function that sort() calls once for each element.
# by length
words.sort(key=len)
# by absolute value
nums.sort(key=abs)

# write the key with lambda
# sort by the 1st element
data.sort(key=lambda x: x[0])
# key1 ascending, key2 ascending
data.sort(key=lambda x: (x[0], x[1]))
# key1 ascending, key2 descending
data.sort(key=lambda x: (x[0], -x[1]))

# sort strings ignoring case
words.sort(key=str.lower)
# same letter, lowercase first
chars.sort(key=lambda x: (x.lower(), x.isupper()))
# same letter, uppercase first
chars.sort(key=lambda x: (x.lower(), x.islower()))
# all lowercase first
chars.sort(key=lambda x: (x.isupper(), x.lower()))
# all uppercase first
chars.sort(key=lambda x: (x.islower(), x.lower()))


# Mixed ascending/descending for strings: if the second key is a string you cannot write -x[1];
# instead use Python's "stable sort": sort by the secondary key first, then by the primary key.
# Requirement: key1 ascending, key2 descending

data.sort(key=lambda x: x[1], reverse=True)   # secondary key
data.sort(key=lambda x: x[0])                 # primary key

  
# ============================================================
# zip / enumerate / range / map quick reference
# ============================================================

# 1. zip: parallel iteration / pairing
[x + y for x, y in zip(a, b)]
pairs = list(zip(a, b))
zip(*matrix)                  # matrix transpose
# Note: it is bounded by the shortest sequence


# 2. enumerate: get index and value together
for i, value in enumerate(a):
    ...

# i: index
# value: element


# 3. range: generate an integer sequence
range(n)                      # 0 ~ n-1
range(start, end)             # start ~ end-1
range(start, end, step)       # step size
range(len(a) - 1, -1, -1)    # reversed


# 4. map: apply a function to elements in bulk
map(int, a)                   # convert each element to int
map(str, a)                   # convert each element to str

nums = list(map(int, input().split()))
# common way to read multiple integers

Bubble sort

  
#%% bubble sort
def bubble_sort(arr):
    n = len(arr)
    # iterate over the array elements
    for i in range(n):
        # each pass moves the current largest element to the end of the array
        for j in range(0, n-i-1): 
            # if the current element is greater than the next, swap them
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  
#%% optimized bubble sort
def bubble_sort1(arr):
    n = len(arr)
    # iterate over the array elements
    exc=n-1
    for i in range(n):
        if exc==0:
            break
        for j in range(0, exc): 
            # if the current element is greater than the next, swap them
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                exc=j
            if exc==n-1:
                exc=0

Bubble sort optimization

  
#%% optimized bubble sort
def bubble_sort_opt(arr):
    n = len(arr)
    # iterate over the array elements
    exc=n-1
    for i in range(n):
        if exc==0:
            break
        for j in range(0, exc): 
            # if the current element is greater than the next, swap them
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                exc=j
            if exc==n-1:
                exc=0

Selection sort

  
#%% selection sort
def selection_sort(arr):
    n = len(arr)
    # iterate over the array
    for i in range(n-1, 0, -1):
        # find the index of the largest element in the unsorted part
        max_index = i
        for j in range(i):
            if arr[j] > arr[max_index]:
                max_index = j
        # swap the largest element with the end of the unsorted part
        arr[i], arr[max_index] = arr[max_index], arr[i]

Heap sort

  
#%% heap sort    
def heapdown(arr, n, i):
    '''
    Build a max-heap.
    Parameters
    ----------
    arr : list
        the heap
    n : int
        heap length
    i : int
        index of the node to sift down
    '''
    largest = i  # initialize the index of the largest element to the root
    l = 2 * i + 1  # index of the left child
    r = 2 * i + 2  # index of the right child

    # if the left child exists and is greater than the root, update the largest index
    if l < n and arr[l] > arr[largest]:
        largest = l

    # if the right child exists and is greater than the root, update the largest index
    if r < n and arr[r] > arr[largest]:
        largest = r

    # if the largest index is not the root, swap them and recurse
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapdown(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    # build a max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapdown(arr, n, i)
    # move the largest element to the end of the array step by step
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap the current root (largest element) with the last element
        heapdown(arr, i, 0)  # rebuild the max-heap; note the array length decreases 

Insertion sort

  
#%% insertion sort
def insertion_sort(arr):
    n = len(arr)
    # starting from the second element, insert each element into its proper position in the sorted sequence
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # move arr[i] to the left until an element smaller than it is found or the start of the array is reached
        while key < arr[j] and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        # insert key at the correct position
        arr[j + 1] = key

Insertion sort optimization

  
#%% optimized insertion sort (binary search)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
       
    return left  # if the target is not found, return the insertion position

def insertion_sort1_opt(arr):
    n = len(arr)
    # starting from the second element, insert each element into its proper position in the sorted sequence
    for i in range(1, n):
        key = arr[i]
        j = binary_search(arr[0:i],key)
        del arr[i]
        arr.insert(j, key)

Merge sort

  
#%% merge sort 
def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
       
    # compare the elements of the two halves and merge them into the result in order
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
   
    # append the remaining elements to the result
    result.extend(left[left_idx:])
    result.extend(right[right_idx:])
       
    return result     
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
       
    # split the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
   
    # recursively merge-sort the two halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
   
    # merge the sorted halves
    return merge(left_half, right_half)

Quick sort

  
#%% quick sort 
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
       
    pivot = arr[len(arr) // 2]  # choose the middle element as the pivot
    left = [x for x in arr if x < pivot]  # elements smaller than the pivot go to the left
    middle = [x for x in arr if x == pivot]  # elements equal to the pivot go in the middle
    right = [x for x in arr if x > pivot]  # elements greater than the pivot go to the right
       
    return quick_sort(left) + middle + quick_sort(right)

Shell sort

  
#%% shell sort 
def stepsequence(n):
    k=0
    step=0
    sequence=[]
    while True:
        if k%2==0:
            step=9*(pow(2,k)-pow(2,k/2))+1
        else:
            step=8*pow(2,k)-6*pow(2,(k+1)/2)+1
        if step>=n:
            break
        sequence.append(int(step))
        k+=1
    return sequence[::-1]
               
def shell_sort(arr):
    n = len(arr)
    sequence=stepsequence(n)
    for gap in sequence:
        # perform insertion sort for each gap
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # insertion sort on the subarray with the given gap
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp

Counting sort

  
#%% counting sort
def counting_sort(arr):
    # find the min and max of the array to be sorted
    min_val = min(arr)
    max_val = max(arr)
   
    # initialize the count array with length (max_val - min_val + 1), each count set to 0
    count = [0] * (max_val - min_val + 1)
   
    # count the occurrences of each element
    for num in arr:
        count[num - min_val] += 1
   
    # place the elements in the correct positions according to the count array
    sorted_arr = []
    for i in range(min_val, max_val + 1):
        sorted_arr.extend([i] * count[i - min_val])
   
    return sorted_arr

Radix sort

  
#%% radix sort
def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
   
    # count the occurrences of each element
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
   
    # convert the count array into a position array
    for i in range(1, 10):
        count[i] += count[i - 1]
   
    # build the output array
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
   
    # copy the output array back into the original array
    for i in range(n):
        arr[i] = output[i]
   
def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

(2) Recursion

Problems it solves:

① The data is defined recursively, such as Fibonacci numbers and factorials;

② The problem is solved by a recursive algorithm, such as GCD, the Tower of Hanoi, climbing stairs, and placing apples;

③ The data structure is defined recursively, such as binary tree depth-first traversal

Backtracking and depth-first search are also forms of recursion

Pseudo-code template

  
def recursion():
    if termination_condition:
        record_answer
        return
    action          # do the action while going down, pre-order traversal
    recursion(new_traversal)
    action          # do the action while coming back, post-order traversal

Fibonacci numbers

  
class Solution:
    def fib(self, n: int) -> int:        
        def recursion(n):
            if n<=1:
                return n
            return recursion(n-1)+recursion(n-2)
        return recursion(n)

Factorial

  
def recursion(n):
    if n==1:
        return 1
    return n*recursion(n-1)

Greatest common divisor
Euclidean algorithm: divide the larger of the two numbers by the smaller to get a remainder, then use the smaller number and the remainder as the new dividend and divisor and continue until the remainder is zero. At that point, the divisor in the last division is the GCD
1 2 3 4 5 6 7 def recursion(a,b): if a<b: a,b=b,a y=a%b if y==0: return b return recursion(b, y)
Subtraction-based method (subtractive Euclid): take the absolute values of the two numbers and subtract them to get the difference, then compare the difference with the smaller number. If the difference is less than the smaller number, use the difference and the smaller number as the new minuend and subtrahend and continue; if the difference is greater than or equal to the smaller number, stop. At that point, the smaller number is the GCD.
1 2 3 4 5 6 7 def recursion(a,b): if a<b: a,b=b,a diff=a-b if diff==0: return b return recursion(b,diff)

Tower of Hanoi

  
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
    n = len(A)        
    def recursion(n,A,B,C):
        if n==1:
            C.append(A.pop())
            return
        recursion(n-1, A, C, B)
        C.append(A.pop())
        recursion(n-1, B, A, C)

Placing apples

Place m identical apples on n identical plates; plates may be left empty. How many different ways are there?

Note: with 7 apples and 3 plates, (5, 1, 1) and (1, 5, 1) are considered the same way.

  
'''
Placing apples splits into two cases: one plate is empty, or every plate has at least one apple.
Let (m,n) be the total number of ways to place m apples on n plates.
1. Assume one plate is empty: the (m,n) problem becomes placing m apples on n-1 plates, i.e. solve (m,n-1).
2. Assume every plate has an apple: each plate has at least one apple, so at most m-n apples remain;
   the problem becomes placing m-n apples on n plates, i.e. solve (m-n, n).
'''
m,n=map(int,input().split())
def recursion(m,n):
    if m < 0 or n < 0:
        return 0
    elif m == 1 or n == 1:
        return 1
    else:
        return recursion(m,n-1)+recursion(m-n,n)
ans=recursion(m,n)
print(ans)

(3) Backtracking

Often used together with recursion; it is a pure brute-force search

Problems it solves: combinations, permutations, subsets, partition, chessboard

Every backtracking algorithm can be abstracted into a tree structure

Pseudo-code template

  
path=[]
ans=[]
def backtracking(params such as start_index, index):
    (pruning)
    if (termination condition):
        store the result
        return
    for i in (choices: the number of selectable elements in this level's set (pruning)):
        path.append()  process the node
        backtracking()## recursion
        path.pop()  backtrack, undo the processing
    return

Example

  
# combination sum
def combinationSum(candidates,target):
    path = []
    ans = []
    def backtracking(target,candidates,start_index):
        if sum(path)>target:return
        if sum(path)==target:
            ans.append(path.copy())
            return
        for i in range(start_index,len(candidates)):
            path.append(candidates[i])
            backtracking(target,candidates,i)
            path.pop()
        return
    backtracking(target,candidates,0)
    return ans
start_index controls permutation vs combination: with start_index it is a combination, without it is a permutation
For combinations: i vs i+1 controls whether an element can be used multiple times; i means it can be reused, i+1 means it can be used only once; to deduplicate, sort first and then skip
For permutations: use a used array to control whether an element can be used multiple times
def permute(self, nums: List[int]) -> List[List[int]]:
    path = []
    ans = []
    used = [False]*len(nums)
    def backtracking(nums):
        if len(path) == len(nums):
            ans.append(path.copy())
        if len(path) > len(nums): return
        for i in range(0, len(nums)):
            if used[i]:continue
            path.append(nums[i])
            used[i] = True
            backtracking(nums)
            used[i] = False
            path.pop()
        return
    backtracking(nums)
    return ans

(4) Greedy Problems

There is no fixed framework for greedy algorithms; the only difficulty is deducing a global optimum from local optima. The best approach is to try.

Basic steps:

Build a mathematical model to describe the problem;
Divide the problem to be solved into several subproblems;
Solve each subproblem and obtain its local optimum;
Combine the local optima of the subproblems into a solution to the original problem.

Common greedy problems

Knapsack problems, interval covering, activity selection, profit from price changes, multi-machine scheduling

(5) Dynamic Programming

Every state in dynamic programming must be derived from the previous state. This is what distinguishes it from greedy: greedy has no state derivation, it directly picks the local optimum.

Common greedy problems: knapsack problems, house robbery, stock problems, subsequence problems

The five steps of dynamic programming
- Determine the dp array (dp table) and the meaning of its indices
- Determine the recurrence formula
- Initialize the dp array
- Determine the iteration order
  If the problem asks for the maximum value a knapsack can carry, or whether the knapsack can be exactly filled, then either “knapsack first, items after” or “items first, knapsack after” works, because only the result is needed, not the process
  If the problem asks for the number of ways to fill the knapsack, then combinations use “knapsack first, items after”; permutations use “items first, knapsack after”, because the process matters
  For a complete knapsack iterate from small to large, for a 0-1 knapsack iterate from large to small
- Derive the dp array by example (print the dp array)

Knapsack problems

0-1 knapsack

N kinds of items, each item exists only once

2D dp array: \(dp[i][j]\) means: choosing freely from items with indices [0-i], put into a knapsack with remaining capacity j, what is the maximum total value

dp array initialization: knapsack capacity 0: \(dp[:][0] = 0\), item 1 weight: \(dp[0][weight[0]: bagweight + 1] = 0\)

Recurrence: \(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\)

Iteration order: items first then knapsack, or knapsack first then items, both work

  
def test_2_wei_bag_problem1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
     
    # 2D array
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]
     
    # initialization
    for j in range(weight[0], bagweight + 1):
        dp[0][j] = value[0]
     
    # the size of the weight array is the number of items
    for i in range(1, len(weight)):  # iterate items
        for j in range(bagweight + 1):  # iterate knapsack capacity
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
     
    return dp[-1][-1]

1D rolling dp array: in a 1D dp array, dp[j] means: for a knapsack of capacity j, the maximum total value of items it can carry is dp[j]

dp array initialization: all item values are greater than 0, so initialize the whole dp array to 0

Recurrence: \(dp[j] = max(dp[j], dp[j - weight[i]] + value[i])\)

Iteration order: iterate the knapsack in reverse order to ensure item i is placed only once

  
def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
     
    # initialization
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # iterate items
        for j in range(bagWeight, weight[i] - 1, -1):  # iterate knapsack capacity
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
     
    return dp[-1]

Complete knapsack

N kinds of items, each item is unlimited

2D dp array: \(dp[i][j]\) means: choosing freely from items with indices [0-i], put into a knapsack with remaining capacity j, what is the maximum total value

dp array initialization: knapsack capacity 0: \(dp[:][0] = 0\), item 1 weight: initialize by weight

Recurrence: \(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\)

Iteration order: items first then knapsack, or knapsack first then items, both work

def test_2_wei_bag_problem1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
     
    # 2D array
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]
     
    # initialization
    for j in range(weight[0], bagweight + 1):
        dp[0][j] = j//weight[0]*value[0]
     
    # the size of the weight array is the number of items
    for i in range(1, len(weight)):  # iterate items
        for j in range(bagweight + 1):  # iterate knapsack capacity
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
     
    return dp[-1][-1]

1D rolling dp array: in a 1D dp array, dp[j] means: for a knapsack of capacity j, the maximum total value of items it can carry is dp[j]

dp array initialization: all item values are greater than 0, so initialize the whole dp array to 0

Recurrence: \(dp[j] = max(dp[j], dp[j - weight[i]] + value[i])\)

Iteration order: iterate the knapsack in forward order to let item i be placed multiple times

  
def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    # initialization
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # iterate items
        for j in range(bagWeight, weight[i] - 1):  # iterate knapsack capacity
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
     
    return dp[-1]

Multiple knapsack
N kinds of items, each kind has a different quantity; each item has at most Mi copies available. Laying out the Mi copies is actually a 0-1 knapsack problem

Knapsack problem variants

Knapsack with attachments (Nowcoder HJ16)

  
N, m = map(int, input().split())
value = []
importance = []
zhufu = []
       
for i in range(m):
    v, p, q = map(int, input().split())
    value.append([v])
    importance.append([p * v])
    zhufu.append(q)
for i in range(m):
    if zhufu[i]!=0:
        if len(value[zhufu[i]-1])==1:
            value[zhufu[i]-1].append(value[zhufu[i]-1][0]+value[i][0])
            importance[zhufu[i]-1].append(importance[zhufu[i]-1][0]+importance[i][0])
        elif len(value[zhufu[i]-1])==2:
            value[zhufu[i]-1].append(value[zhufu[i]-1][0]+value[i][0])
            importance[zhufu[i]-1].append(importance[zhufu[i]-1][0]+importance[i][0])
                   
            value[zhufu[i]-1].append(value[zhufu[i]-1][1]+value[i][0])
            importance[zhufu[i]-1].append(importance[zhufu[i]-1][1]+importance[i][0])
                   
for i in range(m-1,0,-1):
    if zhufu[i]!=0:
        del value[i]
        del importance[i]
       
# dp array
dp=[[0]*int(N/10+1) for _ in range(len(value))]
       
# initialization
for k in range(len(value[0])):
    for i in range(value[0][k]//10,N//10+1):
        dp[0][i]=importance[0][k]
# iteration
for i in range(1,len(value)):
    for j in range(0,N//10+1):
        for k in range(len(value[i])):
            if j*10<value[i][k]:
                dp[i][j]=max(dp[i][j],dp[i-1][j])
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j],dp[i-1][j-value[i][k]//10]+imortance[i][k])
print(dp[-1][-1])
               

House robbery

You are a professional thief planning to rob houses along a street. Each house hides a certain amount of cash, and the only thing stopping you is that adjacent houses are connected by an anti-theft system, so if two adjacent houses are broken into on the same night the system will automatically call the police. Given an array of non-negative integers representing the amount of money in each house, compute the maximum amount you can rob in one night without triggering the alarm.

  
  # House Robber 1
  class Solution:
      def rob(self, nums: List[int]) -> int:
          if len(nums)<=2:
              return max(nums)
          dp=[0]*len(nums)
          dp[0]=nums[0]
          dp[1]=max(nums[1],nums[0])
          for i in range(2,len(nums)):
              dp[i]=max(dp[i-1],dp[i-2]+nums[i])
          return dp[-1]

You are a professional thief planning to rob houses along a street, each hiding a certain amount of cash. All houses here are arranged in a circle, meaning the first and the last house are adjacent. Also, adjacent houses are connected by an anti-theft system, so if two adjacent houses are broken into on the same night the system will automatically call the police. Given an array of non-negative integers representing the amount of money in each house, compute the maximum amount you can rob tonight without triggering the alarm.

  
  # House Robber 2
  class Solution:
      def rob(self, nums: List[int]) -> int:
          if len(nums)<=2:
              return max(nums)
          dp1=[0]*(len(nums)-1)
          dp1[0]=nums[0]
          dp1[1]=nums[0]
          for i in range(2,len(nums)-1):
              dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i])
          dp2=[0]*len(nums)
          dp2[0]=0
          dp2[1]=nums[1]
          for i in range(2,len(nums)):
              dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i])
  
          return max(dp1[-1],dp2[-1])  

The thief finds another feasible area to rob. This area has a single entrance, which we call root. Except for root, each house has exactly one “parent” house connected to it. After some reconnaissance, the clever thief realizes that “the arrangement of all houses in this area is like a binary tree”. If two directly connected houses are robbed on the same night, the houses will automatically call the police. Given the binary tree root. Return the maximum amount the thief can rob without triggering the alarm.

  
  # House Robber 3
  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  class Solution:
      def rob(self, root: Optional[TreeNode]) -> int:
          # meaning of the dp array (dp table) and its indices:
          # 1. index 0 records the maximum money from **not robbing this node**
          # 2. index 1 records the maximum money from **robbing this node**
          dp = self.traversal(root)
          return max(dp)
      # use post-order traversal, because the return value of the recursive function is needed
      # for the next computation
      def traversal(self, node):       
          # recursion termination: when an empty node is reached, it is definitely not robbed
          if not node:
              return (0, 0)
          left = self.traversal(node.left)
          right = self.traversal(node.right)
          # do not rob the current node, rob the child nodes
          val_0 = max(left[0], left[1]) + max(right[0], right[1])
          # rob the current node, do not rob the child nodes
          val_1 = node.val + left[0] + right[0]
          return (val_0, val_1)

Stock problems

2D dp array: \(dp[i][j]\) represents the maximum profit after the trade on day i is completed, where j indicates whether the stock is currently held: j=0 when holding, j=1 when not holding.

dp array initialization: the initial state is \(dp[0][0]=−prices[0]\), all other states are 0.

Given an array prices, its i-th element prices[i] is the price of a given stock on day i. You may choose a single day to buy the stock and choose to sell it on a different day in the future. Design an algorithm to compute the maximum profit you can obtain. Return the maximum profit from this transaction. If you cannot obtain any profit, return 0

  
  # Best Time to Buy and Sell Stock 1
  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          length = len(prices)
          if len == 0:
              return 0
          dp = [[0] * 2 for _ in range(length)]
          dp[0][0] = -prices[0]
          dp[0][1] = 0
          for i in range(1, length):
              dp[i][0] = max(dp[i-1][0], -prices[i])
              dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
          return dp[-1][1]

Given an integer array prices, where prices[i] is the price of a stock on day i. Each day you may decide whether to buy and/or sell the stock. You may hold at most one share of the stock at any time. You may also buy and then sell on the same day. Return the maximum profit you can obtain.

  
  # Best Time to Buy and Sell Stock 2
  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          n = len(prices)
          dp = [[0] * 2 for _ in range(n)]
          dp[0][0] = -prices[0]
          for i in range(1, n):
              dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
              dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
          return dp[-1][-1]

Given an array prices, its i-th element prices[i] is the price of a given stock on day i. Design an algorithm to compute the maximum profit you can obtain. You may complete at most two transactions. Note: you cannot engage in multiple transactions at the same time (you must sell the previous stock before buying again).

  
  # Best Time to Buy and Sell Stock 3
  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          n=len(prices)
          if n<=1:
              return 0
          dp=[[0]*4 for _ in range(n)]
          dp[0][0]=-prices[0]
          dp[0][2]=-prices[0]
          for i in range(1,n):
              dp[i][0]=max(dp[i-1][0],-prices[i])
              dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
              dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i])
              dp[i][3]=max(dp[i-1][3],dp[i-1][2]+prices[i])
          return dp[-1][-1]

Given an integer array prices and an integer k, where prices[i] is the price of a given stock on day i. Design an algorithm to compute the maximum profit you can obtain. You may complete at most k transactions. That is, you may buy at most k times and sell at most k times. Note: you cannot engage in multiple transactions at the same time (you must sell the previous stock before buying again).

  
  # Best Time to Buy and Sell Stock 4
  class Solution:
      def maxProfit(self, k: int, prices: List[int]) -> int:
          n=len(prices)
          if n<=1:
              return 0
          dp=[[0]*k*2 for _ in range(n)]
          for i in range(0,2*k,2):
              dp[0][i]=-prices[0]
          for i in range(1,n):
              dp[i][0]=max(dp[i-1][0],-prices[i])
              dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
              for j in range(2,2*k-1,2):
                  dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
                  dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]+prices[i])
          return dp[-1][-1]

Given an integer array prices, where prices[i] is the stock price on day i. Design an algorithm to compute the maximum profit. Given the following constraint, you may complete as many transactions as you like (buy and sell one stock multiple times): after selling a stock you cannot buy a stock on the next day (i.e. a 1-day cooldown). Note: you cannot engage in multiple transactions at the same time (you must sell the previous stock before buying again)

  
  # Best Time to Buy and Sell Stock (with cooldown)
  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          n = len(prices)
          dp = [[0] * 2 for _ in range(n)]
          dp[0][0] = -prices[0]
          for i in range(1, n):
              dp[i][0] = max(dp[i - 1][0], dp[i - 2][1] - prices[i])
              dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
          return dp[-1][-1]

Given an integer array prices, where prices[i] is the stock price on day i, and an integer fee representing the transaction fee. You may complete transactions an unlimited number of times, but you must pay the fee for each transaction. If you have already bought a stock, you cannot keep buying before selling it. Return the maximum profit. Note: here one transaction refers to the whole process of buying, holding, and selling the stock; you only need to pay the fee once per transaction.

  
  class Solution:
      def maxProfit(self, prices: List[int], fee: int) -> int:
          n = len(prices)
          dp = [[0] * 2 for _ in range(n)]
          dp[0][0] = -prices[0]
          for i in range(1, n):
              dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
              dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]-fee)
          return dp[-1][-1]

Subsequences

(6) Two Pointers

Opposite-direction two pointers

One pointer traverses from front to back while the other traverses from back to front; both move toward the middle at the same time

Two Sum (using a hash table)

  
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashtable=dict()
    for i, num in enumerate(nums):
        if target-num in hashtable:
            return [hashtable[target-num],i]
        else:
            hashtable[num]=i
                    

Three Sum (using two pointers)

  
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans=[]
        for i in range(len(nums)):
            if nums[i]>0:return ans
            if i>0 and nums[i]==nums[i-1]:
                continue
            left=i+1
            right=len(nums)-1
            while right>left:
                sum=nums[i]+nums[left]+nums[right]
                if sum>0:
                    right-=1
                elif sum<0:
                    left+=1
                else:
                    ans.append([nums[i],nums[left],nums[right]])
                    left+=1
                    right-=1
                    while  right>left and nums[right]==nums[right+1]:
                        right-=1
                    while  right>left and nums[left]==nums[left-1]:
                        left+=1
                            
        return ans

Four Sum (using two pointers)

  
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans=[]
        n=len(nums)
        for k in range(n):
            if target>0 and nums[k]>target:# pruning
                break
            if k>0 and nums[k]==nums[k-1]:
                continue
            for i in range(k+1,n):
                if target>0 and nums[i]+nums[k]>target:# pruning
                    break 
                if i>k+1 and nums[i]==nums[i-1]:  
                    continue
                left=i+1
                right=n-1
                while right>left:
                    sum=nums[k]+nums[i]+nums[left]+nums[right]
                    if sum>target:
                        right-=1
                    elif sum<target:
                        left+=1
                    else:
                        ans.append([nums[k],nums[i],nums[left],nums[right]])
                        right-=1
                        left+=1
                        while right>left and nums[right]==nums[right+1]:
                            right-=1
                        while right>left and nums[left]==nums[left-1]:
                            left+=1
        return ans

Same-speed two pointers

Both pointers traverse from front to back; the first pointer moves k steps ahead

Remove the k-th node from the end of a linked list

  
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        
        left = right = dummy = ListNode(next=head)
        # the fast pointer moves n steps first
        for _ in range(n):
            right = right.next
        # the fast and slow pointers move together
        while right.next:
            left = left.next
            right = right.next
        left.next = left.next.next
        return dummy.next

Fast and slow pointers

Define fast and slow pointers starting from the head node; the fast pointer moves two nodes at a time and the slow pointer moves one node at a time, and they meet along the way

Linked list cycle

  
class Solution(object):
    
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

(7) Bit Manipulation

  
# ============================================================
# Bit operations operate on binary representations
# ============================================================


# ------------------------------------------------------------
# 2. AND &: the result is 1 only if both positions are 1
# ------------------------------------------------------------

a = 6            # 110
b = 5            # 101
a & b            # 100 -> 4

# Common use: check whether a bit is 1. If the result != 0 the k-th bit is 1; if the result == 0 the k-th bit is 0
n & (1 << k)

# ------------------------------------------------------------
# 3. OR |: the result is 1 if either position is 1
# ------------------------------------------------------------

a = 6            # 110
b = 5            # 101
a | b            # 111 -> 7

# Common use: set the k-th bit to 1
n = n | (1 << k)


# ------------------------------------------------------------
# 4. XOR ^: 0 if equal, 1 if different
# ------------------------------------------------------------

a = 6            # 110
b = 5            # 101
a ^ b            # 011 -> 3

# XOR is commutative and associative:
# a ^ b ^ a
# = a ^ a ^ b
# = b

# Common use: only one number appears once and the rest appear twice
nums = [2, 3, 2, 4, 4]
ans = 0
for x in nums:
    ans ^= x

# ans -> 3


# ------------------------------------------------------------
# 5. NOT ~
# ------------------------------------------------------------
~x
# ~x == -(x + 1)

# ------------------------------------------------------------
# 6. Left shift <<
# ------------------------------------------------------------
n << k
# equivalent to:
# n * 2^k
3 << 1          # 6
3 << 2          # 12
3 << 3          # 24

# Common use:
# 1 << k means only the k-th bit is 1
1 << 0          # 1     -> 0001
1 << 1          # 2     -> 0010
1 << 2          # 4     -> 0100
1 << 3          # 8     -> 1000


# ------------------------------------------------------------
# 7. Right shift >>
# ------------------------------------------------------------

n >> k

# For non-negative integers it is equivalent to:
# n // 2^k

20 >> 1         # 10
20 >> 2         # 5


# ------------------------------------------------------------
# 8. Check odd/even
# ------------------------------------------------------------

n & 1

# lowest bit is 1 -> odd
# lowest bit is 0 -> even

if n & 1:
    print("odd")
else:
    print("even")


# ------------------------------------------------------------
# 9. Check the k-th bit
# ------------------------------------------------------------

# Note: the lowest bit is usually called bit 0

if n & (1 << k):
    print("the k-th bit is 1")
else:
    print("the k-th bit is 0")


# Alternatively:

(n >> k) & 1

# Result:
# 1 -> the k-th bit is 1
# 0 -> the k-th bit is 0


# ------------------------------------------------------------
# 10. Set the k-th bit to 1
# ------------------------------------------------------------

n |= (1 << k)


# ------------------------------------------------------------
# 11. Set the k-th bit to 0
# ------------------------------------------------------------

n &= ~(1 << k)


# ------------------------------------------------------------
# 12. Flip the k-th bit
# ------------------------------------------------------------

n ^= (1 << k)

# originally 0 -> becomes 1
# originally 1 -> becomes 0


# ------------------------------------------------------------
# 13. Take the lowest set bit
# ------------------------------------------------------------

lowbit = n & -n

# For example:
#
# n = 12
# binary: 1100
#
# n & -n -> 0100 -> 4

12 & -12        # 4

10 & -10        # 2

8 & -8          # 8


# Common uses:
# Fenwick Tree / binary indexed tree
# counting the number of 1 bits


# ------------------------------------------------------------
# 14. Remove the lowest set bit
# ------------------------------------------------------------

n = n & (n - 1)

# For example:
#
# n = 12
# 1100
#
# n - 1
# 1011
#
# n & (n - 1)
# 1000


# Common use: count the number of 1 bits:

count = 0

while n:
    n &= n - 1
    count += 1


# ------------------------------------------------------------
# 15. Check whether a number is a power of 2
# ------------------------------------------------------------

# A power of 2 has only a single 1 bit:
#
# 1  -> 0001
# 2  -> 0010
# 4  -> 0100
# 8  -> 1000

if n > 0 and (n & (n - 1)) == 0:
    print("is a power of 2")


# ------------------------------------------------------------
# 16. Number of 1 bits
# ------------------------------------------------------------

# Method 1: Python built-in

n.bit_count()

# For example:

13.bit_count()
# 13 = 1101
# -> 3


# Method 2:

count = 0

while n:
    n &= n - 1
    count += 1


# ------------------------------------------------------------
# 17. Bitmask / state compression
# ------------------------------------------------------------

# Use each bit of an integer to represent a state:
#
# bit 0 -> state 0
# bit 1 -> state 1
# bit 2 -> state 2
# ...


# Check whether state i exists:
if state & (1 << i):
    ...
# Add state i:
state |= (1 << i)
# Remove state i:
state &= ~(1 << i)
# Toggle state i:
state ^= (1 << i)
# Check bit i of state:
if state & (1 << i):
    ...



# ============================================================
# Key takeaways
# ============================================================

# &   AND: 1 only if both are 1
# |   OR: 1 if either is 1
# ^   XOR: 1 if different, 0 if the same
# ~   NOT
# <<  left shift: multiply by 2
# >>  right shift: divide by 2 (non-negative integers)

# x ^ x = 0
# x ^ 0 = x

# n & 1
# check odd/even

# n & (1 << k)
# check the k-th bit

# n & -n
# take the lowest set bit

# n & (n - 1)
# remove the lowest set bit

III. Search

Sliding window

(Note: a sliding window is essentially maintaining a queue. Moving the right pointer can be seen as enqueuing, and moving the left pointer as dequeuing.)

Fixed-length window: enumerate all windows of a fixed length

Variable-length window: enumerate all windows of variable length to find the longest subarray, the shortest subarray, or the number of subarrays

Template:

  
# LeetCode 438. Find All Anagrams in a String
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        # build the window
        count_p = Counter(p)
        window_count  = Counter(s[:len(p)])
        # check the initial window
        if window_count  == count_p:
            ans.append(0)
 
        for i in range(len(s)-len(p)):
            # remove the left element
            window_count[s[i]]-=1
            if window_count[s[i]]==0:
                del window_count[s[i]]
            # add the new element to the window
            window_count[s[i+len(p)]] += 1
            # compute for this window
            if window_count == count_p:
                ans.append(i+1)
        return ans

Depth-first
Breadth-first

Binary search

To decide whether binary search on the answer is possible, the key is to check three conditions:

The answer is a number within a range
Given a candidate answer x, you can judge whether x is feasible
This “feasible / not feasible” is monotonic
For “minimize the maximum” or “maximize the minimum”, think of binary search on the answer first.

The first kind: find the “first position that satisfies the condition”:

  
  # position: 1  2  3  4  5  6
  # check:    F  F  F  T  T  T
  while left < right:
      mid = (left + right) // 2
    
      if check(mid):
          right = mid
      else:
          left = mid + 1
    
  return left

The second kind: find the “last position that satisfies the condition”:

  
  # position: 1  2  3  4  5  6
  # check:    T  T  T  T  F  F
  while left < right:
      mid = (left + right + 1) // 2
    
      if check(mid):
          left = mid
      else:
          right = mid - 1
    
  return left

IV. Graph Theory

Depth-first search

Template

  
  result = []
  path = []
  # backtracking algorithm
  def dfs(params):
      if (termination condition):
          store the result
          return
      for i in (choices: the other nodes connected to this node):
          process the node;
          dfs(graph, chosen node); // recursion
          backtrack, undo the processing
      return

Breadth-first search
Union-Find
Topological sort
Island problems
Path problems

All possible paths (suited to depth-first)

  
class Solution:
    def __init__(self):
        self.result = []
        self.path = [0]
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        if not graph: return []
        self.dfs(graph, 0)
        return self.result
    def dfs(self, graph, root: int):
        if root == len(graph) - 1:  # a path is successfully found
            # ***Python lists are mutable***
            # ***a deep copy must be used in backtracking***
            self.result.append(self.path[:]) 
            return        
        for node in graph[root]:   # traverse all descendants of node n
            self.path.append(node)
            self.dfs(graph, node)
            self.path.pop() # backtrack

V. Number Theory

Check prime

  
   def is_prime(self, n: int) -> bool:
       return all(n % i for i in range(2, isqrt(n) + 1))

Check leap year

  
def is_leap_year(year):
    if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
        return True
    else:
        return False

Palindrome number, Manacher’s algorithm
Prefix sum

Maximum of two numbers

Mathematically, for the maximum of two numbers we have the following identity:

  
class Solution:
    def maximum(self, a: int, b: int) -> int:
        return int((sqrt(pow(a-b,2)) + a + b)/2)
# similarly for the minimum
class Solution:
    def maximum(self, a: int, b: int) -> int:
        return int(-(sqrt(pow(a-b,2)) + a + b)/2)

Appendix

Input

  
# input one value
num=input()
# input multiple values on one line
# 1. multiple characters on one line
a,b=input().split() (separated by spaces)
a,b=input().split(',') (separated by ',')
# 2. multiple numbers on one line
a,b=map(int,input().split()) (separated by spaces)
# 3. input a list
a=list(map(int,input().split()))
import sys
# input an array
for line in sys.stdin:
    a = line.split()

Output

  
# output
print()
# 1. using sep and end
# end: the default is a newline; it is what the two strings end with.
# sep: the default is a space; it is what separates the two strings.
>>print('a',end=" ")
>>print('b')
>> a b
>>print('a','b',sep=',')
>>a,b
# 2. output multiple variables with %
>>a='leap year'
>>b=366
>>print("%s is %d days"%(a,b))
>> leap year is 366 days
# character output
'%4d' % ( a )
Output an integer string of width 4; if the integer a is fewer than 4 characters, pad spaces on the left, i.e. fill the right side first.
'%-4d' % ( a )
Output an integer string of width 4; if the integer a is fewer than 4 characters, pad spaces on the right, i.e. fill the left side first.
'%.4d' % ( a ) and '%04d' % ( a )
Output an integer string of width 4; if the integer a is fewer than 4 characters, pad zeros in the remaining space on the left.
'%.2f' % ( a ) and '%.02f' % ( a )
Output a float string with 2 decimal places; if the number of decimals is fewer than 2, pad zeros at the end.
'%4.2f' % ( a )
Output a float string with a total width of 4 and 2 decimal places.

Time

  
# datetime() function
# 1. assignment 
tody=datetime.date(2023,4,7)
# 2. determine the weekday:
week=today.weekday() returns 0 if it is Monday
# 3. get year/month/day separately:
today.strftime("%d") day
today.strftime('%m') month
today.strftime('%y') year
# 4. add one day:
delay = datetime.timedelta(days = 1)
tomorrow=today+delay

Subarray, subsequence, substring

Subarray: one or more consecutive elements of an array form a subarray (a subarray contains at least one element)
Subsequence: a subsequence is a sequence formed by taking part of the original sequence (a subsequence is not necessarily contiguous)
Substring: any consecutive characters of a string form a sequence called a substring of that string (a substring may be empty)

算法题 , 基础知识