五百人建站_无极在线观看_凡科网站建设_seo优化广告

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

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] * num1int 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