LeetCode 第180场周赛

半个小时做完前三题然后就开始摸鱼🐟

Contents

1 第一题：矩阵中的幸运数
2 第二题：设计一个支持增量操作的栈
3 第三题：将二叉搜索树变平衡
4 第四题：最大的团队表现值

第一题：矩阵中的幸运数

　　给你一个 m * n 的矩阵，矩阵中的数字各不相同。请你按任意顺序返回矩阵中的所有幸运数。
　　
　　幸运数是指矩阵中满足同时下列两个条件的元素：
　　
　　在同一行的所有元素中最小
　　在同一列的所有元素中最大
　　
　　
　　示例 1：
　　输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
　　输出：[15]
　　解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
　　
　　示例 2：
　　输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
　　输出：[12]
　　解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
　　
　　示例 3：
　　输入：matrix = [[7,8],[1,2]]
　　输出：[7]

思路：
　　先获取每行的最小值的集合，再获取每列的最大值的集合。因为所有元素都是不相同的。两个集合的交集即为结果。

代码：

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        ans = []
        m = len(matrix)
        n = len(matrix[0])
        transpose = [[matrix[i][j] for i in range(m)] for j in range(n)]  # 转置
        line_min = [min(matrix[i]) for i in range(m)]  # 每行的最小值
        col_max = [max(transpose[i]) for i in range(n)]  # 转置以后每行的最大值，也就是原矩阵每列的最大值
        for num in line_min:
            if num in col_max:
                ans.append(num)

        return ans

class Solution:

def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:

ans = []

m = len(matrix)

n = len(matrix[0])

transpose = [[matrix[i][j] for i in range(m)] for j in range(n)] # 转置

line_min = [min(matrix[i]) for i in range(m)] # 每行的最小值

col_max = [max(transpose[i]) for i in range(n)] # 转置以后每行的最大值，也就是原矩阵每列的最大值

for num in line_min:

if num in col_max:

ans.append(num)

return ans

第二题：设计一个支持增量操作的栈

