1.寻找有序矩阵中第K小的元素

def kthSmallest(matrix, k):
    """
    在行列均升序排列的n x n矩阵中，寻找第k小的元素。
    参数:
        matrix: List[List[int]], 行列均有序的矩阵
        k: int, 要寻找的第k小顺序（1-indexed）
    返回:
        int, 第k小的元素
    思路:
        对矩阵值的范围进行二分查找，利用矩阵特性（从右上角开始）统计小于等于mid值的元素个数。
    """
    n = len(matrix)
    left, right = matrix[0][0], matrix[-1][-1]  # 值范围的左右边界

    def count_less_equal(target):
        """统计矩阵中小于等于target的元素个数。从右上角开始遍历，时间复杂度O(n)"""
        i, j = 0, n - 1
        count = 0
        while i < n and j >= 0:
            if matrix[i][j] <= target:
                # 当前行从0到j列的所有元素都<=target
                count += (j + 1)
                i += 1  # 移动到下一行
            else:
                j -= 1  # 在当前行向左移动
        return count

    # 二分查找
    while left < right:
        mid = (left + right) // 2
        cnt = count_less_equal(mid)
        if cnt < k:
            # 第k小的数在右半部分
            left = mid + 1
        else:
            # 第k小的数在左半部分（包含mid）
            right = mid
    return left

# --- 测试用例与直接运行部分 ---
if __name__ == "__main__":
    # 测试用例1：常规情况
    matrix1 = [
        [1, 5, 9],
        [10, 11, 13],
        [12, 13, 15]
    ]
    k1 = 8
    result1 = kthSmallest(matrix1, k1)
    print(f"测试矩阵1: {matrix1}")
    print(f"第 {k1} 小的元素是: {result1}")  # 预期输出: 13
    print("-" * 30)

    # 测试用例2：k=1，即最小值
    matrix2 = [
        [2, 6, 8],
        [3, 7, 10],
        [5, 8, 11]
    ]
    k2 = 1
    result2 = kthSmallest(matrix2, k2)
    print(f"测试矩阵2: {matrix2}")
    print(f"第 {k2} 小的元素是: {result2}")  # 预期输出: 2
    print("-" * 30)

    # 测试用例3：k等于元素总数，即最大值
    matrix3 = [
        [1, 2],
        [3, 4]
    ]
    k3 = 4
    result3 = kthSmallest(matrix3, k3)
    print(f"测试矩阵3: {matrix3}")
    print(f"第 {k3} 小的元素是: {result3}")  # 预期输出: 4
    print("-" * 30)

    # 测试用例4：所有元素都相同的矩阵
    matrix4 = [
        [7, 7],
        [7, 7]
    ]
    k4 = 3
    result4 = kthSmallest(matrix4, k4)
    print(f"测试矩阵4: {matrix4}")
    print(f"第 {k4} 小的元素是: {result4}")  # 预期输出: 7

2.检查字符串是否包含另一个字符串的排列

from collections import defaultdict

def checkInclusion(s1, s2):
    """
    检查s2是否包含s1的一个排列作为子串。
    参数:
        s1: str, 较短的字符串
        s2: str, 较长的字符串
    返回:
        bool, 如果s2包含s1的排列则返回True，否则返回False
    思路:
        使用固定长度的滑动窗口和哈希表计数。维护窗口内字符频率，并与s1的字符频率比较。
    """
    len_s1, len_s2 = len(s1), len(s2)
    if len_s1 > len_s2:
        return False

    need = defaultdict(int)  # 存储s1的字符频率
    window = defaultdict(int) # 存储当前滑动窗口的字符频率

    # 初始化need计数器
    for ch in s1:
        need[ch] += 1

    # 初始化第一个窗口的计数器
    for i in range(len_s1):
        ch = s2[i]
        window[ch] += 1

    # 检查初始窗口
    if window == need:
        return True

    # 开始滑动窗口
    for right in range(len_s1, len_s2):
        left_char = s2[right - len_s1]  # 窗口左边界要移出的字符
        right_char = s2[right]           # 窗口右边界新加入的字符

        # 更新窗口计数器
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]  # 移除计数为0的键，方便后续直接比较字典

        window[right_char] += 1

        # 检查当前窗口是否匹配
        if window == need:
            return True

    return False

