基础算法题解模板

# 通用双指针框架（适用于数组/列表）
def two_pointers(arr):
    n = len(arr)
    if n == 0:
        return 0  # 或其他默认值

    # Step 1: 初始化指针
    left = 0                    # 左指针 / 慢指针
    # right = 0 或 n - 1，根据方向选择

    # Step 2: 根据类型选择遍历结构
    for right in range(n):      # 同向：快慢指针；滑动窗口
    # while left < right:       # 相向：对撞指针（常用于有序数组）
    # while left < n:           # 其他控制条件

        # Step 3: 扩展或移动右指针后，处理当前窗口/状态
        # ... 更新状态

        # Step 4: 判断是否需要收缩左指针（滑动窗口类）
        while left <= right and need_to_move_left(arr, left, right):
            # ... 更新或记录结果
            left += 1

        # 或：根据条件移动双指针（对撞类）
        # if condition:
        #     left += 1
        # else:
        #     right -= 1

    return result

"""
📖描述：给你两个按 非递减顺序 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n`，分别表示 `nums1` 和 `nums2` 中的元素数目。请你 合并 `nums2` 到 `nums1` 中，使合并后的数组同样按 非递减顺序 排列。
🧪样例：输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3；输出：[1,2,2,3,5,6]
💡重点：从后往前操作可以直接覆盖
"""

def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    # 逆向双指针，从后往前操作可以直接覆盖
    p1, p2 = m - 1, n - 1  # 同向，但是从后往前
    tail = m + n - 1  # 需要维护的状态：当前需要处理的索引
    while True:
        if p1 < 0 or p2 < 0:
            break
        if nums1[p1] <= nums2[p2]:
            nums1[tail] = nums2[p2]
            p2 -= 1
            tail -= 1
        else:
            nums1[tail] = nums1[p1]
            p1 -= 1
            tail -= 1
    # 由于比较，总会有一个数组先结束，对于后结束的一个数组：这里肯定是p2
    if p2 >= 0:
        nums1[: p2 + 1] = nums2[: p2 + 1]

def merge(nums1: List[int], nums2: List[int]) -> List[int]:
    """ 合并双指针，非原地操作。
    🧪样例：输入：nums1 = [1,2,3], nums2 = [2,5,6]；输出：[1,2,2,3,5,6]
    """
    m, n = len(num1), len(nums2)
    new_list = []
    i, j = 0, 0
    # 合并的过程只能操作 i, j 的移动，不要去用 list1.pop(0) 之类的操作
    # 因为 pop(0) 是 O(n) 的时间复杂度，而且会改变序号
    while True:
        if i >= m or j >= n:
            break
        if nums[i] < nums[j]:
            new_list.append(nums[i])
            i += 1
        else:
            new_list.append(nums[j])
            j += 1
    # 合并剩下的数到 new_list 里
    while i < m:
        new_list.append(nums[i])
        i += 1
    while j < n:
        new_list.append(nums[j])
        j += 1
    return new_list

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode()  # 虚拟头结点，它的唯一作用就是提供一个起始点，让 p 可以不断向后连接节点
    p = dummy  # p 指向虚拟链表的末尾
    p1 = l1
    p2 = l2

    while p1 is not None and p2 is not None: 
        # 比较 p1 和 p2 两个指针
        # 将值较小的的节点接到 p 指针
        if p1.val > p2.val:
            p.next = p2
            p2 = p2.next
        else:
            p.next = p1
            p1 = p1.next
        # p 指针不断前进
        p = p.next

    if p1 is not None:
        p.next = p1

    if p2 is not None:
        p.next = p2

    return dummy.next  # 注意：不是返回指针 p，而是返回链表的头部，也就是 dummy.next

