算法题记录 6

1299.将每个元素替换为右侧最大元素（1219）

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

涉及知识点

数组

解决思路

秒答题，倒序操作即可。

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        mx = -1
        for i in range(len(arr) - 1, -1, -1):
            x = arr[i]
            arr[i] = mx
            mx = max(mx, x)  # 维护后缀最大值
        return arrclass Solution:

2944.购买水果需要的最少金币数（1709）

给你一个 下标从 0 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i + 1 个水果需要花费的金币数目。

水果超市有如下促销活动：

如果你花费 prices[i] 购买了下标为 i + 1 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j - 1] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

涉及知识点

动态规划

解决思路

定义 dfs(i) 表示在购买第 i 个水果的前提下，获得第 i 个及其后面的水果所需要的最少金币数。

动态规划

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int) -> int:
            if i * 2 >= n:
                return prices[i - 1]  # i 从 1 开始
            return min(dfs(j) for j in range(i + 1, i * 2 + 2)) + prices[i - 1]
        return dfs(1)

递推

class Solution:
    def minimumCoins(self, f: List[int]) -> int:
        n = len(f)
        for i in range((n + 1) // 2 - 1, 0, -1):
            f[i - 1] += min(f[i: i * 2 + 1])
        return f[0]

3242.设计相邻元素求和服务（1334）

给你一个 n x n 的二维数组 grid，它包含范围 [0, n2 - 1] 内的不重复元素。

实现 neighborSum 类：

neighborSum(int [][]grid) 初始化对象。
int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。
int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

涉及知识点

表格，预处理

解决思路

秒答题，预处理记录value位置访问函数时再在grid中进行查找可以，预处理直接保存函数结果调用函数直接返回也可以。

虽然该题很简单，但是从此题可以总结出一个这类题目的共通核心要点：涉及到表格的上下左右，斜向等操作时，因为方向有限，我们可以创建一个DIRS数组来保存各种操作。通过for循环来访问DIRS，并应用到表格的访问中。

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (-1, 1), (-1, -1), (1, -1))

class NeighborSum:

    def __init__(self, grid: List[List[int]]):
        n=len(grid)
        s=[[0,0] for _ in range(n*n)]
        for i,row in enumerate(grid):
            for j,v in enumerate(row):
                for k,(dx,dy) in enumerate(DIRS):
                    x,y=i+dx,j+dy
                    if 0<=x<n and 0<=y<n:
                        s[v][k//4]+=grid[x][y]
        self.s=s

    def adjacentSum(self, value: int) -> int:
        return self.s[value][0]

    def diagonalSum(self, value: int) -> int:
        return self.s[value][1]

3159.查询数组中元素的出现位置（1263）

给你一个整数数组 nums ，一个整数数组 queries 和一个整数 x 。

对于每个查询 queries[i] ，你需要找到 nums 中第 queries[i] 个 x 的位置，并返回它的下标。如果数组中 x 的出现次数少于 queries[i] ，该查询的答案为 -1 。

请你返回一个整数数组 answer ，包含所有查询的答案。给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

涉及知识点

数组

解决思路

秒答题，弄个数组记录与x相等的元素的位置即可。

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        pos=[i for i,num in enumerate(nums) if num==x]
        return [-1 if q>len(pos) else pos[q-1] for q in queries]

1338.数组大小减半（1303）

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回 至少 能删除数组中的一半整数的整数集合的最小大小。

涉及知识点

数组

解决思路

秒答题，Counter函数按value记录次数，通过sorted（reverse=True）排序，得到从大到小排列的元素出现次数。并通过accumulate遍历该排序，找到前i个和大于等于len(ar)//2的位置，此时i+1就是答案。

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnt=sorted(Counter(arr).values(),reverse=True)
        m=len(arr)//2
        for i,s in enumerate(accumulate(cnt)):
            if s>=m:
                return i+1

声明

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