LeetCode - Google 校招100题 第9天 Hard 题汇总 (12题)

LintCode：450 · K组翻转链表

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        """
        模拟多次链表反转，时间O(n)，空间O(1)
        """
        dummy = ListNode()
        dummy.next = head # head节点移动，需要保存
        prev, tail = dummy, dummy
        while head: # 移动head节点
            for i in range(k):
                tail = tail.next  # 更新next节点
                if not tail:  # 链表末尾, 返回头节点
                    return dummy.next
            nxt = tail.next # 下个连接位置
            tail.next = None
            head, tail = self.reverse(head)
            prev.next = head # prev是前置节点
            tail.next = nxt
            prev = tail # 前置节点prev到结尾
            head = nxt # 更新head节点，头节点到nxt继续开始
        return dummy.next
    def reverse(self, head):
        # 最前面节点head变成最后，指向tail.next
        prev, cur = None, head # 当前节点
        while cur:  #移动prev和cur节点
            nxt = cur.next # 保存当前节点nxt
            cur.next = prev  # 下一个指向之前
            prev = cur # 前置节点编程
            cur = nxt # 指向下一个节点
        return prev, head

LintCode：104 · 合并k个排序链表

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
        分而治之，时间O(n*k*logk)，k=2，空间复杂度 O(logk)
        """
        if not lists:
            return None
        res = self.merge(lists,0,len(lists)-1) # 调用分治策略
        return res
    def merge(self, lists, l, r):
        """
        平均分治合并链表
        """
        if l == r:
            return lists[l]  # 返回单独的链表
        mid = (l+r)//2  # 平均分成2份
        l1 = self.merge(lists, l, mid) # 排序l->mid
        l2 = self.merge(lists, mid+1, r)  # 排序mid+1->r
        return self.merge_two_list(l1, l2)  # 合并两个链表
    def merge_two_list(self, l1, l2):
        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val < l2.val: 
                cur.next = l1
                l1 = l1.next
            else: 
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next

LintCode：94 · 二叉树中的最大路径和

class Solution:
    def __init__(self):
        self.res = float("-inf") # 全局变量
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        """
        递归, 非叶节点的最大贡献值,dfs(root)+res, 时间O(n), 空间O(n)
        """
        def dfs(root):
            if not root:
                return 0
            l_val = max(0, dfs(root.left)) 
            r_val = max(0, dfs(root.right))
            tmp = l_val + r_val + root.val
            self.res = max(tmp, self.res)
            return root.val + max(l_val, r_val)  # 最大贡献取决于左右节点
        dfs(root)
        return self.res

LintCode：154 · 正则表达式匹配

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        """
        正则表达式匹配，二维动态规划, 时间O(m*n)，空间O(m*n)
        """
        m, n = len(s), len(p)
        dp = [[False] * (n+1) for _ in range(m+1)]  # 初始化
        dp[0][0] = True
        def matches(i, j):
            if p[j-1] == '.':  # .和任何都match
                return True
            return s[i-1] == p[j-1]  # 或者相等

        # 第2位是*，则与前2位相同
        for i in range(2, n+1):
            if p[i-1] == '*':  
                dp[0][i] = dp[0][i-2]

        for i in range(1, m+1):  # 遍历s
            for j in range(1, n+1):  # 遍历p:1~n+1
                if p[j-1] == '*':  # 末位是*
                    dp[i][j] = dp[i][j-2]  # p[j-2]"*"出现0次
                    if matches(i, j-1):  # 前面匹配
                        # s[i-1]匹配，是j不是j-1，避免剩余p的数量小于s的数量
                        dp[i][j] = dp[i][j] or dp[i-1][j]   
                else:
                    if matches(i, j):  # 不是*，只看是否match
                        dp[i][j] = dp[i-1][j-1]
        return dp[-1][-1]

Lintcode：65 · 两个排序数组的中位数

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        划分数组二分搜索, 时间O(log min(m,n))), 空间O(1)
        """
        if  len(nums1) > len(nums2): # 确保列表1长度小于列表2
            nums2, nums1 = nums1, nums2
        n1, n2 = len(nums1), len(nums2)
        k = (n1+n2+1)//2 # 全量中值
        l, r = 0, n1-1
        while l <= r:  # 二分搜索
            m1 = (r+l)//2 # m1中值
            m2 = k-m1 # m2位置
            if nums1[m1] <= nums2[m2-1]:  # 避免偶数m2越界
                l = m1+1
            else:
                r = m1-1
        m1 = l  # l越界1位，所以-1
        m2 = k-m1 
        v_min = float("-inf")
        c1 = max(nums1[m1-1] if m1>0 else v_min, nums2[m2-1] if m2>0 else v_min)
        if (n1+n2)%2 == 1: # 奇数
            return c1
        v_max = float("inf")
        c2 = min(nums1[m1] if m1<n1 else v_max, nums2[m2] if m2<n2 else v_max)
        return (c1 + c2) / 2 # 偶数

