LeetCode第176场周赛

有一道贪心不太熟排名 167 / 2409

Contents

1 第一题：统计有序矩阵中的负数
2 第二题：最后 K 个数的乘积
3 第三题：最多可以参加的会议数目
4 第四题：多次求和构造目标数组

第一题：统计有序矩阵中的负数

　　给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
　　
　　请你统计并返回 grid 中负数的数目。
　　
　　示例 1：
　　输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
　　输出：8
　　解释：矩阵中共有 8 个负数。
　　
　　示例 2：
　　输入：grid = [[3,2],[1,0]]
　　输出：0
　　
　　示例 3：
　　输入：grid = [[1,-1],[-1,-1]]
　　输出：3
　　
　　示例 4：
　　输入：grid = [[-1]]
　　输出：1

　　思路: 统计即可

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        ans = 0
        for i in grid:
            for j in i:
                if j < 0:
                    ans += 1
        return ans

class Solution:

def countNegatives(self, grid: List[List[int]]) -> int:

ans = 0

for i in grid:

for j in i:

if j < 0:

ans += 1

return ans

第二题：最后 K 个数的乘积

　　请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
　　
　　1. add(int num)
　　
　　将数字 num 添加到当前数字列表的最后面。
　　2. getProduct(int k)
　　
　　返回当前数字列表中，最后 k 个数字的乘积。
　　你可以假设当前列表中始终至少包含 k 个数字。
　　题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
　　
　　示例：
　　输入：
　　[“ProductOfNumbers”,”add”,”add”,”add”,”add”,”add”,”getProduct”,”getProduct”,”getProduct”,”add”,”getProduct”]
　　[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
　　
　　输出：
　　[null,null,null,null,null,null,20,40,0,null,32]
　　
　　解释：
　　ProductOfNumbers productOfNumbers = new ProductOfNumbers();
　　productOfNumbers.add(3); // [3]
　　productOfNumbers.add(0); // [3,0]
　　productOfNumbers.add(2); // [3,0,2]
　　productOfNumbers.add(5); // [3,0,2,5]
　　productOfNumbers.add(4); // [3,0,2,5,4]
　　productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
　　productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
　　productOfNumbers.getProduct(4); // 返回 0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
　　productOfNumbers.add(8); // [3,0,2,5,4,8]
　　productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32

　　思路：这题其实测试用例很简单，不过考虑了时间复杂度用一个数组product[]记录累乘的值，然后用product[-1]与product[-k-1]作除法来求最后k个元素的乘积。

class ProductOfNumbers:

    def __init__(self):
        self.l = 0
        self.product = []
        self.lastzero = -1

    def add(self, num: int) -> None:
        if len(self.product)==0:
            if num==0:
                self.lastzero = 0
            self.product = [num]
        else:
            if num==0:
                self.product.append(1)
                self.lastzero = self.l
            else:
                if self.product[-1]==0:
                    self.product.append(num)
                else:
                    self.product.append(num*self.product[-1])


        self.l += 1


    def getProduct(self, k: int) -> int:
        if self.l - k <= self.lastzero:
            return 0
        try:
            return self.product[-1] // self.product[-k-1]
        except:
            return self.product[-1]

class ProductOfNumbers:

def __init__(self):

self.l = 0

self.product = []

self.lastzero = -1

def add(self, num: int) -> None:

if len(self.product)==0:

if num==0:

self.lastzero = 0

self.product = [num]

else:

if num==0:

self.product.append(1)

self.lastzero = self.l

else:

if self.product[-1]==0:

self.product.append(num)

else:

self.product.append(num*self.product[-1])

self.l += 1

def getProduct(self, k: int) -> int:

if self.l - k <= self.lastzero:

return 0

try:

return self.product[-1] // self.product[-k-1]

except:

return self.product[-1]

第三题：最多可以参加的会议数目

　　给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
　　
　　你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
　　
　　请你返回你可以参加的最大会议数目。
　　
　　示例 1：
　　输入：events = [[1,2],[2,3],[3,4]]
　　输出：3
　　解释：你可以参加所有的三个会议。
　　安排会议的一种方案如上图。
　　第 1 天参加第一个会议。
　　第 2 天参加第二个会议。
　　第 3 天参加第三个会议。
　　
　　示例 2：
　　输入：events= [[1,2],[2,3],[3,4],[1,2]]
　　输出：4
　　
　　示例 3：
　　输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
　　输出：4
　　
　　示例 4：
　　输入：events = [[1,100000]]
　　输出：1
　　
　　示例 5：
　　输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
　　输出：7

　　思路：注意题目中一个会议只需挑一天参加即算参加了。
　　使用贪心算法，开始时令day=1，第day天如果没有参加会议，分为以下两种情况：
　　(1) 第day天能够参加会议，则参加结束时间最早的会议，然后继续考虑第day+1天。
　　(2) 第day天不能参加会议，则等待n天后重试，也就是在剩下的会议中选择开始时间最早的作为新的day值来继续循环。

流程图如下：

　　具体实现时为了节省时间，先将会议排序，假设所有的会议events = [[27,29],[28,32],[3,3],[24,25],[7,7],[22,25],[14,15],[13,17],[1,2],[7,7],[10,12],[9,13],[21,25],[20,21],[20,22],[19,20],[27,28],[9,9],[21,24],[18,21],[6,10],[29,30],[22,24]]，我们先把它按照开始时间为主键，结束时间为次键排序，结果如下：

events = [
   [1, 2],
   [3, 3],
   [6, 10],
   [7, 7],
   [7, 7],
   [9, 9],
   [9, 13],
   [10, 12],
   [13, 17],
   [14, 15],
   [18, 21],
   [19, 20],
   [20, 21],
   [20, 22],
   [21, 24],
   [21, 25],
   [22, 24],
   [22, 25],
   [24, 25],
   [27, 28],
   [27, 29],
   [28, 32],
   [29, 30]]

events = [

[1, 2],

[3, 3],

[6, 10],

[7, 7],

[9, 9],

[9, 13],

[10, 12],

[13, 17],

[14, 15],

[18, 21],

[19, 20],

[20, 21],

[20, 22],

[21, 24],

[21, 25],

[22, 24],

[22, 25],

[24, 25],

[27, 28],

[27, 29],

[28, 32],

[29, 30]]

循环过程为：

第 1 天: 参加 [1, 2], day = day + 1
第 2 天: 没有能参加的会议，休息 n 天后重试(n=1)
第 3 天: 参加 [3, 3], day = day + 1 = 4
第 4 天: 没有能参加的会议，休息 n 天后重试(n=2)
第 6 天: 参加[6, 10], day = day + 1 = 7
第 7 天: 参加[7, 7], day = day + 1 = 8
第 8 天: [7, 7]已开始，但是过了结束时间，移除，day不变
第 8 天: 没有能参加的会议，休息 n 天后重试(n=1)
第 9 天: [9, 9] 和 [9,13]都已经开始了，参加结束时间最早的 [9, 9]，day = day + 1 = 10
第 10 天: 参加[10, 12], day = day + 1 = 11
第 11 天: 没有能参加的会议，休息 n 天后重试(n=2)
第 13 天: 参加[13, 17], day = day + 1 = 14
第 14 天: 参加[14, 15], day = day + 1 = 15
第 15 天: 没有能参加的会议，休息 n 天后重试(n=3)
.........

第 1 天: 参加 [1, 2], day = day + 1

第 2 天: 没有能参加的会议，休息 n 天后重试(n=1)

第 3 天: 参加 [3, 3], day = day + 1 = 4

第 4 天: 没有能参加的会议，休息 n 天后重试(n=2)

第 6 天: 参加[6, 10], day = day + 1 = 7

第 7 天: 参加[7, 7], day = day + 1 = 8

第 8 天: [7, 7]已开始，但是过了结束时间，移除，day不变

第 8 天: 没有能参加的会议，休息 n 天后重试(n=1)

第 9 天: [9, 9] 和 [9,13]都已经开始了，参加结束时间最早的 [9, 9]，day = day + 1 = 10

第 10 天: 参加[10, 12], day = day + 1 = 11

第 11 天: 没有能参加的会议，休息 n 天后重试(n=2)

第 13 天: 参加[13, 17], day = day + 1 = 14

第 14 天: 参加[14, 15], day = day + 1 = 15

第 15 天: 没有能参加的会议，休息 n 天后重试(n=3)

.........

代码：

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        # 按主次键排序
        events = sorted(events, key=lambda kv: (kv[0], kv[1]))
        join = set()
        day = 1
        while len(events) != 0:
            min_i = (9999999, 9999999)
            # 取出第day天已经开始的第一个会议
            for i in events:
                if i[0] <= day and i[1] < min_i[1]:
                    min_i = i
                if i[0] > day:
                    break

            # 没有已经开始的会议 则取排序后的第一个会议
            if min_i == (9999999, 9999999):
                min_i = events[0]

            # 参加该会议
            if min_i[0] <= day and min_i[1] >= day:
                join.add(day)
                day += 1
                events.remove(min_i)

            # 已经结束了，移除，day不变
            elif min_i[1] < day:
                events.remove(min_i)

            # 第day天没有能参加的会议，参加之后排序后的第一个会议
            elif min_i[0] > day:
                join.add(min_i[0])
                day = min_i[0] + 1
                events.remove(min_i)

        return len(join)

class Solution:

def maxEvents(self, events: List[List[int]]) -> int:

# 按主次键排序

events = sorted(events, key=lambda kv: (kv[0], kv[1]))

join = set()

day = 1

while len(events) != 0:

min_i = (9999999, 9999999)

# 取出第day天已经开始的第一个会议

for i in events:

if i[0] <= day and i[1] < min_i[1]:

min_i = i

if i[0] > day:

break

# 没有已经开始的会议则取排序后的第一个会议

if min_i == (9999999, 9999999):

min_i = events[0]

# 参加该会议

if min_i[0] <= day and min_i[1] >= day:

join.add(day)

day += 1

events.remove(min_i)

# 已经结束了，移除，day不变

elif min_i[1] < day:

events.remove(min_i)

# 第day天没有能参加的会议，参加之后排序后的第一个会议

elif min_i[0] > day:

join.add(min_i[0])

day = min_i[0] + 1

events.remove(min_i)

return len(join)

第四题：多次求和构造目标数组　

　　给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：
　　
　　令 x 为你数组里所有元素的和
　　选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
　　你可以重复该过程任意次
　　如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。
　　
　　示例 1：
　　输入：target = [9,3,5]
　　输出：true
　　解释：从 [1, 1, 1] 开始
　　[1, 1, 1], 和为 3 ，选择下标 1
　　[1, 3, 1], 和为 5，选择下标 2
　　[1, 3, 5], 和为 9，选择下标 0
　　[9, 3, 5] 完成
　　
　　示例 2：
　　输入：target = [1,1,1,2]
　　输出：false
　　解释：不可能从 [1,1,1,1] 出发构造目标数组。　　
　　示例 3：
　　输入：target = [8,5]
　　输出：true

　　思路：每次都用target中最大的元素减去其他元素的和。如果最后的结果全是1，则返回True，如果中间出现了小于1的结果，则返回False。

　　示例1, target = [9,3,5]

9最大，target[0] = target[0] - 8 = 1, target = [1, 3, 5]
5最大，target[2] = target[2] - 4 = 1, target = [1, 3, 1]
3最大，target[1] = target[1] - 2 = 1, target = [1, 1, 1]
返回True

9最大，target[0] = target[0] - 8 = 1, target = [1, 3, 5]

5最大，target[2] = target[2] - 4 = 1, target = [1, 3, 1]

3最大，target[1] = target[1] - 2 = 1, target = [1, 1, 1]

返回True

　　示例2, target = [1,1,1,2]：

2最大，target[3] = target[3] - 3 = -1 < 1, 返回False

1 2	2最大，target[3] = target[3] - 3 = -1 < 1, 返回False

　　示例3, target = [8,5]：

8最大，target[0] = target[0] - 5 = 3, target = [3, 5]
5最大，target[1] = target[1] - 3 = 2, target = [3, 2]
3最大，target[0] = target[0] - 2 = 1, target = [1, 2]
2最大，target[1] = target[1] - 1 = 1, target = [1, 2]
返回True

8最大，target[0] = target[0] - 5 = 3, target = [3, 5]

5最大，target[1] = target[1] - 3 = 2, target = [3, 2]

3最大，target[0] = target[0] - 2 = 1, target = [1, 2]

2最大，target[1] = target[1] - 1 = 1, target = [1, 2]

返回True

代码：

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        while True:
            m = max(target)
            n = sum(target) - m
            if m - n < 1:
                return False
            for i in range(len(target)):
                if target[i] == m:
                    target[i] -= n

            ans = True
            for i in target:
                if i < 1:
                    return False
                if i !=1:
                    ans = False
                    break

            if ans:
                return True

class Solution:

def isPossible(self, target: List[int]) -> bool:

while True:

m = max(target)

n = sum(target) - m

if m - n < 1:

return False

for i in range(len(target)):

if target[i] == m:

target[i] -= n

ans = True

for i in target:

if i < 1:

return False

if i !=1:

ans = False

break

if ans:

return True