20240317 Walmart

mail@pastecode.io avatar
unknown
c_cpp
a month ago
2.6 kB
1
Indexable
Never
// #include <cmath>
// #include <cstdio>
// #include <vector>
// #include <iostream>
// #include <algorithm>
// using namespace std;

Provide you a array and a target number. 
Array may containers some number from 0-9. 
Find the largest number no larger than target number using the numbers in array. 
Example:
Array[4,5,8] Target:878 => 858 
  - x x 7   777
  - x x 7 9 799
  - 3 8 9    8 
  874 => 858
  
  854 => 854
Array[4,5,8] Target:843 => 588 
Array[4,5,8] Target:443 => 88
Array[3,4,5,8] Target:442 => 438

[8, 9] 7 -> std::nullopt_t
    target 77 -> 9
// 1)matched
// 2)smaller
// 3)no find anything

stack<int> split(int target) {
    stack<int> s;
    int t = 10;
    while(target > 0) {
        s.push(target % t);
        target /= t;
        t *= 10;
    }
    return s;
}

int find(vector<int>& num, int x) {
    for(int i = 0; i < num.size(); i++)
        if(num[i] == x) return i;
        // if i == 0, return -1;
        if(num[x] > x) return i - 1;
    }
    return -1;
}

int getResult(vector<int>& res) {}

int solve(vector<int>& num, int target) {
    // Split target in to digits
    stack<int> s = split(target);
    
    // process the splitted digits from target: 9 9 5
    // int res = 0;
    vector<int> res;
    while(!s.empty() && num[find(s.top())] == s.top()) {
        // res = res * 10 + s.top();
        res.push_back(s.top());
        s.pop();
    }
    
    // [5 9] target 994    
    // 959
    // [9] 9944 4
    // 9433 

    // 3,4,9 

    // 9399 
    if(!s.empty()) {
        int pos = find(s.top());
        // If the next number is smaller 
        if(pos != -1) {
            // res = res * 10 + num[pos];
            res.push_back(num[pos]);
            s.pop();
            while(!s.empty()) {
                s.pop();
                // res = res * 10 + num.back();
                res.push_back(num.back());
            }
        } else {
            int lastPos = find(res.back());
            if(lastPos == 0) {
                while(s.size() != 1) {
                    s.pop();
                res.push_back(num.back());
                }
            } else {
                res.pop_back();
                res.push_back(num[lastPos - 1]);
                while(!s.empty()) {
                    s.pop();
                    res.push_back(num.back());
                }
            }
        }
    }
    return getResult(res);
}

res
 for i in range(len(target)):
    if matched:
        // go to next digital
    if smaller:
        // add smaller, remaining largest
    if not matched:
        revert(i-1,res)
        

revert(i-1,res):
    // i is first. null
    revert(i-2,res):
    

Leave a Comment