# --- 测试用例与直接运行部分 ---
if __name__ == "__main__":
    # 测试用例1：包含排列
    s1_1, s2_1 = "ab", "eidbaooo"
    result1 = checkInclusion(s1_1, s2_1)
    print(f"s1 = '{s1_1}', s2 = '{s2_1}'")
    print(f"结果: {result1}")  # 预期输出: True
    print("-" * 30)

    # 测试用例2：不包含排列
    s1_2, s2_2 = "ab", "eidboaoo"
    result2 = checkInclusion(s1_2, s2_2)
    print(f"s1 = '{s1_2}', s2 = '{s2_2}'")
    print(f"结果: {result2}")  # 预期输出: False
    print("-" * 30)

    # 测试用例3：s1长度等于s2长度且是排列
    s1_3, s2_3 = "adc", "dcda"
    result3 = checkInclusion(s1_3, s2_3)
    print(f"s1 = '{s1_3}', s2 = '{s2_3}'")
    print(f"结果: {result3}")  # 预期输出: True
    print("-" * 30)

    # 测试用例4：s1长度大于s2长度
    s1_4, s2_4 = "abc", "ab"
    result4 = checkInclusion(s1_4, s2_4)
    print(f"s1 = '{s1_4}', s2 = '{s2_4}'")
    print(f"结果: {result4}")  # 预期输出: False
    print("-" * 30)

    # 测试用例5：包含重复字符的排列
    s1_5, s2_5 = "aab", "baab"
    result5 = checkInclusion(s1_5, s2_5)
    print(f"s1 = '{s1_5}', s2 = '{s2_5}'")
    print(f"结果: {result5}")  # 预期输出: True

3.寻找矩阵中的最长递增路径

def longestIncreasingPath(matrix):
    """
    在矩阵中找到最长递增路径的长度。路径可以向上下左右四个方向移动。
    参数:
        matrix: List[List[int]], 整数矩阵
    返回:
        int, 最长递增路径的长度
    思路:
        深度优先搜索(DFS)结合记忆化(memoization)。从每个点开始DFS，用memo矩阵缓存从该点出发能得到的最长路径长度，避免重复计算。
    """
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    # 记忆化矩阵，初始化为0，表示尚未计算
    memo = [[0] * cols for _ in range(rows)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右，下，左，上
    max_length = 0

    def dfs(i, j):
        """返回从位置(i, j)开始的最长递增路径长度"""
        # 如果已经计算过，直接返回缓存值
        if memo[i][j] != 0:
            return memo[i][j]

        # 路径长度至少为1（当前位置自身）
        length = 1
        for dx, dy in directions:
            ni, nj = i + dx, j + dy
            # 检查新位置是否在矩阵内且值严格大于当前位置
            if 0 <= ni < rows and 0 <= nj < cols and matrix[ni][nj] > matrix[i][j]:
                # 递归计算从新位置开始的路径长度，并更新当前最大长度
                length = max(length, 1 + dfs(ni, nj))

        # 将计算结果存入缓存
        memo[i][j] = length
        return length

    # 遍历矩阵中的每个点作为起点
    for i in range(rows):
        for j in range(cols):
            max_length = max(max_length, dfs(i, j))

    return max_length

# --- 测试用例与直接运行部分 ---
if __name__ == "__main__":
    # 测试用例1：常规矩阵
    matrix1 = [
        [9, 9, 4],
        [6, 6, 8],
        [2, 1, 1]
    ]
    result1 = longestIncreasingPath(matrix1)
    print("测试矩阵1:")
    for row in matrix1:
        print(row)
    print(f"最长递增路径长度: {result1}")  # 预期输出: 4 (路径: 1 -> 2 -> 6 -> 9)
    print("-" * 30)

    # 测试用例2：递增序列
    matrix2 = [
        [3, 4, 5],
        [2, 7, 6],
        [1, 8, 9]
    ]
    result2 = longestIncreasingPath(matrix2)
    print("测试矩阵2:")
    for row in matrix2:
        print(row)
    print(f"最长递增路径长度: {result2}")  # 预期输出: 7 (路径之一: 1->2->3->4->5->6->7->8)
    print("-" * 30)

    # 测试用例3：所有元素相同
    matrix3 = [
        [7, 7],
        [7, 7]
    ]
    result3 = longestIncreasingPath(matrix3)
    print("测试矩阵3:")
    for row in matrix3:
        print(row)
    print(f"最长递增路径长度: {result3}")  # 预期输出: 1
    print("-" * 30)

    # 测试用例4：单行矩阵
    matrix4 = [
        [1, 2, 3, 4, 5]
    ]
    result4 = longestIncreasingPath(matrix4)
    print("测试矩阵4:")
    for row in matrix4:
        print(row)
    print(f"最长递增路径长度: {result4}")  # 预期输出: 5
    print("-" * 30)

    # 测试用例5：空矩阵
    matrix5 = []
    result5 = longestIncreasingPath(matrix5)
    print("测试矩阵5: []")
    print(f"最长递增路径长度: {result5}")  # 预期输出: 0