如何通过长尾关键词攻克所有string编程OJ题目？

本文共计4671个文字，预计阅读时间需要19分钟。

输入：一行文本描述

输出：描述中最后一个单词的长度 + 描述中最后一个单词的描述 + 计算字符串长度描述的最后一个单词的长度

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

描述

计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）

输入描述：

输入一行，代表要计算的字符串，非空，长度小于5000。

输出描述：

输出一个整数，表示输入字符串最后一个单词的长度。

题解思路：

主要是找到最后一个空格，再开始计数，那么如何找最后一个空格呢？可以用rfind，反向找第一个空格的下标位置，然后计算出最后一个单词的长度；另外一个思路是弄一个计数器count，对字符串进行遍历遇到空格就开始将计数器count记为0，不是空格就+1，那么总总能计算出最后一个单词的长度。

代码实现：

第一个版本：

//rfind #include<iostream> #include<string> using namespace std; int Calc_Word_Length(string &str) { if(str.empty()) return 0; int index = str.rfind(' '); if(index == string::npos) return str.size(); return str.size()-index-1; } int main() { string str; getline(cin, str); int len = Calc_Word_Length(str); cout<<len; return 0; }

第二个版本：

//计数器 #include <iostream> using namespace std; int main() { string a; getline(cin,a); int count=0; for(int i=0;i<a.size();i++) { if(a[i]==' ') { count=0; } else { count++; } } cout<<count<<endl; }

二、验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串s，如果它是回文串，返回true；否则，返回false。

题目先是要对字符串s进行过滤，只保留小写字母和数字，那么对字符串进行遍历，用string的成员函数isalnum，能判断一个字符是否是字母或者（十进制）数字，若为字母或者数字，则返回True(非0值)，否者返回False(0)，如果是字母或者数字再将用tolower函数将字母或者数字转为小写，数字会不变，大写字母就会变成小写，最后用自己定义的字符串s1接收，再将字符串s1再赋值给s，用reverse函数将s1进行翻转，再返回s是否等于s1，如果相等就是回文串，否者就不是。

class Solution { public: bool isPalindrome(string s) { string s1; for(int i=0;i<s.length();i++) { if(isalnum(s[i])) { s1+=tolower(s[i]); } } s=s1; reverse(s1.begin(),s1.end()); return s1==s; } };

三、541.反转字符串 II

给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。

• 如果剩余字符少于k个，则将剩余字符全部反转。
• 如果剩余字符小于2k但大于或等于k个，则反转前k个字符，其余字符保持原样。

这题相对来说比较棘手，如果每过2k去不断的判断然后再用计数器，那就程序很复杂，我们可以然后i每次都是走2k个，用reverse进行翻转，只要控制好翻转位置的开始和结尾，重点在控制结尾，如果i+k大于了len，那么就不能翻转到i+k的位置，这样会越界，这就是最后一次，只能到len这个位置。

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

四、557.反转字符串中的单词 III

给定一个字符串s，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

1.去不断的找空格，分割前后单词，对前面的单词进行翻转

2.应为通过找空格的话，最后一个单词是没有进行处理的，再对最后一个单词进行翻转

