分享丨字节面试题 : 小于n的最大数

#include <iostream>
#include <queue>
#include <algorithm>


class Solution{
private:   
    std::vector<int> path;
    std::vector<int> digits;
    int n;
    int ret = -1;
    void dfs(std::vector<int>& A){
        if(ret != -1) return;
        if(path.size() == digits.size()){
            ret = pathNum();
            return;
        }

        for(int i = 0; i < A.size(); ++i){
            path.push_back(A[i]);
            int curNum = pathNum();
            if(curNum <= n){
                dfs(A);
            }
            path.pop_back();
        }
    }

    int pathNum(){
        int ret = 0;
        for(int i = 0; i < path.size(); ++i){
            ret = ret * 10 + path[i];
        }
        for(int j = 0; j < digits.size() - path.size(); ++j){
            ret *= 10;
        }
        return ret;
    }
public:
    int fun(int n_, std::vector<int>& A_){
        n = n_;
        while(n_){
            digits.push_back(n_ % 10);
            n_ /= 10;
        }
        std::reverse(digits.begin(), digits.end());
        std::sort(A_.rbegin(), A_.rend());
        dfs(A_);
        return ret;
    }
};

int main(){
    Solution S;
    std::vector<int> v = {2,3,4,9};
    std::cout<< S.fun(433211, v);
}