Leetcode

买卖股票的最佳时机 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i, own):
            if i>=n:
                if own:
                    return float("-inf")
                else:
                    return 0
            if own:
                return max(dfs(i+1, True), dfs(i+1, False)+prices[i])
            else:
                return max(dfs(i+1, True) - prices[i], dfs(i+1, False))
        ans = dfs(0, False)
        return ans

有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        if n%2:
            return False
        match = {")": "(", "]": "[", "}": "{"}
        st = []
        for c in s:
            if c not in match:
                st.append(c)
            elif not st or st.pop()!=match[c]:
                return False
        return len(st) == 0

环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

全排列 II

注意要sort再全排列避免重复，如果相同项没用就先都不用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 关键：去重前必须排序
        n = len(nums)
        ans = []
        path = [0] * n
        on_path = [False] * n

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            for j, on in enumerate(on_path):
                if on:
                    continue
                if j > 0 and nums[j] == nums[j - 1] and not on_path[j - 1]:
                    continue  # 避免重复
                path[i] = nums[j]
                on_path[j] = True
                dfs(i + 1)
                on_path[j] = False

        dfs(0)
        return ans

接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        leftmax, rightmax = 0, 0
        ans = 0
        while left < right:
            leftmax = max(leftmax, height[left])
            rightmax = max(rightmax, height[right])
            if leftmax < rightmax:
                ans += leftmax - height[left]
                left+=1
            else:
                ans += rightmax - height[right]
                right-=1
        return ans

相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        nodeA = headA
        nodeB = headB
        while nodeA != nodeB:
            nodeA = nodeA.next if nodeA else headB
            nodeB = nodeB.next if nodeB else headA

        return nodeA

仅执行一次字符串交换能否使两个字符串相等

最多交换 s2 中两个字符一次，能不能变成 s1，那必须刚好有 两个位置不同，并且交叉相等

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        diff = []
        for i in range(len(s1)):
            if s1[i]!=s2[i]:
                diff.append(i)
        if len(diff) == 0:
            return True
        if len(diff) !=2:
            return False
        i, j = diff
        return s1[i] == s2[j] and s1[j] == s2[i]

最长递增子序列

dp数组含义是以nums[i]结尾的最长递增子序列长度

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

寻找两个正序数组的中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)

        total = m + n
        half = (total + 1) // 2
        # 这里m+1是因为i的可能区间是[0,m]，有可能一个不取
        left, right = -1, m + 1

        while left + 1 < right:
            # 在 nums1 里取 i 个元素放左边
            # 在 nums2 里取 j 个元素放左边
            i = (left + right) // 2
            j = half - i

            nums1_left = nums1[i - 1] if i > 0 else float("-inf")
            nums1_right = nums1[i] if i < m else float("inf")

            nums2_left = nums2[j - 1] if j > 0 else float("-inf")
            nums2_right = nums2[j] if j < n else float("inf")

            if nums1_left <= nums2_right and nums2_left <= nums1_right:
                if total % 2:
                    return max(nums1_left, nums2_left)
                else:
                    return (
                        max(nums1_left, nums2_left) + min(nums1_right, nums2_right)
                    ) / 2
            # nums1 左边拿多了，i 要变小
            elif nums1_left > nums2_right:
                right = i
            # nums1 左边拿少了，i 要变大
            else:
                left = i

数组中的第K个最大元素

小根堆

1
2
3
4
5
6
7
8
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap,num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

使数组按非递减顺序排列 （重点多理解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        stack = []  # 每个元素是 (num, step)
        ans = 0

        for x in nums:
            step = 0

            # 找左边有没有一个比 x 大的元素，最终能删除 x
            while stack and stack[-1][0] <= x:
                step = max(step, stack[-1][1])
                stack.pop()

            # 如果左边还存在一个比 x 大的数，那么 x 最终会被删除
            if stack:
                step += 1
            else:
                step = 0

            ans = max(ans, step)
            stack.append((x, step))

        return ans

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def quickSort(self, nums: List[int], l: int, r: int) -> None:
        # 区间长度为 0 或 1，直接返回
        if l >= r:
            return

        # 选最后一个数作为基准值
        x = nums[r]

        # i 指向当前 <= x 区间的下一个位置
        i = l

        # 将小于等于基准值的元素放到左边
        for j in range(l, r):
            if nums[j] <= x:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

        # 最后把基准值放到正确位置
        nums[i], nums[r] = nums[r], nums[i]

        # 递归排序左半部分
        self.quickSort(nums, l, i - 1)

        # 递归排序右半部分
        self.quickSort(nums, i + 1, r)

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1],arr[j]
                swapped = True
        
        if not swapped:
            break
    return arr

平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if node is None:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            if left == -1 or right == -1 or abs(left-right)>1:
                return -1
            return max(left, right) + 1
        
        return dfs(root) != -1

