目录
一、14.最⻓公共前缀
题目链接：14.最⻓公共前缀
题目描述：
解题思路：
- 思路一：
-
- 我们直接两两求一下公共前缀，记录在ret字符串中，然后ret与后续继续求公共前缀，最后的ret就是结果
-
- 求公共前缀，我们就求一下在字符串中的公共前缀的最后一个字符 的下一个下标即可。
- 思路二：
-
- 我们就将第一个字符串作为基准，遍历字符串，每个字符再与字符串数组中剩下的字符串，对应下标的字符比较即可。
-
- 当超出某个字符串长度或者字符不同了，就可以返回了。
-
- 最后第一个字符串都遍历完了，还没找到，那么第一个字符串就是结果。
解题代码：
思路一：
//时间复杂度：O(m*n)
//空间复杂度：O(1)
class Solution {
public String longestCommonPrefix(String[] strs) {
//两两比较
String ret = strs[0];
for(int i = 1; i < strs.length; i++) {
ret = commonPrefix(ret, strs[i]);
}
return ret;
}
//返回两个字符串的公共前缀
public String commonPrefix(String s1, String s2) {
int last = 0;
while(last < s2.length() && last < s1.length() && s2.charAt(last) == s1.charAt(last)) last++;
return s1.substring(0,last);
}
}
思路一：
//时间复杂度：O(m*n)
//空间复杂度：O(1)
class Solution {
public 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];
}
}
二、5.最⻓回⽂⼦串
题目链接：5.最⻓回⽂⼦串
题目描述
解题思路：
- 中⼼扩散：从回⽂串的中⼼开始，往左读和往右读。从中⼼向两边扩展，如果两边的字⺟相同，我们就可以继续扩展；如果不同，我们就停⽌扩展。
- 我们还需要将回文子串的长度是奇数和偶数都要考虑。
解题代码：
//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public String longestPalindrome(String s) {
String ret = "";
for(int i = 0; i < s.length(); i++) {
//奇数长度
int left = i;
int right = i;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if(right - left - 1 > ret.length()) ret = s.substring(left+1, right);
//偶数长度
left = i;
right = i+1;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if(right - left - 1 > ret.length()) ret = s.substring(left+1, right);
}
return ret;
}
}
三、67.⼆进制求和
题目链接：67.⼆进制求和
题目描述：
题目解析：
- 简单的竖式加法而已
解题思路：
- 模拟竖式加法过程，从后向前遍历两个字符串，
- 定义一个变量，将对应位的相加，和对2取余就是结果对应位的数字，考虑进位就是除以2
- 当两个字符串都遍历结束，并且变量为0，就得到了结果逆序后的字符串了
- 最后逆序返回就可以
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public String addBinary(String a, String b) {
StringBuffer ret = new StringBuffer();
int cruA = a.length() - 1;
int cruB= b.length() - 1;
int tmp = 0;
while(cruA >= 0 || cruB >= 0 || tmp != 0) {
if(cruA >= 0) tmp += a.charAt(cruA--) - '0';
if(cruB >= 0) tmp += b.charAt(cruB--) - '0';
ret.append((char)(tmp % 2 + '0'));
tmp /= 2;
}
return ret.reverse().toString();
}
}
四、43.字符串相乘
题目链接：43.字符串相乘
题目描述：
题目解析：
- 就相当于每个字符串就是一个数，让我们求乘积，乘积也放在字符串中。
解题思路：
- 还是使用小学的竖式运算规则，
- 但是有所不同的是，我们先不进位（就是如果3*8=24，先不进2），在最后的结果中来进位。
- 我们竖式计算过程是从末尾先开始的，所以我们先将两个字符串逆序。
- 通过竖式计算过程，每个位计算结果在结果中的下标就是原来两个字符串的下标之和
- 在进位的时候，我们只需要将每位数字 ，除以10的结果记录在一个变量中，然后这个变量就是进位的数。
- 现在得到的结果还可能会有前导零：前导零就是指152 * 0 = 000 这就有两个前导零。
- 由于现在的结果是逆序的，所以从最后开始检验，有就删，注意极端情况全为0的时候，还要保留一位。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public String multiply(String num1, String num2) {
int[] arr = new int[num1.length() + num2.length()-1];
//逆序
char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
//无进位相乘，相加
for(int i = 0; i < n1.length; i++) {
for(int j = 0; j < n2.length; j++) {
arr[i+j] += (n1[i] - '0') * (n2[j] - '0');
}
}
// 进位
int tmp = 0;
int cur = 0;
StringBuffer ret = new StringBuffer();
while(cur < arr.length || tmp > 0) {
if(cur < arr.length) tmp += arr[cur++];
ret.append((char)(tmp % 10 + '0'));
tmp /= 10;
}
//处理前导零
while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') ret.deleteCharAt(ret.length() - 1);
return ret.reverse().toString();
}
}