感觉很久不做题了, 本身自己虽然就没水平就是啦哈哈~ 那下面分享几道最近写的几道题, 都很简单, 是关于"字符串"的, 只不过会稍微用到一点代码能力就是了, 算是比较基础的题目.

1.最长公共区域(⭐⭐⭐ 代码)

1.1 题目描述

题目链接: 题目链接
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

1.2 题目思路

这个题目有两种思路, 一种是两两字符串求公共区域的一种思路. 另一种呢就是一下求出一列字符串的公共字符来.

方法1: 两两求公共区域

先说第一种:

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) 
{
    //两两字符串求公共前缀
    int i = 0;
    string ret = strs[0];
    string temp = "";
    for(auto e : strs)
        {
            int i = 0;
            temp = e;
            while(i < ret.size() && i < temp.size())
                {
                    if(temp[i] == ret[i])
                    {
                        i++;
                    }
                    else
                    {
                        break;
                    }
                }
            ret = ret.substr(0, i);
        }

    return ret;

}
};

在这里求两两字符串的时候, 可以根据不同语言特性进行自定义哈, 上面是属于CPP的方式, 而对于Java, Python也都有自己各自的方式, 具体要根据不同的语言特性来处理这个地方.

方法2: 统一求公共区域

第二种方式: 统一比较方式求一列字符串公共的字符
就是我们直接比较一众字符串的一列, 如果相同就下一列, 如果不同就返回. 老师的做法好处就是进行特殊判断, 如果想要不特殊判断, 那么就得算最短字符串长度也可以.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        // 统一比较的方法
        int minlength = 201;
        for(auto e : strs)
        {
            int size = e.size();
            minlength = minlength < size ? minlength : size;
        }

        int i = 0;
        for(i = 0; i < minlength; i++)
        {
            char t = strs[0][i];
            for(int j = 1; j < strs.size(); j++)
            {
                if(t != strs[j][i]) 
                {
                    return strs[0].substr(0, i);
                }
            }
        }

        return strs[0].substr(0, i);
    }
};

2. 最长回文子串(⭐⭐⭐ len = right - left - 1)

2.1 题目描述

2.1 题目思路

方法1: 暴力求解

暴力求解很简单, 我们搞两个指针, 从左向右依次固定, 组合出N*N种子串, 然后验证是不是回文串, 找出最大的回文串即可.
当然, 时间复杂度达到了O(N^3)

方法2: 中心拓展算法

这个其实就是暴力求解的一种优化. 我们定义一个指针, 依次遍历字符串, 作为中心点, 然后定义两个指针, 一左一右, 然后去比较, 相等left–,right++, 不相等就停止, 看看是不是在当前来看算长的回文串, 长的话记录一下即可.

class Solution {
public:
string longestPalindrome(string s) 
{
    //思路: 中心拓展算法
    int n = s.size();
    int begin = 0;
    int len = 0;

    for(int i = 0; i < n; i++) // 遍历每一个中心点
        {
            //奇数中心拓展
            int left = i;
            int right = i;
            while(left >= 0 && right <= n && s[left] == s[right])
                {
                    left--, 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++;
                }//到了这个地方, 实际上left和right所指的地方已经不相等了
            if(right - left - 1 > len)//更新一下
            {
                begin = left + 1;
                len = right - left - 1;
            }
        }

    return s.substr(begin, len);
}
};

3. 二进制求和(⭐⭐⭐⭐ 大数相加类型)

3.1 题目描述

题目链接: Link

3.2 题目思路

class Solution {
public:
string addBinary(string a, string b) 
{
    int cur1 = a.size() - 1;
    int cur2 = b.size() - 1;
    int t = 0; //进位

    string ret;

    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;
}
};

这个地方有个细节: 就是我们先把结果都加到ret字符串中, 这样跟结果字符串肯定是相反的(因为正常是头插), 到最后直接全反过来就行, 因为头插时间复杂度比较高.

4. 字符串相乘(⭐⭐⭐ ⭐⭐ 编码)

4.1 题目描述

题目链接: Link

4.2 题解思路

思路1: 模拟乘法过程

class Solution {
public:
string multiply(string num1, string num2) 
{
    //特殊处理
    if(num1 == "0" || num2 == "0") return "0";

    int size_num1 = num1.size();
    int size_num2 = num2.size();
    string ret;

    for(int i = size_num2 - 1; i >= 0; i--)
        {
            string a_string_ret; //num2[i] * num1
            int add = 0; //进位

            //补0:
            for(int pad_zero_num = size_num2 - 1; pad_zero_num > i; pad_zero_num--)
                {
                    a_string_ret.push_back('0');
                }

            //取乘数
            int x = num2[i] - '0'; // 要注意把字符变成整数哦

            for(int j = size_num1 - 1; j >= 0; j--)
                {
                    int y = num1[j] - '0';
                    int product = x * y + add;
                    add = product / 10;

                    a_string_ret.push_back((product % 10) + '0'); // 入结果的时候记得要变成字符哦
                }
            while(add != 0)
                {
                    a_string_ret.push_back((add % 10) + '0'); // 入结果的时候记得要变成字符哦
                    add /= 10;
                }
            reverse(a_string_ret.begin(), a_string_ret.end());

            ret = add_two_string(ret, a_string_ret);
        }

    return ret;
}

string add_two_string(const string& ret, const string& a_string_ret)
{
    int size_ret = ret.size();
    int size_a_string_ret = a_string_ret.size();
    int add = 0;
    int cur1 = size_ret - 1;
    int cur2 = size_a_string_ret - 1;
    string ans;

    while(cur1 >= 0 | cur2 >= 0 | add != 0)
        {
            int x = cur1 >= 0 ? ret[cur1--] - '0' : 0;
            int y = cur2 >= 0 ? a_string_ret[cur2--] - '0' : 0;

            int product = x + y + add;
            add = product / 10;
            ans.push_back((product % 10) + '0');  入结果的时候记得要变成字符哦
        }
    reverse(ans.begin(), ans.end());

    return ans;
}
};

思路2: 先全乘起来再进位

class Solution {
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0") return "0";
        int size_num1 = num1.size();
        int size_num2 = num2.size();
        vector<int> ret(size_num1 + size_num2, 0);

        //乘起来
        for (int i = size_num2 - 1; i >= 0; i--)
        {
            int x = num2[i] - '0';
            for (int j = size_num1 - 1; j >= 0; j--)
            {
                int y = num1[j] - '0';
                ret[i + j + 1] += x * y;
            }
        }

        //进位
        for (int i = size_num1 + size_num2 - 1; i > 0; i--)
        {
            ret[i - 1] += ret[i] / 10;
            ret[i] = ret[i] % 10;
        }

        //判断位数
        int index = ret[0] == 0 ? 1 : 0;
        //开始数组转字符串
        string ans;
        while (index < size_num1 + size_num2)
        {
            ans.push_back(ret[index] + '0');
            index++;
        }

        return ans;
    }
};

5. 总结

我们简单总结一下这种类型的题目, 这种字符串的题目不会单独出题, 而是跟其他算法一块考, 考的比较多的就是模拟, 或者在暴力求解的思路上进行优化. 总体来说, 这种大部分都需要一点编码能力.

---

EOF