1、最长公共前缀 - 力扣(LeetCode)
思路:
- 解法一:两两比较字符串
- 解法二:比较每一个字符串的同一位
- 图解:
- 代码:
java">class Solution {public String longestCommonPrefix(String[] strs) {String ret = strs[0];for(int i = 1; i < strs.length; i++){//调用方法,两两比较ret = commonStr(strs[i],ret);}return ret;}public String commonStr(String str1, String str2){int i = 0;//进行比较while(i < Math.min(str1.length(),str2.length()) && str1.charAt(i) == str2.charAt(i)){i++;}return str1.substring(0,i);} }
java">public String longestCommonPrefix(String[] strs) {int n = strs.length;for(int i = 0; i < strs[0].length(); i++){//以第一组的字符串为基准char tmp = strs[0].charAt(i);//判断每一组的字符串for(int j = 1; j < n; j++){//如果后面的字符串长度刚好等于基准的 i ,或者不相等就返回if(i == strs[j].length() || strs[j].charAt(i) != tmp){//返回截取的基准return strs[0].substring(0,i);}}}//说明基准就是最长公共前缀return strs[0];}
2、最长回文子串 - 力扣(LeetCode)
思路:
- 从中心开始向右向左遍历,其中需要考虑子串长度为奇数和偶数的情况
- 代码:
java">public String longestPalindrome(String s) {int n = s.length();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.charAt(left) == s.charAt(right)){left--;right++;}if(right - left - 1 > len){len = right - left - 1;begin = left + 1;}//偶数情况,i+1left = i;right = i+1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}if(right - left - 1 > len){len = right - left - 1;//此时left和right的位置都是不合法的位置,需要各自回退begin = left + 1;}}return s.substring(begin,begin + len);}
3、二进制求和 - 力扣(LeetCode)
思路:
- 对两个字符串从后往前相加操作,模2,然后再除2更新t,最后将字符串反转就是结果了
- 代码:
java">public String addBinary(String a, String b) {int len1 = a.length() - 1;int len2 = b.length() - 1;int t = 0;StringBuffer ret = new StringBuffer();while(len1 >= 0 || len2 >= 0 || t != 0){if(len1 >= 0){//加完就向前一个t += a.charAt(len1--) - '0';}if(len2 >= 0){t += b.charAt(len2--) - '0';}//拼接最终结果ret.append((char)('0' + (char)(t % 2)));//更新t的值t /= 2;}return ret.reverse().toString();}
4、字符串相乘 - 力扣(LeetCode)
思路:
- 首先将两个字符翻转,便于模拟乘法操作
- 然后再无进位相乘然后再相加,最后处理进位
- 其中相加的位置就是 i + j 位置,数组的长度就是 两个字符串的长度减去1(99 * 99,长度就是2+2-1 = 3)
- 代码:
java">public String multiply(String num1, String num2) {int m = num1.length();int n = num2.length();int[] tmp = new int[m + n - 1];//1、翻转字符串char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray(); char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray(); //2、进行无进位相乘、相加操作for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){//每一位循环都相加tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');}}//3、处理进位int cur = 0;int t = 0;StringBuffer ret = new StringBuffer();while(cur < m + n - 1 || t != 0){if(cur < m + n - 1){t += tmp[cur++];}ret.append((char)((char)(t % 10) + '0'));t /= 10;}//4、处理前导0while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0'){ret.deleteCharAt(ret.length()-1);}return ret.reverse().toString();}