"""
📖描述：给你一个字符串 `s`，找到 `s` 中最长的 回文 子串。
🧪样例：输入s = "babad"；输出"bab"或"aba"。输入：s = "cbbd"；输出："bb"。
💡重点：
- 需要同时考虑奇数和偶数长的回文串
- 中心扩散
- 这题还可以用动态规划解: 
    - 状态定义：dp[i][j]表示s[i:j+1]是否为回文
    - 初始化：dp = [[False for _ in range(size)] for _ in range(size)]
    - 转移方程：dp[i][j] = dp[i-1][j-1] and s[i] == s[j]
"""
def longestPalindrome(s: str) -> str:
    n = len(s)
    if n <= 1:
        return s
    max_s, max_len = "", 0
    for i in range(n):
        if n - 1 - i < (max_len - 1) / 2:
            break  # 提前终止
        # 处理奇数长度的回文子串，以i为中心向两边移动
        left, right = i, i
        while True:
            if left < 0 or right > n - 1:
                break
            if s[left] == s[right]:
                left -= 1
                right += 1
            else:
                break  # 注意所有break的情况
        cur_len = right - left - 1
        if cur_len > max_len:
            max_s = s[left + 1 : right]
            max_len = cur_len
        # 处理偶数长度的回文子串
        left, right = i, i + 1
        while True:
            if left < 0 or right > n - 1:
                break
            if s[left] == s[right]:
                left -= 1
                right += 1
            else:
                break
        cur_len = right - left - 1
        if cur_len > max_len:
            max_s = s[left + 1 : right]
            max_len = cur_len
    return max_s

"""
📖描述：
🧪样例：
💡重点：
"""

# 滑动窗口模板
def sliding_window(s: str):
    # 用合适的数据结构记录窗口中的数据，根据具体场景变通
    # 比如说，我想记录窗口中元素出现的次数，就用 map
    # 如果我想记录窗口中的元素和，就可以只用一个 int
    window = set()

    left, right = 0, 0
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        window.add(c)
        # 增大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        ...

        # 判断左侧窗口是否要收缩
        while left < right and window_needs_shrink(s, left, right):
            # 把 s[left] 移出窗口
            window.remove(s[left])
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            ...

"""
📖描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
🧪样例：
    输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
💡重点：滑动窗口最重要的是指针只增不减
"""
# 错误用法
# 下面这种写法没有保证每个元素只处理一次（l递增，但r会回退），就是暴力的嵌套循环，复杂度为 O(N^2)
def lengthOfLongestSubstring(s: str) -> int:
    N = len(s)
    ans = 0
    for l in range(N):
        substr = {s[l]}
        for r in range(l + 1, N):
            if s[r] not in substr:
                substr.add(s[r])
            else:
                break
        ans = max(ans, len(substr))
    return ans

# 正确用法 1
# r只增不减：O(N), 23ms
def lengthOfLongestSubstring(s: str) -> int:
    N = len(s)
    right, ans = 0, 0
    for left in range(N):
        substr = s[left:right]
        while True and right < N:
            if s[right] in substr:
                break
            else:
                right += 1
                substr = s[left:right]
        ans = max(ans, len(substr))
    return ans

# 正确用法 2
# window维护每个字符出现的次数, 删除 s[left] 直至 win[s[right]] <= 1, O(N), 76ms
def lengthOfLongestSubstring(s: str) -> int:
    win, ans = dict(), 0
    left, right = 0, 0
    while right < len(s):
        win[s[right]] = win.get(s[right], 0) + 1
        # 滑动左指针直到win[s[right]]<=1
        while win[s[right]] > 1:
            win[s[left]] -= 1
            left += 1
        ans = max(ans, right - left + 1)
        right += 1
    return ans

"""
📖描述：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。
🧪样例：
    输入：s1 = "abb" s2 = "eidbabooo"
    输出：true
    解释：s2 包含 s1 的排列之一 ("bab").
💡重点：
"""

# 错误解法
# 暴力枚举，每次循环都重新计算Counter，时间复杂度 O(N^2)
def checkInclusion(s1: str, s2: str) -> bool:
    from collections import Counter

    N, M = len(s1), len(s2)
    ref = Counter(s1)
    # 窗长始终为N
    for i in range(M):
        substr = s2[i: i + N]
        win = Counter(substr)
        if win == ref:
            return True
    return False

