电商网站开发的项目描述,网站手机版后台,乡下自家院子设计图片,棋牌网站建设文章目录 思路解题方法复杂度CodeRust代码rust 用例 C 代码 Problem: 1423. 可获得的最大点数 思路 两种算法都可以#xff1a; 方法1#xff1a; 直接计算#xff0c; 首尾各自往中间记录两个前缀和#xff0c; 然后单次遍历 从前面取i个和后面取 k-i 个的和#xff0c; … 文章目录 思路解题方法复杂度CodeRust代码rust 用例 C 代码 Problem: 1423. 可获得的最大点数 思路 两种算法都可以 方法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代码 刷题学 Rust 语法 练习 迭代器、切片、求和、vector 等 use std::cmp::min;// struct Solution {}impl Solution {pub fn max_score(card_points: Veci32, 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(vectorint cardPoints, int k) {vectorint headSum(k1, 0);vectorint tailSum(k1, 0);for (int i 1; i k; i) {headSum[i] headSum[i-1] cardPoints[i-1];}for (int i1, j cardPoints.size()-1; ik; 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;}
};
