基础算法题解模板

# 通用双指针框架（适用于数组/列表）
def two_pointers_template(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

"""
📖描述：给你一个字符串 `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 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]

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

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

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

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

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

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