字节一面笔试题：小于n的最大数
指定降序数组arr和数字n，输出数组能组成的小于等于数字n的最大值。比如arr=[9,4,3,2],n=433211,输出432999；
思路，贪心+二分。
难的在于中途有数字找不到比它小的数的话，得回退，需要确认回退逻辑怎么写。
Java代码如下：
public int maxNum(){
List<Integer> arr = Arrays.asList(9,4,3,2);
int n = 433211;
List<Integer> nlist = new ArrayList<>();
int base = 0;
while(n!=0){
nlist.add(0,n%10);
n /= 10;
base = base*10+1;
}
boolean less = false;
int res = 0;
for(int i=0;i<nlist.size();i++){
if(less){
res = res*10+arr.get(0);
continue;
}
int index = find(arr,nlist.get(i));
if(index==-1){
int l = i;
while(l>=0&&index==-1){
index = find(arr,nlist.get(l)-1);
l-=1;
}
if(index==-1){
res = base*arr.get(0)/10;
break;
}
res = res/((int) Math.pow(10,i-l-1));
res = res*10 + nlist.get(index);
for(int p=0;p<i-l-1;p++){
res = res*10+arr.get(0);
}
less = true;
}else if(arr.get(index)==nlist.get(i)){
res = res*10+arr.get(index);
}else{
res = res*10+arr.get(index);
less = true;
}
}
return res;
}
public int find(List<Integer> arr,int k){
if(k<arr.get(arr.size()-1)) return -1;
int index = -1;
int l = 0,r = arr.size()-1;
while(l<=r){
int mid = (l+r)/2;
if(arr.get(mid)==k){
return mid;
}else if(arr.get(mid)<k){
index = mid;
r = mid -1;
}else{
l = mid + 1;
}
}
return index;
}
#字节##面试##笔试##手撕代码#
查看10道真题和解析