题目描述与示例

题目描述

跳房子,也叫跳飞机,是一种世界性的儿童游戏。

游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后一格,然后获得一次选房子的机会,直到所有房子都被选完,房子最多的人获胜。

跳房子的过程中,如果有踩线等违规行为会结束当前回合,甚至可能倒退几步。

假设房子的总格数是count,小红每回合可能连续跳的步数都放在数据steps中,请问数组中是否有一种步数的组合,可以让小红三个回合跳到最后一格?如果有,请输出索引和最小的步数组合,数据保证索引和最小的步数组合是唯一的。

注意:数组中的步数可以重复,但数组中的元素不能重复使用。

输入描述

第一行输入为房子总格数count,它是整数类型int

第二行输入为每回合可能连续跳过的步数,它是整数数组类型。

输出描述

返回索引和最小满足要求的步数组合。

注意:顺序保持steps中的原有顺序。

备注

  • count <= 10000;
  • 3 <= steps.length <= 10000;
  • -100000 <= steps[i] <= 100000;

示例一

输入

1,4,5,2,0,2
9

输出

4,5,0

说明

示例二

输入

1,5,2,0,2,4
9

输出

5,2,2

示例三

输入

-1,2,4,9
12

输出

-1,4,9

解题思路

注意,本题和LeetCode15、三数之和基本完全一致。区别仅仅在于本题需要找到下标和最小的索引。

代码

Python

# 题目:2023B-跳房子II
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:相向双指针
# 代码看不懂的地方,请直接在群上提问


from math import inf

# 输入原数组lst
lst = list(map(int, input().split(",")))
# 输入目标和
target = int(input())

# 获得原数组长度n
n = len(lst)
# 对原nums数组进行排序,同时需要记录在原数组中的下标i,作为排序的第二个依据
nums = sorted((num, i) for i, num in enumerate(lst))

# 初始化一个长度为3的数组,用于储存三个数的下标,初始化均为inf
ans_idx = [inf, inf, inf]

# 考虑第一个数first
for i, (first, idx) in enumerate(nums[:-2]):
    # 如果发现第i、第i+1、第i+2个数的和加起来超过target
    # 则更靠后的的选择肯定和更大,直接退出循环
    if nums[i][0] + nums[i+1][0] + nums[i+2][0] > target:
        break
    # 去重操作,如果遇到连续两个数相等,那么考虑nums[i]和考虑nums[i-1]所作的计算是一样的
    # 直接跳过nums[i]的计算
    if i != 0 and nums[i][0] == nums[i-1][0]:
        continue
    # 构建相向双指针left和right
    left, right = i+1, n-1
    while left < right:
        # 计算三个数的和
        sum3 = first + nums[left][0] + nums[right][0]
        # 三数和太大,right左移
        if sum3 > target:
            right -= 1
        # 三数和太小,left右移
        elif sum3 < target:
            left += 1
        # 三数和等于target,如果三个下标和比之前记录过的三数下标和更小
        # 则更新ans_idx
        else:
            if sum(ans_idx) > idx + nums[left][1] + nums[right][1]:
                ans_idx = [idx, nums[left][1], nums[right][1]]
            right -= 1
            left += 1

