C++初阶：string类相关练习题

1. 字符串相加

1. 题目信息：
   
2. 题目连接：
   字符串相加

class Solution 
{
public:
    string addStrings(string num1, string num2) 
    {
        int ent = 0;
        int count1 = 0;
        int count2 = 0;
        string sum;

        auto it1 = num1.rbegin();
        auto it2 = num2.rbegin();

        while(it1 < num1.rend() || it2 < num2.rend())
        {
            if(it1 < num1.rend())
            {
                count1 = *it1 -'0';
            }

            if(it2 < num2.rend())
            {
                count2 = *it2 - '0';
            }
            
            count1 = count1 + count2 + ent;
            ent = count1 / 10;
            count1 %= 10;

            sum.push_back(count1 + '0');
            count1 = 0;
            count2 = 0;
            if(it1 < num1.rend())
            {
                it1++;
            }

            if(it2 < num2.rend())
            {
                it2++;
            }
        }

        if(ent)
        {
            sum.push_back(ent + '0');
        }

        auto it3 = sum.begin();
        auto it4 = sum.end() - 1;
        while(it3 < it4)
        {
            swap(*it3,*it4);
            it3++;
            it4--;
        }

        return sum;
    }
};

2. 反转字母

1. 题目信息：
   
2. 题目连接：
   反转字母

class Solution 
{
public:
    string reverseOnlyLetters(string s) 
    {
        //快排hoare法单趟
        string ret(s);
        int left = 0;
        int right = ret.size() - 1;
        while(left < right)
        {
            while(left < right && !isalpha(ret[right]))
            {
                right--;
            }

            while(left < right && !isalpha(ret[left]))
            {
                left++;
            }

            swap(ret[left], ret[right]);
            left++;
            right--;
        }

        return ret;
    }
};

3. 字符串中唯一字母

1. 题目信息：
   
2. 题目连接：
   字符串中唯一字母
3. 思路：暴力求解

class Solution 
{
public:
    int firstUniqChar(string s) 
    {
        for (int i = 0; i < s.size(); i++)
        {
            int flag = 1;
            //暴力查找
            for(int k = 0; k < s.size();)
            {
                if(k == i)
                {
                    k++;
                    continue;
                }

                //漏掉前面的字符
                if(s[i] == s[k])
                {
                    flag = 0;
                    break;
                }

                k++;
            }

            //找到存在唯一字符
            if (flag)
            {
                return i;
            }
        }

       return -1;

    }
};

4. 字符串中最后一个单词

1. 题目信息：
   
2. 题目链接：
   字符串最后一个单词的长度

int main() 
{
    string str;
    //遇到' '字符不停读取，一次读取一行
    getline(cin, str);
    int cur = str.length() - 1;
    int i = 0;
    while(str[cur] != ' ' && cur >= 0)
    {
        cur--;
        i++;
    }

    cout << i;

    return 0;
}

5. 验证回文串

1. 题目信息：
   2. 题目链接：
   验证回文串

class Solution 
{
public:
    bool isPalindrome(string s) 
    {
        string copy_s(s);

        auto e = copy_s.begin(); 
        while(e < copy_s.end())
        {
            if(*e >= 'A' && *e <= 'Z')
            {
                *e -= 'A' - 'a';
            }

            if((*e < 'a' || *e > 'z') && (*e < '0' || *e > '9'))
            {
                //迭代器失效，漏掉一个位置
                copy_s.erase(e);
            }
            else
            {
                e++;
            }
        }
        //reverse
        //isalnum字符是否为大小写字母或者数字
        //tolower转小写 toupper转大写
        //islower isupper
        auto it1 = copy_s.begin();
        auto it2 = copy_s.rbegin();

        while(it1 < copy_s.end())
        {
            if(*it1 != *it2)
            {
                return false;
            }
            it1++;
            it2++;
        }

        return true;
    }
};

6. 反转字符II

1. 题目信息：
   
2. 题目链接：
   反转字符II
3. 思路：一次向后遍历2k个字符，字符数大于k个逆置前k个，不足2k个整体逆置

class Solution 
{
public:
    string reverseStr(string s, int k) 
    {
        string rs(s);
        int len = rs.length();
        for(int i = 0; i < len; i += 2 * k)
        {
            reverse(rs.begin() + i, rs.begin() + min(i + k, len));
        }

        return rs;
    }
};

7. 反转字符串中的单词

1. 题目信息：
   
2. 题目链接：
   反转字符串中的单词

class Solution 
{
public:
    string reverseWords(string s) 
    {
        string rs(s);
        int n = rs.length();
        int count = 0;
        for(int i = 0; i < n; i++)
        {
            if(rs[i] == ' ')
            {
                reverse(rs.begin() + count, rs.begin() + i);
                count = i + 1;
            }

            if(i == n - 1)
            {
                reverse(rs.begin() + count, rs.end());
            }
        }

        return rs;
    }
};

8. 字符串相乘

1. 题目信息：
   
2. 题目链接：
   字符串相乘
3. 思路：模拟乘法步骤

class Solution 
{
public:
    string addStrings(string num1, string num2)
    {
        int ent = 0;
        int count1 = 0;
        int count2 = 0;
        string sum;

        auto it1 = num1.rbegin();
        auto it2 = num2.rbegin();

        while (it1 < num1.rend() || it2 < num2.rend())
        {
            if (it1 < num1.rend())
            {
                count1 = *it1 - '0';
            }

            if (it2 < num2.rend())
            {
                count2 = *it2 - '0';
            }

            count1 = count1 + count2 + ent;
            ent = count1 / 10;
            count1 %= 10;

            sum.push_back(count1 + '0');
            count1 = 0;
            count2 = 0;
            if (it1 < num1.rend())
            {
                it1++;
            }

            if (it2 < num2.rend())
            {
                it2++;
            }
        }

        if (ent)
        {
            sum.push_back(ent + '0');
        }

        auto it3 = sum.begin();
        auto it4 = sum.end() - 1;
        while (it3 < it4)
        {
            swap(*it3, *it4);
            it3++;
            it4--;
        }

        return sum;
    }

    string multiply(string num1, string num2)
    {
        //特殊处理
        if(num1 == "0" || num2 == "0")
        {
            return "0";
        }

        //模拟乘法的过程
        int size1 = num1.size();
        int size2 = num2.size();
        string ret;
        //num1 乘 num2
        for (int i = size1 - 1; i >= 0; i--)
        {
            string tran;
            int ent = 0;
            int part1 = num1[i] - '0';
            int k = i;
            for (int j = size2 - 1; j >= 0; j--)
            {
                //对齐
                while(k < size1 - 1)
                {
                    tran.push_back('0');
                    k++;
                }

                int part2 = num2[j] - '0';

                int sum = part1 * part2 + ent;

                int bit = sum % 10;
                ent = sum / 10;

                tran.push_back(bit + '0');
            }

            //处理进位
            if (ent)
            {
                tran.push_back(ent % 10 + '0');
                ent /= 10;
            }

            reverse(tran.begin(), tran.end());

            ret = addStrings(ret, tran);
        }

        return ret;
    }
};