此篇文章与大家分享字符串相关算法
如果有不足的或者错误的请您指出!
目录
- 1.最长公共前缀
- 1.1解析
- 1.2题解
- 2.最长回文子串
- 2.1解析
- 2.2题解
- 3.二级制求和
- 3.1解析
- 3.2题解
- 4.字符串相乘
- 4.1解析
- 4.2题解
1.最长公共前缀
题目:最长公共前缀
1.1解析
有两种比较方式,一种是两个两个比较,比较得出的最长公共前缀再和另一个比较;另一种就是统一比较,每次都比较所有字符串相同下标的字符,直到遇到不相同的字符或者某一串字符串已经遍历完了
本文采用的是第二种方法
1.2题解
class Solution {
public static String longestCommonPrefix(String[] strs) {
for(int i = 0; i < strs[0].length(); i++){
char ch = strs[0].charAt(i);//以第一串字符串为标准
for(int j = 1; j < strs.length; j++){
if(i >= strs[j].length() || ch != strs[j].charAt(i)){
return strs[0].substring(0,i);
}
}
}
return strs[0];//说明此时第一串字符就是最长公共前缀
}
}
2.最长回文子串
题目:最长回文子串
2.1解析
我们最容易想到的就是暴力解法,即对每一个子串都进行判断,但是时间复杂度来到了O(n^3)
但是实际上我们可以通过"回文字符串"的特点来进行判断
如图所示,我们用i来遍历字符串,同时定义left和right变量,left往左走,right变量往后走,每次都判断left下标的字符和right下标的字符是否相等,如果不相等或者left/right超过边界条件,那么此时left 和 right 就是以i下标字符为中心的最长回文字符串
但是实际上这只是考虑奇数个数字符的字符串,因此我们找完奇数情况后还要找偶数情况
如图所示,我们可以让left = i,right = i+1,按照上面的方法去寻找即可
此时时间复杂度降为O(n^2)
2.2题解
class Solution {
public String longestPalindrome(String s) {
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i++){
int l = i;
int r = i;
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
if(right - left < r - l){
right = r;
left = l;
}
l = i;
r = i+1;
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
if(right - left < r - l){
right = r;
left = l;
}
}
return s.substring(left+1,right);
}
}
3.二级制求和
题目:二级制求和
3.1解析
实际上无论是二进制、十进制还是其他进制相加,我们只要模拟出来我们常用的两数相加的过程就好了
对于二进制就是满2就进位,我们只需要在下一次计算的时候将上一次的进位加上就好了
思路比较简单,我们直接通过代码体现
3.2题解
class Solution {
public String addBinary(String a, String b) {
int len1 = a.length();
int len2 = b.length();
int cur1 = len1-1;
int cur2 = len2-1;
int tmp = 0;
StringBuilder ret = new StringBuilder();
while(cur1 >= 0 || cur2 >= 0 || tmp != 0){
if(cur1 >= 0){
tmp += a.charAt(cur1) - '0';
cur1--;
}
if(cur2 >= 0){
tmp += b.charAt(cur2) - '0';
cur2--;
}
ret.append(tmp % 2);
tmp /= 2;
}
return ret.reverse().toString();
}
}
4.字符串相乘
题目:字符串相乘
4.1解析
我们还是模拟我们现实中来两数相乘的计算方式
思路比较简单,但是这种解法细节还是很多的
(1)高位相乘的时候要补上0
即我们最后进行相加的时候,不是738和615相加,而是738和6150相加
(2)处理前导0
假设题目给我们是
但是我们只要的是一个0即可,我们就要处理前面的0
(3)字符串的顺序
对于这种大数的四则运算题目,我们最好都是将字符串先逆置过来,即将个位数放在下标为0的位置,这样我们每次进行计算的时候就直接从下标为1的位置开始计算,最后再将答案逆置即可
而第二种解法实际上是对第一种解法的优化
我们的处理策略是先不考虑进位,直接"无进位相乘"后,得到的结果再考虑进位
此时得到的答案和我们上面是完全一样的
但是这种方法给我们带来的很大的便利
首先我们每次相乘得到数应该存放到以一个数组里,即上面的6 12 18这些数字,假设我们的数组是tmp
而tmp数组的长度最大也就是m+n-1
那么我们会发现,实际上当下标为i的字符和下标为j的字符相乘后,得到的数字是放在 tmp 数组的 [i+j]下标位置的
这样一来我们就不再需要进行什么高位补0的操作了
同时,我们最后将每次相乘得到的数字进行相加的操作,无非就是tmp数组每次累加即可
4.2题解
class Solution {
public String multiply(String num1, String num2) {
int n1 = num1.length();
int n2 = num2.length();
int[] tmp = new int[n1+n2-1];
num1 = new StringBuilder(num1).reverse().toString();//原字符串逆置
num2 = new StringBuilder(num2).reverse().toString();
for(int i = 0; i < n1; i++){
for(int j = 0; j < n2; j++){
tmp[i+j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
}
}
int k = 0;
int t = 0;
StringBuilder ret = new StringBuilder();
//进位
while(k < tmp.length || t != 0){
if(k < tmp.length){
t += tmp[k++];
}
ret.append(t % 10);
t /= 10;
}
ret.reverse();
//处理前导0
k = 0;
while(k < ret.length()-1 && ret.charAt(k) == '0'){
k++;
}
return ret.substring(k);
}
}