目录

1. 最长公共前缀

1.1 算法原理

1.2 算法代码

2. 最长回文子串

2.1 算法原理

2.2 算法代码

3. 二进制求和

3.1 算法原理

 3.2 算法代码

4. 字符串相乘

4.1 算法原理 

4.2 算法代码

---

1. 最长公共前缀

. - 力扣（LeetCode）

1.1 算法原理

有以下两种策略:

1. 两两进行比较
2. 统一进行比较

这里需要注意比较的结束条件:

1. 当对任一字符串访问出现越界时, 应进行返回
2. 当两个字符串相同位置上的元素不相同时, 应进行返回.

1.2 算法代码

class Solution {/*** 两两比较* @param strs* @return*/public String longestCommonPrefix(String[] strs) {String ret = strs[0];for(int i = 1; i < strs.length; i++) {ret = findSame(ret, strs[i]);}return ret;}public String findSame(String s1, String s2) {String ret = "";int i = 0;while(i < Math.min(s1.length(), s2.length()) && s1.charAt(i) == s2.charAt(i))i++;return s1.substring(0, i);}/*** 统一比较* @param strs* @return*/public String longestCommonPrefix1(String[] strs) {StringBuilder ret = new StringBuilder();for(int i = 0; i < strs[0].length(); i++) {char ch = strs[0].charAt(i);for(String str : strs) {if(i >= str.length()) return ret.toString();if(str.charAt(i) != ch) return ret.toString();}ret.append(ch);}return ret.toString();}
}

---

2. 最长回文子串

. - 力扣（LeetCode）

2.1 算法原理

本题有动态规划和中心扩展算法两个解法, 动态规划的解法已经在动态规划的专题上展示了, 这里使用中心扩展算法:

1. 固定一个中心点
2. 从中心点开始, 向两边扩展(注意: 子串长度为奇数和偶数的情况都要考虑)

2.2 算法代码

class Solution {public String longestPalindrome(String s) {int n = s.length();String ret = "";for(int i = 0; i < n; i++) {// 遍历中心位置int left = i, right = i;// 奇数子串while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {left--;right++;}String str = s.substring(left + 1, right);ret = ret.length() >= str.length() ? ret : str;// 偶数子串left = i; right = i + 1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {left--;right++;}str = s.substring(left + 1, right);ret = ret.length() >= str.length() ? ret : str;}return ret;}
}

---

3. 二进制求和

. - 力扣（LeetCode）

3.1 算法原理

本题本质上是一到模拟题, 模拟高精度加法. 高精度, 就是指 数非常的大, 数据的长度非常的长.

1. 关键点在于遍历两个字符串
2. 使用 tmp 记录两个字符串相同的位置相加后的值
3. tmp % 2 => 结果值(二进制)
4. tmp / 2 => 相加所得的进位

 3.2 算法代码

class Solution {public String addBinary(String a, String b) {// 模拟高精度加法int cur1 = a.length() - 1;int cur2 = b.length() - 1;int tmp = 0;StringBuilder sb = new StringBuilder();while(cur1 >= 0 || cur2 >= 0 || tmp != 0) {if(cur1 >= 0) tmp += a.charAt(cur1--) - '0';if(cur2 >= 0) tmp += b.charAt(cur2--) - '0';sb.append(tmp % 2);tmp /= 2;}return sb.reverse().toString();}
}

---

4. 字符串相乘

. - 力扣（LeetCode）

4.1 算法原理 

解法: 无进位相乘再相加, 最后处理进位

1. 逆序字符串
2. 无进位相乘再相加(将得到的结果使用数组存起来, 放到 i+j 位置处)
3. 处理进位
4. 处理前导零

4.2 算法代码

class Solution {public String multiply(String num1, String num2) {// 解法: 无进位相乘再相加, 最后处理进位// 预处理int m = num1.length(), n = num2.length();int[] arr = new int[m + n - 1];StringBuilder s1 = new StringBuilder(num1);StringBuilder s2 = new StringBuilder(num2);s1.reverse();s2.reverse();// 无进位相乘再相加for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) arr[i + j] += (s1.charAt(i) - '0') * (s2.charAt(j) - '0');StringBuilder ret = new StringBuilder();int t = 0;int i = 0;// 处理进位while(i < arr.length || t != 0) {if(i < arr.length) t += arr[i++];ret.append(t % 10);t /= 10;}// 处理前导零ret.reverse();while(ret.charAt(0) == '0' && ret.length() > 1) ret.deleteCharAt(0);return ret.toString();}
}

---

END