E-跳房子I(100p)

跳房子I

问题描述

跳房子是一种广受欢迎的儿童游戏。游戏参与者需要分多个回合，按顺序从第 1 格跳到房子的最后一格。在跳房子的过程中，可以向前跳，也可以向后跳。

假设房子的总格数是 ，小红每回合可能连续跳的步数都放在数组 中。请判断数组中是否存在一种步数的组合，可以让小红在两个回合内跳到最后一格？

如果存在这样的组合，请输出索引和最小的步数组合。

注意：

• 数组中的步数可以重复，但数组中的元素不能重复使用。
• 提供的数据保证存在满足题目要求的组合，且索引和最小的步数组合是唯一的。

输入格式

第一行输入为房子总格数 ，它是 int 整数类型。 第二行输入为每回合可能连续跳的步数，它是 int 整数数组类型。

输出格式

返回索引和最小的满足要求的步数组合（顺序保持 中原有顺序）。

样例输入1

[1,4,5,2,2]
7

样例输出1

[5, 2]

样例输入2

[-1,2,4,9,6]
8

样例输出2

[-1, 9]

样例输入3

[1,2,9,9,9,1,9,9,3,2]
4

样例输出3

[1, 3]

解释说明

数据范围

题解

哈希表+模拟

这道题目本质上是"两数之和"问题的变种。我们需要在给定的数组 中找到两个数，使它们的和等于目标值 。不同于经典的"两数之和"，这里我们还需要考虑索引和最小的组合。

解题思路如下：

1. 创建一个哈希表（字典），用于存储每个步数及其索引。
2. 遍历数组 ，对于每个元素 ：
   • 计算补数
   • 如果 在哈希表中，我们找到了一个有效组合
   • 比较当前组合的索引和与之前找到的最小索引和
   • 如果当前索引和更小，更新结果
3. 如果遍历结束后没有找到有效组合，返回空列表

这种方法的时间复杂度是 ，其中 是数组 的长度。只需要遍历一次数组，而哈希表的查找操作的平均时间复杂度是 。

参考代码

• Python

def find_jump_combination(steps, count):
    # 创建一个字典来存储步数和对应的索引
    step_dict = {}
    # 初始化结果列表和最小索引和
    result = []
    min_index_sum = float('inf')
    
    # 遍历步数数组
    for i, step in enumerate(steps):
        # 计算需要的补数
        complement = count - step
        # 如果补数在字典中，说明找到了一个有效组合
        if complement in step_dict:
            # 计算当前组合的索引和
            current_index_sum = i + step_dict[complement]
            # 如果当前索引和小于之前的最小索引和，更新结果
            if current_index_sum < min_index_sum:
                min_index_sum = current_index_sum
                result = [complement, step] if step_dict[complement] < i else [step, complement]
        # 将当前步数和索引加入字典，如果已存在则不更新（保留最小索引）
        if step not in step_dict:
            step_dict[step] = i
    
    return result

# 读取输入
input_steps = eval(input().strip())  # 使用 eval 来解析输入的列表
count = int(input().strip())

# 调用函数并输出结果
result = find_jump_combination(input_steps, count)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// 定义结构体，用于存储步数及其索引
typedef struct {
    int step;
    int index;
} StepIndex;

// 函数：查找两个步数，使其和为指定值，且索引和最小
int* findJumpCombination(int* steps, int size, int count, int* returnSize) {
    // 创建一个动态数组，用于存储结果
    int* result = (int*)malloc(2 * sizeof(int));
    // 初始化一个很大的索引和，用于比较最小索引和
    int minIndexSum = INT_MAX;
    
    // 创建哈希表，简单使用数组模拟，存储步数及其最小索引
    StepIndex* stepMap = (StepIndex*)malloc(size * sizeof(StepIndex));
    int stepMapSize = 0; // 当前哈希表中元素数量

    // 遍历所有步数
    for (int i = 0; i < size; ++i) {
        int complement = count - steps[i]; // 计算所需补数
        
        // 查找补数是否存在哈希表中
        for (int j = 0; j < stepMapSize; ++j) {
            if (stepMap[j].step == complement) {
                // 找到有效组合，计算当前组合的索引和
                int currentIndexSum = i + stepMap[j].index;
                if (currentIndexSum < minIndexSum) {
                    minIndexSum = currentIndexSum;
                    // 更新结果，确保第一个数较小
                    if (stepMap[j].index < i) {
                        result[0] = complement;
                        result[1] = steps[i];
                    } else {
                        result[0] = steps[i];
                        result[1] = complement;
                    }
                }
                break; // 找到后立即退出查找
            }
        }

        // 将当前步数和索引加入哈希表
        int found = 0; // 是否找到相同的步数
        for (int j = 0; j < stepMapSize; ++j) {
            if (stepMap[j].step == steps[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            stepMap[stepMapSize].step = steps[i];
            stepMap[stepMapSize].index = i;
            stepMapSize++;
        }
    }

    // 返回结果大小为2
    *returnSize = 2;
    free(stepMap); // 释放哈希表内存
    return result;
}

// 函数：解析输入字符串为整数数组
int* parseInput(char* input, int* size) {
    int* result = (int*)malloc(100100 * sizeof(int)); 
    *size = 0;
    
    char* token = strtok(input + 1, ","); // 去掉第一个'['
    while (token != NULL && token[0] != ']') {
        result[(*size)++] = atoi(token); // 将字符串转换为整数
        to