把-1作为标识传递

零钱兑换

完全背包问题

1
2
3
4
5
6
7
8
9
10
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount+1)
        n = len(coins)
        dp[0] = 0
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        
        return dp[amount] if dp[amount]!=float("inf") else -1

拼写单词

1
2
3
4
5
6
7
8
9
10
class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        count_c = Counter(chars)
        ans = 0

        for s in words:
            if Counter(s) <= count_c:
                ans += len(s)

        return ans

最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = 0
        ans_right = 0
        # 奇回文串
        for i in range(n):
            left = right = i
            while left>=0 and right<n and s[left] == s[right]:
                left-=1
                right+=1
            if right - left - 1 > ans_right - ans_left:
                ans_right = right
                ans_left = left+1
        # 偶回文串
        for i in range(n-1):
            left = i
            right = i+1
            while left>=0 and right<n and s[left] == s[right]:
                left-=1
                right+=1
            if right - left - 1 > ans_right - ans_left:
                ans_right = right
                ans_left = left+1
        
        return s[ans_left:ans_right]

丑数

1
2
3
4
5
6
7
8
9
class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        return n & (n - 1) == 0

知道位运算可以判断2的幂次

腐烂的橘子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fresh = 0
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    fresh +=1
                elif grid[i][j] == 2:
                    q.append((i,j))
        
        if fresh == 0:
            return 0
        if len(q) == 0:
            return -1
        
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        ans = 0
        while q and fresh > 0:
            per = len(q)
            for _ in range(per):
                i, j = q.popleft()

                for di, dj in directions:
                    new_i = i + di
                    new_j = j + dj
                    if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] == 1:
                        grid[new_i][new_j] = 2
                        fresh -= 1
                        q.append((new_i, new_j))
            ans +=1
        
        return ans if fresh == 0 else -1

最大数

1
2
3
4
5
6
7
8
9
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = list(map(str, nums))
        nums.sort(
            key=cmp_to_key(
                lambda a, b: int(b + a) - int(a + b)
            )
        )
        return "0" if nums[0] == "0" else ''.join(nums)

机器学习

AUC曲线

基于二分类模型的 ROC 曲线点 (FPR, TPR)，使用 梯形积分法（Trapezoidal Rule） 计算 AUC（Area Under Curve）
$$
\mathrm{TPR}=\mathrm{Recall} = \frac{TP}{TP+FN} \qquad \mathrm{FPR}=\frac{FP}{FP+TN}
$$
衡量的是：模型把正样本排在负样本前面的能力，AUC 越大，说明模型整体排序能力越强

ROC 曲线横轴是FPR，纵轴是TPR

AUC 含义
1.0 完美排序，所有正样本得分都高于负样本
0.5 接近随机猜测
< 0.5 排序方向可能反了，模型倾向于把负样本排在正样本前面

给定一组按 FPR 递增排序 的点：
$$
\left{
(\mathrm{FPR}_0, \mathrm{TPR}_0),
(\mathrm{FPR}_1, \mathrm{TPR}_1),
\ldots,
(\mathrm{FPR}_n, \mathrm{TPR}_n)
\right}
$$
AUC 的梯形积分公式为：
$$
\mathrm{AUC}

\sum_{i=1}^{n}
\frac{
\left(\mathrm{FPR}i-\mathrm{FPR}{i-1}\right)
\left(\mathrm{TPR}i+\mathrm{TPR}{i-1}\right)
}{2}
$$
在画 ROC 曲线时，不断降低分类阈值 threshold

阈值越低，被判为正类的样本越多，所以 TP 可能增加，FP 也可能增加，因此 TPR 和 FPR 都呈现非递减趋势

1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List
def calculate_auc(self, FPR: List[float], TPR: List[float]) -> float:
    """计算曲线下面积 (AUC) 的函数"""
    n = len(FPR)  # 获取假阳性率列表的长度
    auc = 0.0  # 初始化AUC值

    # 遍历FPR和TPR，计算相邻点形成的梯形面积
    for i in range(1, n):
        width = FPR[i] - FPR[i - 1]  # 计算梯形的宽度
        height = (TPR[i] + TPR[i - 1]) / 2  # 计算梯形的高度
        auc += width * height  # 累加当前梯形的面积

    return auc  # 返回最终计算得到的AUC值

ROC 曲线整体向右上方走

因为 threshold 从高到低扫描时，预测为正的样本集合只会越来越大，不会变小

新加入正类集合的样本只有两种情况：

  1. 新加入的是正样本：$TP \uparrow \Rightarrow TPR \uparrow$，表现为 ROC 曲线 向上走
  2. 新加入的是负样本：$FP \uparrow \Rightarrow FPR \uparrow$，表现为 ROC 曲线 向右走