LeetCode冲刺：Day44

发布于 2022-12-21  1069 次阅读

1. 前K个高频单词

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

  1. 字典统计频率
  2. 列表记录键
  3. 将键列表排序
  4. 遍历键列表，将键对应的频率和在键列表中的下标插入堆
  5. 取出堆中最大的k个元素，并按顺序将下标对应字符串插入返回的数组

字典序在键列表排序时排列好了。

代码

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        dic = defaultdict(int)
        for word in words: dic[word] += 1
        words = list(dic.keys())
        words.sort(reverse=True)
        hp = []
        for i in range(len(words)):
            heappush(hp, [dic[words[i]], i])
        res = nlargest(k, hp)
        ans = [words[res[i][1]] for i in range(len(res))]
        return ans

2. 逃脱阻碍者

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

凭直觉写出来的。如果有敌人距离终点的最短路程小于等于我们，那么一定可以在终点前或者终点拦截到我们。那么只要一次遍历对比距离即可。

题解称这种做法为曼哈顿距离，并且给出了严格证明。

代码

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        limit = abs(target[0]) + abs(target[1])
        for enemy in ghosts:
            if abs(enemy[0] - target[0]) + abs(enemy[1] - target[1]) <= limit: return False
        return True

3. 有效的井字游戏

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

井字棋情况有限，可以枚举，但需要考虑一些细节，否则就会一直在修用例不通过。

第一个玩家始终是X，则X的数目要么等于O，等于O的数目加一。

玩家胜利时，可能有一个以上的同号连线，但不可能存在两个记号都有连线。

如果X胜利，则X数目必然等于O的数目加一。如果O胜利，则O的数目必然等于X的数目。

只要判断以上情况即可。

代码

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        num_O = num_X = 0
        win_O = win_X = 0
        for row in board:
            if row == "OOO": win_O += 1
            elif row == "XXX": win_X += 1
            for lattice in row:
                if lattice == "O": num_O += 1
                elif lattice == "X": num_X += 1
        if (num_X - num_O != 0) and (num_X - num_O != 1): return False
        if board[0][0] == "X" and board[1][0] == "X" and board[2][0] == "X": win_X += 1
        if board[0][1] == "X" and board[1][1] == "X" and board[2][1] == "X": win_X += 1
        if board[0][2] == "X" and board[1][2] == "X" and board[2][2] == "X": win_X += 1
        if board[0][0] == "O" and board[1][0] == "O" and board[2][0] == "O": win_O += 1
        if board[0][1] == "O" and board[1][1] == "O" and board[2][1] == "O": win_O += 1
        if board[0][2] == "O" and board[1][2] == "O" and board[2][2] == "O": win_O += 1
        if board[0][0] == "X" and board[1][1] == "X" and board[2][2] == "X": win_X += 1
        if board[0][2] == "X" and board[1][1] == "X" and board[2][0] == "X": win_X += 1
        if board[0][0] == "O" and board[1][1] == "O" and board[2][2] == "O": win_O += 1
        if board[0][2] == "O" and board[1][1] == "O" and board[2][0] == "O": win_O += 1
        if win_X > 0 and win_O > 0: return False
        if (win_X > 0 and num_X == num_O) or (win_O > 0 and num_X != num_O): return False
        return True

4. 找到最终的安全状态

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

优化了三四次终于过了。

如果一个结点的所有出边都指向安全结点，那么这个结点也是安全结点。

于是用DFS，如果当前结点没有出边，或者本身已经是安全结点，那么将当前结点加入安全结点集，并返回True。

否则遍历所有出边。

如果出边指向已经访问过的结点，则返回False，当前结点不可能是安全结点。

如果一条出边返回结果是True，那么这个出边指向的结点加入安全结点集。

如果所有出边遍历结果都是True，那么返回True，当前结点也是安全结点，加入集。

比起初版，主要优化在一旦返回一个True，那么对应结点就立即加入安全结点集，而不是遍历结束才加入当前结点。

代码

class Solution:
    def dfs(self, graph: List[List[int]], visited: List[int], cur: int, safePoint: Set[int]) -> bool:
        if len(graph[cur]) == 0:
            safePoint.add(cur)
            return True
        elif cur in safePoint:
            return True
        else:
            for next in graph[cur]:
                if visited[next] == 0:
                    visited[next] = 1
                    flag = self.dfs(graph, visited, next, safePoint)
                    visited[next] = 0
                    if not flag: return False
                    else: safePoint.add(next)
                else: return False
            return True

    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        safePoint = set()
        n = len(graph)
        visited = [0 for i in range(n)]
        for v in range(n):
            if v not in safePoint:
                visited[v] = 1
                if self.dfs(graph, visited, v, safePoint):
                    safePoint.add(v)
                visited[v] = 0
        ans = sorted(list(safePoint))
        return ans

5. 环形子数组的最大和

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

百思不得其解。浪费一个多小时。

感觉自己的思路没问题，但却就是有一个用例结果不对。

代码

# 题解思路
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        maxSum = minSum = nums[0]
        sumMax = sumMin = 0
        for num in nums:
            sumMax += num
            maxSum = maxSum if maxSum > sumMax else sumMax
            if sumMax <= 0:
                sumMax = 0

            sumMin += num
            minSum = minSum if minSum < sumMin else sumMin
            if sumMin > 0: sumMin = 0
        total = sum(nums)
        return max(maxSum, total - minSum)

# 我的思路
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        n = len(nums)
        nums = nums * 2
        sum = 0
        cnt = 0
        cur = []
        maxSum = nums[0]
        for num in nums:
            sum += num
            cnt += 1
            cur.append(num)
            maxSum = maxSum if maxSum > sum else sum
            if sum <= 0:
                sum = 0
                cnt = 0
                cur = []
            if cnt == n:
                sum -= cur[0]
                cnt -= 1
                cur.pop(0)
                while cur and cur[0] <= 0:
                    sum -= cur[0]
                    cnt -= 1
                    cur.pop(0)
                maxSum = maxSum if maxSum > sum else sum
        return maxSum