【C++ • STL • 力扣】详解string相关OJ-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++ • STL • 力扣】详解string相关OJ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

ヾ(๑╹◡╹)ﾉ" 人总要为过去的懒惰而付出代价 ヾ(๑╹◡╹)ﾉ"

1、仅仅翻转字母

力扣链接
代码1展示：【下标】


class Solution {
bool isLetter(const char& c)
{
    if (c >= 'a' && c <= 'z')
        return true;
    else if (c >= 'A' && c <= 'Z')
        return true;
    else
        return false;
}
public:
    string reverseOnlyLetters(string s)
    {
        int left = 0;
        int right = s.size() - 1;
        while (left < right)
        {
            while (left < right && !isLetter(s[left]))
            {
                left++;
            }
            while (left < right && !isLetter(s[right]))
            {
                right--;
            }
            swap(s[left], s[right]);
            ++left;
            --right;
        }        
        return s;
    }
};

代码2展示：【迭代器】

class Solution {
bool isLetter(const char& c)
{
    if (c >= 'a' && c <= 'z')
        return true;
    else if (c >= 'A' && c <= 'Z')
        return true;
    else
        return false;
}
public:
    string reverseOnlyLetters(string s)
    {
        string::iterator leftIt = s.begin();
        string::iterator rightIt = s.end() - 1;
        while (leftIt < rightIt)
        {
            while (leftIt < rightIt && !isLetter(*leftIt))
            {
                leftIt++;
            }
            while (leftIt < rightIt && !isLetter(*rightIt))
            {
                rightIt--;
            }
            swap(*leftIt, *rightIt);
            ++leftIt;
            --rightIt;
        }        
        return s;
    }
};

思路：快速排序中的单趟排序

知识点：C++库提供了swap的函数，可以直接调用。

2、字符串中的第一个唯一字符

力扣链接
代码展示：

class Solution {
public:
    int firstUniqChar(string s) 
    {
        int count[26] = { 0 };
        for (auto ch : s)
        {
            count[ch - 'a']++;
        }
        for (size_t i = 0; i < s.size(); i++)
        {
            if (count[s[i] - 'a'] == 1)
            {
                return i;
            }
        }
        return -1;

    }
};

思路：计数排序的思想

3、字符串里最后一个单词的长度

牛客链接
代码展示：

#include <iostream>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    size_t pos = s.rfind(' ');
    if (pos != string::npos)
    {
        cout << s.size() - (pos + 1);
    }
    else 
    {
        cout << s.size();
    }
    return 0;
}

思路：首先得到倒数第一个空格的下标，然后size进行减去（下标+1）

知识点：cin遇见空格会认为获取结束，当遇见一行字符串的时候，该字符串中间有空格，那么就不会获取到整行的字符串。getline会获取一行的字符串，遇到空格也不会认为获取终止。

4、验证一个字符串是否是回文

力扣链接
代码展示：

class Solution {
public:
    bool isLetterOrNumber(char ch)
    {
        return (ch >= '0' && ch <= '9')
            || (ch >= 'a' && ch <= 'z')
            || (ch >= 'A' && ch <= 'Z');
    }

    bool isPalindrome(string s) 
    {

        //小写换成大写
        for(auto& ch : s)
        {
            if (ch >= 'a' && ch <= 'z')
            {
                ch -= 32;
            }
        }

        int begin = 0;
        int end = s. size() - 1;
        while (begin < end)
        {
            while(begin < end && !isLetterOrNumber(s[begin]))
            {
                ++begin;
            }
            while(begin < end && !isLetterOrNumber(s[end]))
            {
                --end;
            }

            if(s[begin] != s[end])
            {
                return false;
            }
            else
            {
                ++begin;
                --end;
            }
        }
        return true;
    }
};

5、字符串相加

力扣链接
代码1展示：（头插）

class Solution {
public:
    string addStrings(string num1, string num2) 
    {
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;//进位
        string s;
        while (end1 >= 0 || end2 >= 0)
        {
            //字符转换为数字
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int ret = val1 + val2 + carry;
            if (ret >= 10)
            {
                ret -= 10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            s.insert(s.begin(), ret + '0');
            end1--;
            end2--;
        }
        if (carry == 1)
        {
            s.insert(s.begin(), '1');
        }
        return s;
    }
};

这个代码，使用头插，时间复杂度为O（N^2）,算法不是最优的
代码2展示：

class Solution {
public:
    string addStrings(string num1, string num2) 
    {
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;//进位
        string s;
        while (end1 >= 0 || end2 >= 0)
        {
            //字符转换为数字
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int ret = val1 + val2 + carry;
            if (ret >= 10)
            {
                ret -= 10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            //s.insert(s.begin(), ret + '0');
            s += (ret + '0');
            end1--;
            end2--;
        }
        if (carry == 1)
        {
            s += '1';
            //s.insert(s.begin(), '1');
        }
        reverse(s.begin(), s. end());
        return s;
    }
};