# 20240317 Walmart

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