前缀和题型总结 II ：leetcode 1402、1310、1371、1171

前缀和问题需要考虑：这个题怎么做前缀和，做出前缀和怎么和所求结合起来进而求解

leetcode 1402：做菜的顺序

题目描述：
一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。
请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

示例 1：
输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-11 + 02 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。

示例 2：
输入：satisfaction = [4,3,2]
输出：20
解释：按照原来顺序相反的时间做菜 (21 + 32 + 4*3 = 20)

示例 3：
输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

提示：
n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

思路： 前缀和
本题实际上就求一个数组经删减和排序后最大的前缀和的值。
按照题目的描述，所要做的第一件事一定是给数组进行排序。
但是需要要注意的是，这里为了配合前缀和的计算进行的是从大到小排序。
从第一道菜开始，如果加上这道菜之后喜爱程度增加量是大于0的，那么就把这个菜也加上，所以需要逆序排列，增加一个菜相当于他后面的菜的喜爱值都加了一倍因为多乘了一个1，这样用一个变量一直判断当前菜应不应该加入即可以求出最后的最大值。

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        ans, sum = 0, 0
        for i in range(len(satisfaction)):
            sum += satisfaction[i]
            if sum > 0:
                ans += sum
        return ans
1
2
3
4
5
6
7
8
9

leetcode 1310：子数组异或查询

题目描述：
有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [L_i, R_i]。
对于每个查询 i，请你计算从 L_i 到 R_i 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 1：
输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

示例 2：
输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

提示：
1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

思路： 前缀和
从题目中描述就可以知道是可以直接进行xor操作得到最后的结果，但是注意到因为要求的是对一个数组的情况，所以不能每一对都进行遍历一遍，这样时间复杂度较高；所以想到这样[left，right] 的方式可以利用前缀和的方式进行解决。
找到这样区间的异或运算的规律是：xor[left，right] = xors[left] ^ xors[right+1]
具体推导：

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        xors = [0]
        for i in arr:
            xors.append(xors[-1] ^ i)
        res = []
        for left, right in queries:
            res.append(xors[left] ^ xors[right+1])
        return res
1
2
3
4
5
6
7
8
9

leetcode 1371：每个元音包含偶数次的最长子字符串

题目描述：
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出现了偶数次。

示例 1：
输入：s = “eleetminicoworoep”
输出：13
解释：最长子字符串是 “leetminicowor” ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。

示例 2：
输入：s = “leetcodeisgreat”
输出：5
解释：最长子字符串是 “leetc” ，其中包含 2 个 e 。

示例 3：
输入：s = “bcbcbc”
输出：6
解释：这个示例中，字符串 “bcbcbc” 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。

提示：
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

思路： 前缀和
主要参考的题解链接

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        state = [100] * 32
        state[0] = -1
        pre = 0
        res = 0
        for i in range(len(s)):
            if s[i] == 'a': pre ^= 1
            elif s[i] == 'e': pre ^= 2
            elif s[i] == 'i': pre ^= 4
            elif s[i] == 'o': pre ^= 8
            elif s[i] == 'u': pre ^= 16
            if state[pre] == 100:
                state[pre] = i
            res = max(res, i-state[pre])

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这里的前缀相当于记录当时的状态和之前做过的题统计之间的和有一点不一样，但是前缀的值还是要根据上一个位置的前缀值计算出来的。
重点在于记录了状态，找两次状态一致的地方 他们中的字符串就是满足要求的连续偶数字符串。因为是奇、偶所以本题想到了用二进制的方式进行表示。

leetcode 1171：从链表中删去总和值为零的连续节点

题目描述：
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

示例 2：
输入：head = [1,2,3,-3,4]
输出：[1,2,4]

示例 3：
输入：head = [1,2,3,-3,-2]
输出：[1]

提示：
给你的链表中可能有 1 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

思路： 前缀和
看到删除连续的结点，所以想到了前缀和。删除的连续节点具有这样的特征，前一个结点的前缀和和当前结点的前缀和是相同的，那么这个区间的结点就是和为0的，可以删除的。所以利用一个map记录每个结点的前缀和，然后每次计算的时候，如果前面出现过这个和，直接把这部分中间的结点删除即可。注意这里的map需要维护，要是中间的结点删除了，他们在map中对应的前缀和也要删除。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        d = dict()
        pre = ListNode(-1, head)  # 设置一个哨兵结点
        sum, p = 0, head
        d[0] = pre
        while p is not None:
            sum += p.val
            if sum in d:
                node = d[sum]
                k = node.next
                node.next = p.next
                d_sum = sum
                while k != p:
                    d_sum = d_sum + k.val
                    d.pop(d_sum)
                    k = k.next
            else:
                d[sum] = p
            p = p.next
        return pre.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

进一步可以不维护map的方式：上面的方式是边遍历边判断，这次先遍历一遍，map保存为这个前缀和的最后一个结点；然后再从头遍历一遍，求一个前缀和之后看在map中有没有，有的话直接进行删除操作，遍历一遍就可以完成操作。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        d = dict()
        sum, p = 0, head
        pre = ListNode(0, head)
        d[0] = pre
        while p is not None:
            sum += p.val
            d[sum] = p
            p = p.next
        q = pre
        cur_sum = 0
        while q is not None:
            cur_sum += q.val
            if cur_sum in d and d[cur_sum] != q:
                q.next = d[cur_sum].next
            q = q.next
        return pre.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路参考的题解链接