华为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 版本实现相对复杂，可以考虑使用链表或循环数组来优化。
• 空间优化： 如果原数组可以修改，可以原地删除元素，节省空间。

总结

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