题目描述
给一个正整数数列 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 |
题目解析
本题考试时为核心代码模式,非ACM模式,即无需自己解析输入数据。
本博客代码实现仍然以ACM模式处理,但是会将输入处理 与 算法逻辑 分开,大家只看算法逻辑即可。
题目用例删点过程如下:
通过上面图示我们可以发现,被删除节点其实是作为起跳点,因此基于普通数组来操作的话,既要实现节点删除,又要实现基于删除点进行下次的起跳,这个逻辑是比较复杂的。
我的想法是构建一个循环链表来代替数组,关于循环链表的实现细节,请看代码实现以及注释。
2023.12.12
Python自定义循环链表的性能表现不佳,反而使用动态数组性能更好。
因此,加了一个动态数组解法。
JS算法源码
动态数组解法
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 输入处理
void (async function () {
const nums = (await readline()).split(",").map(Number);
const jump = parseInt(await readline());
const left = parseInt(await readline());
console.log(sumOfLeft(nums, jump, left));
})();
function sumOfLeft(nums, jump, left) {
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始,初始时起跳点为索引0,因此下一个节点为索引1
let start = 1;
// 如果剩余节点数 > 幸存数量,则还需要继续删除节点
while (nums.length > left) {
// 跳 jump 次
start += jump;
// 为了避免越界,新起跳点索引位置对剩余节点数取余
start %= nums.length;
nums.splice(start, 1);
}
return nums.reduce((a, b) => a + b, 0);
}
循环链表解法
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 输入处理
void (async function () {
const nums = (await readline()).split(",").map(Number);
const jump = parseInt(await readline());
const left = parseInt(await readline());
console.log(sumOfLeft(nums, jump, left));
})();
// 循环链表的节点定义
class Node {
constructor(val) {
this.val = val;
this.prev = null;
this.next = null;
}
}
// 循环链表定义
class CycleLink {
constructor(nums) {
this.head = null; // 私有属性,仅用于链接tail,完成循环
this.tail = null; // 私有属性,仅用于链接head,完成循环
this.cur = null; // 循环链表遍历指针
this.size = 0; // 循环链表的节点数
this.sum = 0; // 循环链表中所有节点值之和
// 初始化循环链表
for (let num of nums) {
// 向循环链表中添加节点
this.add(num);
}
// 将普通链表头尾相连,形成循环链表
if (this.head != null) {
this.head.prev = this.tail;
this.tail.next = this.head;
// 初始时循环链表的遍历指针指向头位值
this.cur = this.head;
}
}
add(val) {
const node = new Node(val);
if (this.size == 0) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
this.sum += val;
this.size++;
}
// 删除循环链表cur指针指向的节点
remove() {
// 被删除节点的值从 循环链表和 中去除
this.sum -= this.cur.val;
// 循环链表节点数量-1
this.size--;
// 完成删除节点动作
const prev = this.cur.prev;
const next = this.cur.next;
prev.next = next;
next.prev = prev;
this.cur.prev = null;
this.cur.next = null;
// 遍历指针指向被删除节点的下一个节点
this.cur = next;
}
// 遍历下一个循环链表节点
next() {
this.cur = this.cur.next;
}
}
function sumOfLeft(nums, jump, left) {
const link = new CycleLink(nums);
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始
link.next();
// 如果链表中剩余节点数 > 幸存数量,则还需要继续删除节点
while (link.size > left) {
// 跳 jump 次, 为了避免冗余转圈, 其实只需要跳 jump % link.size
const zip_jump = jump % link.size;
for (let i = 0; i < zip_jump; i++) {
link.next();
}
// 删除当前接节点(被删除的节点其实是下一次的起跳点),这里link.remove方法删除节点后会自动跳到被删除节点的下一个节点,即:起跳点的下一个节点
link.remove();
}
return link.sum;
}
Java算法源码
动态数组解法
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
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(new Main().sumOfLeft(nums, jump, left));
}
public int sumOfLeft(int[] nums, int jump, int left) {
ArrayList<Integer> list =
(ArrayList<Integer>) Arrays.stream(nums).boxed().collect(Collectors.toList());
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始,初始时起跳点为索引0,因此下一个节点为索引1
int start = 1;
// 如果剩余节点数 > 幸存数量,则还需要继续删除节点
while (list.size() > left) {
// 跳 jump 次
start += jump;
// 为了避免越界,新起跳点索引位置对剩余节点数取余
start %= list.size();
list.remove(start);
}
return list.stream().reduce(Integer::sum).orElse(0);
}
}
循环链表解法
import java.util.Arrays;
import java.util.Scanner;
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(new Main().sumOfLeft(nums, jump, left));
}
// 循环链表的节点定义
static class Node {
int val;
Node prev;
Node next;
public Node(int val) {
this.val = val;
}
}
// 循环链表定义
static class CycleLink {
private Node head; // 私有属性,仅用于链接tail,完成循环
private Node tail; // 私有属性,仅用于链接head,完成循环
public Node cur; // 循环链表遍历指针
public int size; // 循环链表的节点数
public int sum; // 循环链表中所有节点值之和
// 初始化循环链表
public CycleLink(int[] nums) {
// 向循环链表中添加节点
for (int num : nums) {
this.add(num);
}
// 将普通链表头尾相连,形成循环链表
if (this.head != null) {
this.head.prev = this.tail;
this.tail.next = this.head;
// 初始时循环链表的遍历指针指向头位值
this.cur = this.head;
}
}
private void add(int val) {
Node node = new Node(val);
if (this.size == 0) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
this.sum += val;
this.size++;
}
// 删除循环链表cur指针指向的节点
public void remove() {
// 被删除节点的值从 循环链表和 中去除
this.sum -= this.cur.val;
// 循环链表节点数量-1
this.size--;
// 完成删除节点动作
Node prev = this.cur.prev;
Node next = this.cur.next;
prev.next = next;
next.prev = prev;
this.cur.prev = null;
this.cur.next = null;
// 遍历指针指向被删除节点的下一个节点
this.cur = next;
}
// 遍历下一个循环链表节点
public void next() {
this.cur = this.cur.next;
}
}
public int sumOfLeft(int[] nums, int jump, int left) {
CycleLink link = new CycleLink(nums);
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始
link.next();
// 如果链表中剩余节点数 > 幸存数量,则还需要继续删除节点
while (link.size > left) {
// 跳 jump 次,为了避免冗余转圈, 其实只需要跳 jump % link.size
int zip_jump = jump % link.size;
for (int i = 0; i < zip_jump; i++) {
link.next();
}
// 删除当前接节点(被删除的节点其实是下一次的起跳点),这里link.remove方法删除节点后会自动跳到被删除节点的下一个节点,即:起跳点的下一个节点
link.remove();
}
return link.sum;
}
}
Python算法源码
动态数组解法
# 输入获取
nums = list(map(int, input().split(",")))
jump = int(input())
left = int(input())
# 算法入口
def sumOfLeft(nums, jump, left):
# 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
# 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
# 这里我们从起跳点的下一个节点开始,初始时起跳点为索引0,因此下一个节点为索引1
start = 1
# 如果剩余节点数 > 幸存数量,则还需要继续删除节点
while len(nums) > left:
# 跳 jump 次
start += jump
# 为了避免越界,新起跳点索引位置对剩余节点数取余
start %= len(nums)
nums.pop(start)
return sum(nums)
# 算法调用
print(sumOfLeft(nums, jump, left))
循环链表解法
# 循环链表的节点定义
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
# 循环链表定义
class CycleLink:
def __init__(self, nums):
self.head = None # 私有属性,仅用于链接tail,完成循环
self.tail = None # 私有属性,仅用于链接head,完成循环
self.cur = None # 循环链表遍历指针
self.size = 0 # 循环链表的节点数
self.sum = 0 # 循环链表中所有节点值之和
# 初始化循环链表
for num in nums:
# 向循环链表中添加节点
self.add(num)
# 将普通链表头尾相连,形成循环链表
if self.head is not None:
self.head.prev = self.tail
self.tail.next = self.head
# 初始时循环链表的遍历指针指向头位值
self.cur = self.head
def add(self, val):
node = Node(val)
if self.size == 0:
self.head = node
self.tail = node
else:
self.tail.next = node
node.prev = self.tail
self.tail = node
self.sum += val
self.size += 1
# 删除循环链表cur指针指向的节点
def remove(self):
# 被删除节点的值从 循环链表和 中去除
self.sum -= self.cur.val
# 循环链表节点数量-1
self.size -= 1
# 完成删除节点动作
prev = self.cur.prev
next = self.cur.next
prev.next = next
next.prev = prev
self.cur.prev = None
self.cur.next = None
# 遍历指针指向被删除节点的下一个节点
self.cur = next
# 遍历下一个循环链表节点
def next(self):
self.cur = self.cur.next
# 输入获取
nums = list(map(int, input().split(",")))
jump = int(input())
left = int(input())
# 算法入口
def sumOfLeft(nums, jump, left):
link = CycleLink(nums)
# 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
# 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
# 这里我们从起跳点的下一个节点开始
link.next()
# 如果链表中剩余节点数 > 幸存数量,则还需要继续删除节点
while link.size > left:
# 跳 jump 次,为了避免冗余转圈, 其实只需要跳 jump % link.size
zip_jump = jump % link.size
for _ in range(zip_jump):
link.next()
# 删除当前接节点(被删除的节点其实是下一次的起跳点),这里link.remove方法删除节点后会自动跳到被删除节点的下一个节点,即:起跳点的下一个节点
link.remove()
return link.sum
# 算法调用
print(sumOfLeft(nums, jump, left))
C算法源码
动态数组解法
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000
int sumOfLeft(int nums[], int nums_size, int jump, int left) {
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始,初始时起跳点为索引0,因此下一个节点为索引1
int start = 1;
// 如果剩余节点数 > 幸存数量,则还需要继续删除节点
while (nums_size > left) {
// 跳 jump 次
start += jump;
// 为了避免越界,新起跳点索引位置对剩余节点数取余
start %= nums_size;
for (int i = start; i < nums_size - 1; i++) {
nums[i] = nums[i + 1];
}
nums_size--;
}
int sum = 0;
for (int i = 0; i < nums_size; i++) {
sum += nums[i];
}
return sum;
}
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;
}
循环链表解法
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000
// 循环链表的节点定义
typedef struct Node {
int val;
struct Node *prev;
struct Node *next;
} Node;
// 循环链表定义
typedef struct CycleLink {
Node *head; // 私有属性,仅用于链接tail,完成循环
Node *tail; // 私有属性,仅用于链接head,完成循环
Node *cur; // 循环链表遍历指针
int size; // 循环链表的节点数
int sum; // 循环链表中所有节点值之和
} CycleLink;
void add_CycleLink(CycleLink *link, int val) {
Node *node = (Node *) malloc(sizeof(Node));
node->val = val;
node->prev = NULL;
node->next = NULL;
if (link->size == 0) {
link->head = node;
link->tail = node;
} else {
link->tail->next = node;
node->prev = link->tail;
link->tail = node;
}
link->size++;
link->sum += val;
}
// 初始化循环链表
CycleLink *new_CycleLink(int nums[], int nums_size) {
CycleLink *link = (CycleLink *) malloc(sizeof(CycleLink));
link->head = NULL;
link->tail = NULL;
link->cur = NULL;
link->size = 0;
link->sum = 0;
// 向循环链表中添加节点
for (int i = 0; i < nums_size; i++) {
add_CycleLink(link, nums[i]);
}
// 将普通链表头尾相连,形成循环链表
if (link->head != NULL) {
link->head->prev = link->tail;
link->tail->next = link->head;
// 初始时循环链表的遍历指针指向头位值
link->cur = link->head;
}
return link;
}
// 删除循环链表cur指针指向的节点
void remove_CycleLink(CycleLink *link) {
// 循环链表节点数量-1
link->size--;
// 被删除节点的值从 循环链表和 中去除
link->sum -= link->cur->val;
// 完成删除节点动作
Node *prev = link->cur->prev;
Node *next = link->cur->next;
prev->next = next;
next->prev = prev;
link->cur->prev = NULL;
link->cur->next = NULL;
// 遍历指针指向被删除节点的下一个节点
link->cur = next;
}
// 遍历下一个循环链表节点
void next_CycleLink(CycleLink *link) {
link->cur = link->cur->next;
}
int sumOfLeft(int nums[], int nums_size, int jump, int left) {
CycleLink *link = new_CycleLink(nums, nums_size);
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始
next_CycleLink(link);
// 如果链表中剩余节点数 > 幸存数量,则还需要继续删除节点
while (link->size > left) {
// 跳 jump 次,为了避免冗余转圈, 其实只需要跳 jump % link.size
int zip_jump = jump % link->size;
for (int i = 0; i < zip_jump; i++) {
next_CycleLink(link);
}
// 删除当前接节点(被删除的节点其实是下一次的起跳点),这里link.remove方法删除节点后会自动跳到被删除节点的下一个节点,即:起跳点的下一个节点
remove_CycleLink(link);
}
return link->sum;
}
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;
}
C++算法源码
动态数组解法
#include <bits/stdc++.h>
using namespace std;
int sumOfLeft(vector<int> &nums, int jump, int left) {
// 从起跳点开始的话,需要跳jump+1次,到达需要删除的节点
// 从起跳点下一个节点开始的话,需要跳jump次,到达需要删除的节点
// 这里我们从起跳点的下一个节点开始,初始时起跳点为索引0,因此下一个节点为索引1
int start = 1;
// 如果剩余节点数 > 幸存数量,则还需要继续删除节点
while (nums.size() > left) {
// 跳 jump 次
start += jump;
// 为了避免越界,新起跳点索引位置对剩余节点数取余
start %= nums.size();
nums.erase(nums.begin() + start);
}
return accumulate(nums.begin(), nums.end(), 0);
}
int main() {
vector<int> nums;
string s;
cin >> s;
stringstream ss(s);
string token;
while (getline(ss, token, ',')) {
nums.emplace_back(stoi(token));
}
int jump, left;
cin >> jump >> left;
cout << sumOfLeft(nums, jump, left) << endl;
return 0;
}