【算法】字符串

个人主页 ： zxctscl

如有转载请先通知

题目

• 1. 14. 最长公共前缀
• • 1.1 分析
  • 1.2 代码
  • 2. 5. 最长回文子串
  • • 2.1 分析
    • 2.2 代码
    • 3. 67. 二进制求和
    • • 3.1 分析
      • 3.2 代码
      • 4. 43. 字符串相乘
      • • 4.1 分析
        • 4.2 代码

          1. 14. 最长公共前缀

          1.1 分析

          从第一个字符串开始两两比较，把比较相同的字符部分更新到一个存放目前相同字符的ret中，然后把ret继续向后面的字符串比较，继续更新ret就行。得注意一下，如果在比较中长度超过了那两个字符中叫小的一个，那么就这组比较就结束，换下一组来继续比较。

          1.2 代码

          class Solution {public:
              string longestCommonPrefix(vector& strs) { string ret=strs[0];
               for(int i=1;i int j=0;
                 while(j 
          2. 5. 最长回文子串
           
          2.1 分析
           
          回文串有个特点，就是从中间扩展它的两边是对称的。
          利用中心扩展算法，固定完中间位置后，用两个指针一个在走左边，一个走右边，如果两个指针执行的字符是一样的，就移动，一直到指针指向的字符不同，或者一个指针越界。
          但是这里得分两种情况，如果回文串为奇数，这个方法是正确的；但是如果为偶数，把右边的中间位置加1，此时左右指针在同时移动的时候才是正确的。
           
          总之就是，先固定一个中心点，然后从中心点开始向两边扩展，注意奇数长度以及偶数长度都需要考虑。
           
          题目要的是最长回文子串，比较一下长度之后，更新一下最大的长度。
           
          2.2 代码
           
          class Solution {public:
              string longestPalindrome(string s) { int begin=0,len=0,n=s.size();
                  for(int i=0;i int left=i,right=i;//奇数
                      while(left>=0&&right left--;right++;
                      }
                      if(right-left-1>len)
                      { begin=left+1;
                          len=right-left-1;
                      }
                      
                       left=i,right=i+1;//偶数
                       while(left>=0&&right left--;right++;
                      }
                      if(right-left-1>len)
                      { begin=left+1;
                          len=right-left-1;
                      }
                  }
                  return s.substr(begin,len);
              }
          };
           
          3. 67. 二进制求和
           
          3.1 分析
           
          模拟的竖式计算的步骤，如果相加等于2，那么就进1，然后将这个字符取模就加到要返回的结果中，一直到两个字符串都结束。但是结果是与题目要的是相反的，所以得将得到字符串逆置。
           
          3.2 代码
           
          class Solution {public:
              string addBinary(string a, string b) { string ret;
                  int t=0;
                  int cur1=a.size()-1,cur2=b.size()-1;
                  while(cur1>=0||cur2>=0||t)
                  { if(cur1>=0) t+=a[cur1--]-'0';
                     if(cur2>=0)t+=b[cur2--]-'0';
                     ret+=t%2+'0';
                     t/=2;
                  }
                 reverse(ret.begin(),ret.end());
                 return ret;
              }
          };
           
          4. 43. 字符串相乘
           
          4.1 分析
           
          如果直接按照竖式计算来的话，思路是很简单的，但是代码不容易写，得处理进位和高位相乘要补上0，还得处理前导0和计算顺序，很多细节。
          所以可以换一种方式，采用无进位相加。
          把每一个位置的值相乘之后，先不进位，把每次计算的结果放在一个数组里面，最后再来处理进位。
          这里得先把两个字符串逆置,再无进位相乘相加，然后处理进位，最后处理前导0。
           
          4.2 代码
           
          class Solution {public:
              string multiply(string num1, string num2) { int m=num1.size(),n=num2.size();
                reverse(num1.begin(),num1.end());
                reverse(num2.begin(),num2.end());
                vector tmp(m+n-1);
                //无进位相乘相加
                for(int i=0;i for(int j=0;j tmp[i+j]+=(num1[i]-'0')*(num2[j]-'0');
                  }
                }
                //处理进位
                int cur=0,t=0;
                string ret;
                while(cur if(cur1&&ret.back()=='0')ret.pop_back();
                reverse(ret.begin(),ret.end());
                return ret;
              }
          };
           
          有问题请指出，大家一起进步！！！