删除与赚取

2019-09-24 12:28 来源:未知
  • 难题汇报

今晚开什么特马查询, 

Given an arraynums990991藏宝阁开奖记录,of integers, you can perform operations on the array.

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick anynums[i]and delete it to earnnums[i]points. After, you must deleteeveryelement equal tonums[i] - 1ornums[i] + 1.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete everyelement equal to nums[i] - 1 or nums[i] + 1.

990888藏宝阁,You start with 0 points. Return the maximum number of points you can earn by applying such operations.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Example 1:

Input: nums = [3, 4, 2]Output: 6Explanation: Delete 4 to earn 4 points, consequently 3 is also deleted.Then, delete 2 to earn 2 points. 6 total points are earned.
Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

 

Input: nums = [2, 2, 3, 3, 3, 4]Output: 9Explanation: Delete 3 to earn 3 points, deleting both 2's and the 4.Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.9 total points are earned.

Example 2:

Note:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
  1. The length ofnumsis at most20000.
  2. Each elementnums[i]is an integer in the range[1, 10000].

 

  • 解题思路

Note:

看难点,能够窥见到是动态规划项指标主题素材,但不知情怎么写迭代式子,正是相不知底情况。所以,一同先心虚的遵照本身的唯利是图算法落成了下,结果就是代码极多,但结果无法对~

  • The length of nums is at most 20000.
  • Each element nums[i] is an integer in the range [1, 10000].

不得已而为之,起先翻看资料,找到了一篇比较可靠的博客。借鉴他的思绪,本人努力写了下动态规划的兑现。思路的关键在于:

 

  1. 收取八个数,其获益为 数的频数 × 数的值。根据准绳,收取八个,必然抽取该值的全体数。
  2. 多少个情形,取出当前数的最大收入,不取当前数的最大收入(maxNoFetch)。
  3. 始于状态:
    •  maxFetch = 0, maxNoFetch = 0;
  4. 现阶段境况与上一景况的关联
    • 不取当前数,则为上一状态的最大值(max(prev马克斯Fetch, prev马克斯NoFetch))。
    • 抽出当前数,若数和上一景观的数关联,则为prev马克斯NoFetch + 收取数的受益。不然,为max(prev马克斯Fetch, prev马克斯NoFetch) +抽出数的低收入。

博主浪了方方面面二个圣诞假期,今后也该收收心了,2018了,今年对此博主是很要紧的一年,有太多的业务要去做,各样小目的需求实现,还会有不小希望去追赶,又要起来努力啦~在博主停更的那三日半的日子内,收到了网上亲密的朋友们的私信和留言催更,请咱们放心,二零一八年博主会继续百折不挠下去,继续追逐进程,就算一向都尚未完全追上-.-|||,照LeetCode那出题速度,今年题号有相当的大几率突破1000大关啊,认为碉堡了有木有,一齐为了幸福而努力吧~

  • 示范代码

好了,来做题吗。那道题给了作者们二个数组,每趟让我们删除一个数字,删除的数字本人变为了积分储存,并且要同不正常间移除此前数的加1和减1的数,但那时移除的数字不一齐积分,让大家求最多能获得多少积分。博主最开头尝试的秘诀是积分大小来排列,先删除大的数字,但是不对。于是乎,博主发掘一样的数字能够同一时候删除,于是正是两手空空了各样数字和其出现次数之间的投射,然后嵌入优先队列里,重写排序情势comparator为数字乘以其冒出次数,先移除能生出最大积分的数字,但是依旧不对。其实那道题跟从前那道House Robber的原形是一致的,那道题小偷不可能偷相邻的屋宇,这道题相邻的数字不能够增加积分,是否二个道理?那么对于每二个数字,我们都有多个挑选,拿大概不拿。即使大家拿了脚下的数字,我们就不可能拿在此之前的数字(借使我们从小往大遍历就不需求思考背后的数字),那么当前的积分正是不拿后边的数字的积分加上圈套前数字之和。倘若大家不拿当前的数字,那么对于最近的数字大家不仅能拿也足以不拿,于是当前的积分就是拿前边的数字的积分和不拿前边数字的积分中的非常的大值。这里我们用take和skip分别表示拿与不拿上二个数字,takei和skipi分别代表拿与不拿当前数字,每便换代完当前的takei和skipi时,也要革新take和skip,为下二个数字做计划,最终只要回到take和skip中的十分大值就能够,参见代码如下:

 

class Solution {public:        int deleteAndEarn(vector<int>& nums) {        map<int, int> freqs;        int size = nums.size();        for(int i = 0; i < size; i++)        {            int curr = nums[i];            // remember frequences for curr            if(freqs.find == freqs.end            {                freqs[curr] = 1;            }            else            {                freqs[curr] += 1;            }                    }                int maxFetch = 0, maxNoFetch = 0;        int prevMaxFetch = 0, prevMaxNoFetch = 0;        map<int, int>::iterator prevChoice;        map<int, int>::iterator currChoice;        // calculate maximum according to previous status        for(currChoice = freqs.begin(); currChoice != freqs.end(); ++currChoice)         {            // initiate            if(currChoice == freqs.begin             {                // get this number                maxFetch = currChoice->first * currChoice->second;                // do not get this number                maxNoFetch = 0;            }            // transferring            else             {                prevMaxFetch = maxFetch;                prevMaxNoFetch = maxNoFetch;                // do not get the number                maxNoFetch = max(prevMaxFetch, prevMaxNoFetch);                // get this number                if(currChoice->first == prevChoice -> first + 1 || currChoice->first == prevChoice -> first - 1) {                    // related -> must not fetch previous node                    maxFetch = prevMaxNoFetch + currChoice->first * currChoice->second;                }                else                 {   // non related                    maxFetch = maxNoFetch + currChoice->first * currChoice->second;                }            }                        prevChoice = currChoice;        }                return max(maxFetch, maxNoFetch);    }};

解法一:

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> sums(10001, 0);
        int take = 0, skip = 0;
        for (int num : nums) sums[num] += num;
        for (int i = 0; i < 10001; ++i) {
            int takei = skip + sums[i];
            int skipi = max(skip, take);
            take = takei; skip = skipi;
        }
        return max(skip, take); 
    }
};

 

上边这种解法间接使用sums数组来更新,而从未应用额外的变量。下面解法中绝非讲明那几个sums数组,这里的sums实际上约等于创立了数字和其总积分的照耀,这里的总积分的揣度情势是由数字乘以其现身次数得来的。由于标题中说了各种数字不会超越一千0,所以sums的长短能够起初化为一千1,然后遍历原数组,将超越的数字都加上到该数字在数组中的地方上。然后从sums数组的第多少个数字起头遍历,更新方法跟上边解法的思路很左近,当前的sums[i]值就等于前三个值sums[i-1]和前五个值sums[i-2]丰裕当前的sums[i]值中的相当的大值,其实想想便是在不拿当前数的积分,跟不拿前三个数的积分加上圈套前的积分之和,取两个中的十分的大值更新当前值sums[i],参见代码如下:

 

解法二:

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> sums(10001, 0);
        for (int num : nums) sums[num] += num;
        for (int i = 2; i < 10001; ++i) {
            sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]);
        }
        return sums[10000];
    }
};

 

附近难题:

House Robber

 

参谋资料:

 

LeetCode All in One 题目批注汇总(持续更新中...)

TAG标签:
版权声明:本文由990888藏宝阁发布于编程算法,转载请注明出处:删除与赚取