1090-受標簽影響的最大值

sunny5541 發布于2019-08-19 11:44 / 1995人閱讀

摘要：前言的受標簽影響的最大值我們有一個項的集合，其中第項的值為，標簽為。我們從這些項中選出一個子集，這樣一來對于任意的標簽，子集中標簽為的項的數目總滿足。返回子集的最大可能的和。示例輸入輸出解釋選出的子集是第一項，第二項和第三項。

前言

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步中的數據并進行處理，處理步驟如下：

遍歷key對應的label列表

如果該label使用次數小于use_limit，則將將最大值加上對應的key，同時num_wanted自減

每輪循環都要判斷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> valueLabelMap = new TreeMap<>(Comparator.reverseOrder());
        // 每個label的出現次數
        Map occurTimes = new HashMap<>();
        // 最大值
        int result = 0;
        for(int i=0;i list=new ArrayList<>();
                list.add(labels[i]);
                valueLabelMap.put(values[i],list);
            }
        }
        Iterator>> it=valueLabelMap.entrySet().iterator();
        while (it.hasNext()){ // 遍歷TreeMap
            Map.Entry> entry = it.next();
            // 對應的值
            Integer value = entry.getKey();
            List labelList = entry.getValue();
            labelList.sort(Comparator.comparing(Integer::intValue));
            for(int i=0;i

云服務器 GPU云服務器受影響行數據云服務器速度受什么影響受美國保護的網站不受保護的頁面

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/77774.html

網頁頂部導航欄加強（分為左右兩部分；添加一個不被污染樣式的搜索框）

摘要：目標中間一段空白把導航欄分為左右兩個部分在導航欄上加上一個搜索框，但不被的樣式污染。前置本文需要對CSS，Vue，ElementUI有基本的了解。本文以ElementUI提供的導航菜單組件為基礎。本文希望能在此組件基礎上實現以下內容：中間一段空白把導航欄分為左右兩個部分在導航欄上加上一個搜索框，但不被 el-menu-item 的樣式污染。先研究清楚ElementUI...

yedf 2019-08-30 15:44 評論0 收藏0
利用PYTHON全自動生成分析報告

摘要：本文通過一個簡單實例，介紹中的一個叫模塊，可以實現全自動獲取數據分析數據最終生成分析報告的全部操作。另外更有用的在于通過嵌入網絡爬蟲，以及對外部的接口，可以快速實現大量手工勞動才能完成的工作，提高工作效率日常工作當中，特別是金融行業當中，有不少人的工作是提取數據，分析數據，得到可視化圖表，并加入自已的研究分析結論，最終生成分析報告，并且有不少報告是定期生成，存在不少重復手工勞動。本文...

xorpay 2019-07-30 15:44 評論0 收藏0
viewport&像素

摘要：屏幕分辨率是指一塊屏幕中畫面水平方向的像素值畫面垂直方向的像素值。圖像分辨率是指每英寸圖像內的像素點數。圖像分辨率是有單位的，叫像素每英寸。設備像素可能不相同物理像素不會改變，單位是。及英寸，而英寸等于厘米舉個 viewport是什么移動端中，分為兩個視口： layout viewport 布局視口: 視口的分辨率接近于PC顯示器,也就是html的寬度接近于pc端的寬度。 visu...

hankkin 2019-08-30 15:56 評論0 收藏0
大型云提供商的云端閃存存儲

摘要：云端閃存部署細節塊存儲僅可用于連接到虛擬實例或虛擬機。在這些產品中，只有彈性塊存儲具有明確使用閃存存儲的功能。谷歌云平臺提供三種主要存儲選項云存儲對象永久磁盤塊和云文件存儲文件。隨著閃存存儲價格下降且設備容量提升，閃存存儲逐漸成為企業的首選存儲選項。公共云平臺上的存儲同樣是如此，這些平臺具有基于固態的存儲產品，可為需要存儲功能的應用程序提高性能和吞吐量。本文中，讓我們來看看哪些閃存作為云存儲...

Maxiye 2019-04-29 14:22 評論0 收藏0