算法题记录 39

1863.找出所有子集的异或总和再求和（1372）

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

涉及知识点

dfs

解决思路

首先要产生子集，子集往往用递归选与不选来产生，然后我们用一个变量来存储异或结果即可。

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
       result=0
       def dfs(i:int,xor:int):
           nonlocal result
           if i==len(nums):
               result+=xor
               return
           dfs(i+1,xor^nums[i])
           dfs(i+1,xor)
       dfs(0,0)
       return result

122.买卖股票的最佳时机（中等）

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

涉及知识点

dfs

解决思路

首先要产生子集，子集往往用递归选与不选来产生，然后我们用一个变量来存储异或结果即可。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i:int,hold:int)->int:
            if i==n:
                return 0
            if hold:
                return max(dfs(i+1,0)+prices[i],dfs(i+1,1))
            else:
                return max(dfs(i+1,1)-prices[i],dfs(i+1,0))
        return dfs(0,0)

274.H指数（中等）

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

涉及知识点

数组

解决思路

先对数组从大到小排序，然后遍历数组，判断当前的引用次数是否小于等于当前的索引，如果是则返回当前的索引，如果循环结束就直接返回数组长度。

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n =len(citations)
        citations.sort(reverse=True)
        for i in range(n):
            if citations[i] <= i:
                return i
        return n

135.分发糖果（困难）

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

涉及知识点

数组

解决思路

先从左到右遍历一遍，形成满足左规则的糖果分配，然后从右到左遍历一遍，同样形成满足右规则的糖果分配，两个数组取最大值即是同时满足左右规则的糖果分配。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        left = [1 for _ in range(len(ratings))]
        right = left[:]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1
        count = left[-1]
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]: right[i] = right[i + 1] + 1
            count += max(left[i], right[i])
        return count

声明

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