【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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

代码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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

知识点：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;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路：计数排序的思想

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

牛客链接
代码展示：

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路：首先得到倒数第一个空格的下标，然后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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

这个代码，使用头插，时间复杂度为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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

思路：倒着进行加法运算，当两个字符串的位数不一样的时候，位数少的前面进行补0【两个字符串都结束的时候才可以认为结束。【注意下标问为0的位置的进位】】

知识点：大数运算（当一个数字非常大的时候，可以用字符串的形式进行存放），字符串是不能进行加减运算的。此时就需要我们写代码。

---

总结

以上就是今天要讲的内容，本文详细的介绍了string的OJ题。希望给友友们带来帮助！