LeetCode740

LeetCode740

目录

• 题目描述
• 示例
• 思路分析
• 代码段
• 代码逐行讲解
• 复杂度分析
• 总结的知识点
• 整合
• 总结

---

题目描述

给定一个整数数组 nums，你可以从中删除一些元素。删除一个元素 nums[i] 后，你将获得 nums[i] 的分数，但同时必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。请你返回通过删除元素获得的最大分数。

---

示例

示例 1

输入:

nums = [3, 4, 2]

输出:

6

解释:

• 删除元素 4 获得 4 分，同时删除元素 3 和 5（不存在）。
• 删除元素 2 获得 2 分。
• 总得分为 6。

---

示例 2

输入:

nums = [2, 2, 3, 3, 3, 4]

输出:

9

解释:

• 删除元素 3 获得 3 分，同时删除元素 2 和 4。
• 删除元素 3 获得 3 分。
• 删除元素 3 获得 3 分。
• 总得分为 9。

---

思路分析

问题核心

我们需要通过删除元素获得最大分数，同时删除相邻的元素。

思路拆解

1. 统计分数：
   • 使用数组 dp 统计每个元素的分数总和。
2. 动态规划：
   • 使用动态规划计算在不选择相邻元素的情况下，可以获得的最大分数。

---

代码段

class Solution {public int deleteAndEarn(int[] nums) {Arrays.sort(nums);int[] dp = new int[nums[nums.length - 1] + 1];for (int i = 0; i < nums.length; i++) {dp[nums[i]] += nums[i];}return rob(dp);}private int rob(int[] nums) {if (nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = nums[0];for (int k = 2; k <= n; k++) {dp[k] = Math.max(dp[k - 1], nums[k - 1] + dp[k - 2]);}return dp[n];}
}

---

代码逐行讲解

1. 排序数组：

   Arrays.sort(nums);
   

   • 将数组排序，方便后续处理。

2. 初始化分数数组：

   int[] dp = new int[nums[nums.length - 1] + 1];
   

   • 初始化数组 dp，用于统计每个元素的分数总和。

3. 统计分数：

   for (int i = 0; i < nums.length; i++) {dp[nums[i]] += nums[i];
   }
   

   • 遍历数组，统计每个元素的分数总和。

4. 调用动态规划函数：

   return rob(dp);
   

   • 调用动态规划函数 rob，计算最大分数。

5. 动态规划函数：

   private int rob(int[] nums) {if (nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = nums[0];for (int k = 2; k <= n; k++) {dp[k] = Math.max(dp[k - 1], nums[k - 1] + dp[k - 2]);}return dp[n];
   }
   

   • 使用动态规划计算在不选择相邻元素的情况下，可以获得的最大分数。

---

复杂度分析

时间复杂度

• 排序数组的时间复杂度为 O(n log n)。
• 遍历数组统计分数的时间复杂度为 O(n)。
• 动态规划的时间复杂度为 O(m)，其中 m 是数组 dp 的长度。
• 因此，总时间复杂度为 O(n log n + m)。

空间复杂度

• 使用了数组 dp 和动态规划数组，空间复杂度为 O(m)。

---

总结的知识点

1. 排序：

   • 使用 Arrays.sort 对数组进行排序。

2. 动态规划：

   • 使用动态规划计算最大分数。

3. 数组遍历：

   • 遍历数组统计分数。

---

整合

class Solution {public int deleteAndEarn(int[] nums) {Arrays.sort(nums);int[] dp = new int[nums[nums.length - 1] + 1];for (int i = 0; i < nums.length; i++) {dp[nums[i]] += nums[i];}return rob(dp);}private int rob(int[] nums) {if (nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = nums[0];for (int k = 2; k <= n; k++) {dp[k] = Math.max(dp[k - 1], nums[k - 1] + dp[k - 2]);}return dp[n];}
}

---

总结

通过排序和动态规划，能够高效地计算通过删除元素获得的最大分数。