E卷-跳房子I(100分)

跳房子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); // 将字符串转换为整数
        token = strtok(NULL, ",");
    }
    return result;
}

int main() {
    char input[100100];
    fgets(input, 100100, stdin); // 获取输入的步数列表
    
    int size;
    int* steps = parseInput(input, &size); // 解析输入为整数数组
    
    int count;
    scanf("%d", &count); // 获取目标值

    int returnSize;
    int* result = findJumpCombination(steps, size, count, &returnSize); // 查找组合

    // 输出结果
    printf("[%d, %d]\n", result[0], result[1]);

    free(steps);   // 释放steps数组内存
    free(result);  // 释放result数组内存
    
    return 0;
}

• Javascript

// 寻找跳跃组合的函数
function findJumpCombination(steps, count) {
    // 使用Map来存储步数和对应的索引
    const stepMap = new Map();
    // 初始化结果数组和最小索引和
    let result = [];
    let minIndexSum = Infinity;
    
    // 遍历步数数组
    for (let i = 0; i < steps.length; i++) {
        // 计算需要的补数
        const complement = count - steps[i];
        // 如果补数在Map中存在，说明找到了一个有效组合
        if (stepMap.has(complement)) {
            // 计算当前组合的索引和
            const currentIndexSum = i + stepMap.get(complement);
            // 如果当前索引和小于之前的最小索引和，更新结果
            if (currentIndexSum < minIndexSum) {
                minIndexSum = currentIndexSum;
                // 确保结果数组中的元素按原始顺序排列
                if (stepMap.get(complement) < i) {
                    result = [complement, steps[i]];
                } else {
                    result = [steps[i], complement];
                }
            }
        }
        // 将当前步数和索引加入Map，如果已存在则不更新（保留最小索引）
        if (!stepMap.has(steps[i])) {
            stepMap.set(steps[i], i);
        }
    }
    
    return result;
}

// 解析输入字符串为数字数组
function parseInput(input) {
    // 移除首尾的方括号，分割字符串，并将每个元素转换为数字
    return input.slice(1, -1).split(',').map(Number);
}

// 引入readline模块以处理控制台输入
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 读取第一行输入（步数数组）
rl.question('', (input) => {
    const steps = parseInput(input);
    // 读取第二行输入（目标计数）
    rl.question('', (count) => {
        // 调用findJumpCombination函数并输出结果
        const result = findJumpCombination(steps, parseInt(count));
        console.log(`[${result[0]}, ${result[1]}]`);
        rl.close();
    });
});

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取步数数组
        String stepsInput = scanner.nextLine().trim();
        stepsInput = stepsInput.substring(1, stepsInput.length() - 1); // 移除方括号
        String[] stepsStr = stepsInput.split(",");
        int[] steps = new int[stepsStr.length];
        for (int i = 0; i < stepsStr.length; i++) {
            steps[i] = Integer.parseInt(stepsStr[i].trim());
        }
        
        // 读取房子总格数
        int count = scanner.nextInt();
        
        // 调用函数并输出结果
        int[] result = findJumpCombination(steps, count);
        System.out.println(Arrays.toString(result));
        
        scanner.close();
    }
    
    public static int[] findJumpCombination(int[] steps, int count) {
        // 创建一个 Map 来存储步数和对应的索引
        Map<Integer, Integer> stepMap = new HashMap<>();
        // 初始化结果数组和最小索引和
        int[] result = new int[2];
        int minIndexSum = Integer.MAX_VALUE;
        
        // 遍历步数数组
        for (int i = 0; i < steps.length; i++) {
            // 计算需要的补数
            int complement = count - steps[i];
            // 如果补数在 Map 中，说明找到了一个有效组合
            if (stepMap.containsKey(complement)) {
                // 计算当前组合的索引和
                int currentIndexSum = i + stepMap.get(complement);
                // 如果当前索引和小于之前的最小索引和，更新结果
                if (currentIndexSum < minIndexSum) {
                    minIndexSum = currentIndexSum;
                    if (stepMap.get(complement) < i) {
                        result[0] = complement;
                        result[1] = steps[i];
                    } else {
                        result[0] = steps[i];
                        result[1] = complement;
                    }
                }
            }
            // 将当前步数和索引加入 Map，如果已存在则不更新（保留最小索引）
            stepMap.putIfAbsent(steps[i], i);
        }
        
        return result;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <sstream>
#include <string>

using namespace std;

vector<int> findJumpCombination(const vector<int>& steps, int count) {
    // 创建一个 unordered_map 来存储步数和对应的索引
    unordered_map<int, int> stepMap;
    // 初始化结果向量和最小索引和
    vector<int> result;
    int minIndexSum = INT_MAX;
    
    // 遍历步数数组
    for (int i = 0; i < steps.size(); ++i) {
        // 计算需要的补数
        int complement = count - steps[i];
        // 如果补数在 map 中，说明找到了一个有效组合
        if (stepMap.find(complement) != stepMap.end()) {
            // 计算当前组合的索引和
            int currentIndexSum = i + stepMap[complement];
            // 如果当前索引和小于之前的最小索引和，更新结果
            if (currentIndexSum < minIndexSum) {
                minIndexSum = currentIndexSum;
                if (stepMap[complement] < i) {
                    result = {complement, steps[i]};
                } else {
                    result = {steps[i], complement};
                }
            }
        }
        // 将当前步数和索引加入 map，如果已存在则不更新（保留最小索引）
        if (stepMap.find(steps[i]) == stepMap.end()) {
            stepMap[steps[i]] = i;
        }
    }
    
    return result;
}

vector<int> parseInput(const string& input) {
    vector<int> result;
    stringstream ss(input.substr(1, input.size() - 2)); // 移除方括号
    string item;
    while (getline(ss, item, ',')) {
        result.push_back(stoi(item));
    }
    return result;
}

int main() {
    string input;
    getline(cin, input);
    vector<int> steps = parseInput(input);
    
    int count;
    cin >> count;
    
    vector<int> result = findJumpCombination(steps, count);
    
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    
    return 0;
}