电商数据网站有哪些,中铁建设集团官网登录,免费咨询牙齿问题,wordpress 设置首页1. 题目链接#xff1a;740. 删除并获得点数
2. 题目描述#xff1a; 给你一个整数数组 nums #xff0c;你可以对它进行一些操作。 每次操作中#xff0c;选择任意一个 nums[i] #xff0c;删除它并获得 nums[i] 的点数。之后#xff0c;你必须删除 所有 等于 nums[i] …1. 题目链接740. 删除并获得点数
2. 题目描述 给你一个整数数组 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 * 1041 nums[i] 104 3. 解法动态规划
3.1 算法思路
定义一个常量N表示数组的最大值加1。这里假设输入数组nums中的元素都是非负整数并且小于等于N-1。创建一个长度为N的整数数组arr并初始化为0。这个数组用于存储每个元素出现的次数。遍历输入数组nums将每个元素的值累加到对应的arr数组位置上。这样可以统计每个元素出现的次数。创建一个长度为N的整数向量f用于存储动态规划的状态。这个向量f[i]表示在考虑前i个元素时可以获得的最大收益。创建一个引用g指向向量f以便在后续计算中使用。使用循环迭代计算状态转移方程。从i1开始依次计算f[i]和g[i]的值。 f[i] g[i - 1] arr[i]表示在考虑前i个元素时可以选择当前元素或者不选择当前元素。g[i] max(f[i - 1], g[i - 1])表示在考虑前i个元素时可以选择当前元素或者不选择当前元素。 返回最终结果即最大收益。可以通过比较f[N - 1]和g[N - 1]的值来得到最大收益。 3.2 C算法代码
class Solution {
public:int deleteAndEarn(vectorint nums) {const int N 10001; // 定义一个常量N表示数组的最大值加1int arr[N] {0}; // 创建一个长度为N的整数数组arr并初始化为0for (auto x : nums) arr[x] x; // 遍历输入数组nums将每个元素的值累加到对应的arr数组位置上vectorint f(N); // 创建一个长度为N的整数向量f用于存储动态规划的状态auto g f; // 创建一个引用g指向向量f以便在后续计算中使用for (int i 1; i N; i) {f[i] g[i - 1] arr[i]; // 更新状态转移方程计算当前位置的最大收益g[i] max(f[i - 1], g[i - 1]); // 更新状态转移方程计算当前位置的最大收益不选择当前元素}return max(f[N - 1], g[N - 1]); // 返回最终结果即最大收益}
};
