给定正整数N和集合K，求不大于N的、每一位数字都在K中的最大值M，比如N=...

Question

给定正整数N和集合K，求不大于N的、每一位数字都在K中的最大值M，比如N=297 K={2, 5, 8}，则返回288

Answer 1

思路

先尝试得到一个与N相等的，全由K中数字拼接的结果，即从高位往低位，每一位优先选择K中等于N对应位的数字，
如果没有，则选择小于的数字。一旦选择了小于的数字，后面直接选择K中最大的数字。
如果最终有相等的结果，那就从最低位开始逐个换成较小的选择。换完后，再把换完后面的全部替换掉K中最大的数字。
如果根本得不到相等的结果，说明相同位数根本不行，直接换成位数减一，每一位都是K中最大的数字。

code

`

include <bits/stdc++.h>

using namespace std;

void transfer(uint32_t target, vector<uint32_t> &target_nums) {
//把字符串转为数字数组 方便调试
while (target != 0) {
target_nums.insert(target_nums.begin(), target % 10);
target = target / 10;
}
}
string findMaxNumLessThanTarget(const vector<uint32_t> &target_nums, const vector<uint32_t> &src) {
cout << “target_nums:”;
for (const auto it : target_nums) {
cout << “ “ << it;
}
cout << “ src_nums:”;
for (const auto it : src) {
cout << “ “ << it;
}
cout << endl;
//结果存在数组中
vector<uint32_t> result;
result.resize(target_nums.size(), 0);

bool lessThanTarget = false;
bool equalWithTarget = true;

//先尝试位数相同的场景
//先争取找到与target相同的数字
for (int i = 0; i < target_nums.size(); ++i) {
    //如果高位已经选择了比target更小的数字
    if (lessThanTarget) {
        result[i] = src[src.size() - 1];
        equalWithTarget = false;
        continue;
    }
    //not less than
    auto lower_idx = lower_bound(src.begin(), src.end(), target_nums[i]);
    cout << "i:" << i << " target:" << target_nums[i] << " low_idx:" << (lower_idx - src.begin()) << " val:" << *lower_idx << endl;
    //找不到更大的数字了
    if (lower_idx == src.end()) {
        result[i] = src[src.size() - 1];
        lessThanTarget = true;
        continue;
    }
    if (*lower_idx == target_nums[i]) {
        result[i] = *lower_idx;
        continue;
    }
    //首元素 都比target[i]大
    if (lower_idx == src.begin()) {
        lessThanTarget = false;
        equalWithTarget = false;
        break;
    }

    cout << " found less than. i: " << i << " target[i]: " << target_nums[i] << " src[idx]:" << *(lower_idx - 1) << endl;
    result[i] = *(lower_idx - 1);
    lessThanTarget = true;
    equalWithTarget = false;
}
//找到了更小的数字
if (lessThanTarget) {
    stringstream ss;
    for (const auto &it : result) {
        ss << it;
    }
    return ss.str();
}
//从低位往高位逐个的尝试把result的元素变小
if (equalWithTarget) {
    for (int i = result.size() - 1; i >= 0; --i) {
        //找到第一个小于
        auto loc = upper_bound(src.begin(), src.end(), result[i], greater<>());
        //没有更小的了
        if (loc == src.end()) {
            continue;
        }
        result[i] = *(loc - 1);
        lessThanTarget = true;
        cout << "change to less than i:" << i
             << " target[i]:" << target_nums[i] << " src[loc]" << *(loc - 1) << endl;
        for (int j = i + 1; j < result.size(); ++j) {
            result[j] = src[src.size() + 1];
        }
        break;
    }
}
//成功变小了
if (lessThanTarget) {
    stringstream ss;
    for (const auto &it : result) {
        ss << it;
    }
    return ss.str();
}
//只能减少位数了
cout << "try to get less weishu size:" << (target_nums.size() - 1) << " max value:" << src[src.size() - 1] << endl;
stringstream ss;
for (int i = 0; i < (target_nums.size() - 1); ++i) {
    ss << src[src.size() - 1];
}
return ss.str();

}

int main() {
{
int n = 12123;
vector<uint32_t> k{2, 9};
vector<uint32_t> n_nums;
transfer(n, n_nums);
auto res = findMaxNumLessThanTarget(n_nums, k);
cout << “testcase1: “ << res << endl;
}
cout << endl;
{
int n = 12123;
vector<uint32_t> k{1, 2};
vector<uint32_t> n_nums;
transfer(n, n_nums);
auto res = findMaxNumLessThanTarget(n_nums, k);
cout << “testcase2: “ << res << endl;
}

cout << endl;
{
    int n = 2;
    vector<uint32_t> k{2};
    vector<uint32_t> n_nums;
    transfer(n, n_nums);
    auto res = findMaxNumLessThanTarget(n_nums, k);
    cout << "testcase3: " << res << endl;
}

cout << endl;
{
    int n = 2;
    vector<uint32_t> k{1};
    vector<uint32_t> n_nums;
    transfer(n, n_nums);
    auto res = findMaxNumLessThanTarget(n_nums, k);
    cout << "testcase4: " << res << endl;
}

cout << endl;
{
    int n = 297;
    vector<uint32_t> k{2, 5, 8};
    vector<uint32_t> n_nums;
    transfer(n, n_nums);
    auto res = findMaxNumLessThanTarget(n_nums, k);
    cout << "testcase5: " << res << endl;
}

cout << endl;
{
    int n = 2888;
    vector<uint32_t> k{2,8};
    vector<uint32_t> n_nums;
    transfer(n, n_nums);
    auto res = findMaxNumLessThanTarget(n_nums, k);
    cout << "testcase6: " << res << endl;
}
return 0;

}
`