245｜高频算法思想：二分、双指针、滑动窗口、回溯、贪心和动态规划

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:          # 左闭右闭，left == right 时区间仍有效
        mid = left + (right - left) // 2   # 防溢出写法
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1         # target 在右半部分
        else:
            right = mid - 1        # target 在左半部分
    return -1

def lower_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid            # mid 可能是答案，但左边可能还有
        else:
            left = mid + 1
    return left

def upper_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > target:
            right = mid
        else:
            left = mid + 1
    return left - 1

def min_eating_speed(piles, h):
    def can_finish(k):
        return sum((p + k - 1) // k for p in piles) <= h

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid
        else:
            left = mid + 1
    return left

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1    # 和太小，左指针右移增大和
        else:
            right -= 1   # 和太大，右指针左移减小和

    return [ ]

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

def three_sum(nums):
    nums.sort()

    res = [ ]

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # 跳过重复的固定值
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

def sliding_window(s):
    left = 0
    window = {}  # 窗口内数据的状态
    result = 0

    for right in range(len(s)):
        # 1. 将 s[right] 加入窗口
        add_to_window(window, s[right])

        # 2. 当窗口不满足条件时，收缩左边界
        while not is_valid(window):
            remove_from_window(window, s[left])
            left += 1

        # 3. 更新结果（窗口现在是有效的）
        result = max(result, right - left + 1)

    return result

def length_of_longest_substring(s):
    window = {}
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        # 如果当前字符已在窗口内，收缩左边界
        if ch in window and window[ch] >= left:
            left = window[ch] + 1
        window[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len

def min_window(s, t):
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    window = {}
    left = 0
    valid = 0  # 已满足条件的字符种类数
    start, length = 0, float('inf')

    for right, ch in enumerate(s):
        if ch in need:
            window[ch] = window.get(ch, 0) + 1
            if window[ch] == need[ch]:
                valid += 1

        while valid == len(need):
            if right - left + 1 < length:
                start, length = left, right - left + 1
            if s[left] in need:
                if window[s[left]] == need[s[left]]:
                    valid -= 1
                window[s[left]] -= 1
            left += 1

    return s[start:start+length] if length != float('inf') else ''

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

    for 选择 in 选择列表:
        if 选择不合法:
            continue           # 剪枝
        做选择
        backtrack(路径, 选择列表)
        撤销选择

def solve_n_queens(n):

    res = [ ]

    board = [['.'] * n for _ in range(n)]

    def is_valid(row, col):
        # 检查列
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        # 检查左上对角线
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # 检查右上对角线
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def backtrack(row):
        if row == n:
            res.append([''.join(row) for row in board])
            return
        for col in range(n):
            if not is_valid(row, col):
                continue  # 剪枝
            board[row][col] = 'Q'
            backtrack(row + 1)
            board[row][col] = '.'

    backtrack(0)
    return res

def permute(nums):

    res = [ ]

    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False


    backtrack([ ])

    return res

def jump(nums):
    n = len(nums)
    if n == 1:
        return 0
    jumps = 0
    current_end = 0  # 当前跳跃能到达的最远位置
    farthest = 0     # 从当前区间内能到达的最远位置

    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= n - 1:
                break
    return jumps

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])  # 按结束时间排序
    count = 0
    end = float('-inf')
    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish
    return len(intervals) - count

dp[i][j] = max(
    dp[i-1][j],                    // 不选第 i 个物品
    dp[i-1][j-w[i]] + v[i]        // 选第 i 个物品（需要 j >= w[i]）
)

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for j in range(W, weights[i] - 1, -1):  # 倒序遍历！
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

graph TD
    A[分析问题特征] --> B{数据是否有序？}
    B -->|是| C[二分查找/二分答案]
    B -->|否| D{是否求连续子数组/子串？}
    D -->|是| E[滑动窗口]
    D -->|否| F{是否穷举所有解？}
    F -->|是| G[回溯]
    F -->|否| H{是否有重叠子问题？}
    H -->|是| I[动态规划 / 记忆化搜索]
    H -->|否| J{是否局部最优推全局最优？}
    J -->|是| K[贪心算法]
    J -->|否| L[双指针 / 其他技巧]