LeetCode 数据结构基础勋章 - day5

小柴带你一起刷LeetCode题的第五天

字符串

415.字符串相加

解法：直接用stoi()函数，然后存进一个string对象中，记得反转就行。
有个缺点就是数据大了会“out of range”

classSolution{public:
    string addStrings(string num1, string num2){int n1 =stoi(num1);int n2 =stoi(num2);int n3 = n1 + n2;if(n3==0)return"0";
        string num3;while(n3){
            num3.push_back(n3%10+'0');
            n3 /=10;}reverse(num3.begin(),num3.end());return num3;}};

解法2：对它进行加法模拟。（把握好进位carry就行），模拟一位存一位，最后进行翻转就🆗了。

classSolution{public:
    string addStrings(string num1, string num2){int carry =0;
        string num3;int i = num1.size()-1, j = num2.size()-1;while(i>=0||j>=0||carry>0){int x =0, y =0;if(i>=0)
            x = num1[i--]-'0';if(j>=0)
            y = num2[j--]-'0';
            num3.push_back((x+y+carry)%10+'0');
            carry =(x+y+carry)/10;}reverse(num3.begin(),num3.end());return num3;}};

409.最长回文串

解法：利用哈希表统计字符串各个字符出现的总次数。根据回文子串的理解，左右相同字符对称，然后可以得到一个某字符可参与回文子串的关系式，字符个数/2*2，当出现次数为奇数的时候，那回文最长子串应该为奇数，可以先用关系式算出长度，然后如果出现字符个数为奇数的，再在最后的长度基础上加1。
代码如下：

classSolution{public:intlongestPalindrome(string s){if(s.size()==1)return1;
        unordered_map<char,int> mp;for(int i=0;i<s.size();++i)//统计该字符串中每个字符的个数
            mp[s[i]]++;int len =0;int odd =0;auto it = mp.begin();while(it!=mp.end()){if(it->second%2!=0){
                odd =1;}
            len += it->second - it->second%2;++it;}
        len += odd;return len;}};

290.单词规律

解法：题目要求满足一一对应，那相互之间对应就行了，先字符和单词对应，而后再拿单词与字符对应，这里是相互的，不能只对应一次，俩方有那种所属关系（像DR一样“一生只爱一人” 0.0 比如a对应b，c也对应b，但反过来b对应了俩，这就不满足一一对应了，不是题目所满足的规律）
我们可以先定义一个string对象，里面按顺序存字符串里的单词，然后再用哈希表去对应关系就行了。
代码如下：

classSolution{public:boolwordPattern(string pattern, string s){
        string ss[s.size()];int count =0;
        unordered_map<string,char> mp1;
        unordered_map<char,string> mp2;int i =0;for(int j =0;j<s.size();++j){if(s[j]==' '){
                ss[count++]= s.substr(i,j-i);
                i = j+1;}}
        
        ss[count++]= s.substr(i,s.size()-i);if(count!=pattern.size())//单词数和pattern中的字符数不相同则不匹配returnfalse;

        count =0;for(char ch:pattern){if(mp1.find(ss[count])==mp1.end())
            mp1[ss[count++]]= ch;elseif(mp1[ss[count++]]!=ch){returnfalse;}}
        count =0;for(char ch:pattern){if(mp2.find(ch)==mp2.end())
            mp2[ch]= ss[count++];elseif(mp2[ch]!=ss[count++]){returnfalse;}}returntrue;}};

763.划分字母区间

解法：题目要求一个字符最多只能出现在一个片段中，由片段和片段长度，这让小柴同学一下子想到了区间，我们只要把每个字符的片段区间存入到哈希表中，然后再转换成合并区间问题，合并区间问题我们可以排序然后再用双指针解题 56.合并区间（这个我一篇博客上有，在这篇博客的第二题）
当我们满足条件的区间都知道了，那接下来直接进行区间终端减初端+1就得出长度了，把答案都存入要返回的容器内，就简单解决了。

代码如下：

classSolution{public:
    vector<int>partitionLabels(string s){
        unordered_map<char,pair<int,int>> mp;//指出字符串中的字符出现的区间段for(int i=0;i<s.size();++i){if(mp.find(s[i])==mp.end()){
                mp[s[i]].first = i;
                mp[s[i]].second = i;}else{
                mp[s[i]].second =max(i,mp[s[i]].second);}}//转到合并区间问题  56.合并区间，先进行区间排序
        vector<pair<int,int>> vec;for(auto it = mp.begin();it!=mp.end();++it){
            vec.push_back(it->second);}sort(vec.begin(),vec.end(),[&](pair<int,int> a,pair<int,int> b){return a.first<b.first;});
        vector<int> answer;//存入片段长度，也就是合并完的区间长度//利用双指针，left表示这个区间段最小端，right表示最大端int left = vec[0].first;int right = vec[0].second;int i=1;while(i<vec.size()){if(vec[i].first<right)
            right =max(right,vec[i].second);elseif(vec[i].first>=right){
                answer.push_back(right-left+1);//更新区间初始阶段
                left = vec[i].first;
                right = vec[i].second;}if(i+1==vec.size())//没有下一个区间片段了，存入最后一个区间长度
            answer.push_back(right-left+1);++i;}return answer;}};

解法2：（每次看完官方答案，就觉得自己是个傻逼）贪心。我们需要一个片段，片段有初有尾，那我们可以记录片段的结尾索引。访问每一个字符串s的每一个字符，不断更新访问到的字符的结尾索引。
然后再次遍历字符串，不断更新访问顺序中字符的结尾索引，更新最大结尾索引，ends = max(end,ends)当访问到字符的end==ends时，就将ends-start+1存入容器，然后再更新start = ends+1，不断重复。。。

classSolution{public:
    vector<int>partitionLabels(string s){int len = s.size();int ch[26];//记录s中字符的片段结尾索引for(int i=0;i<len;++i){
            ch[s[i]-'a']= i;}

        vector<int> answer;int start =0;int ends =0;for(int i =0;i<len;++i){
            ends =max(ends,ch[s[i]-'a']);//这里的ch[s[i]-'a']就是endif(ends==i){
                answer.push_back(ends-start+1);
                start = ends +1;}}return answer;}};

其实这题解题关键就是发现题目是将s这个字符串分成片段，但总长度就s.size()那么多，想到区间问题。（其实我觉得那个for循环存入字符串结尾索引的那个地方挺好的，是我的话可能还会傻傻的搁那用max 0.0）