Lintcode：532 · 逆序对

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        """
        计算逆序对的总数，归并排序，时间O(nlogn)，空间O(n)
        """
        n = len(nums)
        res = self.merge_sort(nums, 0, n-1)  # 均为数值边界值
        return res
    def merge_sort(self, nums, l, r):
        if l >= r:  # 1. 中止条件
            return 0
        # 2. 递归划分
        m = (l+r)//2
        vl = self.merge_sort(nums, l, m)
        vr = self.merge_sort(nums, m+1, r)
        # 3. 合并阶段
        v = self.merge(nums, l, r)
        res = vl + vr + v
        return res
    def merge(self, nums, l, r):
        res = 0
        m = (l+r)//2
        tmp = [0]*(r-l+1)
        i, j = l, m+1  # 左右的起始位置
        k = 0
        while i < m+1 and j < r+1:
            if nums[i] <= nums[j]:  
                tmp[k] = nums[i]
                i += 1
            else:
                tmp[k] = nums[j]
                j += 1
                res += m - i + 1 # 统计逆序对
            k += 1
        if i == m+1:  # i到达j的位置
            tmp[k:] = nums[j:r+1]
        if j == r+1:
            tmp[k:] = nums[i:m+1]
        nums[l:r+1] = tmp  # 更新有序列表
        return res

Lintcode：363 · 接雨水

class Solution:
    def trap(self, height: List[int]) -> int:
        """
        接雨水，左右遍历最大值，时间O(n)，空间O(n)
        """
        n = len(height) # 样本数量
        left_max = [height[0]] + [0] * (n-1) # 左侧最大值
        for i in range(1, n):  # 正序
            left_max[i] = max(left_max[i-1], height[i]) # 更新左侧最大值
        right_max = [0] * (n-1) + [height[n-1]] # 右侧最大值
        for i in range(n-2, -1, -1):  # 倒序
            right_max[i] = max(right_max[i+1], height[i]) # 更新右侧最大值
        res = 0
        for i in range(n):
          	# min()获取上沿，减去高度就是雨水数量
            tmp = min(left_max[i], right_max[i]) - height[i]
            res += tmp
        return res

Lintcode：412 · 分糖果

class Solution:
    def candy(self, ratings: List[int]) -> int:
        """
        更高评分更多的糖果，至少1个，两次遍历，满足左规则和右规则，时间O(n)，空间O(n)
        """
        n = len(ratings)
        if n <= 1:
            return n
        res = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                res[i] = max(res[i], res[i-1]+1)
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                res[i] = max(res[i], res[i+1]+1)
        return sum(res)

Lintcode：362 · 滑动窗口的最大值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        队列，将单调递减序列的idx存入q，即队头最大，例如[3,2,1]，判断序号，当idx超过i-k时，队头出队
        输出连续窗口中的最大值列表，时间O(n)，空间O(k)
        """
        n = len(nums)
        if n == 0:
            return []
        if n <= k:
            return [max(nums)]
        q = []  # 队列，队头索引最大
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
        res = []
        res.append(nums[q[0]])
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            if q[0] <= i-k:
                q.pop(0)
            res.append(nums[q[0]])
        return res

LintCode：32 · 最小子串覆盖

from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        滑动窗口，覆盖最小的子串，子串不考虑顺序，时间复杂度 O(m+n)，空间复杂度 O(1)
        """
        m = len(s)
        n = len(t)
        if m < n:
            return ""
        cnt_t = Counter(t)  # 目标计数器字典
        cnt_w = Counter()   # 区间的计数器字典
        nc = len(cnt_t)  # 字母种类
        rl, rr = -1, len(s)  # 目标的最大窗口，超出边界
        tmp = 0
        l = 0  # 左指针
        for r, c in enumerate(s):
            cnt_w[c] += 1  # s计数器
            if cnt_w[c] == cnt_t[c]:  # 某个字符数量相等
                tmp += 1  
            while tmp == nc:  # 满足条件
                if rr - rl >= r - l:  # 区间更小
                    rl, rr = l, r  # 更新左右指针
                # 如果数量相等，之后数量需要减一，所以less需要提前+1
                c_tmp = s[l]  # 左指针当前字母
                if cnt_w[c_tmp] == cnt_t[c_tmp]:
                    tmp -= 1  # 不重复+1
                cnt_w[c_tmp] -= 1  # 指针减1
                l += 1  # 已经更新，所以需要移动左指针
        return "" if rl < 0 else s[rl:rr+1]

LintCode：426 · 恢复IP地址

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        """
        复原IP地址，回溯法，划分数字，时间O(3^4*|s|)，3个数字、4段；空间O(4)
        """
        m = 4
        n = len(s)
        if n < 4:
            return []
        res = []
        tmp = [0] * m
        def dfs(i, j, tmp):  # i是ip位置，j是字符串位置
            if i == m and j == n:
                res.append(".".join([str(t) for t in tmp]))
                return
            if i == m or j == n:
                return
            if s[j] == "0":
                tmp[i] = 0
                dfs(i+1, j+1, tmp)
                return
            v = 0
            for k in range(j, n):
                v = v*10 + int(s[k])
                if 0 < v <= 255:
                    tmp[i] = v
                    dfs(i+1, k+1, tmp)  # 注意是k
                else:
                    break
        dfs(0, 0, tmp)
        return res

Lintcode: 193 · 最长有效括号

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        """
        最长有效括号, stack+flags更清晰，格式正确且连续，时间O(n), 空间O(n)
        """
        n = len(s)
        if n <= 1:
            return 0
        flags = [False] * n
        stack = []
        for i in range(n):
            if s[i] == "(":
                stack.append(i)
            else:
                if stack:
                    j = stack.pop(-1)
                    flags[i] = flags[j] = True
        res = 0
        tmp = 0
        for f in flags:
            if f:
                tmp += 1
                res = max(res, tmp)
            else:
                tmp = 0
        return res