查找数字“内”的最大三位数

Question

对于这个问题，我需要在一个较大的数字中找到最大的三位数字。

示例测试用例 1：

534535

输出：

535

---

示例测试用例 2：

23457888976

输出 ：

976

---

我试过以下代码：

         #include <iostream>
        using namespace std;
        int main() {
        int num;
        cin>>num;
        int len= to_string(num).length();
        int arr[10],lnum=0,max=0;
        for (int i =len-1;i>=0;i--)
        {
        arr[i] = num%10;
        num =num/10;    //to convert int into array
        }
        for (int i=0;i<len-2;i++)
        {
        if (arr[i] >arr[i+1])
            lnum = arr[i]*100+arr[i+1]*10+arr[i];
        if (lnum>max)
            max= lnum;
        }
        cout<<max;
        return 0;
    }

---

尽管此代码似乎适用于测试用例 1，但它不适用于大多数输入。

---

（也请帮忙。）

1. 这仅适用于 10 位数字（同样，大多数输出错误）。如果数字较大怎么办？

2.有没有更好的方法将整数转换成数组？或者字符串数组会以类似的方式工作吗？

3.真的很慢，谁能帮我弄清楚如何加快速度？

---

谢谢你的帮助 ！！

原文由 Shinichi 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

#include <iostream>
#include <string>
using namespace std;
int main() {
    int i, n;
    string s;
    cin >> s;
    n = (int)s.size();
    if(n<3){
        /* there are less than 3 digits in the input number
        Here, you can print the number itself as it will be largest number or
        print -1 which can state that no 3 digit number exists.
        */
        cout<<-1;
        return 0;
    }
    int maxans = (s[0]-'0')*100 + (s[1]-'0')*10 + (s[2]-'0');
    // storing the first 3 digits as the maximum answer till now.
    int prev = maxans;
    for(i = 3;i<n;i++){
        int cur = (prev%100)*10 + (s[i]-'0'); // using %100 to extract the last two digits and then multiplying by 10 and adding the ith digit to make the next 3 digit number.
        maxans = max(maxans, cur);
        prev = cur;
    }
    cout<<maxans;
    return 0;
}

此代码的时间复杂度为 O(n)，其中 n 是输入字符串的长度，空间复杂度为 O(1)

原文由 risingStark 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

阅读评论以了解以下代码：

 #include <assert.h>
#include <iostream>
#include <boost/hana/functional/partial.hpp>
#include <functional>
#include <range/v3/to_container.hpp>
#include <range/v3/view/all.hpp>
#include <range/v3/view/drop.hpp>
#include <range/v3/view/subrange.hpp>
#include <range/v3/view/take.hpp>
#include <range/v3/algorithm/all_of.hpp>
#include <string>

using namespace boost::hana;
using namespace ranges;
using namespace ranges::views;

auto constexpr is9 = partial(std::equal_to<>{}, 9);

template<typename Range>
Range fun(Range const& r) {
    if (r.size() == 3) {                   // 3 digits only?
        return r;                              // this is the result
    } else if (all_of(r | take(3), is9)) { // 999?
        return r | take(3);                    // nothing better than this!
    } else {                               // otherwise?
        auto tail = r | drop(1);               // drop the first to get the tail
        if (r.front() < tail.front()) {        // if the first is less the the tip of the tail
            return fun(tail);                      // then let the first go and recurse on the tail
        } else {                               // otherwise
            auto result = std::max(                // get the maximum between
                    r | take(3) | to<std::string>, // the current first three
                    fun(tail)   | to<std::string>  // and the result of recursing on the tail
                    );
            return result;                         // and that's the result
        }
    }
    return r;
}

int main() {
    std::string s1 = "534535";
    std::string s2 = "23457888976";
    assert((fun(subrange(s1)) | to<std::string>) == std::string{"535"});
    assert((fun(subrange(s2)) | to<std::string>) == std::string{"976"});
}

该数字被视为一个字符串，并且由于我们需要比较长度为 3 的（子）字符串，因此 std::string s 的词典 operator< 给我们与算术相同的结果 operator< 会给出两个对应的数字。

逻辑是：

• 如果需要，我们从左边开始并向右递归
• 在只剩下 3 位的情况下， r.size() == 3 ，我们返回所有的， return r;
• 在三个前导 9 的情况下， all_of(r | take(3), is9) ，我们简单地返回这三个 return r | take(3); ；
• 否则，我们采用前三位字符串 std::max 之间的 r | take(3) | to<std::string> 和 std::string 我们通过在没有第一个序列的情况下递归获得的序列数字， fun(tail) | to<std::string> 。

原文由 Enlico 发布，翻译遵循 CC BY-SA 4.0 许可协议