# 退出循环,ans_idx为在原数组中的三个数的下标
# 答案需要按照下标大小进行排列
ans_idx.sort()
ans = ",".join(str(lst[idx]) for idx in ans_idx)
print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取一行包含逗号分隔数字的数组
        String line = scanner.nextLine();

        // 使用 StringTokenizer 分割数字
        StringTokenizer tokenizer = new StringTokenizer(line, ",");
        List<Integer> lst = new ArrayList<>();
        while (tokenizer.hasMoreTokens()) {
            lst.add(Integer.parseInt(tokenizer.nextToken()));
        }

        // 读取下一行的数字
        int target = scanner.nextInt();

        // 获得原数组长度 n
        int n = lst.size();
        // 对原 nums 数组进行排序,同时需要记录在原数组中的下标 i,作为排序的第二个依据
        List<Pair> nums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nums.add(new Pair(lst.get(i), i));
        }
        Collections.sort(nums);

        // 初始化一个长度为 3 的数组,用于储存三个数的下标,初始化均为 n
        List<Integer> ansIdx = new ArrayList<>(Arrays.asList(n, n, n));

        // 考虑第一个数 first
        for (int i = 0; i < n - 2; i++) {
            // 如果发现第 i、第 i+1、第 i+2 个数的和加起来超过 target
            // 则更靠后的选择肯定和更大,直接退出循环
            if (nums.get(i).first + nums.get(i + 1).first + nums.get(i + 2).first > target) {
                break;
            }
            // 去重操作,如果遇到连续两个数相等,那么考虑 nums[i] 和考虑 nums[i-1] 所作的计算是一样的
            // 直接跳过 nums[i] 的计算
            if (i != 0 && nums.get(i).first == nums.get(i - 1).first) {
                continue;
            }
            // 构建相向双指针 left 和 right
            int left = i + 1, right = n - 1;
            while (left < right) {
                // 计算三个数的和
                int sum3 = nums.get(i).first + nums.get(left).first + nums.get(right).first;
                // 三数和太大,right 左移
                if (sum3 > target) {
                    right--;
                }
                // 三数和太小,left 右移
                else if (sum3 < target) {
                    left++;
                }
                // 三数和等于 target,如果三个下标和比之前记录过的三数下标和更小
                // 则更新 ansIdx
                else {
                    if (ansIdx.get(0) + ansIdx.get(1) + ansIdx.get(2) > nums.get(i).second + nums.get(left).second + nums.get(right).second) {
                        ansIdx = Arrays.asList(nums.get(i).second, nums.get(left).second, nums.get(right).second);
                    }
                    right--;
                    left++;
                }
            }
        }

        // 退出循环,ansIdx 为在原数组中的三个数的下标
        // 答案需要按照下标大小进行排列
        Collections.sort(ansIdx);
        for (int i = 0; i < 3; i++) {
            System.out.print(lst.get(ansIdx.get(i)));
            if (i < 2) {
                System.out.print(",");
            }
        }
        System.out.println();
    }

    static class Pair implements Comparable<Pair> {
        int first;
        int second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair other) {
            return Integer.compare(this.first, other.first);
        }
    }
}

C++

“`C++
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
// 读取一行包含逗号分隔数字的数组
string line;
getline(cin, line);

<pre><code>// 使用 stringstream 分割数字
stringstream ss(line);
vector<int> lst;
int num;
char comma;
while (ss >> num >> comma) {
lst.push_back(num);
}

// 读取下一行的数字
int target;
cin >> target;

// 获得原数组长度 n
int n = lst.size();
// 对原 nums 数组进行排序,同时需要记录在原数组中的下标 i,作为排序的第二个依据
vector<pair<int, int>> nums;
for (int i = 0; i < n; i++) {
nums.push_back({lst[i], i});
}
sort(nums.begin(), nums.end());

// 初始化一个长度为 3 的数组,用于储存三个数的下标,初始化均为 n
vector<int> ansIdx(3, n);

// 考虑第一个数 first
for (int i = 0; i < n – 2; i++) {
// 如果发现第 i、第 i+1、第 i+2 个数的和加起来超过 target
// 则更靠后的选择肯定和更大,直接退出循环
if (nums[i].first + nums[i + 1].first + nums[i + 2].first > target) {
break;
}
// 去重操作,如果遇到连续两个数相等,那么考虑 nums[i] 和考虑 nums[i-1] 所作的计算是一样的
// 直接跳过 nums[i] 的计算
if (i != 0 && nums[i].first == nums[i – 1].first) {
continue;
}
// 构建相向双指针 left 和 right
int left = i + 1, right = n – 1;
while (left < right) {
// 计算三个数的和
int sum3 = nums[i].first + nums[left].first + nums[right].first;
// 三数和太大,right 左移
if (sum3 > target) {
right–;
}
// 三数和太小,left 右移
else if (sum3 < target) {
left++;
}
// 三数和等于 target,如果三个下标和比之前记录过的三数下标和更小
// 则更新 ansIdx
else {
if (accumulate(ansIdx.begin(), ansIdx.end(), 0) > nums[i].second + nums[left].second + nums[right].second) {
ansIdx = {nums[i].second, nums[left].second, nums[right].second};
}
right–;
left++;
}
}
}

// 退出循环,ansIdx 为在原数组中的三个数的下标
// 答案需要按照下标大小进行排列
sort(ansIdx.begin(), ansIdx.end());
for (int i = 0; i < 3; i++) {
cout << lst[ansIdx[i]];
if (i < 2) {
cout << ",";
}
}
cout << endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度:O(``n^2``)。双重循环所需时间复杂度。

空间复杂度:O(``n``)。列表nums所占空间。

说明

华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。

机试分数越⾼评级越⾼,⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知

关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)