#C64. 华为OD机试统一考试D卷C卷 - 求幸存数之和
华为OD机试统一考试D卷C卷 - 求幸存数之和
题目链接
华为OD机试统一考试D卷C卷 - 求幸存数之和(C++ Java JavaScript Python)
https://blog.csdn.net/banxia_frontend/article/details/135029449
题目描述
给一个正整数数列 nums,一个跳数 jump,及幸存数量 left。 运算过程为:从索引0的位置开始向后跳,中间跳过 J 个数字,命中索引为 J+1 的数字,该数被敲出,并从该点起跳,以此类推,直到幸存 left 个数为止,然后返回幸存数之和。
约束:
- 0是第一个起跳点
- 起跳点和命中点之间间隔 jump 个数字,已被敲出的数字不计入在内。
- 跳到末尾时无缝从头开始(循环查找),并可以多次循环。
- 若起始时 left > len(nums) 则无需跳数处理过程。
方法设计:
* @param nums 正整数数列,长度范围 [1, 10000]
* @param jump 跳数,范围 [1, 10000]
* @param left 幸存数量,范围 [0, 10000]
* @return 幸存数之和
int sumOfLeft(int[] nums, int jump, int left){
}
输入描述
第一行输入正整数数列
第二行输入跳数
第三行输入幸存数量
输出描述
输出幸存数之和
用例
输入 | 1,2,3,4,5,6,7,8,9 4 3 |
---|---|
输出 | 13 |
说明 | 从1(索引为0)开始起跳,中间跳过 4 个数字,因此依次删除 6,2,8,5,4,7。剩余1,3,9,返回和为13 |
解题思路
本题考试时为Lettoce模式,无需自己获取输入数据。
本题主要是模拟操作,按照每次跳数的位置,从数列中删掉跳到的数组,直到剩余幸存数量的数字。
C++
#include <iostream>
#include <list>
#include <numeric>
#include <sstream>
#include <string>
#include <vector>
#include <numeric>
using namespace std;
// 计算幸存数之和
int sumOfLeft(int nums[], int jump, int left, int length) {
// 如果幸存数量大于等于数组长度,则直接返回数组元素之和
if (left >= length) {
return accumulate(nums, nums + length, 0);
}
// 使用vector存储数组元素,方便删除操作
vector<int> lst(nums, nums + length);
// 初始化起跳点索引为0
int index = 0;
// 当列表大小大于幸存数量时,执行删除操作
while (lst.size() > left) {
// 计算下一个要删除元素的索引
index = (index + jump + 1) % lst.size();
// 删除计算出的索引处的元素
lst.erase(lst.begin() + index);
// 由于删除元素后,列表会缩短,下一个起跳点应当向前移动一位
index = index - 1 ;
}
// 计算并返回剩余元素之和
return accumulate(lst.begin(), lst.end(), 0);
}
int main() {
string line;
vector<int> nums;
int jump, left;
// 读取一行输入,按逗号分割,转换为整数数组
getline(cin, line);
stringstream ss(line);
string num;
while (getline(ss, num, ',')) {
nums.push_back(stoi(num));
}
// 读取跳数
cin >> jump;
// 读取幸存数量
cin >> left;
// 输出幸存数之和
cout << sumOfLeft(&nums[0], jump, left, nums.size()) << endl;
return 0;
}
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取一行输入,按逗号分割,转换为整数数组
int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
// 读取跳数
int jump = Integer.parseInt(sc.nextLine());
// 读取幸存数量
int left = Integer.parseInt(sc.nextLine());
// 输出幸存数之和
System.out.println(sumOfLeft(nums, jump, left));
}
public static int sumOfLeft(int[] nums, int jump, int left) {
// 如果幸存数量大于等于数组长度,则直接返回数组元素之和
if (left >= nums.length) {
return Arrays.stream(nums).sum();
}
// 使用LinkedList存储数组元素,方便删除操作
LinkedList<Integer> list = new LinkedList<>();
for (int num : nums) {
list.add(num);
}
// 初始化起跳点索引为0
int index = 0;
// 当列表大小大于幸存数量时,执行删除操作
while (list.size() > left) {
// 计算下一个要删除元素的索引
index = index + jump + 1;
// 为了实现循环跳跃,索引可能会超出列表大小,因此取模
index = index % list.size();
// 删除计算出的索引处的元素
list.remove(index);
// 由于删除元素后,列表会缩短,下一个起跳点应当向前移动一位
index = index - 1;
}
// 计算并返回剩余元素之和
return list.stream().mapToInt(Integer::intValue).sum();
}
}
javaScript
// 导入必要的库
const readline = require('readline');
// 创建readline接口实例
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 读取输入
rl.on('line', (line) => {
// 根据输入行数,分别处理
if (!this.nums) {
// 读取一行输入,按逗号分割,转换为整数数组
this.nums = line.split(',').map(Number);
} else if (!this.jump) {
// 读取跳数
this.jump = Number(line);
} else if (!this.left) {
// 读取幸存数量
this.left = Number(line);
// 输出幸存数之和
console.log(sumOfLeft(this.nums, this.jump, this.left));
rl.close();
}
});
// 计算幸存数之和
function sumOfLeft(nums, jump, left) {
// 如果幸存数量大于等于数组长度,则直接返回数组元素之和
if (left >= nums.length) {
return nums.reduce((acc, val) => acc + val, 0);
}
// 使用数组存储元素,方便删除操作
let list = nums.slice();
// 初始化起跳点索引为0
let index = 0;
// 当列表大小大于幸存数量时,执行删除操作
while (list.length > left) {
// 计算下一个要删除元素的索引
index = (index + jump + 1) % list.length;
// 删除计算出的索引处的元素
list.splice(index, 1);
// 由于删除元素后,列表会缩短,下一个起跳点应当向前移动一位
index = index - 1 ;
}
// 计算并返回剩余元素之和
return list.reduce((acc, val) => acc + val, 0);
}
Python
def sum_of_left(nums, jump, left):
# 如果幸存数量大于等于数组长度,则直接返回数组元素之和
if left >= len(nums):
return sum(nums)
# 使用列表存储数组元素,方便删除操作
lst = nums[:]
# 初始化起跳点索引为0
index = 0
# 当列表大小大于幸存数量时,执行删除操作
while len(lst) > left:
# 计算下一个要删除元素的索引
index = (index + jump + 1) % len(lst)
# 删除计算出的索引处的元素
del lst[index]
# 由于删除元素后,列表会缩短,下一个起跳点应当向前移动一位
index = index - 1
# 计算并返回剩余元素之和
return sum(lst)
# 读取一行输入,按逗号分割,转换为整数数组
nums = list(map(int, input().split(',')))
# 读取跳数
jump = int(input())
# 读取幸存数量
left = int(input())
# 输出幸存数之和
print(sum_of_left(nums, jump, left))
C语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义最大数组大小常量
#define MAX_SIZE 10000
// 计算幸存数之和的函数
int sumOfLeft(int nums[], int nums_size, int jump, int left);
// 主函数
int main() {
int nums[MAX_SIZE];
int nums_size = 0;
while (scanf("%d", &nums[nums_size++])) {
if (getchar() != ',') break;
}
int jump;
scanf("%d", &jump);
int left;
scanf("%d", &left);
printf("%d\n", sumOfLeft(nums, nums_size, jump, left));
return 0;
}
// 计算幸存数之和的函数
int sumOfLeft(int nums[], int nums_size, int jump, int left) {
// 特殊情况处理:如果幸存数量为0,直接返回0
if (left == 0) {
return 0;
}
// 如果幸存数量大于等于数组长度,则直接返回数组元素之和
if (left >= nums_size) {
int sum = 0;
for (int i = 0; i < nums_size; i++) {
sum += nums[i];
}
return sum;
}
// 初始化起跳点索引为0
int index = 0;
// 当数组大小大于幸存数量时,执行删除操作
while (nums_size > left) {
// 计算下一个要删除元素的索引
index = (index + jump + 1) % nums_size;
// 删除计算出的索引处的元素
for (int i = index; i < nums_size - 1; i++) {
nums[i] = nums[i + 1];
}
nums_size--; // 更新数组大小
// 由于删除元素后,数组会缩短,下一个起跳点应当向前移动一位
index = (index - 1 + nums_size) % nums_size;
}
// 计算并返回剩余元素之和
int sum = 0;
for (int i = 0; i < nums_size; i++) {
sum += nums[i];
}
return sum;
}
完整用例
用例1
1,2,3,4,5,6,7,8,9,10 2 4
用例2
1,2,3,4,5 6 2
用例3
1,2,3,4,5 1 5
用例4
1,2,3,4,5,6,7,8,9,10 3 0
用例5
1 1 1
用例6
1,2,3,4,5,6,7,8,9,10 1 3
用例7
1,2,3,4,5,6,7,8,9,10 10 5
用例8
2,4,6,8,10,12 3 2
用例9
1,2 1 1
用例10
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 14 3 @[TOC]