阅读量:5
题目描述
给一个正整数数列 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; }