Rust 力扣 - 740. 删除并获得点数

题目描述

题解思路

首先对于这题我们如果将所有点数装入一个切片f中，该切片f中的i号下标表示所有点数为i的点数之和

那么这题就转换成了打家劫舍这道题，也就是求选择了切片中某个下标的元素后，该下标相邻元素就不能选择，求最终能选择的元素之和的最大值

那么在切片的[0, i]范围内选择元素的最大值 = max(i号索引元素 + [0, i - 2]范围内选择元素的最大值, [0, i - 1]范围内选择元素的最大值)

题解代码

impl Solution {pub fn delete_and_earn(nums: Vec<i32>) -> i32 {if nums.len() == 1 {return nums[0];}let mut max_val = nums[0];for &num in &nums {max_val = max_val.max(num);}let mut f = vec![0; max_val as usize + 1];for &num in &nums {f[num as usize] += num;}let (mut a, mut b) = (f[0], f[1].max(f[0]));for i in 2..=max_val as usize {(a, b) = (b, b.max(a + f[i]));}b}
}

题目链接

https://leetcode.cn/problems/delete-and-earn/