LWC 61:740. Delete and Earn

LWC 61:740. Delete and Earn

传送门:740. Delete and Earn

Problem:

Given an array nums of integers, you can perform operations on the array. In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1. You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

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: 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.

Note:

The length of nums is at most 20000.

Each element nums[i] is an integer in the range [1, 10000].

思路: 最简单的思路,选择一个数后,比如[3, 4, 2]选择4,那么3失效,剩余数组为[2],当作子问题来求解即可,这是一种情况。选择3,那么4和2均失效,剩余数组为[],也可以当作子问题求解。选择2,则3失效,剩余数组为[4],在这几种情况中选择profit最多的情况即可。

但上述递归存在一个严重的问题,子问题无法被记录下来,因为选择是无序的。因此可以采用背包的思路,先对这些元素排序,这样数组变为[2, 3, 4],这样一来对于2选or不选,进一步影响3是否被包含,子问题能够轻而易举的被状态化,因为此时当前位置i,那么对应的i到n的位置可以表示子问题。而这些子问题与第一种求解思路不同的是,它们因位置而存在唯一性。

Java版本:(递归+记忆化)

    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> mem = new HashMap<>();
        for (int n : nums) {
            mem.put(n, mem.getOrDefault(n, 0) + 1);
        }

        int[] cnt = new int[mem.size()];
        Set<Integer> keys = mem.keySet();

        int[] key = keys.stream().mapToInt(i -> i).toArray();
        Arrays.sort(key);

        for (int i = 0; i < key.length; ++i) {
            cnt[i] = mem.get(key[i]);
        }
        dp = new int[20000 + 16];
        return robot(key, cnt, 0);
    }

    int[] dp;
    public int robot(int[] key, int[] cnt, int pos) {
        if (pos >= key.length) return 0;
        if (dp[pos] > 0) return dp[pos];

        int ans = 0;
        int choose = 0;

        // choose
        if (pos + 1 < key.length && key[pos + 1] - 1 == key[pos]) {
            choose = key[pos] * cnt[pos] + robot(key, cnt, pos + 2);
        }
        else {
            choose = key[pos] * cnt[pos] + robot(key, cnt, pos + 1);
        }
        ans = Math.max(ans, choose);
        // no choose
        ans = Math.max(ans, robot(key, cnt, pos + 1));
        return dp[pos] = ans;
    }

递推版本:

    public int deleteAndEarn(int[] nums) {
        if (nums.length == 0) return 0;

        Map<Integer, Integer> mem = new HashMap<>();
        for (int n : nums) {
            mem.put(n, mem.getOrDefault(n, 0) + 1);
        }

        int[] cnt = new int[mem.size()];
        Set<Integer> keys = mem.keySet();

        int[] key = keys.stream().mapToInt(i -> i).toArray();
        Arrays.sort(key);

        for (int i = 0; i < key.length; ++i) {
            cnt[i] = mem.get(key[i]);
        }

        int[] dp = new int[20000 + 16];
        int last = key.length;

        dp[last - 1] = key[last - 1] * cnt[last - 1];
        for (int i = last - 2; i >= 0; --i) {
            if (key[i] + 1 == key[i + 1]) {
                dp[i] = Math.max(dp[i], dp[i + 2] + key[i] * cnt[i]);
            }
            else {
                dp[i] = Math.max(dp[i], dp[i + 1] + key[i] * cnt[i]);
            }

            dp[i] = Math.max(dp[i], dp[i + 1]);
        }

        return dp[0];
    }

简化map版本,用数组位置排序+计数:

      public int deleteAndEarn(int[] nums) {
          int[] cnt = new int[10016];
          for (int num : nums) cnt[num]++;

          int[] dp = new int[10016];
          dp[0] = 0;
          dp[1] = cnt[1];

          for (int i = 2; i <= 10000; ++i) {
              dp[i] = Math.max(dp[i - 1], dp[i - 2] + cnt[i] * i);
          }

          return dp[10000];
      }

Python版本:

    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = [0] * 10016
        for num in nums:
            cnt[num] = cnt[num] + 1
        dp = [0] * 10016
        dp[0] = 0
        dp[1] = cnt[1]

        for i in range(2, 10001):
            dp[i] = max(dp[i - 1], dp[i - 2] + i * cnt[i])

        return dp[10000]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏恰同学骚年

数据结构基础温故-1.线性表(下)

在上一篇中,我们了解了单链表与双链表,本次将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循...

702
来自专栏尾尾部落

[剑指offer] 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排...

662
来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

822
来自专栏Java技术

Java提供的排序算法是怎么实现的?快排?

前几天整理的一套面试题,其中有一个问题就是Java的JDK中我们见到的Collections.sort()和Arrays.sort()这两个排序算法的实现方式是...

663
来自专栏数据结构与算法

HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)

五位数点问题,写个cdq分治套cdq分治套cdq分治套cdq分析就完了 可以用bitset搞

391
来自专栏King_3的技术专栏

leetcode-443-String Compression

1526
来自专栏python读书笔记

《python算法教程》Day4 - 拓扑排序(基于有向无环图)拓扑排序简介代码实例

这是《python算法教程》的第4篇读书笔记。这篇笔记的主要内容为拓扑排序。 拓扑排序简介 在将一件事情分解为若干个小事情时,会发现小事情之间有完成的先后次序之...

33911
来自专栏青玉伏案

算法与数据结构(四) 图的物理存储结构与深搜、广搜(Swift版)

开门见山,本篇博客就介绍图相关的东西。图其实就是树结构的升级版。上篇博客我们聊了树的一种,在后边的博客中我们还会介绍其他类型的树,比如红黑树,B树等等,以及这些...

16210
来自专栏Android知识点总结

03--图解数据结构之双链表实现容器

745
来自专栏JavaQ

HashMap在JDK1.8前后区别精简说

在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存...

3257

扫码关注云+社区