　　请你设计一个支持下述操作的栈。
　　
　　实现自定义栈类 CustomStack ：
　　
　　CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push 操作。
　　void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
　　int pop()：返回栈顶的值，或栈为空时返回 -1 。
　　void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
　　
　　示例：
　　输入：
　　[“CustomStack”,”push”,”push”,”pop”,”push”,”push”,”push”,”increment”,”increment”,”pop”,”pop”,”pop”,”pop”]
　　[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
　　输出：
　　[null,null,null,2,null,null,null,null,null,103,202,201,-1]
　　解释：
　　CustomStack customStack = new CustomStack(3); // 栈是空的 []
　　customStack.push(1); // 栈变为 [1]
　　customStack.push(2); // 栈变为 [1, 2]
　　customStack.pop(); // 返回 2 –> 返回栈顶值 2，栈变为 [1]
　　customStack.push(2); // 栈变为 [1, 2]
　　customStack.push(3); // 栈变为 [1, 2, 3]
　　customStack.push(4); // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
　　customStack.increment(5, 100); // 栈变为 [101, 102, 103]
　　customStack.increment(2, 100); // 栈变为 [201, 202, 103]
　　customStack.pop(); // 返回 103 –> 返回栈顶值 103，栈变为 [201, 202]
　　customStack.pop(); // 返回 202 –> 返回栈顶值 202，栈变为 [201]
　　customStack.pop(); // 返回 201 –> 返回栈顶值 201，栈变为 []
　　customStack.pop(); // 返回 -1 –> 栈为空，返回 -1

思路：
　　按要求写就行了，见代码。

代码：

class CustomStack:

    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.data = []

    def push(self, x: int) -> None:
        if len(self.data) >= self.maxSize:
            return
        self.data.append(x)


    def pop(self) -> int:
        if len(self.data) == 0:
            return -1
        top = self.data[-1]
        self.data = self.data[:-1]
        return top


    def increment(self, k: int, val: int) -> None:
        k = min(k, len(self.data))
        for i in range(k):
            self.data[i] += val

class CustomStack:

def __init__(self, maxSize: int):

self.maxSize = maxSize

self.data = []

def push(self, x: int) -> None:

if len(self.data) >= self.maxSize:

return

self.data.append(x)

def pop(self) -> int:

if len(self.data) == 0:

return -1

top = self.data[-1]

self.data = self.data[:-1]

return top

def increment(self, k: int, val: int) -> None:

k = min(k, len(self.data))

for i in range(k):

self.data[i] += val

第三题：将二叉搜索树变平衡

　　给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
　　
　　如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是平衡的。
　　
　　如果有多种构造方法，请你返回任意一种。
　　
　　
　　示例：
　　
　　输入：root = [1,null,2,null,3,null,4,null,null]
　　输出：[2,1,3,null,null,null,4]
　　解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

思路：
　　常见做法：旋转换根。
　　非常见做法：用有序数组重构树🌲。先中序遍历二叉搜索树得到有序数组。再通过有序数组构建平衡二叉树。

代码：
　　这里给出的是非常见做法

class Solution:
    def build(self, nums, i, j):
        mid = (i+j)//2
        root = TreeNode(nums[mid])
        if(i==j):
            return root
        if i <= mid-1:
            root.left = self.build(nums,i,mid-1)
        if mid+1 <= j:
            root.right = self.build(nums, mid+1, j)

        return root


    def balanceBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return root

        nums = []  
        def dfs(root):
            if root.left:
                dfs(root.left)

            nums.append(root.val)  # 中序遍历得到有序数组

            if root.right:
                dfs(root.right)

        dfs(root)
        return self.build(nums, 0, len(nums)-1)

class Solution:

def build(self, nums, i, j):

mid = (i+j)//2

root = TreeNode(nums[mid])

if(i==j):

return root

if i <= mid-1:

root.left = self.build(nums,i,mid-1)

if mid+1 <= j:

root.right = self.build(nums, mid+1, j)

return root

def balanceBST(self, root: TreeNode) -> TreeNode:

if not root:

return root

nums = []

def dfs(root):

if root.left:

dfs(root.left)

nums.append(root.val) # 中序遍历得到有序数组

if root.right:

dfs(root.right)

dfs(root)

return self.build(nums, 0, len(nums)-1)

第四题：最大的团队表现值

　　公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。
　　
　　团队表现值的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
　　
　　
　　示例 1：
　　输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
　　输出：60
　　解释：
　　我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
　　
　　示例 2：
　　输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
　　输出：68
　　解释：
　　
　　此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。
　　
　　输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
　　输出：72

思路：

　　先按效率降序排序，然后用一个最多含有k个元素的堆维护当前最大的k个速度。
　　分析：根据题目给出的数据量，复杂度应该控制在O(nlogn)之内。由于遍历效率复杂度已经为O(n)，所以要在O(logn)的时间复杂度找到当前最大的k个速度。如果使用有序的数组来维护当前最大的k个速度，查找新速度位置的复杂度为O(logn)(二分查找)，但是插入的复杂度为O(n)，因此只能使用堆。
　　用一个变量speeds_sum记录当前堆中元素的和。因为重新计算堆的和需要的时间复杂度是O(n)。

代码：

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

        z = list(zip(speed, efficiency))

        s = sorted(z, key=lambda kv: (kv[1], kv[0]), reverse=True)  
        speed = [i[0] for i in s]  # 按效率降序排序后的速度
        efficiency = [i[1] for i in s]  # 按效率降序排序后的效率

        speeds = []
        heapq.heappush(speeds, speed[0])
        speeds_sum = speed[0]
        ans = speed[0] * efficiency[0]
        for i in range(1, k):  # 不到k个元素，直接插入堆
            speed_i = speed[i]

            heapq.heappush(speeds, speed_i)
            speeds_sum += speed_i

            ans = max(ans, speeds_sum * efficiency[i])

        for i in range(k, n):  # 超过k个元素，如果新元素比堆中最小的元素大才能插入堆。
            speed_i = speed[i]
            speeds_min = heapq.heappop(speeds)
            if speed_i <= speeds_min:
                heapq.heappush(speeds, speeds_min)
                continue

            speeds_sum -= speeds_min
            heapq.heappush(speeds, speed_i)
            speeds_sum += speed_i

            ans = max(ans, speeds_sum * efficiency[i])

        return ans % (1000000000 + 7)

class Solution:

def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

z = list(zip(speed, efficiency))

s = sorted(z, key=lambda kv: (kv[1], kv[0]), reverse=True)

speed = [i[0] for i in s] # 按效率降序排序后的速度

efficiency = [i[1] for i in s] # 按效率降序排序后的效率

speeds = []

heapq.heappush(speeds, speed[0])

speeds_sum = speed[0]

ans = speed[0] * efficiency[0]

for i in range(1, k): # 不到k个元素，直接插入堆

speed_i = speed[i]

heapq.heappush(speeds, speed_i)

speeds_sum += speed_i

ans = max(ans, speeds_sum * efficiency[i])

for i in range(k, n): # 超过k个元素，如果新元素比堆中最小的元素大才能插入堆。

speed_i = speed[i]

speeds_min = heapq.heappop(speeds)

if speed_i <= speeds_min:

heapq.heappush(speeds, speeds_min)

continue

speeds_sum -= speeds_min

heapq.heappush(speeds, speed_i)

speeds_sum += speed_i

ans = max(ans, speeds_sum * efficiency[i])

return ans % (1000000000 + 7)