2020 第38周 LeetCode 记录

发表于 |

1582. Special Positions in a Binary Matrix

直接遍历二维数组之后，如果某个位置是 1，再去统计每行的和和每列的和是否为 1 时间复杂度太高，可以先统计每行每列的和，然后再遍历二维数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n, ans = len(mat), len(mat[0]), 0
        row, col = [0] * m, [0] * n
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    row[i] += 1
                    col[j] += 1
        pool = [j for j in range(n) if col[j] == 1]
        for i in range(m):
            if row[i] != 1:
                continue
            for j in pool:
                if mat[i][j]:
                    ans += 1
                    break
        return ans

1025. Divisor Game

如果N是奇数，因为奇数的所有因数都是奇数，因此 N 进行一次 N-x 的操作结果一定是偶数，所以如果 a 拿到了一个奇数，那么轮到 b 的时候，b拿到的肯定是偶数，这个时候 b 只要进行 -1， 还给 a 一个奇数，那么这样子b就会一直拿到偶数，到最后b一定会拿到最小偶数2，a就输了。

所以如果游戏开始时Alice拿到N为奇数，那么她必输，也就是false。如果拿到N为偶数，她只用 -1，让bob 拿到奇数，最后bob必输，结果就是true。

1
2
3
class Solution:
    def divisorGame(self, N: int) -> bool:
        return not N%2

1583. Count Unhappy Friends

题目有些绕，python 可以直接用 index 方法来切片，golang 只能自己实现了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        dd = {}
        
        for i,x in pairs:
            dd[i] = preferences[i][:preferences[i].index(x)]
            dd[x] = preferences[x][:preferences[x].index(i)]
        
        ans = 0
        print(dd)
            
        for i in dd:
            for x in dd[i]:
                if i in dd[x]:
                    ans += 1
                    break
        
        return ans

1282. Group the People Given the Group Size They Belong To

对分组进行统计，组人数作为 key，在该人数的用户索引列表作为 value，然后遍历。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = collections.defaultdict(list)
        for i, _id in enumerate(groupSizes):
            groups[_id].append(i)
        
        ans = list()
        for gsize, users in groups.items():
            for it in range(0, len(users), gsize):
                ans.append(users[it : it + gsize])
        return ans

1305. All Elements in Two Binary Search Trees

如果只是单纯的用列表存储所有值，然后进行排序是最简单的实现方式，但是这道题考察的应该是归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        def dfs(node, v):
            if not node:
                return
            dfs(node.left, v)
            v.append(node.val)
            dfs(node.right, v)
        
        v1, v2 = list(), list()
        dfs(root1, v1)
        dfs(root2, v2)
        ans, i, j = list(), 0, 0
        while i < len(v1) or j < len(v2):
            if i < len(v1) and (j == len(v2) or v1[i] <= v2[j]):
                ans.append(v1[i])
                i += 1
            else:
                ans.append(v2[j])
                j += 1
        return ans