删除并获得点数

2021-05-05

740. 删除并获得点数

难度中等257收藏分享切换为英文接收动态反馈

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4

解题思路

通过预处理数组将该问题转换成打家劫舍问题

哈希表+动态规划

若选择了 $x$，则可以获取$ \textit{sum}[x]$ 的点数，且无法再选择 $x-1$ 和 $x+1$。这与打家劫舍中的描述是一样的（相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。）的意思是一样的。所不同的是：这个题目里面是对数字的相邻做了要求，可以使用哈希表来实现数字的相邻的判断，这样就可以将原先的问题转换到打家劫舍问题上来。

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        // 找数据的最大值，即哈希表的大小
        int max = 0;
        for(int i=0;i<n;i++){
            max = Math.max(nums[i],max);
        }
        // 将相同的数字合并到一块，因为选择一个数字的时候可以选择这个数字的所有值
        int [] hash = new int [max+1];
        for(int val:nums){
            hash[val] += val;
        }
		// 打家劫舍问题通解
        int [] dp = new int[max+1];
        dp[0] = hash[0];
        dp[1] = Math.max(hash[0],hash[1]);
        for(int i=2;i<=max;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+hash[i]);
        }
        return dp[max];
    }
}

动态规划优化空间复杂度

class Solution {
    public int deleteAndEarn(int[] nums) {
        int []cnt=new int[10001];
        int []dp=new int[10001];
        for (int i : nums) ++cnt[i];// 统计每个数字出现的次数
        dp[0] = 0;
        dp[1] = 1*cnt[1];
        for (int i = 2; i <= 10000; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * cnt[i]);   	 
        }
        return dp[10000];
    }
}

动态规划

class Solution {
    public int deleteAndEarn(int[] nums) {
        int []cnt=new int[10001];
        int [][]dp=new int[10001][2];

        for (int i : nums) ++cnt[i];// 统计每个数字出现的次数

        for (int i = 1; i <= 10000; ++i) {
            dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]); // 0 代表不取
            dp[i][1] = dp[i - 1][0] + i * cnt[i];       	 // 1 代表取
        }
        return Math.max(dp[10000][0], dp[10000][1]);
    }
}

排序+动态规划

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int ans = 0;
        Arrays.sort(nums);
        List<Integer> sum = new ArrayList<Integer>();
        sum.add(nums[0]);
        int size = 1;
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.set(size - 1, sum.get(size - 1) + val);
            } else if (val == nums[i - 1] + 1) {
                sum.add(val);
                ++size;
            } else {
                ans += rob(sum);
                sum.clear();
                sum.add(val);
                size = 1;
            }
        }
        ans += rob(sum);
        return ans;
    }

    public int rob(List<Integer> nums) {
        int size = nums.size();
        if (size == 1) {
            return nums.get(0);
        }
        int first = nums.get(0), second = Math.max(nums.get(0), nums.get(1));
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums.get(i), second);
            first = temp;
        }
        return second;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

回溯超时

class Solution {
    Map<Integer,Integer> map;
    List<Integer> keyList;
    Map<Integer,Boolean> visMap;
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        map = new HashMap<>();
        visMap = new HashMap<>();
        for(int i=0;i<n;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+nums[i]);
            visMap.put(nums[i],false);
        }
        keyList=new ArrayList<>(map.keySet());

        dfs(0,0);
        return max;
    }
    int max = 0;
    public void dfs(int index,int sum){
        if(index==keyList.size()){
            max = Math.max(sum,max);
            return;
        }
        for(int i=index;i<keyList.size();i++){
            int key = keyList.get(i);
            if(!visMap.get(key)){
                visMap.put(key,true);
                if(map.containsKey(key+1)){
                    visMap.put(key+1,true);
                }
                if(map.containsKey(key-1)){
                    visMap.put(key-1,true);
                }
                dfs(i+1,sum+map.get(key));
                visMap.put(key,false);
                if(map.containsKey(key+1)){
                    visMap.put(key+1,false);
                }
                if(map.containsKey(key-1)){
                    visMap.put(key-1,false);
                }
            }else {
                dfs(i + 1, sum);
            }
        }
    }
}

参考文献

https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/923701