C++：OJ练习(每日练习系列)

比眉伴天荒 2024-02-17 12:09 20阅读 0赞

![2bb454ddefd943acbfe94a7bfea810d0.png][]

## 编程题： ##

### 题一：字符串相加 ###

[415. 字符串相加 - 力扣（LeetCode）][415. _ - _LeetCode]

![1f4cd45934fc47c8b7276def1edf6630.png][]

#### 思路一： ####

**第一步：**需要**获取字符串的两个尾节点下标**；

**第二步：**创建用于**记录进位数、获得的字符串的变量**；

**第三步：**只要**有进位或还有数没有加完继续循环**：**利用三目运算：有符号+符号，无符号+0**；

**第四步：**最后将得到的**字符串逆置**，就是需要的结果。

class Solution {
    public:
        string addStrings(string num1, string num2) 
        {
            //获取字符串的尾节点
            int it1 = num1.size() - 1;
            int it2 = num2.size() - 1;
            //记录进位数
            int count = 0;
            //获得的字符串
            string s1 = "";
            //有进位或还有数没有加完
            while(it1 >= 0 || it2 >= 0 || count != 0)
            {
                //三目运算：有符号+符号，无符号+0
                int x = it1 >= 0 ? num1[it1] - '0' : 0;
                int y = it2 >= 0 ? num2[it2] - '0' : 0;
                int n = x + y + count;
                int num = n % 10;
                count = n / 10;
                s1.push_back(num + '0');
                --it1;
                --it2;
            }
            //得到的是逆置的字符串
            reverse(s1.begin(),s1.end());
            return s1;
        }
    };

### 题二：验证回文串 ###

[125. 验证回文串 - 力扣（LeetCode）][125. _ - _LeetCode]

![72fb3d3123634e158e239b3b7d9654dc.png][]

#### 思路一： ####

**第一步：遍历字符串将大写改小写并删除非字母和数字的字符；**

**第二步：判断对称比较字符是否相等；**

