字节面试算法题

试探回溯法就行，找到所有数，选出小于n的最大数就行了，复杂度没提要求应该能过； public class Main { public static void main(String[] args) { int n=23121; int[] array=new int[] {2,4,9}; System.out.println(find(n, array)); }     public static int find(int n, int[] array) {      int depth=0;      List<Integer> list=new ArrayList<>();      int path=0;      char[] digits=Integer.toString(n).toCharArray();      dfs(n, depth, digits, array, path, list);      int result=0;      Collections.sort(list);      for(int i=0;i<list.size();i++) {      if(list.get(i)>=n) {      result=list.get(i-1);      break;      }      }      return result;     }          public static void dfs(int n, int depth, char[] digits, int[] array, int path, List<Integer> list) {      if(depth==digits.length) {      list.add(path);      return;      }      for (int i = 0; i < array.length; i++) { path = path * 10 + array[i]; dfs(n, depth + 1, digits, array, path, list); path = path / 10; } } }

将数组排序 n转字符串 从左到右遍历n 对于每一位在数组中二分查找 如果位存在于数组中则选择并继续下一位 否则选择小于该位的最大值并且对与后面的位全部填充数组最大值

字节一面遇到了，讲了模拟思路没写出来

不用回溯，将给定的数组排序(理论上不用排序On时间复杂度)，得到数组中的最大值和最小值。然后从给定数字的个位到高位遍历，直到找到第一个大于数组min的位。如果没有找到，答案就是原数字长度-1个数组最大值的拼接；如果找到了，找到那一位的更高位都不变，找到的那一位变成数组中小于它的最大值，然后比当前低的位用数组里面的最大值max替换即可。

双指针可以考虑的

#include<bits/stdc++.h> using namespace std; int main(){ int n=23121,m ; //cin>>n; vector<int>a={2,4,9},b,c; /*while(cin>>m){ a.push_back(m); }*/ sort(a.begin(),a.end()); while(n/10){ c.push_back(n%10); n/=10; } c.push_back(n); int target=0; for(int i=c.size()-1;i>=0;i--){ if(target==1){ b.push_back(a.back()); continue; } for(int j=0;j<a.size();j++){ if(c[i]==a[j]){ b.push_back(c[i]); break; } if(c[i]>a[j]){ b.push_back(a[j]); target=1; break; } } } int sum=0; for(int i =0;i<b.size();i++){ sum+=b[i]*pow(10,b.size()-i-1); } cout<<sum<<endl; }