leetcode(四) 字符串专题

文章目录

• • 38.外观数列
  • 49.字母异位词分组 **
  • 151.翻转字符串里的单词 **
  • 165.比较版本号 ？？
  • 929.独特的电子邮件地址
  • 5.最长回文子串**
  • 6.Z字形变换
  • 3.无重复字符的最长子串 （双指针）
  • 208.实现Trie 树
  • 273.整数转化英文表示

38.外观数列

题意很简单就是每次对上一个字符串计数
不能用递归，一开始用爆栈了
就用两层循环更新答案

class Solution {
public:string countAndSay(int n) {string res="1";                //最终答案，初始化 为1for(int i=0;i<n-1;i++){        //输入n应当更新n-1次string ans;                //每次更新的字符串for(int j=0;j<res.size();){char key=res[j];         //标记int count=0;             //计数while(res[j]==key){      //循环到第一个不等于key的字符j++;count++;}ans+=to_string(count)+key;}res=ans;                  //替换}return res;}
};

49.字母异位词分组 **

这题是哈希表的应用
我们建立这样一个从string映射到vector< string >的哈希表
将每个字符串排好序之后对应的字符串作为一个key，存放到哈希表的string中，并将对应的值存放到key对应的vector中

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> res;unordered_map<string,vector<string>>  hash;for(auto str:strs){string key=str;                   sort(key.begin(),key.end());        //将映射的key进行排序hash[key].push_back(move(str));           //每个排完序相同的字符串都将存到一个key值的vector中  ,,使用move避免重新复制字符串，直接改变指针指向str}for(auto it:hash)res.push_back(move(it.second));  //vector存入res中return res;}
};

151.翻转字符串里的单词 **

这题要求翻转字符串中的单词，并且不准开额外的空间
基本的思路是先翻转字符串的每个单词，再翻转字符串整体，通过reverse函数，效果如下，即可实现整个字符串的翻转
具体做法是使用k，i，j三个指针，i，j先指向字符串的每个单词，使其先翻转，再使用s[k++]=s[i++]从头开始对s赋值（ij是前进指针，k是跟进指针）
要注意该题的空格在代码中的解决

class Solution {
public:string reverseWords(string s) {int k=0;                                //从s[0]开始赋值，避免开头有空格for(int i=0;i<s.size();i++){while(s[i]==' '&&i<s.size())i++;    //i前进到下一个不是空格的位置if(i==s.size())break;int j=i;while(s[j]!=' '&&j<s.size())j++;    //j前进到单词末尾，指向下一个空格reverse(s.begin()+i,s.begin()+j);   //翻转这个单词if(k)s[k++]=' ';                    //在每个单词结束加上一个空格，第一个除外，最后一个空格由于if(i==s.size())break也无法加入while(i<j)s[k++]=s[i++];}s.erase(s.begin()+k,s.end());      //收尾，删掉最后一个单词后面的空格   reverse(s.begin(),s.end());        //翻转整个字符串return s;}};

165.比较版本号 ？？

题目本身还是比较简单的，只不过在写法上需要点技巧和经验
思路：
小数点将每个字符串都分割成一段一段的数字，只要对应比较每一段数字大小就行。。这里用atoi函数转化成数字，手写也行
需要注意的是，如果两串分出的部分不一样多的话，（同长度的部分比较完依旧没有分出大小），那么继续比较，没有数的那个串看做是0就行了

• 使用的函数:
• substr(start,lenth), 截断字符串
• atoi(char*[]),字符数组转换成数字，需要传字符数组首地址
• c_str(null),将string转化成字符数组char* []并返回首地址

未解决：
while(x while(y

class Solution {
public:int compareVersion(string s1, string s2) {int i=0,j=0;while(i<s1.size()||j<s2.size()){int x=i,y=j;while(x<s1.size()&&s1[x]!='.')x++;    //每次找到一串数字的终点while(y<s2.size()&&s2[y]!='.')y++;int a= i==x?0:atoi(s1.substr(i,x-i).c_str());    //将每一段转化为数字，如果该段长度为0或者不存在则返回0int b= j==y?0:atoi(s2.substr(j,y-j).c_str());i=x+1,j=y+1;           //ij跳向'.'下一个位置if(a>b)return 1;if(a<b)return -1;}return 0;}
};

929.独特的电子邮件地址

思路：按照题目要求简化每一个所给的邮件地址，得到新的邮件地址加入哈希表中，最后返回哈希表元素个数（哈希表自带判重功能）

class Solution {
public:int numUniqueEmails(vector<string>& emails) {unordered_set<string> hash;     //无需映射的哈希表for(auto email:emails){int at=email.find('@');    //找到每个邮件地址@的位置string domain=email.substr(at+1);    //取出域名部分string name;for(auto it:email.substr(0,at)){     //简化本地名称部分if(it=='+')break;else if(it!='.')name+=it;        //去掉里面的'.'}string s=name+'@'+domain;          //构造简化后的邮件地址hash.insert(s);}return hash.size();}
};

5.最长回文子串**

该题使用暴力解法，直接枚举每一个字符，把他当做子串的对称中心点（如果最长回文子串是奇数长，则对称中心是一个点，偶数则是两个点）像两边延伸，找到最长的回文子串

class Solution {
public:string longestPalindrome(string s) {string  res;for(int i=0;i<s.size();i++){for(int m=i,n=i; m>=0 && n<s.size()&& s[n]==s[m]; m--,n++)     //找奇数对称最长串if(res.size()<n-m+1)res=s.substr(m,n-m+1);for(int m=i,n=i+1; m>=0 && n<s.size() && s[n]==s[m]; m--,n++)   //找偶数对称最长串if(res.size()<n-m+1)res=s.substr(m,n-m+1);}return res;}
};

6.Z字形变换

y总做法是找规律，感觉也就这样。。
首先我们按规律找寻每一行元素的下标，然后依次添进结果字符串res中
首先第一行和最后一行都是公差为2*（n-1）的数列
其余的行分别是交错的两个公差为2*（n-1）等差数列
他们的开头分别是i，2*（n-1）-i

class Solution {
public:string convert(string s, int n) {if(n==1)return s;string res;for(int i=0;i<n;i++){                //列举当前行if(!i||i==n-1)                   //列举如果是第一行或者最后一行的情况for(int j=i;j<s.size();j+=2*(n-1))res+=s[j];    else{    //列举其他行（每行有两个等差数列）for(int j=i,k=2*(n-1)-i;j<s.size()||k<s.size();j+=2*(n-1),k+=2*(n-1)){if(j<s.size())res+=s[j];       //如果枚举在范围内，则加上该字符if(k<s.size())res+=s[k];}}}return res;}
};

附上自己的写法，想法很简单，就是按照要求吧字符串依次放进二维向量里再读出来，

• 二维向量初始化没有给定长度，所以报了空指针（？）

class Solution {
public:string convert(string s, int numRows) {int n=s.size();vector<vector<char>>  res(numRows);int i=0;while(i<n){for(int j=0;j<numRows&&i<n;j++,i++)   //填满一列res[j].push_back(s[i]); for(int k=numRows-2;k>0&&i<n;k--,i++)  //斜着向上填res[k].push_back(s[i]);}string ans;for(auto items:res){                        //二维向量遍历for(auto item:items){cout<<item<<" ";ans+=item;}}return ans;}
};

3.无重复字符的最长子串 （双指针）

思路：双指针算法

• 前指针i,后指针j
• 我们保证当前维护的子串（i,j）没有重复元素，当前子串不可能向前拓展（即i不能往前移动）
• 依靠哈希表来判断维护的区间是否出现重复元素
• 每次j向后移动，扩展最长子串，那么可能会出现重复的元素，为此需要不断向后移动i，直到满足没有重复元素为止
• 更新最大子串

ps:如何满足i所在位置是当前最大子串位置？只需要i从头开始行进即可，不需要额外判断

菜鸡(O(n²))写法

class Solution {
public:const int N=200;int lengthOfLongestSubstring(string s) {int res=0;int flag[N];for(int i=0;i<s.size();i++){            //外层循环n次，内层循环每次最多走n步，所以复杂度是O(n ^ 2)memset(flag,0,sizeof(flag));int j;for( j=i;j<s.size()&&!flag[s[j]];j++)flag[s[j]]=true;res=max(res,j-i);}return res;}
};

O(n)写法

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> hash;int res = 0;for (int i = 0, j = 0; j < s.size(); j ++ )   //时间复杂度：虽然是双重循环，但由于i最多总共只向后走n步，平均到每一层循环走一步，那么时间复杂度是O(n){hash[s[j]] ++ ;while (hash[s[j]] > 1) hash[s[i ++ ]] -- ;  //如果出现重复元素，让i往后走直到没有重复元素为止res = max(res, j - i + 1);}return res;}
};

208.实现Trie 树

目标是使用结构体的方式实现一个字典树，基础算法里实现过一个二维数组的Trie树，基本思路相同
首先初始化一个根节点root，根节点不存放数据，根节点存在26个子节点指针

• 插入：对于每个字符串，遍历插入树中，如果该节点不存在则初始化一个节点
  并将结尾Node的is_end赋值为true
• 查询：遍历当前字符串到其结尾，如果is_end存在则代表有该字符串存在
• 查询前缀：只要Trie树中存在前缀字符串即可

class Trie {
public:struct  Node{bool is_end;Node* son[26];Node(){is_end=false;for(int i=0;i<26;i++)son[i]=NULL;     }}*root;  //root指向结构体Node/** Initialize your data structure here. */Trie() {root=new Node();}/** Inserts a word into the trie. */void insert(string word) {auto p=root;for(auto s:word){int u=s-'a';if(!p->son[u])p->son[u]=new Node();   //如果子节点不存在则初始化一个节点p=p->son[u];}p->is_end=true;}/** Returns if the word is in the trie. */bool search(string word) {auto p=root;for(auto s:word){int u=s-'a';if(p->son[u])p=p->son[u];else return false;}return p->is_end;}/** Returns if there is any word in the trie that starts with the given prefix. */bool startsWith(string prefix) {auto p=root;for(auto s:prefix){int u=s-'a';if(p->son[u])p=p->son[u];else return false;}return true;}
};

273.整数转化英文表示

这题不注意写法确实麻烦的一批，看了一下好像也有拿递归写的也还不错，但还是这个容易理解一点
思路：转化为每三个一位每三个一位的数，并且逐段翻译，每段中间加上相应的计数（billion,million,thousand）

class Solution {
public://映射到字符串数组中string small[20]={"Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};string decade[10]={"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};string  big[4]={"Billion","Million","Thousand",""};string numberToWords(int num) {if(!num)return small[0];string res;for(int i=1000000000,j=0;i>0;i=i/1000,j++){   //从最高三位开始转换，每次转三位，最多四次int n=num/i;if(n)res+=helper(n)+big[j]+" ";num%=i;   }while(res.back()==' ')res.pop_back();   //删除最后字符串的多余空格 return res;}string helper(int n){                     //每段的三位数转化为英文string res;if(n>=100){res+=small[n/100]+" Hundred ";n=n%100;}if(!n)return res;if(n>=20){res+=decade[n/10]+" ";n=n%10;if(!n)return res;res+=small[n]+" ";}else res+=small[n]+" ";return res;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！