Leetcode第274场周赛write up

发表于

前言

老三样如约而至。。。。

检查是否所有 A 都在 B 之前

1
给你一个 仅 由字符 'a' 和 'b' 组成的字符串  s 。如果字符串中 每个 'a' 都出现在 每个 'b' 之前，返回 true ；否则，返回 false 。
1
2
3
4
5
输入：s = "aaabbb"
输出：true
解释：
'a' 位于下标 0、1 和 2 ；而 'b' 位于下标 3、4 和 5 。
因此，每个 'a' 都出现在每个 'b' 之前，所以返回 true 。
1
2
3
4
5
输入：s = "abab"
输出：false
解释：
存在一个 'a' 位于下标 2 ，而一个 'b' 位于下标 1 。
因此，不能满足每个 'a' 都出现在每个 'b' 之前，所以返回 false
1
2
3
4
输入：s = "bbb"
输出：true
解释：
不存在 'a' ，因此可以视作每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

There’s nothing to say，第一道题面前重拳出击！🐶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def checkString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if 'a' not in s or 'b' not in s:
            return True
        count = 0
        for i in s:
            if i == 'a':
                count += 1
        index_b = s.index('b')
        if count <= index_b:
            return True
        return False

银行中的激光束数量

1
2
3
4
5
6
银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。
对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：
两个设备位于两个 不同行 ：r1 和 r2 ，其中 r1 < r2 。
满足 r1 < i < r2 的 所有 行 i ，都 没有安全设备 。
激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。
返回银行中激光束的总数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
输入：bank = ["011001","000000","010100","001000"]
输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。
1
2
3
输入：bank = ["000","111","000"]
输出：0
解释：不存在两个位于不同行的设备

这道题的思路就是交叉相成，看成一个多行的数组，每一行的1的个数乘其他行1的个数。前提是两行之前能相乘的原则是中间行1的个数都为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def numberOfBeams(self, bank):
        """
        :type bank: List[str]
        :rtype: int
        """
        res = []
        #统计每一行1的个数
        for line in bank:
            res.append(list(line).count('1'))
        #设置保存光束的全局值
        ans = 0
        for i in range(len(res)):
            for j in range(i+1,len(res)):
                #如果当前行都是0，则走到下一行
                if res[j] == 0:
                    continue
                #如果当前行存在1，则直接计算光束值，后续的行就不需要计算，直接跳出循环
                else:
                    ans += res[i]*res[j]
                    break
        return ans

摧毁小行星

1
2
3
给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。
你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。
如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。
1
2
3
4
5
6
7
8
9
输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。
1
2
3
4
5
6
输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

这道题我们使用贪心的做法，每次撞击行星的时候总是从最小的那个撞起。因此质量肯定可以累加。这里我们不用从最小的开始撞，从不超过mass值的最大值开始向后计算。因此我们首先需要对asteroids进行排序，找到初始mass应该插入的位置。如果插入位置为0的话，则证明初始mass的值不足以撞击任何行星，直接返回false即可。如果插入位置不为0，则依次向后判断，更新mass的值。

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
class Solution(object):
    def asteroidsDestroyed(self, mass, asteroids):
        """
        :type mass: int
        :type asteroids: List[int]
        :rtype: bool
        """
        #对行星大小排序
        asteroids = sorted(asteroids)
        #找到mass在行星中的插入位置
        insert = bisect.bisect(asteroids,mass)
        #如果插入位置是0，说明mass无法和任何行星碰撞，直接返回false
        if insert == 0:
            return False
        #如果插入位置不是0，则mass的最大质量是插入位置之前所有行星质量之和加上mass的初始质量
        mass = sum(asteroids[:insert])+mass
        #从mass插入位置之后开始遍历，判断当前mass质量是否小于当前行星质量
        #如果小于直接返回false
        #如果大于则更新mass的质量
        for i in range(insert,len(asteroids)):
            if mass < asteroids[i]:
                return False
            else:
                mass += asteroids[i]
        return True

参加会议的最多员工数

1
2
3
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
1
2
3
4
5
6
7
输入：favorite = [2,2,1,2]
输出：3
解释：
上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。
注意，公司也可以邀请员工 1，2 和 3 参加会议。
所以最多参加会议的员工数目为 3 。
1
2
3
4
5
6
7
8
9
输入：favorite = [1,2,0]
输出：3
解释：
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。
座位安排同图 1 所示：
- 员工 0 坐在员工 2 和 1 之间。
- 员工 1 坐在员工 0 和 2 之间。
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。
1
2
3
4
5
6
7
输入：favorite = [3,0,1,4,1]
输出：4
解释：
上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。
员工 2 无法参加，因为他喜欢的员工 0 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。
参加会议的最多员工数目为 4 。

一脸懵逼，等一手题解