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

思路

两种算法可以

解题方法

代码

复杂

时间复杂度:

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: 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&gt;&amp; cardPoints, int k) {
        vector<int&gt; headSum(k+1, 0);
        vector<int&gt; 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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注