华为OD机试 - 求幸存数之和（Java & JS & Python & C & C++）

题目描述

给一个正整数数列 nums，一个跳数 jump，及幸存数量 left。

运算过程为：从索引0的位置开始向后跳，中间跳过 J 个数字，命中索引为 J+1 的数字，该数被敲出，并从该点起跳，以此类推，直到幸存 left 个数为止，然后返回幸存数之和。

约束：

1. 0是第一个起跳点
2. 起跳点和命中点之间间隔 jump 个数字，已被敲出的数字不计入在内。
3. 跳到末尾时无缝从头开始（循环查找），并可以多次循环。
4. 若起始时 left > len(nums) 则无需跳数处理过程。

方法设计：

/**
 * @param nums 正整数数列，长度范围 [1, 10000]
 * @param jump 跳数，范围 [1, 10000]
 * @param left 幸存数量，范围 [0, 10000]
 * @return 幸存数之和
 */
int sumOfLeft(int[] nums, int jump, int left)

输入描述

第一行输入正整数数列

第二行输入跳数

第三行输入幸存数量

输出描述

输出幸存数之和

用例

题目解析

本题考试时为核心代码模式，非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;
}