2025-01-18：施咒的最大总伤害。用 go 语言，一个魔法师掌握了多种不同的咒语，每个咒语对应一个伤害值，这些伤害值存储在数组 power 中，其中可能会有多个咒语具有相同的伤害值。
使用某个特定伤害值为 power[i] 的咒语后，魔法师不能再使用伤害值为 power[i] - 2、power[i] - 1、power[i] + 1 或 power[i] + 2 的任何咒语。此外，每个咒语只能被施放一次。
请你计算并返回魔法师能够实现的最大伤害值总和。
1 <= power.length <= 100000。
1 <= power[i] <= 1000000000。
输入：power = [7,1,6,6]。
输出：13。
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。
答案 2025-01-18：
chatgpt
题目来自 leetcode3186。
大体步骤如下：
1.在 main 函数中，定义了输入的 power 数组，然后调用 maximumTotalDamage 函数，并打印最终结果。
2.在 maximumTotalDamage 函数中，首先使用一个 map 统计每种攻击力出现的次数，并将不同的攻击力存储到一个切片中，并进行排序。
3.使用动态规划的方法计算最大伤害值总和。创建一个数组 dp 用于存储计算过程中的最大伤害值总和，然后遍历排序后的攻击力数组。
4.对于每个攻击力，根据规则选择是否使用当前攻击力，并更新最大伤害值总和。
5.最终返回 dp[n+2]，即最大伤害值总和。
总的时间复杂度：
总的额外空间复杂度：
综上，总的时间复杂度为 O(nlogn)，总的额外空间复杂度为 O(n)。
Go 完整代码如下：
package main
import ( "fmt" "sort")
func maximumTotalDamage(power []int) int64 { // 统计每种攻击力的出现次数 cnt := make(map[int]int) for _, p := range power { cnt[p]++ }
// 将不同的攻击力存储到一个切片并排序 powers := make([]int, 0, len(cnt)) for p := range cnt { powers = append(powers, p) } sort.Ints(powers)
n := len(powers) // dp数组多开几个空间防止下标越界 dp := make([]int64, n+3)
for i := 0; i < n; i++ { x := powers[i]
// 继承不选当前值的情况 dp[i+3] = dp[i+2]
// 选择当前值x，并处理不同的跳过情况 if _, ok1 := cnt[x-2]; ok1 && cnt[x-1] > 0 { dp[i+3] = max(dp[i+3], dp[i]+int64(x)*int64(cnt[x])) } else if ok1 || cnt[x-1] > 0 { dp[i+3] = max(dp[i+3], dp[i+1]+int64(x)*int64(cnt[x])) } else { dp[i+3] += int64(x) * int64(cnt[x]) } }
return dp[n+2]}
func main() { power := []int{7, 1, 6, 6} result := maximumTotalDamage(power) fmt.Println(result)}
复制代码
Rust 完整代码如下：
use std::collections::HashMap;
fn maximum_total_damage(power: Vec<i32>) -> i64 { // 统计每种攻击力的出现次数 let mut cnt = HashMap::new(); for &p in &power { *cnt.entry(p).or_insert(0) += 1; }
// 将不同的攻击力存储到一个 Vec 中并排序 let mut powers: Vec<i32> = cnt.keys().cloned().collect(); powers.sort();
let n = powers.len(); // dp数组多开几个空间防止下标越界 let mut dp = vec![0; n + 3];
for i in 0..n { let x = powers[i];
// 继承不选当前值的情况 dp[i + 3] = dp[i + 2];
// 选择当前值 x，并处理不同的跳过情况 if cnt.contains_key(&(x - 2)) && cnt.contains_key(&(x - 1)) { dp[i + 3] = dp[i + 3].max(dp[i] + x as i64 * cnt[&x] as i64); } else if cnt.contains_key(&(x - 2)) || cnt.contains_key(&(x - 1)) { dp[i + 3] = dp[i + 3].max(dp[i + 1] + x as i64 * cnt[&x] as i64); } else { dp[i + 3] += x as i64 * cnt[&x] as i64; } }
dp[n + 2]}
fn main() { let power = vec![7, 1, 6, 6]; let result = maximum_total_damage(power); println!("{}", result);}
复制代码
C 完整代码如下：
#include <stdio.h>#include <stdlib.h>
#define MAX_POWERS 1000 // 假设最大的咒语伤害值不会超过1000
// 比较函数用于 qsortint compare(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
// 计算最大总伤害long long maximumTotalDamage(int *power, int size) { int cnt[MAX_POWERS] = {0}; // 统计每种攻击力的出现次数 for (int i = 0; i < size; i++) { cnt[power[i]]++; }
int powers[MAX_POWERS]; int n = 0;
// 将不同的攻击力存储到数组并排序 for (int i = 0; i < MAX_POWERS; i++) { if (cnt[i] > 0) { powers[n++] = i; } } // 排序 qsort(powers, n, sizeof(int), compare);
long long dp[n + 3]; // dp数组 for (int i = 0; i < n + 3; i++) { dp[i] = 0; // 初始化 }
for (int i = 0; i < n; i++) { int x = powers[i];
// 继承不选当前值的情况 dp[i + 3] = dp[i + 2];
// 选择当前值x，并处理不同的跳过情况 if (cnt[x - 2] > 0 && cnt[x - 1] > 0) { dp[i + 3] = dp[i + 3] > dp[i] + (long long)x * cnt[x] ? dp[i + 3] : (dp[i] + (long long)x * cnt[x]); } else if (cnt[x - 2] > 0 || cnt[x - 1] > 0) { dp[i + 3] = dp[i + 3] > dp[i + 1] + (long long)x * cnt[x] ? dp[i + 3] : (dp[i + 1] + (long long)x * cnt[x]); } else { dp[i + 3] += (long long)x * cnt[x]; } }
return dp[n + 2];}
int main() { int power[] = {7, 1, 6, 6}; // 示例输入 int size = sizeof(power) / sizeof(power[0]); long long result = maximumTotalDamage(power, size); printf("%lld\n", result); // 输出结果 return 0;}
复制代码
C++完整代码如下：
#include <iostream>#include <vector>#include <unordered_map>#include <algorithm>
using namespace std;
long long maximumTotalDamage(vector<int>& power) { // 统计每种攻击力的出现次数 unordered_map<int, int> cnt; for (const auto& p : power) { cnt[p]++; }
// 将不同的攻击力存储到一个向量中并排序 vector<int> powers; for (const auto& p : cnt) { powers.push_back(p.first); } sort(powers.begin(), powers.end());
int n = powers.size(); // dp 数组多开几个空间防止下标越界 vector<long long> dp(n + 3, 0);
for (int i = 0; i < n; i++) { int x = powers[i];
// 继承不选当前值的情况 dp[i + 3] = dp[i + 2];
// 选择当前值 x，并处理不同的跳过情况 if (cnt.count(x - 2) && cnt[x - 1] > 0) { dp[i + 3] = max(dp[i + 3], dp[i] + static_cast<long long>(x) * cnt[x]); } else if (cnt.count(x - 2) || cnt[x - 1] > 0) { dp[i + 3] = max(dp[i + 3], dp[i + 1] + static_cast<long long>(x) * cnt[x]); } else { dp[i + 3] += static_cast<long long>(x) * cnt[x]; } }
return dp[n + 2];}
int main() { vector<int> power = {7, 1, 6, 6}; // 示例输入 long long result = maximumTotalDamage(power); cout << result << endl; // 输出结果 return 0;}
复制代码
Python 完整代码如下：
# -*-coding:utf-8-*-
from collections import Counter
def maximum_total_damage(power): # 统计每种攻击力的出现次数 cnt = Counter(power) # 获取不同的攻击力并排序 powers = sorted(cnt.keys())
n = len(powers) # dp数组多开几个空间防止下标越界 dp = [0] * (n + 3)
for i in range(n): x = powers[i]
# 不选当前值的情况 dp[i + 3] = dp[i + 2]
# 选择当前值 x，并处理不同的跳过情况 if (x - 2) in cnt and (x - 1) in cnt: dp[i + 3] = max(dp[i + 3], dp[i] + x * cnt[x]) elif (x - 2) in cnt or (x - 1) in cnt: dp[i + 3] = max(dp[i + 3], dp[i + 1] + x * cnt[x]) else: dp[i + 3] += x * cnt[x]
return dp[n + 2]
# 示例测试if __name__ == "__main__": power = [7, 1, 6, 6] result = maximum_total_damage(power) print(result) # 输出结果
复制代码
Javascript 完整代码如下：
function maximumTotalDamage(power) { // 统计每种攻击力的出现次数 const cnt = {}; for (const p of power) { cnt[p] = (cnt[p] || 0) + 1; // 计数 }
// 将不同的攻击力存储到一个数组并排序 const powers = Object.keys(cnt).map(Number); powers.sort((a, b) => a - b);
const n = powers.length; // dp数组多开几个空间防止下标越界 const dp = new Array(n + 3).fill(0);
for (let i = 0; i < n; i++) { const x = powers[i];
// 继承不选当前值的情况 dp[i + 3] = dp[i + 2];
// 选择当前值x，并处理不同的跳过情况 if ((x - 2) in cnt && (x - 1) in cnt) { dp[i + 3] = Math.max(dp[i + 3], dp[i] + x * cnt[x]); } else if ((x - 2) in cnt || (x - 1) in cnt) { dp[i + 3] = Math.max(dp[i + 3], dp[i + 1] + x * cnt[x]); } else { dp[i + 3] += x * cnt[x]; } }
return dp[n + 2];}
// 示例测试const power = [7, 1, 6, 6];const result = maximumTotalDamage(power);console.log(result); // 输出结果
复制代码
评论