Shopee8月26日后端笔试代码

1、包含小写字母出现abcde为偶数的最长子串。枚举然后判断

bool JudgeStr(string s)
{
    unordered_map<char, int> umap;
    for (int i = 0; i < s.size(); ++i)
    {
        if (!islower(s[i]))
        {
            return false;
        }
        else
        {
            umap[s[i]]++;
        }
    }
    if ((umap['a'] % 2 == 0) && (umap['b'] % 2 == 0) &&
    (umap['c'] % 2 == 0) && (umap['d'] % 2 == 0) && (umap['e'] % 2 == 0))
    {
        return true;
    }
    return false;
}
int getMaxSubstringLen(string str) {
    // write code here
    int len = str.size(), max_len = 0;
    for (int i = 0; i < len; ++i)
    {
        for (int j = i; j < len; ++j)
        {
            if (JudgeStr(str.substr(i, j + 1 - i)))
            {
                max_len = max(max_len, j - i + 1);
            }
        }
    }
    return max_len;
}
int main()
{
    string test1 = "aabbffced", test2 = "asdfajskfbb";
    cout << getMaxSubstringLen(test2);
    system("pause");
    return 0;
}

2、判断两个字符串是否相同。可以把字符串分成两部分。递归

bool isStrsEqu(string str1, string str2) 
{
    // write code here
    if (str1.size() != str2.size())
    {
        return false;
    }
    int len = str1.size();

    if (str1 == str2)
    {
        return true;
    }
    else if (len % 2 == 1)
    {
        return false;
    }
    else
    {
        if (isStrsEqu(str1.substr(0, len / 2), str2.substr(0, len / 2)) && 
                isStrsEqu(str1.substr(len / 2, len / 2), str2.substr(len / 2, len / 2)))
        {
            return true;
        }

        if (isStrsEqu(str1.substr(0, len / 2), str2.substr(len / 2, len / 2)) && 
                isStrsEqu(str1.substr(len / 2, len / 2), str2.substr(0, len / 2)))
        {
            return true;
        }
        
    }
    return false;
}
int main()
{
    string test1 ="aaba", test2 = "abaa";
    string test3 ="abab", test4 = "aabb";
    cout << isStrsEqu(test1, test2);
    system("pause");
    return 0;
}

3、两个子串长度的最大乘积。暴力匹配

int getMaxsubSet(string& str, set<char>& sub1)
{
    int max_len = 0;
    for (int i = 0; i < str.size(); ++i)
    {
        for (int j = i; j < str.size(); ++j)
        {
            if (sub1.find(str[j]) != sub1.end())
            {
                max_len = max(j - i + 1, max_len);
            }
            else
            {
                break;
            }
            
        }
    }
    return max_len;
}

int getMaxMul(string str) 
{
    // write code here
    int N = 0;
    for (char& c : str)
    {
        N = max(N, c - 'a' + 1);
    }
    set<char> aset;
    for (int k = 0; k < N; ++k)
    {
        aset.insert(k + 'a');
    }
    int max_len = 0;
    for (int i = 0; i < str.size(); ++i)
    {
        set<char> sub1;
        set<char> sub2 = aset;
        for (int j = i; j < str.size(); ++j)
        {
            if (sub1.find(str[j]) == sub1.end())
            {
                sub1.insert(str[j]);
                sub2.erase(str[j]);
            }
            if (sub1.size() == N) break;
            max_len = max(getMaxsubSet(str, sub2) * (j - i + 1), max_len);
        }
    }
    return max_len;
}
int main()
{
    string test = "adcbadcbedbadedcbacbcadbc";
    cout << getMaxMul(test);
    system("pause");
    return 0;
}

#笔试题目##C++工程师##Shopee#