您现在的位置是：首页 >技术教程 >【2024年华为OD机试】(B卷,200分)- 跳房子II （JavaScript&Java & Python&C/C++）网站首页技术教程
【2024年华为OD机试】(B卷,200分)- 跳房子II （JavaScript&Java & Python&C/C++）
简介【2024年华为OD机试】(B卷,200分)- 跳房子II （JavaScript&Java & Python&C/C++）
一、问题描述
跳房子游戏步数组合问题
题目描述
跳房子是一种世界性的儿童游戏。游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后一格，然后获得一次选房子的机会，直到所有房子被选完，房子最多的人获胜。跳房子的过程中，如果有踩线等违规行为，会结束当前回合，甚至可能倒退几步。
假设房子的总格数是count，小红每回合可能连续跳的步数都放在数组steps中。请问数组中是否有一种步数的组合，可以让小红三个回合跳到最后一格？如果有，请输出索引和最小的步数组合（数据保证索引和最小的步数组合是唯一的）。
注意：数组中的步数可以重复，但数组中的元素不能重复使用。
输入描述
- 第一行输入为房子总格数
count，它是int整数类型。 - 第二行输入为每回合可能连续跳的步数，它是
int整数数组类型。
输出描述
返回索引和最小的满足要求的步数组合（顺序保持steps中原有顺序）。
备注
count ≤ 100003 ≤ steps.length ≤ 10000-100000 ≤ steps[i] ≤ 100000
用例
示例1
输入:
[1,4,5,2,0,2]
9
输出:
[4,5,0]
说明: 无
示例2
输入:
[1,5,2,0,2,4]
9
输出:
[5,2,2]
说明: 无
示例3
输入:
[-1,2,4,9]
12
输出:
[-1,4,9]
说明: 无
题目解析
本题是“三数之和”问题的变种。给定一个数组steps，需要从中找出三个数，保证这三个数的和等于count。本题的变化在于，可能存在多个三数组合满足要求，但我们只取其中三数的索引和最小的组合。
解题思路
-
数据结构转换：
- 首先根据输入的
steps数组，将其转化为newSteps数组，newSteps数组的元素是{val: steps[i], idx: i}。 - 然后将
newSteps数组按照元素的val值进行升序排序，若val值相同，则继续按照idx值升序排序。
- 首先根据输入的
-
三数之和逻辑：
- 定义一个双重循环，外层
for循环遍历newSteps每一个元素，指针为i。 - 定义两个指针
l = i + 1，r = newSteps.length - 1。 - 计算
valSum = newSteps[i].val + newSteps[l].val + newSteps[r].val。- 如果
valSum < count，则l++。 - 如果
valSum > count，则r--。 - 如果
valSum == count，则i、l、r指向的三数组合符合要求，计算三数的索引之和idxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx。- 如果
idxSum < minIdxSum，则更新minIdxSum = idxSum，并继续尝试更优解（r--）。 - 如果
idxSum > minIdxSum，则丢弃。 - 如果
idxSum == minIdxSum，则不存在此场景（题目保证索引和最小的步数组合是唯一的）。
- 如果
- 如果
- 定义一个双重循环，外层
-
剪枝优化：
- 剪枝1：如果
steps[i] > count且steps[i] > 0、count > 0，则steps[i] + steps[l] + steps[r] > count是必然的，可以break掉i的遍历。 - 剪枝2：避免统计重复组合。
- R指针去重：如果
steps[r] == steps[r-1]，则左移R指针。 - L指针去重：如果
steps[l] == steps[l+1]，则右移L指针。 - i指针去重：如果
steps[i] == steps[i-1]，则直接continue。
- R指针去重：如果
- 剪枝1：如果
-
进一步剪枝：
- 确定
i指针后，L、R指针指向数的目标和已经确定为count - steps[i]。 - 由于
steps[L] <= steps[R]，因此必然存在：steps[L] <= (count - steps[i]) / 2steps[R] >= (count - steps[i]) / 2
- 如果初始时
steps[L]、steps[R]不满足上述关系，则可以剪枝。
- 确定
总结
本题通过将问题转化为“三数之和”问题，并结合剪枝优化策略，能够有效地找到索引和最小的步数组合。通过合理的剪枝和去重策略，可以在大规模数据下避免超时问题。
二、JavaScript算法源码
代码整体结构
代码分为几个部分：
- 读取输入：使用
readline模块从标准输入读取数据。 - 数据处理：将读取的数据进行处理，转换为适合后续计算的格式。
- 逻辑运算：执行特定的逻辑运算来找到满足条件的结果。
- 输出结果：将计算结果输出到标准输出。
详细讲解
读取输入
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length == 2) {
const steps = lines[0].slice(1, -1).split(",").map(Number); // 去掉首尾字符，分割并转换为数字
const count = parseInt(lines[1]); // 将第二行转换为整数
console.log(getResult(steps, count)); // 调用函数处理数据并输出结果
lines.length = 0; // 清空数组，准备接收下一组数据
}
});
- 使用
readline模块创建接口，监听标准输入。 - 每读取一行数据，将其存入
lines数组。 - 当读取到两行数据时，处理这两行数据：第一行是步骤数组（去掉首尾的方括号，分割成字符串数组，再转换为数字数组），第二行是一个整数。
- 调用
getResult函数处理这些数据，并输出结果。 - 清空
lines数组，为下一组数据做准备。
逻辑运算
function getResult(steps, count) {
const n = steps.length;
// 将步骤数组转换为包含值和索引的对象数组
const newSteps = [];
for (let i = 0; i < n; i++) {
newSteps.push(new Step(steps[i], i));
}
// 按值和索引排序
newSteps.sort((a, b) => (a.val != b.val ? a.val - b.val : a.idx - b.idx));
let minStepIdxSum = Infinity;
let ans = "";
// 遍历步骤数组，尝试找到满足条件的三元组
for (let i = 0; i < n; i++) {
// 剪枝优化：如果当前值大于0且剩余步数大于0但当前值大于剩余步数，则不可能找到满足条件的三元组
if (newSteps[i].val > 0 && count > 0 && newSteps[i].val > count) {
break;
}
// 剪枝优化：如果当前值与上一个值相同，则跳过，避免重复计算
if (i > 0 && newSteps[i].val == newSteps[i - 1].val) {
continue;
}
let l = i + 1;
let r = n - 1;
while (l < r) {
// 剪枝优化：根据中间值计算阈值，如果L或R指针指向的值超出阈值范围，则不可能找到满足条件的三元组
const threshold = (count - newSteps[i].val) / 2;
if (newSteps[l].val > threshold || newSteps[r].val < threshold) break;
const stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val;
if (stepValSum < count) {
l++;
} else if (stepValSum > count) {
r--;
} else {
// 剪枝优化：跳过重复值
while (l < r - 1 && newSteps[r].val == newSteps[r - 1].val) {
r--;
}
// 计算索引和，更新最小索引和及对应的三元组值
const stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx;
if (stepIdxSum < minStepIdxSum) {
minStepIdxSum = stepIdxSum;
const arr = [newSteps[i], newSteps[l], newSteps[r]];
arr.sort((a, b) => a.idx - b.idx);
ans = `[${arr.map((step) => step.val).join(",")}]`;
}
// 剪枝优化：跳过重复值
while (l + 1 < r && newSteps[l].val == newSteps[l + 1].val) {
l++;
}
l++;
r--;
}
}
}
return ans;
}
- 将步骤数组转换为包含值和索引的对象数组，并按值和索引排序。
- 遍历排序后的步骤数组，尝试找到三个步骤，它们的值之和等于给定的
count。 - 使用双指针方法，在遍历过程中应用多个剪枝优化来减少不必要的计算。
- 当找到满足条件的三元组时，计算其索引和，如果这是目前找到的最小索引和，则更新结果。
- 返回结果字符串，格式为
[值1,值2,值3]，表示满足条件且索引和最小的三个步骤的值。
Step类
class Step {
constructor(val, idx) {
this.val = val;
this.idx = idx;
}
}
Step类用于存储步骤的值和索引。- 在处理步骤数组时，将每个步骤转换为一个
Step对象，方便后续按值和索引排序及计算。
总结
这段代码实现了一个特定的逻辑运算，用于从输入数据中找出满足特定条件（值之和等于给定数，且索引和最小）的三个步骤。通过排序和双指针方法，结合多个剪枝优化，提高了算法的效率。
三、Java算法源码
该代码的主要功能是处理一个由整数构成的数组（代表步数），并找到三个数，它们的和等于给定的目标数count，同时这三个数的索引之和最小。如果找到多个满足条件的组合，则选择索引之和最小的那个，并且输出这三个数的升序排列。
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;
public class Main {
// 定义一个内部类Step，用于存储步数和对应的索引
static class Step {
int val; // 步数
int idx; // 索引
public Step(int val, int idx) {
this.idx = idx; // 初始化索引
this.val = val; // 初始化步数
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入的第一行，即步数数组，去掉首尾的方括号，并按逗号分割成字符串数组
String tmp = sc.nextLine();
int[] steps =
Arrays.stream(tmp.substring(1, tmp.length() - 1).split(","))
.mapToInt(Integer::parseInt)
.toArray();
// 读取第二行，即目标和count
int count = Integer.parseInt(sc.nextLine());
// 输出结果
System.out.println(getResult(steps, count));
}
// 查找三个数的和等于count，且索引之和最小的组合
public static String getResult(int[] steps, int count) {
int n = steps.length; // 获取步数数组的长度
// 将步数数组转换为Step数组，同时记录每个步数的索引
Step[] newSteps = new Step[n];
for (int i = 0; i < n; i++) {
newSteps[i] = new Step(steps[i], i);
}
// 按步数值升序排序，如果步数值相同，则按索引升序排序
Arrays.sort(newSteps, (a, b) -> a.val != b.val ? a.val - b.val : a.idx - b.idx);
int minStepIdxSum = Integer.MAX_VALUE; // 初始化索引之和的最小值为最大整数
String ans = ""; // 初始化结果字符串为空
// 遍历数组，尝试找到三个数的组合
for (int i = 0; i < n; i++) {
// 如果当前步数值大于count且count大于0，则无需继续查找，因为后面的值都会更大
if (newSteps[i].val > count && newSteps[i].val > 0 && count > 0) break;
// 如果当前步数值与前一个相同，则跳过，避免重复计算
if (i > 0 && newSteps[i].val == newSteps[i - 1].val) continue;
int l = i + 1; // 左指针，从当前元素的下一个元素开始
int r = n - 1; // 右指针，指向数组的最后一个元素
// 使用双指针法查找另外两个数
while (l < r) {
// 计算目标和的一半，用于剪枝优化
int threshold = (count - newSteps[i].val) / 2;
// 如果左指针指向的值大于阈值或右指针指向的值小于阈值，则无需继续查找
if (newSteps[l].val > threshold || newSteps[r].val < threshold) break;
int stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val; // 计算三个数的和
if (stepValSum < count) {
l++; // 和小于目标和，移动左指针
} else if (stepValSum > count) {
r--; // 和大于目标和，移动右指针
} else {
// 找到满足条件的组合，进一步处理
// 跳过右指针指向的重复值，避免重复计算
while (l < r - 1 && newSteps[r].val == newSteps[r - 1].val) {
r--;
}
// 计算当前组合的索引之和
int stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx;
// 如果当前组合的索引之和更小，则更新最小索引之和和结果字符串
if (stepIdxSum < minStepIdxSum) {
minStepIdxSum = stepIdxSum;
// 将满足条件的三个Step对象放入数组，并按索引升序排序
Step[] arr = {newSteps[i], newSteps[l], newSteps[r]};
Arrays.sort(arr, (a, b) -> a.idx - b.idx);
// 使用StringJoiner将结果转换为字符串格式
StringJoiner sj = new StringJoiner(",", "[", "]");
for (Step step : arr) sj.add(step.val + "");
ans = sj.toString(); // 更新结果字符串
}
// 跳过左指针指向的重复值，避免重复计算
while (l + 1 < r && newSteps[l].val == newSteps[l + 1].val) {
l++;
}
// 移动指针，继续查找其他可能的组合
l++;
r--;
}
}
}
return ans; // 返回结果字符串
}
}
这段代码通过双指针法和一些剪枝优化来高效地查找满足条件的三个数的组合。它首先将所有步数及其索引存储在Step数组中，并对该数组进行排序。然后，它遍历排序后的数组，并使用双指针法查找另外两个数，使得三个数的和等于给定的目标数count。在查找过程中，它还会检查索引之和，并更新最小索引之和和结果字符串。
四、Python算法源码
这段代码的主要功能是从一个整数列表 steps 中找到三个数，使得它们的和等于给定的目标值 count，并且这三个数的索引之和最小。如果存在多个满足条件的三元组，则选择索引之和最小的那个，并返回该三元组的值。
代码详细注释与讲解
import sys
# 输入获取
steps = list(map(int, input()[1:-1].split(","))) # 从输入中获取整数列表，去掉首尾的方括号并按逗号分割
count = int(input()) # 获取目标值 count
class Step:
def __init__(self, val, idx):
self.val = val # 存储整数值
self.idx = idx # 存储该整数的索引
# 算法入口
def getResult():
n = len(steps) # 获取 steps 列表的长度
# 将 steps 列表中的每个元素转换为 Step 对象，方便后续操作
newSteps = [Step(steps[i], i) for i in range(n)]
# 对 newSteps 列表进行排序，首先按 val 升序，其次按 idx 升序
newSteps.sort(key=lambda x: (x.val, x.idx))
minStepIdxSum = sys.maxsize # 初始化最小索引和为系统最大整数值
ans = "" # 初始化结果字符串
# 遍历 newSteps 列表，寻找满足条件的三元组
for i in range(n):
# 剪枝优化：如果当前值大于 0 且目标值小于当前值，则后续的值都会更大，直接跳出循环
if newSteps[i].val > 0 and 0 < count < newSteps[i].val:
break
# 剪枝优化：如果当前值与上一个值相同，则跳过，避免重复计算
if i > 0 and newSteps[i].val == newSteps[i - 1].val:
continue
l = i + 1 # 左指针，指向当前元素的下一个元素
r = n - 1 # 右指针，指向列表的最后一个元素
# 使用双指针法在剩余的元素中寻找满足条件的三元组
while l < r:
# 剪枝优化：L 和 R 指针指向的值的和应该等于 count - newSteps[i].val
# 因此 L 指针指向的值应该小于等于 (count - newSteps[i].val) / 2
# R 指针指向的值应该大于等于 (count - newSteps[i].val) / 2
threshold = (count - newSteps[i].val) / 2
if newSteps[l].val > threshold or newSteps[r].val < threshold:
break
# 计算当前三元组的和
stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val
# 根据和的大小调整指针
if stepValSum < count:
l += 1 # 和小于目标值，左指针右移
elif stepValSum > count:
r -= 1 # 和大于目标值，右指针左移
else:
# 剪枝优化：如果右指针指向的值与下一个值相同，则右指针左移，避免重复计算
while l < r - 1 and newSteps[r].val == newSteps[r - 1].val:
r -= 1
# 计算当前三元组的索引和
stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx
# 如果当前三元组的索引和小于最小索引和，则更新最小索引和和结果字符串
if stepIdxSum < minStepIdxSum:
minStepIdxSum = stepIdxSum
# 将三元组按索引排序
arr = [newSteps[i], newSteps[l], newSteps[r]]
arr.sort(key=lambda x: x.idx)
# 生成结果字符串
ans = "[" + ",".join(map(lambda x: str(x.val), arr)) + "]"
# 剪枝优化：如果左指针指向的值与下一个值相同，则左指针右移，避免重复计算
while l + 1 < r and newSteps[l].val == newSteps[l + 1].val:
l += 1
# 移动指针，继续寻找下一个可能的三元组
l += 1
r -= 1
return ans # 返回结果字符串
# 算法调用
print(getResult())
代码逻辑讲解
-
输入处理：
- 从输入中获取整数列表
steps和目标值count。 - 将
steps列表中的每个元素转换为Step对象，方便后续操作。
- 从输入中获取整数列表
-
排序：
- 对
newSteps列表进行排序，首先按val升序，其次按idx升序。这样做的目的是为了后续的双指针法能够高效地找到满足条件的三元组。
- 对
-
剪枝优化：
- 在遍历
newSteps列表时，如果当前值大于 0 且目标值小于当前值，则后续的值都会更大，直接跳出循环。 - 如果当前值与上一个值相同，则跳过，避免重复计算。
- 在遍历
-
双指针法：
- 使用双指针法在剩余的元素中寻找满足条件的三元组。左指针
l指向当前元素的下一个元素，右指针r指向列表的最后一个元素。 - 根据当前三元组的和与目标值的大小关系，调整指针的位置。
- 使用双指针法在剩余的元素中寻找满足条件的三元组。左指针
-
结果更新：
- 如果找到满足条件的三元组，则计算其索引和，并与当前最小索引和进行比较。如果更小，则更新最小索引和和结果字符串。
-
返回结果：
- 最终返回结果字符串，表示满足条件的三元组。
总结
这段代码通过排序和双指针法，高效地找到了满足条件的三元组，并且通过剪枝优化减少了不必要的计算。最终返回的结果是索引和最小的三元组。
五、C/C++算法源码：
以下是 C语言代码 和 C++代码 的实现，并附带详细的中文注释和讲解。
C语言代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 10000
// 定义结构体 Step，用于存储值和索引
typedef struct {
int val; // 存储整数值
int idx; // 存储该整数的索引
} Step;
// 函数声明
void getResult(const int steps[], int steps_size, int count);
// 主函数
int main() {
int steps[MAX_SIZE];
int steps_size = 0;
// 从输入中读取 steps 数组
while (scanf("[%d", &steps[steps_size]) || scanf("%d", &steps[steps_size])) {
steps_size++;
if (getchar() != ',') break; // 如果下一个字符不是逗号，则结束输入
}
int count;
scanf("%d", &count); // 读取目标值 count
getResult(steps, steps_size, count); // 调用算法函数
return 0;
}
// 比较函数，用于排序 Step 结构体数组
int cmp(const void* a, const void* b) {
Step* A = (Step*)a;
Step* B = (Step*)b;
// 先按 val 升序，再按 idx 升序
return A->val != B->val ? A->val - B->val : A->idx - B->idx;
}
// 比较函数，用于按索引排序 Step 结构体数组
int cmp2(const void* a, const void* b) {
Step* A = (Step*)a;
Step* B = (Step*)b;
return A->idx - B->idx; // 按 idx 升序
}
// 算法函数
void getResult(const int steps[], int steps_size, int count) {
Step newSteps[steps_size];
// 将 steps 数组转换为 Step 结构体数组
for (int i = 0; i < steps_size; i++) {
newSteps[i].val = steps[i];
newSteps[i].idx = i;
}
// 对 newSteps 数组按 val 和 idx 排序
qsort(newSteps, steps_size, sizeof(Step), cmp);
int minStepIdxSum = INT_MAX; // 初始化最小索引和为最大整数值
char ans[100000] = ""; // 初始化结果字符串
// 遍历 newSteps 数组，寻找满足条件的三元组
for (int i = 0; i < steps_size; i++) {
// 剪枝优化：如果当前值大于 count 且 count > 0，则后续值更大，直接跳出循环
if (newSteps[i].val > count && count > 0) break;
// 剪枝优化：如果当前值与上一个值相同，则跳过，避免重复计算
if (i > 0 && newSteps[i].val == newSteps[i - 1].val) continue;
int l = i + 1; // 左指针
int r = steps_size - 1; // 右指针
// 双指针法寻找满足条件的三元组
while (l < r) {
// 剪枝优化：L 和 R 指针指向的值的和应该等于 count - newSteps[i].val
int threshold = (count - newSteps[i].val) / 2;
if (newSteps[l].val > threshold || newSteps[r].val < threshold) break;
int stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val;
if (stepValSum < count) {
l++; // 和小于目标值，左指针右移
} else if (stepValSum > count) {
r--; // 和大于目标值，右指针左移
} else {
// 剪枝优化：如果右指针指向的值与下一个值相同，则右指针左移，避免重复计算
while (l < r - 1 && newSteps[r].val == newSteps[r - 1].val) {
r--;
}
// 计算当前三元组的索引和
int stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx;
// 如果当前三元组的索引和小于最小索引和，则更新最小索引和和结果字符串
if (stepIdxSum < minStepIdxSum) {
minStepIdxSum = stepIdxSum;
Step arr[] = {newSteps[i], newSteps[l], newSteps[r]};
qsort(arr, 3, sizeof(Step), cmp2); // 按索引排序
char res[100000] = {' '};
res[0] = '[';
// 生成结果字符串
for (int j = 0; j < 3; j++) {
Step step = arr[j];
char tmp[1000];
sprintf(tmp, "%d", step.val);
strcat(res, tmp);
if (j < 2) {
strcat(res, ",");
} else {
strcat(res, "]");
}
}
strcpy(ans, res); // 更新结果字符串
}
// 剪枝优化：如果左指针指向的值与下一个值相同，则左指针右移，避免重复计算
while (l + 1 < r && newSteps[l].val == newSteps[l + 1].val) {
l++;
}
l++;
r--;
}
}
}
puts(ans); // 输出结果
}
C++代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 定义结构体 Step，用于存储值和索引
struct Step {
int val; // 存储整数值
int idx; // 存储该整数的索引
};
// 比较函数，用于排序 Step 结构体数组
bool cmp(const Step& a, const Step& b) {
return a.val != b.val ? a.val < b.val : a.idx < b.idx;
}
// 比较函数，用于按索引排序 Step 结构体数组
bool cmp2(const Step& a, const Step& b) {
return a.idx < b.idx;
}
// 算法函数
void getResult(const vector<int>& steps, int count) {
int steps_size = steps.size();
vector<Step> newSteps(steps_size);
// 将 steps 数组转换为 Step 结构体数组
for (int i = 0; i < steps_size; i++) {
newSteps[i].val = steps[i];
newSteps[i].idx = i;
}
// 对 newSteps 数组按 val 和 idx 排序
sort(newSteps.begin(), newSteps.end(), cmp);
int minStepIdxSum = INT_MAX; // 初始化最小索引和为最大整数值
string ans = ""; // 初始化结果字符串
// 遍历 newSteps 数组，寻找满足条件的三元组
for (int i = 0; i < steps_size; i++) {
// 剪枝优化：如果当前值大于 count 且 count > 0，则后续值更大，直接跳出循环
if (newSteps[i].val > count && count > 0) break;
// 剪枝优化：如果当前值与上一个值相同，则跳过，避免重复计算
if (i > 0 && newSteps[i].val == newSteps[i - 1].val) continue;
int l = i + 1; // 左指针
int r = steps_size - 1; // 右指针
// 双指针法寻找满足条件的三元组
while (l < r) {
// 剪枝优化：L 和 R 指针指向的值的和应该等于 count - newSteps[i].val
int threshold = (count - newSteps[i].val) / 2;
if (newSteps[l].val > threshold || newSteps[r].val < threshold) break;
int stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val;
if (stepValSum < count) {
l++; // 和小于目标值，左指针右移
} else if (stepValSum > count) {
r--; // 和大于目标值，右指针左移
} else {
// 剪枝优化：如果右指针指向的值与下一个值相同，则右指针左移，避免重复计算
while (l < r - 1 && newSteps[r].val == newSteps[r - 1].val) {
r--;
}
// 计算当前三元组的索引和
int stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx;
// 如果当前三元组的索引和小于最小索引和，则更新最小索引和和结果字符串
if (stepIdxSum < minStepIdxSum) {
minStepIdxSum = stepIdxSum;
vector<Step> arr = {newSteps[i], newSteps[l], newSteps[r]};
sort(arr.begin(), arr.end(), cmp2); // 按索引排序
string res = "[";
for (int j = 0; j < 3; j++) {
res += to_string(arr[j].val);
if (j < 2) res += ",";
}
res += "]";
ans = res; // 更新结果字符串
}
// 剪枝优化：如果左指针指向的值与下一个值相同，则左指针右移，避免重复计算
while (l + 1 < r && newSteps[l].val == newSteps[l + 1].val) {
l++;
}
l++;
r--;
}
}
}
cout << ans << endl; // 输出结果
}
// 主函数
int main() {
vector<int> steps;
char c;
int num;
// 从输入中读取 steps 数组
while (cin >> c >> num) {
steps.push_back(num);
if (c == ']') break;
}
int count;
cin >> count; // 读取目标值 count
getResult(steps, count); // 调用算法函数
return 0;
}
代码讲解
核心逻辑
-
输入处理：
- 从输入中读取整数数组
steps和目标值count。 - 将
steps数组转换为Step结构体数组，方便后续操作。
- 从输入中读取整数数组
-
排序：
- 对
Step结构体数组按val和idx进行排序，以便使用双指针法高效查找。
- 对
-
双指针法：
- 使用双指针法在剩余的元素中寻找满足条件的三元组。
- 根据当前三元组的和与目标值的大小关系，调整指针的位置。
-
剪枝优化：
- 通过跳过重复值和提前终止循环，减少不必要的计算。
-
结果更新：
- 如果找到满足条件的三元组，则计算其索引和，并与当前最小索引和进行比较。如果更小，则更新最小索引和和结果字符串。
-
输出结果：
- 最终输出满足条件的三元组。
C语言与C++的区别
- 输入输出：
- C语言使用
scanf和printf，C++ 使用cin和cout。
- C语言使用
- 数据结构：
- C语言使用数组和指针，C++ 使用
vector和string。
- C语言使用数组和指针，C++ 使用
- 排序：
- C语言使用
qsort，C++ 使用sort。
- C语言使用
六、尾言
什么是华为OD？
华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。
为什么刷题很重要？
-
机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。 -
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。 -
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。
刷题策略与说明：
2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：
-
关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
-
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
-
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
-
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。
如何获取资源？
-
官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
-
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
-
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。
积极心态与持续努力：
刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。
考试注意细节
-
本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
-
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
-
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
-
快捷键使用
- 删除行可用
Ctrl+D，复制、粘贴和撤销分别为Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。 - 避免使用
Ctrl+S，以免触发浏览器的保存功能。
- 删除行可用
-
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
-
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
-
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
-
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
-
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。
祝你考试顺利，取得理想成绩！
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效) - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。... - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权