刷题记录- 202512

已做题目

sorting

quick sort/ quick selection

Find TopK largest- QuickSelect快速选择 method

思路： divide and conquer. 每次找到start, end-1 范围内array[end]适合插入的位置，该位置左边是大于array[end]的所以元素，右边是所有小于array[end]的元素

searching

二分查找-II_牛客题霸_牛客网www.nowcoder.com

思路：移动边界时，+1， -1是为了避免死循环，不+/-1是为了保留数值

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        if not nums:
            return -1
        # write code here
        l, r = 0, len(nums)
        while l<r:
            mid = (l+r)//2
            if nums[mid] <target:
                # +1是确保在 r= l+1时 不会mid=l 导致死循环
                l = mid+1
            elif nums[mid] > target:
                # -1 是确保在 r= l+1时 不会mid=r 导致死循环
                r = mid-1
            else:
                #确保找到target后，l和r至少有一个是包含target
                r = mid
        if l< len(nums) and nums[l]==target:
            return l
        if r >=0 and nums[r] == target:
            return r
        return -1

heap/Array

23. 合并 K 个升序链表 - 力扣（LeetCode）力扣 LeetCode

思路: min-heap, 时间复杂度nlogk

滑动窗口的最大值_牛客题霸_牛客网www.nowcoder.com

滑动窗口+ max-heap

DFS

216. 组合总和 III - 力扣（LeetCode）力扣 LeetCode

思路：组合问题，不是排列问题， recursion 里只有2个child
备注：细节问题，注意传参被传错

BFS

岛屿数量_牛客题霸_牛客网www.nowcoder.com

思路： bfs，遍历整个matrix，每次找到element=1 就bfs queue。注意：queue append要是当前位置的上下左右4个方向，而不是右下，因为queue append的方向并不是往右下角遍历

Tree

树遍历

在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网www.nowcoder.com

注意：o1, o2不能是ancester
代码

class Solution:
    def helper(self, root, o1, o2):
        if not root:
            return -1

        l = self.helper(root.left, o1, o2)
        r = self.helper(root.right, o1, o2)
        if (l and r ) or (root.val in [o1, o2] and (l or r)):
            self.ancester = root.val
            
        if root.val in [o1,o2] or l or r:
            return 1
        return -1

    def helper2(self, root, o1, o2):
        if not root:
            return None
        if root.val in [o1, o2]:
            return root
        t1 = self.helper2(root.left, o1,o2)
        t2 = self.helper2(root.right, o1,o2)
        if not t1:
            return t2
        if not t2:
            return t1
        return root


    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        # self.ancester = -1
        # self.helper(root, o1,o2)
        # return self.ancester
        val= self.helper2(root,o1,o2)
        if val:
            return val.val
        return -1