字节跳动经典算法题(提问次数最多)
题目描述:给定一个数n如23121;给定一组数字a,如[2 4 9];求由a中元素组成的小于n的最大数。
思路分析:暴力分析手法
1. 判断该位的数值是否在数字a中;
2. 如果存在继续判断下一位;
3. 如果不存在,则判断该位在数字中的大小,选择小于该位的最大数存入结果数组中,若该值小于数字a中的所有值,则返回前一位,选择小于前一位的最大数存入结果数组中,以此类推,后续位置添补数字a中的最大值。
这里使用了二分查找方法searchInsert (),但有所更改,查询目标值是否在给定的一组数字中,存在则返回该值,不存在则返回小于目标值的最大值,如果没有则返回0。
可使用C++、Java、JavaScript、Python等语言,这里使用最简便的JavaScript脚本语言。
var n = 23121; var n1 = 121; var n2 = 99; var n3 = 201;n4 = 20002; n5 = 250;n6 = 215;
var a = [2,4,9]
var MaxNum = function(nums, arr){
// let arr = Array.from(array) // 将object转换成数组
if(arr.length == 0){ // 如果数字长度为0,返回-1
return -1
}
// 给定数字变为数组形式。
var num = (nums).toString().split('')
console.log('在给定元素中组成的小于' + num.join('') + '的最大数为:')
var res = [] //定义一个结果数组
for(let i = 0; i < num.length; i++){ // 遍历给定数字变换成的数组
if(a.indexOf(parseInt(num[i])) != -1){ // 如果值在给定一组数字a中,则将该值放入结果数组中
if((i + 1) < num.length){
if(num[i + 1] <= arr[0]){
res.push(0)
for(var k = 0; k < num.length - i -1; k ++){
res.push(arr[arr.length - 1])
}
break
}else{
res.push(a[a.indexOf(parseInt(num[i]))]) // 直接存放这位数
}
}else{
res.push(searchInsert(arr,parseInt(num[i])-1)) // 搜索小于这一位的最大数
}
}else{
num_max = searchInsert(arr,parseInt(num[i])); // 保存小于num[i]的最大值
res.push(num_max)
for(var k = 0; k < num.length - i -1; k ++){
res.push(arr[arr.length - 1])
}
break
}
}
var result = [] // 定义一个最终结果数组,将前面是0的变成最终数组
for(let z = 0; z < res.length; z++){
if(res[z] != 0){
result.push(res[z])
}
}
return result.join("")
}
// 查询目标值是否在给定的一组数字中,存在则返回该值,不存在则返回小于目标值的最大值,如果没有则返回0
var searchInsert = function(nums, target) { // 采用二分查找
const n = nums.length;
let left = 0, right = n - 1, ans = n;
while (left <= right) {
let mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
//如果target不存在,插入其中不是最小位置,则返回前一位,小于目标值的最大值
if(nums.indexOf(target) == -1 && ans != 0){
return nums[ans - 1]
}
//如果target不存在,并且比所有值都小,则返回0
if(nums.indexOf(target) == -1 && ans == 0){
return 0
}else{ // 否则找到该值,返回该值
return nums[ans]
}
};
// var n = 23121; var n1 = 121; var n2 = 99; var n3 = 100;n4 = 20001;
console.log(MaxNum(n, a)) // 23121 22999
console.log(MaxNum(n1, a)) // 121 99
console.log(MaxNum(n2, a)) // 99 94
console.log(MaxNum(n3, a)) // 201 99
console.log(MaxNum(n4, a)) // 20001 9999
console.log(MaxNum(n5, a)) // 250 249
console.log(MaxNum(n6, a)) // 215 99