如何提高加扰代码的性能？-解网

问：

我需要完成函数 scramble（str1， str2），如果可以重新排列 str1 字符以匹配 str2，则返回 true，否则返回 false。通过哪种方法可以提高此代码的性能？例如，如果我在 str1 和 str2 中有 200k+ 个字符，则性能非常糟糕。

bool scramble(const string& s1, const string& s2) 
{
    string reference = s2;
    string inputStr = s1;
    size_t refLen = reference.length();
    size_t lenCounter = 0;

    for (auto n = 0; n < reference.length(); n++)
    {
        auto tempLetter = reference[n];
        size_t letterPos = inputStr.find(tempLetter);
        if (letterPos != string::npos)
        {
            lenCounter++;
            inputStr.erase(letterPos, 1);
            if (lenCounter == refLen)
            {
                return true;
            }
        }
        else
            return false;
    }
    if (refLen == lenCounter)
        return true;
    else
        return false;
}

这是一个现成的解决方案，可以满足我的要求。@Dave提供的此解决方案的想法

bool scramble(const string& s1, const string& s2)
{
    string ref = s2;
    string input = s1;
    string result = "";
    char tempLetter = '\0';
 
    sort(ref.begin(), ref.end());
    sort(input.begin(), input.end());
   
    map<char, int> letters;

    for (auto n = 0; n < input.length(); n++)
    {
        tempLetter = input[n];
        map<char, int> ::iterator it = letters.find(tempLetter);
        if (it == letters.end())
        {
            letters.insert(make_pair(tempLetter, 0));
            letters.at(tempLetter) = 1;
        }
        else
        {
            letters.at(tempLetter) += 1;
        }
    }
    for (auto i = 0; i < ref.length(); i++)
    {
        tempLetter = ref[i];
        map<char, int> ::iterator it = letters.find(tempLetter);
        if (it != letters.end() && letters.at(tempLetter) >=0)
        {
            letters.at(tempLetter) -= 1;
            if (letters.at(tempLetter) < 0)
                return false;
            result.push_back(tempLetter);
        }
    }
    if (result!=ref)
        return false;
    else
        return true;
}

C++ 字符串算法性能优化

@n.m.couldbeanAI 通常你是对的。但是，对于无法扩展的程序，我们有一个例外。如果代码在小输入上正常工作（输出正确的值），则代码将属于我们的缩放规则。此外，如果您仍然不相信我，我想向您指出我们的 time-limit-exceeded 标签。感谢您帮助我们避免偏离主题的问题 Code Review。

1赞 MPIchael 10/31/2023

欢迎来到 Scicomp！您可以测试的一种方法是对两个字符串进行排序，然后开始查找。这样一来，您可以大大减少出现负面结果的时间，但代价是对两个字符串进行排序。尝试类似的东西：std：：sort（std：：begin（array）， std：：end（array））

3赞 MPIchael 10/31/2023

另一个想法是做一次传递，你数“a”、“b”的数量......并保留一张桌子。然后对第二个数组执行相同的操作。然后检查数组中是否有足够的“a”和“b”。这应该会降低线性的复杂性，但会消耗一些记帐内存。

答：

1赞 Avi Lachmish 10/31/2023 #1

出于两个原因，我会写得有点不同：

可读性和可维护性
复杂性

比方说，那应该更大.m = sizeof s1;n = sizeof s2;nm

首先对字符串进行排序将花费 O（nlog（n）），但随后，在一次传递中，您可以获得输出，这意味着我的加扰函数复杂度为：

O(n+nlogn) = O(nlongn)

但是，在您的情况下，复杂性是 .O(n*m)

我是这样写的：

bool is_scramble(std::string s1, std::string s2) 
{
    if (s2.size() < s1.size()) return false;

    std::ranges::sort(s1);
    std::ranges::sort(s2);

    return std::ranges::includes(s2, s1);
}

正如评论中提到的，您可以进行计数排序（在 ASCII 或 EBCDIC 的限制下），这在时间复杂度方面甚至更便宜，然后编写以下代码。

它确实需要 256 字节的额外存储空间（有 ASCII 或 EBCDIC 的限制）。恕我直言，它的可读性也较差。

bool is_scramble2(std::string s1, std::string s2) 
{
    // s1 needs to be contain in s2
    if (s2.size() < s1.size()) return false;

    constexpr int maxChar = 256; // Assuming ASCII character set
    std::array<int, maxChar> count = {0};

    // Count the occurrences of each character in the string
    for (char c : s2) {
        count[static_cast<int>(c)]++;
    }

    for(const auto c : s1) {
        if (count[static_cast<int>(c)] <= 0) return false;
        count[static_cast<int>(c)]--;
    }
    return true;
}

如何提高加扰代码的性能？

How can I improve performance of scramble code?

评论

评论

评论