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[1]
题目来自leetcode3186。
大体步骤如下：1.在 main 函数中，定义了输入的 power 数组，然后调用 maximumTotalDamage 函数，并打印最终结果。
2.在 maximumTotalDamage 函数中，首先使用一个 map 统计每种攻击力出现的次数，并将不同的攻击力存储到一个切片中，并进行排序。
3.使用动态规划的方法计算最大伤害值总和。创建一个数组 dp 用于存储计算过程中的最大伤害值总和，然后遍历排序后的攻击力数组。
4.对于每个攻击力，根据规则选择是否使用当前攻击力，并更新最大伤害值总和。
5.最终返回 dp[n+2]，即最大伤害值总和。
总的时间复杂度：
• 统计每种攻击力的出现次数时间复杂度为 O(n)。• 将不同的攻击力进行排序的时间复杂度为 O(nlogn)。• 最大伤害值总和的动态规划过程时间复杂度为 O(n)。• 所以总的时间复杂度为 O(n + nlogn)。总的额外空间复杂度：
• 除了 power 数组外，在统计每种攻击力的出现次数、排序和动态规划过程中额外使用的空间为 O(n)。• 所以总的额外空间复杂度为 O(n)。综上，总的时间复杂度为 O(nlogn)，总的额外空间复杂度为 O(n)。
Go完整代码如下：package mainimport ( "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 Counterdef 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); // 输出结果
在这里插入图片描述
引用链接[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP
