在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given an array In each operation, you pick any You start with 0 points. Return the maximum number of points you can earn by applying such operations. Example 1: Input: nums = [3, 4, 2] Output: 6 Explanation: Delete 4 to earn 4 points, consequently 3 is also deleted. Then, delete 2 to earn 2 points. 6 total points are earned. Example 2: Input: nums = [2, 2, 3, 3, 3, 4] Output: 9 Explanation: Delete 3 to earn 3 points, deleting both 2's and the 4. Then, delete 3 again to earn 3 points, and 3 again to earn 3 points. 9 total points are earned. Note:
给定一个整数数组 每次操作中,选择任意一个 开始你拥有 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 个点数。 注意:
36ms 1 class Solution { 2 func deleteAndEarn(_ nums: [Int]) -> Int { 3 if nums.count == 0 { 4 return 0 5 } 6 7 let maxN = nums.max()! 8 var M = [Int](repeating: 0, count: maxN + 1) 9 var DP = [Int](repeating: 0, count: maxN + 1) 10 11 for i in 0..<nums.count { 12 M[nums[i]] += nums[i] 13 } 14 15 DP[0] = M[0] 16 DP[1] = M[1] 17 for i in 2..<M.count { 18 DP[i] = max(DP[i - 2] + M[i],DP[i - 1]) 19 } 20 21 return DP.last! 22 } 23 } 40ms 1 class Solution { 2 func deleteAndEarn(_ nums: [Int]) -> Int { 3 let minValue = nums.min() ?? 0 4 let maxValue = nums.max() ?? 0 5 var dp = [Int](repeating: 0, count:maxValue + 1) 6 for item in nums { 7 dp[item] += item 8 } 9 10 if maxValue >= 2{ 11 for i in 2...maxValue { 12 dp[i] = max(dp[i-2] + dp[i], dp[i-1]) 13 } 14 } 15 16 return dp[maxValue] 17 } 18 } 44ms 1 class Solution { 2 func deleteAndEarn(_ nums: [Int]) -> Int { 3 var counts = [Int: Int]() 4 for num in nums { 5 counts[num, default: 0] += 1 6 } 7 8 var prev = -1 9 var avoid = 0 10 var using = 0 11 12 for num in counts.keys.sorted() { 13 if num - 1 != prev { 14 (avoid, using) = (max(avoid, using), num * counts[num]! + max(avoid, using)) 15 } else { 16 (avoid, using) = (max(avoid, using), num * counts[num]! + avoid) 17 } 18 19 prev = num 20 } 21 22 return max(avoid, using) 23 } 24 } Runtime: 52 ms
Memory Usage: 19.3 MB
1 class Solution { 2 func deleteAndEarn(_ nums: [Int]) -> Int { 3 var sums:[Int] = [Int](repeating:0,count:10001) 4 for num in nums 5 { 6 sums[num] += num 7 } 8 for i in 2..<10001 9 { 10 sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]) 11 } 12 return sums[10000] 13 } 14 } 92ms 1 class Solution { 2 func deleteAndEarn(_ nums: [Int]) -> Int { 3 if nums.count == 0 { 4 return 0 5 } 6 if nums.count == 1 { 7 return nums[0] 8 } 9 var numCount: [String: Int] = [:] 10 var dp: [String : Int] = [:] 11 var maxCount = 0 12 for i in 0 ..< nums.count { 13 if let a = numCount["\(nums[i])"] { 14 numCount["\(nums[i])"] = a + 1 15 }else { 16 numCount["\(nums[i])"] = 1 17 } 18 if nums[i] > maxCount { 19 maxCount = nums[i] 20 } 21 } 22 dp["0"] = 0 23 if let a = numCount["1"] { 24 dp["1"] = a 25 }else { 26 dp["1"] = 0 27 } 28 for i in 2 ... maxCount { 29 var a = 0 30 if let e = dp["\(i - 1)"] { 31 a = e 32 } 33 var b = 0 34 var c = 0 35 if let count = dp["\(i - 2)"] { 36 c = count 37 } 38 if let count = numCount["\(i)"] { 39 b = count * i + c 40 } 41 dp["\(i)"] = max(a, b) 42 } 43 return dp["\(maxCount)"]! 44 } 45 }
|
请发表评论