2021-11-5
题目
1.最小的k个数
2.数组中出现次数超过数组长度一半的数
3.最长差定子序列
4.礼物的最大价值
题解
1.最小的k个数
本题太过简单！！！
看代码就可以理解！！！
2.数组中出现次数超过数组长度一半的数
本题我是用哈希表来解的，但是本题应该不止一种方法，所以大家也可以自己试试自己的方法！
我们先用一个字典把不同的元素放到字典中，初始值都为0，然后我们在遍历nums数组，然后找到每个元素的有多少个，然后返回value里面的最大值得键就可以！！
3.最长差定子序列
本题时一个一维dp问题，我们先创建一个哈希表，如果num在这个哈希表里面，就把这个元素加一，然后返回最大得哈希值！！！
4.礼物的最大价值
本题也是一个dp问题，其实画一个矩阵是可以非常简单明了的，由于时间问题我就没有画了，大家可以自行脑部hhhhh，我们把矩阵的每个从左上角叠加的值计算出来，然后进行比较相加，然后返回右下角里面的那个值就可以。
代码
1.最小的k个数
class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: arr.sort() return arr[:k]
2.数组中出现次数超过数组长度一半的数
class Solution: def majorityElement(self, nums: List[int]) -> int: d = {} for i in set(nums): d[i] = 0 for i in nums: d[i] += 1 for i in d: if d[i] > len(nums)//2: return i
3.最长差定子序列
class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: d = defaultdict(int) for num in arr: d[num] = d[num - difference] + 1 return max(d.values())
4.礼物的最大价值
class Solution: def maxValue(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) for j in range(1, n): # 初始化第一行 grid[0][j] += grid[0][j - 1] for i in range(1, m): # 初始化第一列 grid[i][0] += grid[i - 1][0] for i in range(1, m): for j in range(1, n): grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]) return grid[-1][-1]
