2020 第21周 LeetCode 记录

发表于 |

1446. Consecutive Characters

判断最长连续相同字符的长度，记录下当前字母，然后比较与 flag 是否相同，如果相同则 +1，不相同则重置为 1。

也可以通过 itertools.groupby 来实现（新学习的。。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxPower(self, s: str) -> int:
        if len(s) == 1:
            return 1
        tmp = s[0]
        cnt = 1
        max_cnt = 0
        for i in s[1:]:
            if i == tmp:
                cnt += 1
            else:
                tmp = i
                cnt = 1
            max_cnt = max(max_cnt, cnt)
        return max_cnt

1447. Simplified Fractions

遍历分子与分母，求最大公约数，如果最大公约数为1，则将结果保存下来。分母从 2 开始计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func simplifiedFractions(n int) []string {
    ret := []string{}
    for i := 2; i <= n; i++ {
        for j := 1; j < i; j++ {
            if gcd(i, j) == 1 {
                ret = append(ret, fmt.Sprintf("%d/%d", j, i))
            }
        }
    }
    return ret
}

func gcd(x, y int) int {
    for x%y != 0 {
        x, y = y, x%y
    }
    return y
}

1448. Count Good Nodes in Binary Tree

遍历所有节点，记录 root 节点到当前节点经过的最大值，当前节点数值与最大值进行比较，如果符合条件，则结果 +1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        self.res = 0
        def dfs(node, curmax):
            if not node:
                return 
            if node.val >= curmax:
                self.res += 1
            curmax = max(curmax, node.val)
            if node.left:
                dfs(node.left, curmax)
            if node.right:
                dfs(node.right, curmax)
            
        dfs(root, -float('inf'))
        return self.res

1450. Number of Students Doing Homework at a Given Time

遍历开始时间和结束时间，判断查询时间是否在两者之间。

1
2
3
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        return sum(a<=queryTime<=b for a,b in zip(startTime,endTime))

896. Monotonic Array

遍历数组，记录前一个数字与当前数字的差值，判断是否单调递增或递减。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isMonotonic(self, A: List[int]) -> bool:
        cnt_inc = 0; cnt_dec = 0
        for i, v in enumerate(A):
            if i == 0: prev = v; continue
            if   v > prev: cnt_inc += 1
            elif v < prev: cnt_dec += 1
            if cnt_inc and cnt_dec: return False
            prev = v
        return True