当前位置：首页 > article >正文

【LeetCode热题100】字符串

article 2024/11/19 2:46:04

本篇博客记录了关于字符串相关的几道题目，包括最长公共前缀、最长回文子串、二进制求和、字符串相乘。

//解法1
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        string ret = strs[0];
        for(int i = 1 ; i < strs.size() ; i++)
            ret = FindCommon(ret, strs[i]);
        return ret;
    }
    string FindCommon(const string& s1, const string& s2)
    {
        int i = 0;
        while(i < min(s1.size(),s2.size()) && s1[i] == s2[i]) i++;
        return s1.substr(0, i);
    }
};
//解法2
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        for(int i = 0 ; i < strs[0].size() ; i++)
        {
            char tmp = strs[0][i];
            for(int j = 1 ; j < strs.size() ; j++)
            {
                if(i == strs[j].size() || strs[j][i] != tmp) return strs[0].substr(0,i);
            }
        }
        return strs[0];
        
    }
};

题目分析：本道题有两种思路：

第一种方法是两个进行查找最长公共子串，最后返回这两个字符串的公共子串，再把这个公共子串和下一个字符串进行查找，返回这两个字符串的公共子串，依次查找下去。

第二种方法是同时比较所有子串，先比较第一个字符串的第一个字母和剩下字符串的第一个字母，然后再比较第一个字符串的剩下字符串的第二个字母，依次类推。

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int begin = 0, len = 0;
        int 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);
        
    }
};

题目分析：这道题是要找回文子串，而回文子串是对称的，我们可以利用这样的特性来结题。把这个字符串的每个字母依次作为中心点i，如果回文子串是奇数个，那么先让right和left都指向i，判断s[left]和s[right]是否相等，如果相等，那么让left--，right++；如果回文子串是偶数个，让left指向i，right指向i+1（或者让left指向i-1，right指向i），判断s[left]和s[right]是否相等，如果相等，那么让left--，right++。

class Solution {
public:
    string addBinary(string a, string b) 
    {
       string ret; 
       int cur1 = a.size() - 1, cur2  = b.size() - 1;
       int tmp = 0;
       while(cur1 >= 0 || cur2 >= 0 || tmp)
       {
            if(cur1 >= 0) tmp += a[cur1--] - '0';
            if(cur2 >= 0) tmp += b[cur2--] - '0';
            ret += tmp%2 + '0';
            tmp /= 2;
       }
       reverse(ret.begin(), ret.end());
       return ret;
    }
};

题目分析：这道题就是模拟相加过程，把两个字符串的最低位加到tmp变量上，然后%2得到最后结果的倒数第一位，然后tmp/2是进位，然后再去把倒数第二位都加到tmp，再%2最后结果的倒数第二位，然后tmp/2是进位，依次这样下去。

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        //1.处理为0的情况
        if(num1 == "0" || num2 == "0") return "0";
        string ret;
        int m = num1.size();
        int n = num2.size();
        vector<int> tmp(m + n - 1, 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        //2.先无进位相乘后相加
        for(int i = 0; i < n ; i++)
        {
            for(int j = 0 ; j < m ; j++)
            {
                tmp[i + j] += (num2[i] - '0')*(num1[j] - '0');
            }
        }
        //3.处理进位
        int cur = 0 , t = 0;
        while(cur < m + n -1 || t)
        {
            if(cur < m + n -1) t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

题目分析：有两种思路，无论哪种思路，都要将两个字符串先逆序，这样下标0、1、2代表的是真实列竖式运算从低位到高位的顺序：1）模拟列竖式计算，string ret = "0"，string tmp，tmp存的是每次相乘后的结果，然后把tmp累加到ret上，再计算下一位相乘的结果，再累加到ret上。要注意几个细节：高位相乘的时候要补上0，处理为0的情况。