# 正确解法
# 不需要每次都重新计算，只需要更新 left 和 right 的计数，时间复杂度 O(N)
def checkInclusion(s1: str, s2: str) -> bool:
    N, M = len(s1), len(s2)
    if N > M:
        return False

    ref = {}
    for c in s1:
        ref[c] = ref.get(c, 0) + 1

    window = {}
    for i in range(N):
        window[s2[i]] = window.get(s2[i], 0) + 1

    right = N
    while right < M:
        # print(window)
        if window == ref:
            return True
        new = s2[right]
        old = s2[right - N]
        # 维护滑动窗
        window[new] = window.get(new, 0) + 1
        window[old] = window.get(old, 0) - 1
        if window[old] == 0:
            del window[old]
        right += 1

    if window == ref:
        return True
    return False

def hash_search(arr, query):
    # 哈希查找，用于无序数组
    seen = {}
    for i, val in enumerate(arr):
        complement = query - val
        if complement in seen:
            return [seen[complement], i]  # 如两数之和
        seen[val] = i
    return -1

def binary_search(array, query):
    """ Two points. [low, high] will be splitted:
        (1) [low, mid - 1]
        (2) [mid]
        (3) [mid + 1, high]
    """
    low, high = 0, len(array) - 1  # 闭区间 [left, right]
    while low <= high:
        mid = low + (high - low) // 2  # 防溢出
        val = array[mid]
        # array[low:mid], array[mid], array[mid+1:high+1]
        if val == query:
            return mid
        if val < query:
            low = mid + 1
        else:
            high = mid - 1
    return None

def binary_search_recur(array, low, high, query):
    """ Recurrence. [low, high] will be splitted:
        (1) [low, mid - 1]
        (2) [mid]
        (3) [mid + 1, high]
    """
    if low > high:
        return -1
    mid = low + (high - low) // 2   # This mid will not break integer range
    if query < array[mid]:
        return binary_search_recur(array, low, mid - 1, query)  # Go search in the left subarray
    if query > array[mid]:
        return binary_search_recur(array, mid + 1, high, query)  # Go search in the right subarray
    return mid  # `array[mid] = query`, stop recurrence

"""
📖描述：给定旋转后的数组 `nums` 和一个整数 `target`，如果 `nums` 中存在这个目标值 `target`，则返回它的下标，否则返回 `-1`。
🧪样例：输入：`nums = [2,3,4,5,6,7,0,1]`, `target = 0`；输出：`target`的下标为`6`。
💡重点：
1. 数组不是有序的，但是是局部有序的。有序的那端一定是最左边小于最右边，无序的那端一定是最左边大于最右边。
2. 目标是否在有序部分比较好判断`nums[left_] <= target and target < nums[right_]`，如果不满足则落在另一边。
https://leetcode.cn/problems/search-in-rotated-sorted-array/solutions/2636954/javapython3cer-fen-cha-zhao-you-xu-de-ba-5g7e
"""
def search(nums: List[int], target: int) -> int:
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        val = nums[mid]
        # print(mid, nums[low:mid], nums[mid], nums[mid+1:high+1])
        if val == target:
            return mid
        if low < mid and nums[low] <= nums[mid - 1]:
            # 左边有序，先判断是否在左边
            if nums[low] <= target and target <= nums[mid - 1]:
                high = mid - 1
            else:
                low = mid + 1
        elif mid < high:
            # 右边有序，先判断是否在右边
            if nums[mid + 1] <= target and target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
        else:
            return -1
    return -1

"""
📖描述：给定一个排序好的数组 `arr`，两个整数 `k` 和 `x`，从数组中找到最靠近 `x` 的 `k` 个数。返回的结果必须要是按升序排好的。
🧪样例：输入：`arr = [1,2,3,4,5]`, `k = 4`, `x = 3`；输出：`[1,2,3,4]`。
💡重点：
1. 反向思维，删除最边缘的`n - k`个，每次判断删最左边还是删最右边。
2. 返回结果要排好序，可以用双指针寻找最优子区间。
"""