class Solution { public: string reverseWords(string s) { int len=s.length(); int start=0; for(int i=0;i<len;i++) { //通过i来找空格 if(s[i]==' ') { reverse(s.begin()+start,s.begin()+i); //跳过空格 start=i+1; } } //最后一个翻转一下 reverse(s.begin()+start,s.end()); return s; } };

五、43.字符串相乘（※）

给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

这题明确的说了不能用BigInteger 库进行大数相乘，如果将num1和num2先转化为int类型或者long类型再去×，一样的会出现溢出。这题主要的思想就是去模拟乘法，模拟乘法相对比较复杂，先对num1和num2进行翻转，我采用先将模拟乘法的每一步运算存到数组里面，再最后去判断是否大于9，进位等操作，还有就是前导可能为0，那么要判断一下最后一个数是否为0，如果为0，那么数组的实际长度为s1+s2-2，否者就是s1+s2-1，最后逆序输出存到字符串string里面，返回即可。

class Solution { public: string multiply(string num1, string num2) { if(num1 == "0" || num2 == "0") { return "0"; } reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int s1 = num1.length(), s2 = num2.length(); vector ans(s1+s2,0); for(int i = 0; i < s1; i++) { for(int j = 0; j < s2; j++) { ans[i + j] += (num1[i] - '0') * (num2[j] - '0'); } } for(int i = 0; i < s1 + s2; i++) { if(ans[i] > 9) { int t = ans[i]; ans[i] = t % 10; ans[i + 1] += (t / 10); } } int pos = (ans[s1 + s2 - 1] == 0 ? s1 + s2 - 2 : s1 + s2 - 1); string aa = ""; for(; pos >= 0; --pos) { aa += (ans[pos] + '0'); } return aa; } };

六、NC31第一个只出现一次的字符

在一个长为n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

数据范围：，且字符串只有字母组成。

要求：空间复杂度，时间复杂度

这题的要求是找出字符串中第一个只出现一次的字符，那么最理想的方法是用哈希表，记录所有字符出现的次数，再按字符串的顺序输出判断，当找到一个次数为1的就返回，循环结束没有就返回-1

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @return int整型 */ int FirstNotRepeatingChar(string str) { // write code here int v1[1000]={0}; for(int i=0;i<str.length();i++) { int val=str[i]-'0'; v1[val]++; } for(int i=0;i<str.length();i++) { int val=str[i]-'0'; if(v1[val]==1) { return i; } } return -1; } };

七、面试题 01.01.判定字符是否唯一

实现一个算法，确定一个字符串s的所有字符是否全都不同。

这里还是用的哈希表的思想，将字符串的所有字符映射到数组里面统计出现次数，再遍历一遍出现大于1的次数就返回false，循环判断结束就返回true这里int hs[1000]最好是定义到全局。

class Solution { public: int hs[1000]; bool isUnique(string astr) { for(int i=0;i<astr.length();i++) { int val=astr[i]-'0'; hs[val]++; } for(int i=0;i<astr.length();i++) { int val=astr[i]-'0'; if(hs[val]>=2) { return false; } } return true; } };

八、面试题 01.02.判定是否互为字符重排

给定两个由小写字母组成的字符串s1和s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

判断两个字符串是否为重排列，首先如果长度不相等那么肯定不是重排列，其次，两个字符串都可以经过变换变成另外一个字符串，那么他们的对应元素个数肯定是一样的这个可以用来判断是否为重排（哈希思想），再者既然他们可以互相转化那么就可以把他们都进行排序然后如果相等就是重排，不是就不是重排。

class Solution { public: bool CheckPermutation(string s1, string s2) { if(s1.length()!=s2.length()) { return false; } else { //将s1和s2进行排序 //如果排序相等那么就是互为字符重排 sort(s1.begin(),s1.end()); sort(s2.begin(),s2.end()); if(s1==s2) { return true; } else { return false; } } } };

九、面试题 01.04.回文排列

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

本题要判断是否为某一个回文的排列之一，那么传进来的字符串可能是回文也可能不是回文，我们通过观察发现回文字符出现奇数个的个数要么为0要么为1，不能超过2个，其他字符出现偶数个的个数没有要求，那么我们还是用哈希表映射一下，统计一下每一个字符出现的次数，再进行一次遍历统计奇数个出现的个数，当超过1，那么就肯定不是回文，直到循环结束，返回真。

class Solution { public: bool canPermutePalindrome(string s) { unordered_map<char,int> dic; for(auto x:s) { dic[x]++; } int count; for(auto k:dic) { if(k.second%2==1) { count++; if(count>1) { return false; } } } return true; } };

十、面试题 01.06.字符串压缩

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

这题给的string字符串有一定的特点，就是单个字符是会连续出现，而且出现过的字符还是可能会出现，就像示例1一样，所以不能用哈希表的方法，这样无法完成对后面又重复出现的字符完成字符的压缩。那么这里可以用到双指针的方法，先定于string s1用来接收这个压缩的答案，设两个指针i，j，只要i<s.length()，j要比i大1，应为j要和前面的一个进行比较防止越界，j不断比较计数，如果前后相等那么j++，当不相等了，这个循环结束，相同字符的长度就是j-i，再将长度用to_string()传进s1，再更新一下i，让i=j，此时的i又重新到另外一个新字符的第一个了。直到循环结束，判断s1的长度和s的长度，如果s1.length()>=s.length()，那么相等于压缩没有效果，返回s，否者就返回s1.

class Solution { public: string compressString(string S) { //记录每一个字符第一次出现的位置 //S为'1'的情况 if(S.length()==1) { return S; } string s1; int i=0; while(i<S.length()) { s1+=S[i]; int j=i+1; while(S[j-1]==S[j]&&j<S.length()) { j++; } //个数 int val=j-i; s1+=to_string(val); i=j; } if(s1.length()>=S.length()) { return S; } return s1; } };