Leetcode之string

前言

本篇整理了一些关于string类题目的练习, 希望能够学以巩固.

博客主页: 酷酷学!!! 点击关注~

---

1. 字符串相加

题目思路:
本题为大数运算类型题目, 不能用于处理大整数的库, 但可以使用一般的算术运算, 我们进行模拟, 首先依次取出每个数字的最后一位,进行加法运算, 并且将值分为进位和数值, 第一次的进位next = 0 , 这里只有当num1和num2都结束才能结束循环, 例如下面999999999+1, 如果其中一个数字已经结束, 则在高位补0, 并且将每一次的值追加到答案字符串, 循环结束, 如果进位还有值, 也追加到结束字符串, 最后逆置字符串.

参考代码:

class Solution {
public:string addStrings(string num1, string num2) {int end1 = num1.size() - 1;int end2 = num2.size() - 1;string str;int next = 0;while (end1 >= 0 || end2 >= 0) {int x1 = end1 >= 0 ? num1[end1] - '0' : 0;int x2 = end2 >= 0 ? num2[end2] - '0' : 0;int x = x1 + x2 + next;next = x / 10;x = x % 10;str += (x + '0');end1--;end2--;}if (next == 1) {str += '1';}reverse(str.begin(), str.end());return str;}
};

---

2. 仅仅反转字母

题目思路:

首先题目要求仅仅反转字符, 字母包括大写字母和小写字母, 其余位置不动, 那么我们就需要先判断什么元素需要反转, 首先判断是否为字母, 定义双指针, 如果相遇则结束, 遇到字母开始进行位置交换, 之后进行下一轮交换.

参考代码:

class Solution {
public:bool isZm(char c){if((c <= 'z'&& c>='a')||(c <= 'Z' && c>= 'A')){return true;}else{return false;}}string reverseOnlyLetters(string s) {int begin = 0;int end = s.size() - 1;while(begin < end){if(!isZm(s[begin])){begin++;}if(!isZm(s[end])){end--;}if(isZm(s[begin])&&isZm(s[end])){char tmp = s[begin];s[begin] = s[end];s[end] = tmp;begin++;end--;}}return s;}
};

---

3. 字符串中的第一个唯一字符

题目思路:

首先题目给出了条件, 仅包含小写字母, 我们可以采用计数排序的思想, 将出现的字母次数记录下来, 之后重新遍历字符串, 然后找到第一次出现一次的字符串, 这里需要注意对应的下标.

参考代码:

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

4. 字符串最后一个单词的长度

题目思路:

首先题目指出, 字符串以空格分隔, 并且不以空格结尾, 可以使用字符串的成员函数, 从后往前寻找, 找到空格的位置, 即为最后一个字符串的分割位置, 使用成员函数substr进行字符串分割, 从pos+1位置,不传第二个参数默认到字符串结尾, 随后输出字符串长度即可.

参考代码:

#include <iostream>
#include<string>
using namespace std;int main() {string s;cin>>s;size_t pos = s.rfind(' ');string s2;s2 = s.substr(pos+1);cout<<s2.size()<<endl;
}

---

5. 验证回文串

题目思路:

首先题目中给出所需要判断回文的为大小写字母以及数字, 不区分大小写, 正反读都一样, 即为回文串, 那么我们可以直接先将大写字母转化为小写字母, 接着定义双指针, 从头尾遍历, 相遇结束, 如果是字母和数字则判断下标位置的字符是否相同, 如果相同即为回文.

参考代码:

class Solution {
public:bool isZm(char c){if((c>='a'&&c<='z')||(c<='9'&&c>='0')){return true;}return false;}bool isPalindrome(string s) {for(int i = 0 ; i < s.size() ; ++i){if(s[i]<='Z'&&s[i]>='A'){s[i] += 32;}}int begin = 0;int end = s.size()-1;while(begin<end){while(!isZm(s[begin])){begin++;}while(!isZm(s[end])){end--;}if(s[begin]==s[end]){begin++;end--;}else{return false;}}return true;}
};