class Solution {
    public:
        bool isPalindrome(string s) 
        {
            //遍历字符串将大写改小写并删除非字母和数字的字符
            for(int i = 0; i < s.size();i++)
            {
                s[i] = tolower(s[i]);
                if((s[i] < 'a' || s[i] > 'z') && (s[i] < '0' || s[i] > '9'))
                {
                    s.erase(i,1);
                    i--;
                }
            }
            //对称比较字符是否相等
            int left = 0;
            int right = s.size() - 1;
            while(left < right)
            {
                if(s[left] != s[right])
                {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    };

### 题三：反转字符串 ###

[541. 反转字符串 II - 力扣（LeetCode）][541. _ II - _LeetCode]

![0ceb4080a69f492aa4fe95935c473971.png][]

#### 思路一： ####

**第一步：**分别**创建记录起始位置和末尾位置的节点**；

**第二步：**只要**后面还有字符就继续执行循环**：**1.计数2k个字符，就反转这2k字符中的前k个字符；2.字符小于2k但大于或等于k个，则反转前k个字符；3.剩余字符少于k个，将剩余字符全部反转。**

**特别注意：reverse是逆置左闭右开的区间！！！**

class Solution {
    public:
        string reverseStr(string s, int k) 
        {
            //分别创建记录起始位置和末尾位置的节点
            string::iterator cur = s.begin();
            string::iterator tail = s.end();
            //只要后面还有字符就继续执行
            while(cur != tail)
            {
                //计数2k 个字符，就反转这2k字符中的前k个字符
                if(cur + 2*k <= tail)
                {
                    //需要注意reverse是左闭右开的区间
                    reverse(cur,cur + k );
                    cur += 2*k;
                }
                //字符小于2k但大于或等于k个，则反转前k个字符
                else if(cur + k <= tail)
                {
                    reverse(cur,cur + k );
                    break;
                }
                //剩余字符少于k个，将剩余字符全部反转
                else
                {
                    reverse(cur,tail);
                    break;
                }
            }
            return s;
        }
    };

#### 思路二： ####

**反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。**

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

### 题四：反转字符串的单词 ###

[557. 反转字符串中的单词 III - 力扣（LeetCode）][557. _ III - _LeetCode]

![263c2f9c717c4523a9431251ca4c7b66.png][]

#### 思路一： ####

**第一步：**定义**变量left、right从第一个字符开始，以及tail来记录字符串长度**；

**第二步：**如果**没有超过字符串长度就继续循环**：**1.定位一个单词的区间、2。逆置(我们这里用的是下标访问，无法使用reverse来进行逆置)、3.再排除空格的影响；**

void my_reverse(string& s1,int left,int right)
    {
        while(left < right)
        {
            swap(s1[left],s1[right]);
            ++left;
            --right;
        }
    }
    class Solution {
    public:
        string reverseWords(string s) 
        {
            int left = 0;
            int right = 0;
            int tail = s.size();
            //没有超过字符串长度就循环
            while(right < tail)
            {
                //定位一个单词的区间
                while(s[right] != ' ' && s[right] != '\0')
                {
                    ++right;
                }
                //逆置
                my_reverse(s,left,right-1);
                //排除空格的影响
                while(s[right] == ' ')
                    ++right;
                left = right;
            }
            return s;
        }
    };

### 题五：字符串相乘 ###

[43. 字符串相乘 - 力扣（LeetCode）][43. _ - _LeetCode]

![82e410421fe14f77b41bc68cb5abd6e8.png][]

#### 思路一： ####

**第一步**：**创建：1.得到最后的结果的s1、2.count用于记录进位、enter用于记录进行了几次乘加；**

**第二步：while循环中1.n1做为被乘数，n2做为乘数，tmp用于记录当前的乘积**，**2.再内置一个while循环实现乘法，3.将所得结果逆置，4.对每一次的乘积进行当前结果求和**(**这里直接在题意字符串相加的基础上缩小了相加的范围实现了乘加)；**

**第三步：**最后：**判断：如果字符串全为‘0’，则返回“0”，否则正常输出计算所得的字符串。**

class Solution {
    public:
    string addStrings(string num1, string num2,int enter) 
        {
            //获取字符串的尾节点
            int it1 = num1.size() - 1 -enter;
            int it2 = num2.size() - 1;
            //记录进位数
            int count = 0;
            //获得的字符串
            string s1 = "";
            //有进位或还有数没有加完
    		while(enter--)
    		{
    			s1.push_back(num1[it1+enter+1]);
    		}
            while(it1 >= 0 || it2 >= 0 || count != 0)
            {
                //三目运算：有符号+符号，无符号+0
                int x = it1 >= 0 ? num1[it1] - '0' : 0;
                int y = it2 >= 0 ? num2[it2] - '0' : 0;
                int n = x + y + count;
                int num = n % 10;
                count = n / 10;
                s1.push_back(num + '0');
                --it1;
                --it2;
            }
            //得到的是逆置的字符串
            reverse(s1.begin(),s1.end());
            return s1;
        }
     string multiply(string num1, string num2) 
        {
            //得到最后的结果的s1
            string s1;
            //count用于记录进位
            int count = 0;
            //enter用于记录进行了几次乘加
            int enter = 0;
            //n1做为被乘数
            int n1 = num1.size() - 1;
            while(0 <= n1)
            {
                //n2做为乘数
                int n2 = num2.size() - 1;
                //tmp用于记录当前的乘积
    			string tmp;
                //实现乘法
                while(0 <= n2 || count != 0)
                {
    				int x = n1 >= 0 ? num1[n1] - '0' : 0;
    				int y = n2 >= 0 ? num2[n2] - '0' : 0;
                    int num = x * y + count;
                    count = num / 10;
                    tmp.push_back((num % 10) + '0');
                    --n2;
                }
                //所得结果逆置
                reverse(tmp.begin(),tmp.end());
                //对每一次的乘积进行当前结果求和
                s1 = addStrings(s1,tmp,enter);
                ++enter;
    			--n1;
            }
            //判断：如果字符串全为‘0’，则返回“0”
            int nn = s1.size() ;
            while(nn--)
            {
                if(s1[nn] - '0' != 0)
                {
                    return s1;
                }
            }
            return "0";
        }
    
    };

**本人实力有限可能对一些地方解释和理解的不够清晰，可以自己尝试读代码，或者评论区指出错误，望海涵！**

**感谢大佬们的一键三连！ 感谢大佬们的一键三连！ 感谢大佬们的一键三连！**

![c90de1178d0345148d109f22b2169307.jpeg][]

[2bb454ddefd943acbfe94a7bfea810d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/c68bfa9d9f6241418055c1bcc48f16e3.png
[415. _ - _LeetCode]: https://leetcode.cn/problems/add-strings/
[1f4cd45934fc47c8b7276def1edf6630.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/78bab921583b4907aefa921c095d1aa7.png
[125. _ - _LeetCode]: https://leetcode.cn/problems/valid-palindrome/description/
[72fb3d3123634e158e239b3b7d9654dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/1fcca2845a854dfe9468984958956a9d.png
[541. _ II - _LeetCode]: https://leetcode.cn/problems/reverse-string-ii/submissions/485384853/
[0ceb4080a69f492aa4fe95935c473971.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/be6a9878b6444beaa679bfc9e82f0fd3.png
[557. _ III - _LeetCode]: https://leetcode.cn/problems/reverse-words-in-a-string-iii/submissions/485519801/
[263c2f9c717c4523a9431251ca4c7b66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/e081ed5262f24c93bb951491c3f88b78.png
[43. _ - _LeetCode]: https://leetcode.cn/problems/multiply-strings/
[82e410421fe14f77b41bc68cb5abd6e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/5fddcbd50a8e418f9afd647e2aa72c05.png
[c90de1178d0345148d109f22b2169307.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/b68b210006dc4eb9a5713f6acfe47740.png