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

2023-12-04 07:52

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

文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code
    • Rust代码
      • 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: 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;}
};

这篇关于[NEO解题报告]《Leetcode》1423. 可获得的最大点数 - Rust/C++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/452721

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C