6. 反转字符串Ⅱ

题目思路: 首先题目要求每2k个字符, 若这段区间少于k个字符, 则全部反转, 若大于或等于k个字符, 则反转前k个字符, 于是乎我们进行模拟实现, 首先将字符串划分为每次2k的小区间, 判断此区间如果不是字符串结尾则反转前k个, 若是字符串结尾, 则判断最后一个区间是否小于k个字符, 如果最后剩余的字符个数小于k, 则全部反转, 如果大于, 则反转前k个.

参考代码:

class Solution {
public:string reverseStr(string s, int k) {int size = s.size();//min()里面接受参数为变量for(int i = 0; i< s.size(); i+= 2*k){reverse(s.begin()+i,s.begin()+min(i+k,size));}return s;}
};

---

7. 反转字符串的单词Ⅲ

题目思路:

本题没有良好的区间划分, 我们不能用上题的思路进行求解, 首先题目要求反转字符串的单词, 那我们需要找到每个单词, 遍历字符串, 找到字符串分割符, 然后取出单词的区间, 将字符依次进行交换, 完成反转, 控制i的位置并维护这段区间, 将单词进行反转.

参考代码:

class Solution {
public:string reverseWords(string s) {int i = 0;while(i<s.size()){int start = i;while(i<s.size() && s[i] != ' '){i++;}int begin = start;int end = i - 1;while(begin < end){swap(s[begin++] , s[end--]);}while(i < s.size() && s[i] == ' '){i++;}}return s;}
};

---

8. 字符串相乘

题目思路:

模拟数字乘法, 如果其中有一个为0直接返回0, 然后取出依次乘数的最后一位将结果范围底数和进位, 分别进行运算, 再依次取出被乘数, 但是在运算过程中, 除了最后一个数字相乘时, 其他都需要补0, 并将结果尾插到字符串中, 然后进行反转, 每一次躺求的结果进行加法, 可以根据我们实现加法的方法 , 最后返回结果.

参考代码:

class Solution {
public:string multiply(string num1, string num2) {string ans = "0";if (num1 == "0" || num2 == "0") {return "0";}int m = num1.size(), n = num2.size();for (int i = n - 1; i >= 0; i--) // 相乘多少次{int add = 0;string cur; // 记录每趟相乘结果for (int j = n - 1; j > i; j--) {cur.push_back(0);}int y = num2[i] - '0';for (int j = m - 1; j >= 0; j--) {int x = num1[j] - '0';int product = x * y + add;cur.push_back(product % 10);add = product / 10;}if (add != 0)cur.push_back(add);reverse(cur.begin(), cur.end());for (auto& c : cur) {c += '0';}ans = Stringadd(cur, ans);}return ans;}string Stringadd(string& num1, string& num2) {int i = num1.size() - 1, j = num2.size() - 1;int add = 0;string ansl;while (i >= 0 || j >= 0 || add) {int x = i >= 0 ? num1[i--] - '0' : 0;int y = j >= 0 ? num2[j--] - '0' : 0;int result = x + y + add;ansl.push_back(result % 10);add = result / 10;}for (auto& c : ansl) {c += '0';}reverse(ansl.begin(), ansl.end());return ansl;}
};

---

9. 打印日期

题目思路:

自一月开始, 如果天数小于当前月份最大天数, 则直接格式化输出, 如果天数大于当前月份最大天数, 则减去当前月份的天数, 进入下一个月份, 这里需要判断闰年, 如果为闰年, 则天数为29天.

参考代码:

#include <iostream>
using namespace std;int main() {int year,count;while (cin >> year >> count) { // 注意 while 处理多个 caseint months[12] = {31,28,31,30,31,30,31,31,30,31,30,31};if((year%4==0 && year % 100 !=0)||year % 400 ==0){months[1] = 29;}for(int i = 0;i < 12 ;i++){if(count <= months[i]){printf("%04d-%02d-%02d\n", year, i + 1, count);break;}else{count -= months[i];}}}
}

---

完