算法题记录 9

624.数组列表中的最大距离（中等）

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

涉及知识点

数学

解决思路

秒答题。

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        big=-inf
        small=inf
        ans=-inf
        for each in arrays:
            ans=max(ans,each[-1]-small,big-each[0])
            big=max(big,each[-1])
            small=min(small,each[0])
        return ans

2207.字符串中最多数目的子序列（1550）

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。

你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。

请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。

子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

涉及知识点

贪心

解决思路

秒答题，要么pattern[0]放最左边，要么pattern[1]放最右边，求出组合数加上出现频率最多的即可。

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        x,y=pattern
        ans=cnt_x=cnt_y=0
        for c in text:
            if c==y:
                ans+=cnt_x
                cnt_y+=1
            if c==x:
                cnt_x+=1
        return ans+max(cnt_x,cnt_y)

3285.找到稳定山的下标（1166）

有 n 座山排成一列，每座山都有一个高度。给你一个整数数组 height ，其中 height[i] 表示第 i 座山的高度，再给你一个整数 threshold 。

对于下标不为 0 的一座山，如果它左侧相邻的山的高度 严格大于 threshold ，那么我们称它是 稳定 的。我们定义下标为 0 的山 不是 稳定的。

请你返回一个数组，包含所有 稳定 山的下标，你可以以 任意 顺序返回下标数组。

涉及知识点

数组

解决思路

秒答题。

class Solution:
    def stableMountains(self, height: List[int], threshold: int) -> List[int]:
        ans=[]
        for i,value in enumerate(height):
            if value>threshold and i<len(height)-1:
                ans.append(i+1)
        return ans

633.平方数之和（中等）

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

涉及知识点

数学

解决思路

秒答题，while循环。

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a=0
        while a*a*2<=c:
            b=isqrt(c-a*a)
            if a*a+b*b==c:
                return True
            a+=1
        return False

1705.吃苹果的最大数目（1930）

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

涉及知识点

最小堆

解决思路

思路很容易想到，实现过程判断条件较多，套用最小堆模型会简化不少，总体思路是快腐烂的先吃。当apples遍历完后，剩下最小堆不再存在“添加”情况，可以简化操作，跳步数判断，从而提高效率。

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        ans = 0
        h = []
        for i, (num, day) in enumerate(zip(apples, days)):
            while h and h[0][0] == i:  # 已腐烂
                heappop(h)
            if num:
                heappush(h, [i + day, num])
            if h:
                ans += 1
                h[0][1] -= 1  # 吃一个最早腐烂的苹果
                if h[0][1] == 0:
                    heappop(h)

        i = len(apples)
        while True:
            while h and h[0][0] <= i:  # 已腐烂
                heappop(h)
            if not h:
                return ans
            rotten_day, num = heappop(h)
            k = min(num, rotten_day - i)
            ans += k
            i += k

743.网络延迟时间（中等）

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

涉及知识点

Dijkstra算法

解决思路

考察基本的Dijkstra算法，属于必会项目。

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[inf for _ in range(n)] for _ in range(n)]  # 邻接矩阵
        for x, y, d in times:
            g[x - 1][y - 1] = d

        dis = [inf] * n
        ans = dis[k - 1] = 0
        done = [False] * n
        while True:
            x = -1
            for i, ok in enumerate(done):
                if not ok and (x < 0 or dis[i] < dis[x]):
                    x = i
            if x < 0:
                return ans  # 最后一次算出的最短路就是最大的
            if dis[x] == inf:  # 有节点无法到达
                return -1
            ans = dis[x]  # 求出的最短路会越来越大
            done[x] = True  # 最短路长度已确定（无法变得更小）
            for y, d in enumerate(g[x]):
                # 更新 x 的邻居的最短路
                dis[y] = min(dis[y], dis[x] + d)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。