1090受标签影响的最大值

jiezi

6 年前

Weekly Contest 141 的受标签影响的最大值：

我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。

我们从这些项中选出一个子集 S，这样一来：

|S| <= num_wanted

对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。

返回子集 S 的最大可能的和。

示例 1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。
示例 2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。
示例 3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。
示例 4：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。
提示：

1 <= values.length == labels.length <= 20000

0 <= values[i], labels[i] <= 20000

1 <= num_wanted, use_limit <= values.length

本题题目可能会有点难以理解，可用把题目中的项看做 带有值的标签 。而labels 就是标签列表，values就是标签列表对应的标签值列表。

简单点说，标签与标签值的关系为 多对多，一个标签可以有多个标签值，而一个相同的值可以多个标签都使用。

而题目的意思就是在所有项中选取 num_wanted 个元素，但是选取的元素如果存在标签一致的情况，只能存在 use_limit 个相同标签的项。找出满足上述条件的子集，且该子集的项的标签值之和最大，并返回该最大值。

下面我以示例 4 作为例子，讲解一下我的解题思路：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。

将 values 和labels转化为以 values 为key，每个 key 对应多个 label 的结构，同时以 key 从大到小进行排序。内容如下所示
```
9 : [0]
8 : [0,0]
7 : [1]
6 : [1]
```
依次遍历第 1 步中的数据并进行处理，处理步骤如下：
1. 遍历 key 对应的 label 列表
2. 如果该 label 使用次数小于 use_limit，则将将最大值加上对应的key，同时num_wanted 自减
3. 每轮循环都要判断 num_wanted 是否为0

    /**
     * 1090. 受标签影响的最大值
     * @param values 标签值列表
     * @param labels 标签名列表
     * @param num_wanted 期待的标签个数
     * @param use_limit 每个标签可重复的次数
     * @return
     */
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        // value 和 label 的映射，需要注意使用的是入参 values 作为 key 倒序（从大到小）存储
        Map<Integer, List<Integer>> valueLabelMap = new TreeMap<>(Comparator.reverseOrder());
        // 每个 label 的出现次数
        Map<Integer,Integer> occurTimes = new HashMap<>();
        // 最大值
        int result = 0;
        for(int i=0;i<labels.length;i++){ // 转成 value 和 label 的映射
            if(valueLabelMap.containsKey(values[i])){valueLabelMap.get(values[i]).add(labels[i]);
            }else{List<Integer> list=new ArrayList<>();
                list.add(labels[i]);
                valueLabelMap.put(values[i],list);
            }
        }
        Iterator<Map.Entry<Integer,List<Integer>>> it=valueLabelMap.entrySet().iterator();
        while (it.hasNext()){ // 遍历 TreeMap
            Map.Entry<Integer,List<Integer>> entry = it.next();
            // 对应的值
            Integer value = entry.getKey();
            List<Integer> labelList = entry.getValue();
            labelList.sort(Comparator.comparing(Integer::intValue));
            for(int i=0;i<labelList.size();i++){ // 遍历 label 列表
                Integer label=labelList.get(i);
                if(occurTimes.containsKey(label)){ // label 是否被使用过
                    if(occurTimes.get(label)<use_limit){ // 是否超出使用上限
                        result+=value;
                        occurTimes.put(label,occurTimes.get(label)+1);
                        --num_wanted; // 减少可用个数
                    }
                }else{occurTimes.put(label,1);
                    result+=value;
                    --num_wanted; // 减少可用个数
                }
                if(num_wanted==0){ // 可用个数为 0，中断循环
                    break;
                }
            }
            if(num_wanted==0){break;}
        }
        return result;
    }

1090受标签影响的最大值

前言

解题思路

实现代码