二分查找

理解方法

知道范围猜价格。每次在可能的范围中猜最中间的那个数,然后根据反馈调整范围。

使用场景

有序数组中查找某一个值。

方法模板

begin, end = 0, len(nums) - 1
while begin <= end:
    current = (begin + end) // 2
    #...

例题

702 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        begin, end = 0, len(nums) - 1
        while end >= begin:
            current_index = (begin + end) // 2
            current_num = nums[current_index]
            if current_num == target:
                return current_index
            elif current_num < target:
                begin = current_index + 1
            else:
                end = current_index - 1
        return -1

双指针

理解方法

可以用小明、小红两人赛跑来帮助理解,分别代表两个指针。

使用场景

需要一遍遍历解决数组或者链表上的问题时常用。

方法模板

head, tail = 0,0
#...

例题

19 删除倒数第N个节点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

#Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        target, tail = head, head
        for i in range(n):
            tail = tail.next
        if tail == None:
            head= head.next
            return head
        while(tail.next != None):
            tail = tail.next
            target = target.next
        target.next = target.next.next
        return head

广度(深度)优先遍历

理解方法

广度优先遍历用队列实现,深度优先遍历用栈来实现。

应用场景

广度优先遍历用来求距离非常好用。广度优先遍历还可以处理多起点,只需要一开始将所有起点都加入队列即可。

方法模板

对于树的遍历没有mark和处理顺序的要求,但是对于图的遍历尽量采用下面的模板进行处理:

q = []
went = [[Flase] * n for _ in range(m)]

# 起点处理和mark
process(start)
mark(start)
# 起点入队
q += [start]

while q:
    p = q.pop(0)
    for p_ in p.nearby:
        if valid(p_) and not went[p_] and condition[p_]:
            # 处理,mark,入队
            process(p_)
            mark(p_)
            q += [p]

例题

994 腐烂橘子

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。

from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        distance = [[-1] * n for _ in range(m)]
        max_distance = 0
        total = 0
        q = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q += [(i, j)]
                    distance[i][j] = 0
                elif grid[i][j] == 1:
                    total += 1
        while q:
            x0, y0 = q.pop(0)
            for x_, y_ in [(x0 + 1, y0), (x0 - 1, y0), (x0, y0 + 1), (x0, y0 - 1)]:
                if 0<= x_ < m and 0<= y_ < n and distance[x_][y_] == -1 and grid[x_][y_] == 1:
                    total -= 1
                    distance[x_][y_] = distance[x0][y0] + 1
                    max_distance = max(max_distance, distance[x_][y_])
                    q += [(x_, y_)]
        if total > 0:
            return -1
        else:
            return max_distance

腐烂橘子问题是一个典型的多起点广度优先遍历问题。一开始把所有的腐烂起点加入队列即可。

排列 组合 笛卡尔积