【算法】字符串

个人主页 ： 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<string>& strs) {
     string ret=strs[0];
     for(int i=1;i<strs.size();i++)
     {
       int j=0;
       while(j<min(ret.size(),strs[i].size())&&ret[j]==strs[i][j])j++;
       ret= ret.substr(0,j);
     }
     return ret;
    }    
    
};

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<n;i++)
        {
            int left=i,right=i;//奇数
            while(left>=0&&right<n&&s[left]==s[right])
            {
                left--;right++;
            }
            if(right-left-1>len)
            {
                begin=left+1;
                len=right-left-1;
            }
            
             left=i,right=i+1;//偶数
             while(left>=0&&right<n&&s[left]==s[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<int> tmp(m+n-1);

      //无进位相乘相加
      for(int i=0;i<m;i++)
      {
        for(int j=0;j<n;j++)
        {
            tmp[i+j]+=(num1[i]-'0')*(num2[j]-'0');
        }
      }

      //处理进位
      int cur=0,t=0;
      string ret;
      while(cur<m+n-1||t!=0)
      {
        if(cur<m+n-1)t+=tmp[cur++];
        ret+=t%10+'0';
        t/=10;
      }
      
      //处理前导0
      while(ret.size()>1&&ret.back()=='0')ret.pop_back();

      reverse(ret.begin(),ret.end());
      return ret;
    }
};

有问题请指出，大家一起进步！！！