【C++ • STL • 力扣】详解string相关OJ

雨点打透心脏的1/2处 2023-10-15 11:06 11阅读 0赞

#### 文章目录 ####

*  1、仅仅翻转字母
 *  2、字符串中的第一个唯一字符
 *  3、字符串里最后一个单词的长度
 *  4、验证一个字符串是否是回文
 *  5、字符串相加
 *  总结

--------------------

> ヾ(๑╹◡╹)ﾉ" **人总要为过去的懒惰而付出代价** ヾ(๑╹◡╹)ﾉ"  
> ![在是图片描是小刘述][ba68c80b5765481fb645f3452bf9b77b.png_pic_center]

--------------------

## 1、仅仅翻转字母 ##

[力扣链接][Link 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、字符串中的第一个唯一字符 ##

[力扣链接][Link 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、字符串里最后一个单词的长度 ##

[牛客链接][Link 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、验证一个字符串是否是回文 ##

[力扣链接][Link 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、字符串相加 ##

[力扣链接][Link 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;
        }
    };

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

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

--------------------

## 总结 ##

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

[ba68c80b5765481fb645f3452bf9b77b.png_pic_center]: https://img-blog.csdnimg.cn/ba68c80b5765481fb645f3452bf9b77b.png#pic_center
[Link 1]: https://leetcode.cn/problems/reverse-only-letters/description/
[Link 2]: https://leetcode.cn/problems/first-unique-character-in-a-string/
[Link 3]: https://www.nowcoder.com/practice/8c949ea5f36f422594b306a2300315da?tpId=37&&tqId=21224&rp=5&ru=/activity/oj&qru=/ta/huawei/question-ranking
[Link 4]: https://leetcode.cn/problems/valid-palindrome/description/
[Link 5]: https://leetcode.cn/problems/add-strings/