思路
- 方法1: 直接计算, 首尾各自往中间记录两个前缀和, 然后单次遍历 从前面取i个和后面取 k–i 个的和, 求最大值即可; (C++ 实现)
- 方法2: 问题转换成 计算中间连续 剩余数字
len-k
长度的和 的最小值, 划窗解决, 每次去掉最早的数字加入最右边的数字, 计算出最小剩余和, 目标则为 整体和 – 最小剩余和 ; (rust 实现)
解题方法
见代码
复杂度
O
(
n
)
O(n)
O(n)
O
(
1
)
O(1)
O(1), C++:
O
(
n
)
O(n)
O(n)
Code
Rust代码
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;
}
};
原文地址:https://blog.csdn.net/Quner6/article/details/134772584
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_36084.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。