脚本宝典收集整理的这篇文章主要介绍了删除并获得点数,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给你一个整数数组 nums ,你可以对它进行一些操作。
每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/delete-and-earn 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.Arrays;
class Solution {
private int rob(int[] data) {
if (data == null || data.length == 0) {
return 0;
}
int get = data[0], notGet = 0;
for (int i = 1; i < data.length; ++i) {
int tmp = get;
get = Math.max(get, notGet + data[i]);
notGet = Math.max(notGet, tmp);
}
return Math.max(get, notGet);
}
/**
* O(n + maxVal)
* @param nums
* @return
*/
public int deleteAndEarn(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int max = Arrays.stream(nums).max().getAsInt();
int[] data = new int[max + 1];
for (int i = 0; i < nums.length; ++i) {
data[nums[i]] += nums[i];
}
return rob(data);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 时间复杂度 * O(nlog(n)) * 空间复杂度 * O(n)
*/
class Solution {
private static int rob(List<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int get = 0, notGet = 0, tmp, val;
for (int i = 0; i < nums.size(); ++i) {
tmp = get;
get = nums.get(i) + notGet;
notGet = Math.max(notGet, tmp);
}
return Math.max(notGet, get);
}
public static int deleteAndEarn(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int ret = 0;
Arrays.sort(nums);
List<Integer> segment = new ArrayList<>();
segment.add(nums[0]);
for (int i = 1; i < nums.length; ++i) {
if (nums[i] == nums[i - 1]) {
segment.set(segment.size() - 1, segment.get(segment.size() - 1) + nums[i]);
} else if (nums[i] > nums[i - 1] + 1) {
ret += rob(segment);
segment.clear();
segment.add(nums[i]);
} else {
segment.add(nums[i]);
}
}
ret += rob(segment);
return ret;
}
public static void main(String[] args) {
int[] nums = {3, 1};
System.out.println(deleteAndEarn(nums));
}
}
以上是脚本宝典为你收集整理的删除并获得点数全部内容,希望文章能够帮你解决删除并获得点数所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。