leetcode-740-删除并获得点数

[题目描述]

  1. //给你一个整数数组 nums ，你可以对它进行一些操作。 
  2. //
  3. // 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] +
  4. // 1 的元素。 
  5. //
  6. // 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 
  7. //
  8. // 
  9. //
  10. // 示例 1： 
  11. //
  12. // 
  13. //输入：nums = [3,4,2]
  14. //输出：6
  15. //解释：
  16. //删除 4 获得 4 个点数，因此 3 也被删除。
  17. //之后，删除 2 获得 2 个点数。总共获得 6 个点数。
  18. // 
  19. //
  20. // 示例 2： 
  21. //
  22. // 
  23. //输入：nums = [2,2,3,3,3,4]
  24. //输出：9
  25. //解释：
  26. //删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
  27. //之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
  28. //总共获得 9 个点数。
  29. // 
  30. //
  31. // 
  32. //
  33. // 提示： 
  34. //
  35. // 
  36. // 1 <= nums.length <= 2 * 104 
  37. // 1 <= nums[i] <= 104 
  38. // 
  39. // Related Topics 动态规划 
  40. // 👍 294 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：动态规划

  • 根据题意可分析用贪心法或者动态规划，动态规划一定可解，所以选择动态规划
  • 相关题目链接 leetcode-198 打家劫舍
  • 因为包含相同元素，所以当取得x元素后，相当于取得了所有相同x元素，并删除了所有x-1 以及 x+1元素
  • 维护一个数组，存入所有元素的数量*元素值存入
  • dp[i]=max(dp[i−2]+nums[i],dp[i−1])
  • 因为是一维，所以可以不用定义数组，用两个元素代替dp方程求之
  • 题目保证正整数
  1. public int deleteAndEarn(int[] nums) {
  2.             //找出最大元素,确定维护数组边界大小
  3.             int max = 0;
  4.             for (int n : nums
  5.             ) {
  6.                 max = Math.max(max, n);
  7.             }
  8.             int[] sum = new int[max + 1];
  9.             for (int n : nums
  10.             ) {
  11.                 sum[n] += n;
  12.             }
  13.             //动态规划取相隔元素
  14.             int first = sum[0], second = Math.max(sum[0], sum[1]);
  15.             for (int i = 2; i < max + 1; i++) {
  16.                 int temp = second;
  17.                 second = Math.max(first + sum[i], second);
  18.                 first = temp;
  19.             }
  21.             return second;
  24.         }

时间复杂度O(n + nums.max) nums.max为数组元素最大值

思路二：排序+ 动态规划

  • 将数组排序，以相距不超过1为子数组，对每个子数组参照思路1进行dp，dp求值后进行聚合
  1. public int deleteAndEarn(int[] nums) {
  2.             int n = nums.length;
  3.             int ans = 0;
  4.             Arrays.sort(nums);
  5.             List<Integer> sum = new ArrayList<Integer>();
  6.             sum.add(nums[0]);
  7.             int size = 1;
  8.             for (int i = 1; i < n; ++i) {
  9.                 int val = nums[i];
  10.                 //想等元素，存入链表获得最后值
  11.                 if (val == nums[i - 1]) {
  12.                     sum.set(size - 1, sum.get(size - 1) + val);
  13.                 }
  14.                 //距离上一个元素差值为1，则加入链表进行聚合
  15.                 else if (val == nums[i - 1] + 1) {
  16.                     sum.add(val);
  17.                     ++size;
  18.                 }
  19.                 //取得所有相邻区间，如果不在连续区间内，新建一个子链表循环操作
  20.                 else {
  21.                     ans += rob(sum);
  22.                     sum.clear();
  23.                     sum.add(val);
  24.                     size = 1;
  25.                 }
  26.             }
  27.             ans += rob(sum);
  28.             return ans;
  29.         }
  31.         private int rob(List<Integer> nums) {
  32.             int size = nums.size();
  33.             if (size == 1) {
  34.                 return nums.get(0);
  35.             }
  36.             int first = nums.get(0), second = Math.max(nums.get(0), nums.get(1));
  37.             for (int i = 2; i < size; i++) {
  38.                 int temp = second;
  39.                 second = Math.max(first + nums.get(i), second);
  40.                 first = temp;
  41.             }
  42.             return second;
  43.         }
  44.     }

时间复杂度O(nlgn)