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

算法学习（十）—— 字符串

article 2024/11/6 20:25:47

关于字符串操作

这类题一般是和其它算法合起来，比如模拟，双指针，动态规划或者回溯等，所以字符串相关的题目类型一般是非常非常丰富的，这里我们选取几道经典的题目进行讲解

部分OJ题详解

14. 最长公共前缀

14. 最长公共前缀 - 力扣（LeetCode）

题目题意还是很简单的，就是返回单词的公共前缀，没有公共前缀就返回空，下面来分析下这道题：

解法一：两两比较，找公共前缀；假设有四个字符串，分成三组，每两组找公共前缀，然后再两个前缀再找公共前缀，最终结果就是所有字符串的公共前缀，这道题我们主要就是解决“如何找到两个字符串的公共前缀”，很简单，定义两个指针即可
解法二：统一比较；就是定义一个指针，然后一次性比较所有字符串的前缀，当有空或者有一个字符不一样，停止遍历，返回结果。

解法一：

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(string s1, string s2)
    {
        int i = 0;
        while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
        //i是遍历两个字符串的指针，所以i的大小必须小于等于最短的那个字符串，不然会越界访问
        return s1.substr(0, i);
    }
};

解法二：

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() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
        }
        return strs[0];
    }
};

5. 最长回文字串

5. 最长回文子串 - 力扣（LeetCode）

题目要我们找出一个字符串s中的最长回文字串，其中这个字串是一串连续的字串，下面我们来分析下这道题：

解法：中心扩展算法；这个算法的本质还是暴力枚举，但是这里是利用了回文串的特性来做枚举的，比正常枚举要快
我们先固定一个位置，假设为i，然后定义两个指针，向前向后移动，因为如果是回文，左边和右边的字符是对称的，所以指针移动的时候，如果指针指向的值相同，就继续移动，如果不一样了，记录结果
但是这样只能找奇数的回文字串，偶数的找不了，所以我们固定i，先left = right找奇数找一次，然后再right = left + 1，再找偶数找一次，就能把奇数偶数全找到
步骤：1，固定一个中心点 2，从中心开始，向两边扩展，奇数偶数各找一次

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int begin = 0, len = 0; 
        for(int i = 0; i < s.size(); i++) //依次枚举所有的中点
        {
            //先找奇数的扩展
            int left = i, right = i;
            while(left >= 0 && right < s.size())
            {
                if(s[left] == s[right])
                {
                    left--;
                    right++;
                }
                else
                    break;
            }
             if(right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
            //再做偶数的扩展
            left = i, right = left + 1;
            while(left >= 0 && right < s.size())
            {
                if(s[left] == s[right])
                {
                    left--;
                    right++;
                }
                else
                    break;
            }
            if(right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
        }    
        return s.substr(begin, len);
    }
};

67. 二进制求和

67. 二进制求和 - 力扣（LeetCode）

这个题目是一道经典的算法题，用到的算法是“高精度加法”，而同样的还是高精度减法，乘法和触发。而高精度顾名思义就是一个数实在是太大，平常的数据类型存不下，然后我们要对这种很大的数字进行运算，用到的算法就是“高精度运算”

下面我们来分析下这道题：

解法：模拟列竖式运算。这道题和我们链表章节的“两数相加”那个题目很相似，我们定义一个t = 0记录相加的结果，具体步骤和链表的“两数相加”很像：算法学习（八） —— 链表-CSDN博客

class Solution {
public:
    string addBinary(string a, string b) 
    {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
        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;
    }
};

43. 字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

这一题用到的就是我们上一题提到的“高精度乘法”这个算法，题目很简单，就是把字符串的值相乘，注意不能使用stoi和to_string等字符串整型转换函数，因为这时题目要求的，下面来解释下这道题：

解法一：模拟列竖式运算；步骤一：单独拿nums2的一位和num1相乘步骤而：再把所有的结果累加起来。
细节一：高位相乘的时候，要补0 细节二：处理前导0 细节三：注意计算结果的顺序（可以看到解法一思路很简单，但是细节很多很多，稍不注意就会出错，所以解法一的代码不太好写）
解法二：对解法一做优化 --> 五进位相乘再相加，最后处理进位
对于步骤②，我们可以搞一个数组int[m + n - 1] tmp，m是num1的程度，n是num2的长度，然后我们就可以直接相加，因为同一列算出来的数存进数组时，下标是一样的，可以直接相加
对于步骤③，就是处理进位，就是遍历一次数组，然后一边累加再放到最终字符串ret里
细节：处理前导零

解法一的代码太复杂就不写了，我们直接用解法二来写：

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        //解法二：无进位相乘然后相加，最后处理进位
        //1，准备工作
        reverse(num1.begin(), num1.end());    
        reverse(num2.begin(), num2.end()); //逆序是为了方便处理前导零
        int m = num1.size(), n = num2.size();
        vector<int> tmp(m + n - 1); //存储步骤②的结果，顺便实现相加

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

        //3，处理进位
        int cur = 0, t = 0; //cur遍历数组，t表示进位
        string ret; //存储最终结果
        while(cur < m + n - 1 || t != 0)
        {
            if(cur < m + n - 1) 
                t += tmp[cur++];
            ret += (t % 10) + '0';
            t /= 10;
        }

        //4，处理前导零
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

查看全文

http://www.kler.cn/a/382011.html