[NEO解题报告]《Leetcode》1423. 可获得的最大点数

[NEO解题报告]《Leetcode》1423. 可获得的最大点数 - Rust/C++

本文主要是介绍[NEO解题报告]《Leetcode》1423. 可获得的最大点数 - Rust/C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

思路
解题方法
复杂度
Code
- Rust代码
- - rust 用例
- C++ 代码

Problem: 1423. 可获得的最大点数

思路

两种算法都可以：

方法1：直接计算，首尾各自往中间记录两个前缀和，然后单次遍历从前面取i个和后面取 k-i 个的和，求最大值即可； (C++ 实现）
方法2：问题转换成计算中间连续剩余数字len-k 长度的和的最小值，划窗解决，每次去掉最早的数字加入最右边的数字，计算出最小剩余和，目标则为整体和 - 最小剩余和； (rust 实现）

解题方法

见代码

复杂度

时间复杂度:

$O (n)$

空间复杂度:

$O (1)$ ， C++： $O (n)$

Code

Rust代码

刷题学 Rust 语法，练习 迭代器、切片、求和、vector 等；

use std::cmp::min;// struct Solution {}impl Solution {pub fn max_score(card_points: Vec<i32>, k: i32) -> i32 {let total = card_points.iter().sum();if card_points.len() as i32 == k {return total;}let remain_cnt = card_points.len() - k as usize;let mut remain_sum: i32 = card_points[0..remain_cnt].iter().sum();let mut remain_sum_min = remain_sum;for i in 1..(k + 1) {remain_sum += card_points[i as usize - 1 + remain_cnt] - card_points[i as usize - 1];remain_sum_min = min(remain_sum_min, remain_sum);}return total - remain_sum_min;}
}

rust 用例

#[test]
fn tc1() {let card_points = vec![1, 2, 3, 4, 5, 6, 1];let k = 3;let ans = Solution::max_score(card_points, k);assert_eq!(ans, 12);
}#[test]
fn tc2() {let card_points = vec![2, 2, 2];let k = 2;let ans = Solution::max_score(card_points, k);assert_eq!(ans, 4);
}#[test]
fn tc3() {let card_points = vec![9, 7, 7, 9, 7, 7, 9];let k = 7;let ans = Solution::max_score(card_points, k);assert_eq!(ans, 55);
}#[test]
fn tc4() {let card_points = vec![1, 1000, 1];let k = 1;let ans = Solution::max_score(card_points, k);assert_eq!(ans, 1);
}#[test]
fn tc5() {let card_points = vec![1, 79, 80, 1, 1, 1, 200, 1];let k = 3;let ans = Solution::max_score(card_points, k);assert_eq!(ans, 202);
}#[test]
fn tc6() {let card_points = vec![9, 5, 2, 7];let total = card_points.iter().sum();let k = card_points.len();let ans = Solution::max_score(card_points, k as i32);assert_eq!(ans, total);
}#[test]
fn tc7() {let card_points = vec![9, 5, 2, 7];let k = 1;let ans = Solution::max_score(card_points, k as i32);assert_eq!(ans, 9);
}#[test]
fn tc8() {let card_points = vec![9, 5, 2, 70];let k = 1;let ans = Solution::max_score(card_points, k as i32);assert_eq!(ans, 70);
}

C++ 代码

class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {vector<int> headSum(k+1, 0);vector<int> tailSum(k+1, 0);for (int i = 1; i <= k; i++) {headSum[i] = headSum[i-1] + cardPoints[i-1];}for (int i=1, j = cardPoints.size()-1; i<=k; i++, j--) {tailSum[i] = tailSum[i-1] + cardPoints[j];}int ans = 0;for (int i = 0; i <= k; i++) {ans = max(ans, headSum[i] + tailSum[k-i]);}return ans;}
};