5、字典问题

1090. 受标签影响的最大值

我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

从 n 个元素中选择一个子集 s :

• 子集 s 的大小 小于或等于 numWanted 。
• s 中 最多 有相同标签的 useLimit 项。

一个子集的 分数 是该子集的值之和。

返回子集 s 的最大 分数 。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出：16
解释：选出的子集是第一项和第四项。

思路：

我们需要对组合后的集合进行排序，然后找到最多numWanted，每个标签最多useLimit的子集

class Solution:
    def largestValsFromLabels(
        self, values: List[int], labels: List[int], numWanted: int, useLimit: int
    ) -> int:
        from collections import defaultdict

        result = 0
        items = []
        for item in zip(labels, values):
            items.append(item)
        items.sort(key=lambda obj: obj[1], reverse=True)

        hash_data = defaultdict(int)
        for item in items:
            lable, val = item
            if hash_data[lable] < useLimit and numWanted > 0:
                result += val
                numWanted -= 1
                hash_data[lable] += 1
            else:
                continue
        return result

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

思路：

• 存储每个字符最后出现的位置
• 找到当前字符出现的最远位置
• 如果当前位置是最远位置，表示可以分割出一个区间

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_distance = dict()
        for i, char in enumerate(s):
            last_distance[char] = i

        result = []
        start = 0
        end = 0
        for i in range(len(s)):
            end = max(end, last_distance[s[i]])
            if end == i:
                result.append(end - start + 1)
                start = i + 1
        return result