求幸存数之和 - 华为OD统一考试

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

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

约束:

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

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

示例1

输入：
[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

题解

以上是题目的 Java、Python 和 C++ 解法。这个题目的主要思路是模拟起跳的过程，删除指定的数字，然后计算幸存数之和。

解题步骤如下：

计算需要删除的次数 cnt = len(nums) - left。
使用循环进行删除操作，每次根据跳数 jump 计算下一个要删除的索引位置。
删除指定索引位置后面的元素，并更新数组长度。
计算剩余元素的和并返回。

这个题目主要涉及数组的操作，包括删除元素和前移元素，同时需要考虑循环查找的情况。在 Java 中使用 System.arraycopy 进行元素前移，而在 Python 和 C++ 中使用 pop 和 erase 进行元素删除。

在时间复杂度方面，主要是在循环中进行了数组的删除操作，整体的时间复杂度取决于数组删除操作的复杂度。在空间复杂度方面，除了输入参数外，主要使用了常数级的额外空间。

Java

/**
 * @author code5bug
 */
class Solution {
    /**
     * @param nums 正整数数列，长度范围 [1,10000]
     * @param jump 跳数，范围 [1,10000]
     * @param left 幸存数量，范围 [1,10000]
     * @return 幸存数之和
     */
    int sumOfLeft(int[] nums, int jump, int left) {
        int len = nums.length; // 正整数数列的长度
        int cnt = len - left;

        for (int i = 0, idx = 1; i < cnt; i++) {
            idx = (idx + jump) % len;
            // nums[idx] 后面的所有元素前移 1 位
            System.arraycopy(nums, idx + 1, nums, idx, len - idx - 1);
            len--;
        }

        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }

        return sum;
    }
}

Python

class Solution:
    def sumOfLeft(self, nums, jump, left):
        # 需要删除的次数
        cnt = len(nums) - left
        # 索引位置
        idx = 1
        for _ in range(cnt):
            idx = (idx + jump) % len(nums)
            nums.pop(idx)
        return sum(nums)

C++

class Solution {
public:
    int sumOfLeft(vector<int>& nums, int jump, int left) {
        int cnt = nums.size() - left;

        for(int i=0, idx = 1; i < cnt; i++) {
            idx = (idx + jump) % nums.size();
            nums.erase(nums.begin() + idx);
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        return sum;
    }
};