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

华为OD机试 - 求幸存数之和 问题详解与解法

题目描述

给定一个正整数数组 nums，一个跳数 jump 和一个幸存数量 left。从数组索引为 0 的位置开始，每跳过 jump 个数字，就删除一个数字。重复此过程，直到数组中只剩下 left 个数字。求剩余数字的和。

题目分析

这道题本质上是一个模拟问题，我们可以通过模拟删除元素的过程来得到最终的答案。

解题思路：

1. 初始化： 创建一个列表或数组来存储原始数据，设置两个指针，一个指向当前要删除的元素，另一个指向下一个要开始计数的位置。
2. 模拟删除：
   • 从起始位置开始，每隔 jump 个元素删除一个元素。
   • 为了避免索引越界，当到达数组末尾时，从数组开头继续计数。
   • 重复上述过程，直到数组中只剩下 left 个元素。
3. 计算总和： 遍历剩余的元素，计算并返回它们的和。

代码实现

Java

import java.util.ArrayList;
import java.util.List;

public class SurvivorSum {
    public int survivorSum(int[] nums, int jump, int left) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }

        int index = 0;
        while (list.size() > left) {
            list.remove(index);
            index = (index + jump) % list.size();
        }

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

Python

def survivor_sum(nums, jump, left):
    while len(nums) > left:
        nums.pop((jump - 1) % len(nums))
    return sum(nums)

JavaScript

function survivorSum(nums, jump, left) {
    while (nums.length > left) {
        nums.splice((jump - 1) % nums.length, 1);
    }
    return nums.reduce((sum, num) => sum + num, 0);
}

C++

#include <vector>

int survivorSum(std::vector<int>& nums, int jump, int left) {
    while (nums.size() > left) {
        nums.erase(nums.begin() + (jump - 1) % nums.size());
    }
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return sum;
}

C

#include <stdio.h>

int survivorSum(int nums[], int n, int jump, int left) {
    int index = 0;
    while (n > left) {
        for (int i = index + 1; i < index + jump; i++) {
            index = i % n;
        }
        for (int i = index; i < n - 1; i++) {
            nums[i] = nums[i + 1];
        }
        n--;
        index = (index + jump - 1) % n;
    }

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

优化

• C++ 版本中使用了 erase 函数来删除元素，效率更高。
• C 版本实现相对复杂，可以考虑使用链表或循环数组来优化。
• 空间优化： 如果原数组可以修改，可以原地删除元素，节省空间。

总结

这道题考察了对数组操作、模拟算法以及语言特性的掌握。通过模拟删除元素的过程，我们可以有效地解决这个问题。不同的编程语言提供了不同的数组操作方式，选择适合的语言和数据结构可以提高代码的效率和可读性。