2020 第20周 LeetCode 记录

发表于 |

1441. Build an Array With Stack Operations

遍历数组，比较当前值与目标值是否相同，如果相同，则在结果追加 Push ，如果不同，则追加 Push, Pop 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        res = []
        keep = 0
        for num in range(1, n+1):
            res.append("Push")
            keep += 1
            if num not in target:
                res.append("Pop")
                keep -= 1
            if keep == len(target):
                break
        return res

1442. Count Triplets That Can Form Two Arrays of Equal XOR

求子数组中是否存在左侧部分异或值与右侧部分异或值相等的情况，a==b -> a ^ b = 0，也就是是否存在子数组所有元素异或值为0 的情况，如果存在，那么子数组所有的元素都可以符合条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        if len(arr) < 2:
            return 0

        count = 0

        for i in range(len(arr)-1):
            temp = arr[i]
            for j in range(i+1, len(arr)):
                temp = temp^arr[j]
                if temp == 0:
                    count += j-i

        return count

1317. Convert Integer to the Sum of Two No-Zero Integers

从 1 开始遍历判断两个拆分数字是否包含 0 ，判断对 10 取余是否为0 。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        for i in range(1, n):
            if self.check(i) and self.check(n - i):
                return [i, n - i]

    def check(self, n: int) -> bool:
        while n > 0:
            if n % 10 == 0:
                return False
            n //= 10
        return True

1443. Minimum Time to Collect All Apples in a Tree

通过字典来保证每条路径只走一次，判断子节点是否有苹果，如果没有，则将子节点从字典中删除，最终字典中保存的是必须要经过的节点，要走 2 次，所以需要 * 2 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minTime(self, n: int, edges: List[List[int]],
                hasApple: List[bool]) -> int:
        maps = collections.defaultdict(list)
        for e in edges:
            maps[e[0]].append(e[1])

        def dfs(i):
            selfOrChildHasApple = hasApple[i]
            for nex in maps[i]:
                selfOrChildHasApple |= dfs(nex)
            if not selfOrChildHasApple:
                del maps[i]
            return selfOrChildHasApple

        dfs(0)
        return max(0, 2 * (len(maps) - 1))

807. Max Increase to Keep City Skyline

分别找出每行、每列的最大值，然后遍历判断当前值距离两个最大值中的最小值需要增加多少，累加计算。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        max_cols = [max(col) for col in zip(*grid)]
        max_rows = [max(row) for row in grid]
        inc = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                inc += (min(max_cols[j], max_rows[i]) - grid[i][j])
        return inc