def findClosestElements(arr: List[int], k: int, x: int) -> List[int]:
    # 排除法（双指针）
    N = len(arr)
    remove_nums = N - k
    left, right = 0, N - 1
    while remove_nums:
        # 注意：这里等于号的含义，题目中说，差值相等的时候取小的
        # 因此相等的时候，尽量缩小右边界
        if x - arr[left] <= arr[right] - x:
            right -= 1
        else:
            left += 1
        remove_nums -= 1
    return arr[left:left + k]

"""
📖描述：
    给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
🧪样例：
    输入: [3,2,1,5,6,4], k = 2
    输出: 5

    输入: [3,2,3,1,2,4,5,5,6], k = 4
    输出: 4
💡重点：
"""
class Solution:
    def partition(self, nums: List[int], left: int, right: int) -> int:
        """
        在子数组 [left, right] 中随机选择一个基准元素 pivot
        根据 pivot 重新排列子数组 [left, right]
        重新排列后，<= pivot 的元素都在 pivot 的左侧，>= pivot 的元素都在 pivot 的右侧
        返回 pivot 在重新排列后的 nums 中的下标
        特别地，如果子数组的所有元素都等于 pivot，我们会返回子数组的中心下标，避免退化
        """

        # 1. 在子数组 [left, right] 中随机选择一个基准元素 pivot
        i = random.randint(left, right)
        pivot = nums[i]
        # 把 pivot 与子数组第一个元素交换，避免 pivot 干扰后续划分，从而简化实现逻辑
        nums[i], nums[left] = nums[left], nums[i]

        # 2. 相向双指针遍历子数组 [left + 1, right]
        # 循环不变量：在循环过程中，子数组的数据分布始终如下图
        # [ pivot | <=pivot | 尚未遍历 | >=pivot ]
        #   ^                 ^     ^         ^
        #   left              i     j         right

        i, j = left + 1, right
        while True:
            while i <= j and nums[i] < pivot:
                i += 1
            # 此时 nums[i] >= pivot

            while i <= j and nums[j] > pivot:
                j -= 1
            # 此时 nums[j] <= pivot

            if i >= j:
                break

            # 维持循环不变量
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

        # 循环结束后
        # [ pivot | <=pivot | >=pivot ]
        #   ^             ^   ^     ^
        #   left          j   i     right

        # 3. 把 pivot 与 nums[j] 交换，完成划分（partition）
        # 为什么与 j 交换？
        # 如果与 i 交换，可能会出现 i = right + 1 的情况，已经下标越界了，无法交换
        # 另一个原因是如果 nums[i] > pivot，交换会导致一个大于 pivot 的数出现在子数组最左边，不是有效划分
        # 与 j 交换，即使 j = left，交换也不会出错
        nums[left], nums[j] = nums[j], nums[left]

        # 交换后
        # [ <=pivot | pivot | >=pivot ]
        #               ^
        #               j

        # 返回 pivot 的下标
        return j

    def findKthLargest(self, nums: list[int], k: int) -> int:
        n = len(nums)
        target_index = n - k  # 第 k 大元素在升序数组中的下标是 n - k
        left, right = 0, n - 1  # 闭区间
        while True:
            i = self.partition(nums, left, right)
            if i == target_index:
                # 找到第 k 大元素
                return nums[i]
            if i > target_index:
                # 第 k 大元素在 [left, i - 1] 中
                right = i - 1
            else:
                # 第 k 大元素在 [i + 1, right] 中
                left = i + 1

"""
📖描述：
🧪样例：
💡重点：
"""

"""
📖描述：
🧪样例：
💡重点：
"""

"""
📖描述：
🧪样例：
💡重点：
"""

"""
📖描述：
🧪样例：
💡重点：
"""

def dfs(参数列表):
    if 递归出口:
        记录答案
        return
    for 所有的拆解可能性:
        修改所有的参数
        dfs(参数列表)
        还原所有被修改过的参数
    return

"""
📖描述：
🧪样例：
💡重点：
"""