小朋友出操,按学号从小到大排成一列;
小明来迟了,请你给小明出个主意,让他尽快找到他应该排的位置。
算法复杂度要求不高于nLog(n);学号为整数类型,队列规模 ≤ 10000;
第一行:输入已排成队列的小朋友的学号(正整数),以","隔开;例如:
93,95,97,100,102,123,155
第二行:小明学号,如:
110
输出一个数字,代表队列位置(从1开始)。例如:
6
输入
93,95,97,100,102,123,155
110
输出
6
考察二分查找算法。
left
指针的位置即为目标值的插入位置。以下是 JavaScript 代码的详细中文注释和讲解:
// 引入 readline 模块,用于从控制台读取输入
const rl = require("readline").createInterface({ input: process.stdin });
// 获取异步迭代器
var iter = rl[Symbol.asyncIterator]();
// 定义异步函数 readline,用于读取一行输入
const readline = async () => (await iter.next()).value;
// 立即执行异步函数
void (async function () {
// 读取第一行输入,按逗号分割并转换为数字数组
const nums = (await readline()).split(",").map(Number);
// 读取第二行输入,转换为目标值
const target = parseInt(await readline());
// 调用二分查找函数,查找目标值的位置
let idx = binarySearch(nums, target);
// 如果目标值不存在,计算其有序插入位置
if (idx < 0) {
idx = -idx - 1;
}
// 输出队列位置(从1开始),因此索引+1
console.log(idx + 1);
})();
// 二分查找函数,参照 Java 的 Arrays.binarySearch 实现
function binarySearch(nums, target) {
let low = 0; // 查找范围的左边界
let high = nums.length - 1; // 查找范围的右边界
// 当左边界小于等于右边界时,继续查找
while (low <= high) {
// 计算中间位置
const mid = (low + high) >> 1; // 等价于 Math.floor((low + high) / 2)
const midVal = nums[mid]; // 中间位置的值
// 如果中间值大于目标值,缩小查找范围到左半部分
if (midVal > target) {
high = mid - 1;
}
// 如果中间值小于目标值,缩小查找范围到右半部分
else if (midVal < target) {
low = mid + 1;
}
// 如果中间值等于目标值,返回目标值的位置
else {
return mid;
}
}
// 如果目标值不存在,返回其有序插入位置的负数形式
return -low - 1;
}
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
readline
模块从控制台读取输入。rl[Symbol.asyncIterator]()
获取异步迭代器。readline
函数每次调用会返回一行输入。void (async function () {
// 读取第一行输入,按逗号分割并转换为数字数组
const nums = (await readline()).split(",").map(Number);
// 读取第二行输入,转换为目标值
const target = parseInt(await readline());
// 调用二分查找函数,查找目标值的位置
let idx = binarySearch(nums, target);
// 如果目标值不存在,计算其有序插入位置
if (idx < 0) {
idx = -idx - 1;
}
// 输出队列位置(从1开始),因此索引+1
console.log(idx + 1);
})();
split(",")
按逗号分割字符串。map(Number)
将字符串数组转换为数字数组。parseInt
将目标值转换为整数。function binarySearch(nums, target) {
let low = 0; // 查找范围的左边界
let high = nums.length - 1; // 查找范围的右边界
// 当左边界小于等于右边界时,继续查找
while (low <= high) {
// 计算中间位置
const mid = (low + high) >> 1; // 等价于 Math.floor((low + high) / 2)
const midVal = nums[mid]; // 中间位置的值
// 如果中间值大于目标值,缩小查找范围到左半部分
if (midVal > target) {
high = mid - 1;
}
// 如果中间值小于目标值,缩小查找范围到右半部分
else if (midVal < target) {
low = mid + 1;
}
// 如果中间值等于目标值,返回目标值的位置
else {
return mid;
}
}
// 如果目标值不存在,返回其有序插入位置的负数形式
return -low - 1;
}
nums
中查找目标值 target
。low
和 high
分别表示查找范围的左右边界。mid
是中间位置的索引。>> 1
是位运算,等价于除以 2 并向下取整。low
是其有序插入位置。输入:
1,3,5,7,9
5
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 5
的索引为 2
。3
。输入:
1,3,5,7,9
4
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 4
不存在。2
(插入后数组为 [1, 3, 4, 5, 7, 9]
)。3
。功能:
优点:
O(log n)
,效率高。适用场景:
如果您有其他问题,欢迎随时提问!
以下是 Java 代码的详细中文注释和讲解:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建 Scanner 对象,用于从控制台读取输入
Scanner sc = new Scanner(System.in);
// 读取第一行输入,按逗号分割并转换为整数数组
int[] nums = Arrays.stream(sc.nextLine().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// 读取第二行输入,转换为目标值
int target = Integer.parseInt(sc.nextLine());
// 使用 Arrays.binarySearch 查找目标值的位置
// 如果目标值不存在,返回其有序插入位置的负数形式
int idx = Arrays.binarySearch(nums, target);
// 如果目标值不存在,计算其有序插入位置
if (idx < 0) {
idx = -idx - 1;
}
// 输出队列位置(从1开始),因此索引+1
System.out.println(idx + 1);
}
}
Scanner sc = new Scanner(System.in);
Scanner
对象,用于从控制台读取输入。Scanner
是 Java 中常用的输入工具类。int[] nums = Arrays.stream(sc.nextLine().split(","))
.mapToInt(Integer::parseInt)
.toArray();
sc.nextLine()
读取一行输入。split(",")
按逗号分割字符串。Arrays.stream()
将字符串数组转换为流。mapToInt(Integer::parseInt)
将字符串流转换为整数流。toArray()
将流转换为整数数组。int target = Integer.parseInt(sc.nextLine());
sc.nextLine()
读取一行输入。Integer.parseInt()
将字符串转换为整数。int idx = Arrays.binarySearch(nums, target);
Arrays.binarySearch
在有序数组 nums
中查找目标值 target
。-low - 1
)。if (idx < 0) {
idx = -idx - 1;
}
Arrays.binarySearch
返回负数时,表示目标值不存在。-idx - 1
是目标值的有序插入位置。System.out.println(idx + 1);
idx + 1
将索引转换为队列位置。输入:
1,3,5,7,9
5
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 5
的索引为 2
。3
。输入:
1,3,5,7,9
4
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 4
不存在。2
(插入后数组为 [1, 3, 4, 5, 7, 9]
)。3
。功能:
优点:
Arrays.binarySearch
,时间复杂度为 O(log n)
,效率高。适用场景:
如果您有其他问题,欢迎随时提问!
以下是 Python 代码的详细中文注释和讲解:
# 输入获取
nums = list(map(int, input().split(","))) # 读取输入并转换为整数列表
target = int(input()) # 读取目标值
# 算法入口
def binarySearch():
# 参照 Java 的 Arrays.binarySearch 实现
low = 0 # 查找范围的左边界
high = len(nums) - 1 # 查找范围的右边界
while low <= high:
mid = (low + high) >> 1 # 计算中间位置,等价于 (low + high) // 2
midVal = nums[mid] # 中间位置的值
if midVal > target:
high = mid - 1 # 如果中间值大于目标值,缩小查找范围到左半部分
elif midVal < target:
low = mid + 1 # 如果中间值小于目标值,缩小查找范围到右半部分
else:
return mid # 如果中间值等于目标值,返回目标值的位置
return -low - 1 # 如果目标值不存在,返回其有序插入位置的负数形式
# 算法调用
idx = binarySearch()
# 如果目标值不存在,计算其有序插入位置
if idx < 0:
idx = -idx - 1
# 输出队列位置(从1开始),因此索引+1
print(idx + 1)
nums = list(map(int, input().split(","))) # 读取输入并转换为整数列表
target = int(input()) # 读取目标值
input()
读取一行输入。split(",")
按逗号分割字符串。map(int, ...)
将字符串列表转换为整数列表。list(...)
将映射结果转换为列表。def binarySearch():
low = 0 # 查找范围的左边界
high = len(nums) - 1 # 查找范围的右边界
while low <= high:
mid = (low + high) >> 1 # 计算中间位置,等价于 (low + high) // 2
midVal = nums[mid] # 中间位置的值
if midVal > target:
high = mid - 1 # 如果中间值大于目标值,缩小查找范围到左半部分
elif midVal < target:
low = mid + 1 # 如果中间值小于目标值,缩小查找范围到右半部分
else:
return mid # 如果中间值等于目标值,返回目标值的位置
return -low - 1 # 如果目标值不存在,返回其有序插入位置的负数形式
nums
中查找目标值 target
。low
和 high
分别表示查找范围的左右边界。mid
是中间位置的索引。>> 1
是位运算,等价于除以 2 并向下取整。low
是其有序插入位置。idx = binarySearch()
if idx < 0:
idx = -idx - 1
binarySearch
返回负数时,表示目标值不存在。-idx - 1
是目标值的有序插入位置。print(idx + 1)
idx + 1
将索引转换为队列位置。输入:
1,3,5,7,9
5
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 5
的索引为 2
。3
。输入:
1,3,5,7,9
4
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 4
不存在。2
(插入后数组为 [1, 3, 4, 5, 7, 9]
)。3
。功能:
优点:
O(log n)
,效率高。适用场景:
如果您有其他问题,欢迎随时提问!
以下是 C语言 和 C++ 代码的详细中文注释和讲解:
#include <stdio.h>
#define MAX_SIZE 10000 // 定义数组的最大长度
// 二分查找函数,参照 Java 的 Arrays.binarySearch 实现
int binarySearch(const int *nums, int nums_size, int target) {
int low = 0; // 查找范围的左边界
int high = nums_size - 1; // 查找范围的右边界
while (low <= high) {
int mid = (low + high) >> 1; // 计算中间位置,等价于 (low + high) / 2
int midVal = nums[mid]; // 中间位置的值
if (midVal > target) {
high = mid - 1; // 如果中间值大于目标值,缩小查找范围到左半部分
} else if (midVal < target) {
low = mid + 1; // 如果中间值小于目标值,缩小查找范围到右半部分
} else {
return mid; // 如果中间值等于目标值,返回目标值的位置
}
}
return -low - 1; // 如果目标值不存在,返回其有序插入位置的负数形式
}
int main() {
int nums[MAX_SIZE]; // 定义数组
int nums_size = 0; // 数组的当前长度
// 读取输入,按逗号分割并存储到数组中
while (scanf("%d", &nums[nums_size++])) {
if (getchar() != ',') break; // 如果下一个字符不是逗号,结束输入
}
int target; // 定义目标值
scanf("%d", &target); // 读取目标值
// 调用二分查找函数,查找目标值的位置
int idx = binarySearch(nums, nums_size, target);
// 如果目标值不存在,计算其有序插入位置
if (idx < 0) {
idx = -idx - 1;
}
// 输出队列位置(从1开始),因此索引+1
printf("%d\n", idx + 1);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
// 二分查找函数,参照 Java 的 Arrays.binarySearch 实现
int binarySearch(const vector<int>& nums, int target) {
int low = 0; // 查找范围的左边界
int high = nums.size() - 1; // 查找范围的右边界
while (low <= high) {
int mid = (low + high) >> 1; // 计算中间位置,等价于 (low + high) / 2
int midVal = nums[mid]; // 中间位置的值
if (midVal > target) {
high = mid - 1; // 如果中间值大于目标值,缩小查找范围到左半部分
} else if (midVal < target) {
low = mid + 1; // 如果中间值小于目标值,缩小查找范围到右半部分
} else {
return mid; // 如果中间值等于目标值,返回目标值的位置
}
}
return -low - 1; // 如果目标值不存在,返回其有序插入位置的负数形式
}
int main() {
vector<int> nums; // 定义动态数组
int num;
char sep;
// 读取输入,按逗号分割并存储到数组中
while (cin >> num) {
nums.push_back(num);
sep = cin.get(); // 读取分隔符
if (sep != ',') break; // 如果下一个字符不是逗号,结束输入
}
int target; // 定义目标值
cin >> target; // 读取目标值
// 调用二分查找函数,查找目标值的位置
int idx = binarySearch(nums, target);
// 如果目标值不存在,计算其有序插入位置
if (idx < 0) {
idx = -idx - 1;
}
// 输出队列位置(从1开始),因此索引+1
cout << idx + 1 << endl;
return 0;
}
C语言:
while (scanf("%d", &nums[nums_size++])) {
if (getchar() != ',') break;
}
scanf
读取整数,getchar
读取分隔符。C++:
while (cin >> num) {
nums.push_back(num);
sep = cin.get();
if (sep != ',') break;
}
cin
读取整数,cin.get
读取分隔符。int binarySearch(const int *nums, int nums_size, int target) {
int low = 0;
int high = nums_size - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = nums[mid];
if (midVal > target) {
high = mid - 1;
} else if (midVal < target) {
low = mid + 1;
} else {
return mid;
}
}
return -low - 1;
}
nums
中查找目标值 target
。low
和 high
分别表示查找范围的左右边界。mid
是中间位置的索引。>> 1
是位运算,等价于除以 2 并向下取整。low
是其有序插入位置。if (idx < 0) {
idx = -idx - 1;
}
binarySearch
返回负数时,表示目标值不存在。-idx - 1
是目标值的有序插入位置。printf("%d\n", idx + 1);
idx + 1
将索引转换为队列位置。输入:
1,3,5,7,9
5
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 5
的索引为 2
。3
。输入:
1,3,5,7,9
4
输出:
3
解释:
[1, 3, 5, 7, 9]
中,目标值 4
不存在。2
(插入后数组为 [1, 3, 4, 5, 7, 9]
)。3
。功能:
优点:
O(log n)
,效率高。适用场景:
如果您有其他问题,欢迎随时提问!
华为OD(Outsourcing Developer,外包开发工程师)是华为针对软件开发工程师岗位的一种招聘形式,主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分,算法题的机试至关重要。
机试是进入技术面的第一关:
华为OD机试(常被称为机考)主要考察算法和编程能力。只有通过机试,才能进入后续的技术面试环节。
技术面试需要手撕代码:
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。
入职后的可信考试:
入职华为后,还需要通过“可信考试”。可信考试分为三个等级:
2024年8月14日之后,华为OD机试的题库转为 E卷,由往年题库(D卷、A卷、B卷、C卷)和全新题目组成。刷题时可以参考以下策略:
关注历年真题:
适应新题目:
掌握常见算法:
华为OD考试通常涉及以下算法和数据结构:
保持编程规范:
官方参考:
加入刷题社区:
寻找系统性的教程:
刷题的过程可能会比较枯燥,但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试,还是为了未来的职业发展,这些积累都会成为重要的财富。
本地编写代码
调整心态,保持冷静
输入输出完整性
快捷键使用
Ctrl+D
,复制、粘贴和撤销分别为 Ctrl+C
,Ctrl+V
,Ctrl+Z
,这些可以正常使用。Ctrl+S
,以免触发浏览器的保存功能。浏览器要求
交卷相关
时间和分数安排
考试环境准备
技术问题处理
祝你考试顺利,取得理想成绩!
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- huatuo8.com 版权所有 湘ICP备2023022238号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务