本文主要是介绍算法题--华为od机试考试（执行时长、找数字、数据最节约的备份方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
执行时长
题目描述
输入描述
输出描述
示例1
输入
输出
说明
示例2
输入
输出
说明
解析
找数字
题目描述
输入描述
输出描述
示例1
输入
输出
示例2
输入
输出
示例3
输入
输出
解析
数据最节约的备份方法
题目描述
输入描述
输出描述
备注
示例1
输入
输出
示例2
输入
输出
解析
执行时长
考察理解能力
题目描述
为了充分发挥GPU算力,需要尽可能多的将任务交给GPU执行,现在有一个任务数组,数组元素表示在这1秒内新增的任务个数且每秒都有新增任务,
假设GPU最多一次执行n个任务,一次执行耗时1秒,在保证GPU不空闲情况下,最少需要多长时间执行完成
输入描述
第一个参数为GPU一次最多执行的任务个数,取值范围[1,10000]
第二个参数为任务数组长度,取值范围[1,10000]
第三个参数为任务数组,数字范围[1,10000]
输出描述
执行完所有任务最少要要多少秒
示例1
输入
3
5
1 2 3 4 5
输出
6
说明
一次最多执行3个任务,最少耗时6s。
示例2
输入
4
5
5 4 1 1 1
输出
5
说明
一次最多执行4个任务，最少耗时5s
解析
按顺序执行，每次用最多执行的任务个数减去当前的任务个数和上次剩余的个数，如果有剩余的任务未执行就留到下一次，
如果没有则下一次剩余的任务为0，最后剩下的任务直接除以最多执行的任务个数向上取整。
function executeTime(n, len, arr) {let tmp = 0for (let i = 0; i < len; i++) {if (n > arr[i]) {tmp = (tmp - n + arr[i]) < 0 ? 0 : (tmp - n + arr[i])} else {tmp = tmp + arr[i] - n}}return len + Math.ceil(tmp / n)}console.log(executeTime(3, 5, [1, 2, 3, 4, 5]))console.log(executeTime(4, 5, [5, 4, 1, 1, 1]))找数字
考察二进制和十进制的转换
题目描述
小扇和小船今天又玩起来了数字游戏，
小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：
4对应二进制100
8对应二进制1000
其中1的个数都为1个
现在求 m 的最小值。
输入描述
输入一个正整数 n（1 ≤ n ≤ 1e9）
输出描述
输出一个正整数 m
示例1
输入
128
输出
256
示例2
输入
6
输出
9
示例3
输入
5
输出
6
解析
将n转换为二进制，如果是所有的1在左边，0在右边，则需要进一位，例如111100 => 1000111。全为1也同样需要进一位。
其它情况从右到左，把第一个01交换顺序即可，例如1001 => 1010。最后将结果转为十进制的数字。
function getMin(n) {let arr = n.toString(2).split('').map(Number)for (let i = arr.length - 2; i > 0; i--) {if (arr[i] === 0 && arr[i + 1] === 1) {arr[i + 1] = 0arr[i] = 1return parseInt(arr.join(''), 2)}}arr = arr.sort((a, b) => a - b)arr[arr.indexOf(1)] = 0arr.unshift(1)return parseInt(arr.join(''), 2)
}
console.log(getMin(128))
console.log(getMin(6))
console.log(getMin(5))数据最节约的备份方法
考察二分法、深度遍历、递归
题目描述
有若干个文件，使用刻录光盘的方式进行备份，假设每张光盘的容量是500MB，求使用光盘最小的
文件分布方式所有文件的大小都是整数的MB，且不超过500MB；文件不能分隔、分卷打包
输入描述
组文件大小的数据
输出描述
使用光盘的数量
备注
不用考虑输入数据不合法的情况;假设最多100个输入文件
示例1
输入
100,500,300,200,400
输出
3
示例2
输入
1,100,200,300
输出
2
解析
这里我们采用二分法确定最小使用光盘的数量。例如示例1有5组文件，这里我们先确认3个光盘是否可以装下，用深度遍历去分析，如果可以的话，再确认(1+3)/2=2个光盘
是否可以装下，不行的话，返回最小为3，可以的话继续上述操作。
这里关键在于dfs函数函数实现：
1.确定入参，1>当前所有光盘容量、2>组文件、3>当前需要装的序号。这里2、3是用来表示剩余的未装光盘数据，可以用一个数组表示，不过需要一直改变数组的长度大小。
2.确定f(x)和f(x-1)的关系。f(x)=f(x-1)0 || f(x-1)1 || ...。
当前这一次等于将x的数据依次放入所有光盘中取或，f(x-1)0表示把x的数据放入0号光盘中，只有有一组可以返回true即表示当前的光盘数量可以装下所有数据。
3.确定出口和剪枝，
1>光盘容量+当前需要放下的数据小于等于500才能放入
2>当放入的序号等于组文件数量是表示已全部放入，返回true
3>当前的光盘和上一个光盘容量大小一样，故装入该光盘中和装入上一个光盘中无区别，可以跳过
4>下一次循环前需还原光盘容量
function minCopy(str) {let arr = str.split(',').map(Number).sort((a, b) => b - a)let l = 1;let r = arr.length;let ans = r;// 二分模板while (l <= r) {const mid = Math.floor((l + r) / 2);if (check(mid, arr)) {ans = mid;r = mid - 1;} else {l = mid + 1;}}return ans;
}
// 返回bucket.length个光盘是否可以装下，bucket为光盘，num为未装的组文件，index为当前需要装的组文件序号
function dfs(buckets, nums, index) {// 所有组文件都已装入光盘中if (index === nums.length) {return true;}// 将序号为index的组文件依次递归放入bucket中for (let i = 0; i < buckets.length; i++) {// 剪枝，当前的光盘和上一个光盘容量大小一样，故装入该光盘中和装入上一个光盘中无区别，可以跳过if (i !== 0 && buckets[i] === buckets[i - 1]) {continue;}// 该光盘可以装下此组文件if (buckets[i] + nums[index] <= 500) {buckets[i] += nums[index]; //回溯// 找到结果后不再往下递归if (dfs(buckets, nums, index + 1)) {return true;}// 下一次循环前还原光盘容量buckets[i] -= nums[index];}}return false;
}// 返回是否能使用count个光盘备份数据
function check(count, nums) {const buckets = new Array(count).fill(0);return dfs(buckets, nums, 0);}
console.log(minCopy('100,500,300,200,400'))
console.log(minCopy('1,100,200,300'))这篇关于算法题--华为od机试考试（执行时长、找数字、数据最节约的备份方法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
