【算法】字符串算法技巧系列

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

引入：字符串相关算法技巧

1：字符串转数组

2：子字符串

3：数组转字符串

4：字符串拼接方式

5：返回字符串指定下标的字符

6：StringBuilder/StringBuffer用法

7：Integer类型转换为String类型

一：最后一个单词的长度

二：最长公共前缀

三：最长回文子串（ex）

四：二进制求和

五：找字符串中第一个匹配项的下标

六：字符串相乘

引入：字符串相关算法技巧

1：字符串转数组

String a = “abcdefg” char[] a1= a.toCharArray()

//将字符串数组转换为字符数组（常用）

.charAt(下标0~length()-1)

//返回下标对应的字符。字符串长度是length() 数组没有括号

2：子字符串

.substring()：

截取字符串中介于两个指定下标之间的字符，第一个字符下标为0

注意：(就是小写)两个参数：截取的结果,不包括结束位置的字符。一个参数：从起始位置至字符串末尾的字符串

3：数组转字符串

String.ValueOf(数组名称);

4：字符串拼接方式

方式一：

String ret = " ";

ret += num[i];

方式二：

5：返回字符串指定下标的字符

字符串的名字.charAt(下标);

6：StringBuilder/StringBuffer用法

(1) StringBuilder性能更好，StringBuffer线程更安全，两者方法一样

（2）append追加字符，字符拼接，

（3）计算长度 .length()

（4）删除指定位置的元素 .deleteCharAt()

（5）转化为字符串 .toString()

（6）反转字符 .reverse();返回类型是StringBuffer或StringBuilder

StringBuilder下的toString方法，把拼接的内容以字符串的形式输出。

7：Integer类型转换为String类型

Integer.toString(num1 - num2);

一：最后一个单词的长度

58. 最后一个单词的长度

这个边界问题，老生常谈了，非常重要啊！！老弟

class Solution {public int lengthOfLastWord(String s) {int n = s.length();StringBuffer buffer = new StringBuffer();for (int i = n - 1; i >= 0;) {while(i >= 0 && s.charAt(i) == ' '){i--;}while (i >= 0 && s.charAt(i) != ' ') {buffer.append(s.charAt(i));i--;}break;}return buffer.length();}
}

二：最长公共前缀

14. 最长公共前缀

要退出两层for循环的话，可以很巧妙的引入一个标志符作为参考。同样也可以在for循环中返回结果，女少~！！

class Solution {public String longestCommonPrefix(String[] strs) {String str = strs[0];if (str == "") {return "";}int n = strs.length;// 数组的长度int m = strs[0].length();// 第一个字符串的长度StringBuffer buffer = new StringBuffer();int target = 0;for (int i = 0; i < m; i++) {// i表示第一个字符串中字符的下标char ch = strs[0].charAt(i);for (int j = 1; j < n; j++) {// j表示数组中第几个字符串String curStr = strs[j];int curStrLen = curStr.length();if (i > curStrLen - 1 || curStr.charAt(i) != ch) {// 当前下标的比较// target = -1;// break;return buffer.toString();}}// if(target == -1){// break;// }buffer.append(ch);}return buffer.toString();//如果for循环中没有返回的话，说明所有元素都是相等的，直接返回即可}
}

三：最长回文子串（ex）

心得感悟：这道题我的奇偶性分情况思路是正确的，但是边界情况处理的跟一坨*一样，尤其是while循环条件的书写，思路清晰是最重要的，在就是子字符串算法工具还需要熟悉，这道题到是不难，中心扩展算法还是很好理解的。

下面的板书画图是我一开始的思路，大体方向正确，但代码冗杂

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n == 1) return s;int ret = 1;  // 最大回文长度String str = s.substring(0, 1);  // 初始化结果字符串int left = 0, right = 0;for (int cur = 0; cur < n; cur++) {  // 从第一个字符开始// 检查以 cur 为中心的奇数长度回文left = cur; right = cur;while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {left--;right++;}int curLen = right - left - 1;if (curLen > ret) {ret = curLen;str = s.substring(left + 1, right);  // 截取回文子串}// 检查以 cur 和 cur+1 为中心的偶数长度回文left = cur; right = cur + 1;while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {left--;right++;}curLen = right - left - 1;if (curLen > ret) {ret = curLen;str = s.substring(left + 1, right);  // 截取回文子串}}return str;}
}

四：二进制求和

思路正确但是麻烦并且数据大了会溢出，（超过long64位时）

class Solution {public String addBinary(String a, String b) {long num1 = 0 , num2 = 0;char[] aa = a.toCharArray();char[] bb = b.toCharArray();// 将2进制转化为10进制for(char ch : aa){num1 = 2 * num1 + switchNum(ch);}for(char ch : bb){num2 = 2 * num2 + switchNum(ch);}long ret = num1 + num2;if(ret == 0) return "0";StringBuffer buffer = new StringBuffer();while(ret != 0){buffer.append(ret % 2 == 1 ? '1' : '0');ret = ret / 2;}     return buffer.reverse().toString();}public int switchNum(char ch){switch (ch){case '1':return 1;case '0':return 0;    }return -1;  }
}

思路二：能行得通，但罗里吧嗦

class Solution {public String addBinary(String a, String b) {int len1 = a.length() , len2 = b.length();int cur1 = len1-1 , cur2 = len2-1;int tmp = 0;StringBuilder builder = new StringBuilder();while(cur1 >= 0 || cur2 >= 0){if(cur1 >= 0){tmp += a.charAt(cur1) == '0' ? 0 : 1;cur1--;}if(cur2 >= 0){tmp += b.charAt(cur2) == '0' ? 0 : 1;cur2--;}if(tmp == 0){builder.append('0'); }else if(tmp == 1){builder.append('1');tmp = 0;}else if(tmp == 2){builder.append('0');tmp = 1;}else if(tmp == 3){  //穷举法（包含进位的数字）builder.append('1');tmp = 1;}}if(tmp == 1){builder.append('1');//处理最前端还有进位的情况}return builder.reverse().toString();}
}

五：找字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

class Solution {public int strStr(String haystack, String needle) {String str1 = haystack, str2 = needle;char ch = str2.charAt(0);char[] s1 = str1.toCharArray();int n = s1.length, m = str2.length() , ret = -1;if (n < m) return -1;boolean sign = false;for (int i = 0; i <= n - m;) {if (s1[i] != ch) i++;if (i == n - m) {//单独处理一下最后长度一样的字符串n-m是剩下的长度上限，下标上限就是n-m这种情况单独处理sign = str1.substring(i).equals(str2);} else if (i < n - m) {sign = str1.substring(i, i + m).equals(str2);}if (sign == true) {ret = i;break;} else {i++;}}return ret;}
}

六：字符串相乘

43. 字符串相乘

tip:被这道题恶心坏了，首先这道题关键在于，下标的确定，关键步骤一，确定好nums3数组，关键步骤二遍历nums3数组确定进位，模拟相加。

这道题暴露出来：

整型转字符—— (char)(nums3[j]%10 + '0') 重点重点！！！

字符转整型——str1.charAt(i)-'0'

class Solution {public String multiply(String num1, String num2) {if(num1.charAt(0) == '0' || num2.charAt(0) == '0') return "0";int n1 = num1.length() , n2 = num2.length();int n3 = n2 + n1 - 1;int[] nums3 = new int[n3];StringBuilder builder1 = new StringBuilder(num1);StringBuilder builder2 = new StringBuilder(num2);String str1 = builder1.reverse().toString();String str2 = builder2.reverse().toString();for(int i = 0 ; i < n1 ; i++){for(int j = 0 ; j < n2 ; j++){nums3[i+j] += (str1.charAt(i)-'0')*(str2.charAt(j)-'0');}}StringBuilder builder3 = new StringBuilder();int tmp = 0;for(int j = 0 ; j < n3 ; j++){tmp = nums3[j]/10;//进位的builder3.append((char)(nums3[j]%10 + '0'));if(j < n3-1){nums3[j+1] += tmp;}if(j == n3-1 && nums3[j] >= 10){builder3.append((char)(tmp + '0'));}}String ret = builder3.reverse().toString();return ret;}
}

七：验证回文串

125. 验证回文串

这道题暴露出来的问题，大小写转换还不太熟悉，对于字符数组leetcode不支持进行foreach循环遍历

class Solution {public boolean isPalindrome(String s) {if(s == "") return true;//先转化为纯的字符串int len = s.length();StringBuilder builder = new StringBuilder();for(int i = 0 ; i < len ; i++){char ch = s.charAt(i);if((ch >= 'a' && ch <='z') || (ch >= 'A' && ch <='Z') || (ch >= '0' && ch <='9') ){builder.append(ch);}}String str = builder.toString().toLowerCase();int n = str.length();int left = 0 , right = n-1;while(left >= 0 && right <= n-1){if(n % 2 == 0){left = (0 + n - 1)/2;right = left+1;while(left >= 0 && right <= n-1){if(str.charAt(left) == str.charAt(right)){left--;right++;}else{return false;}}}if(n % 2 == 1){left = (0 + n - 1)/2;; right = left;while(left >= 0 && right <= n-1){if(str.charAt(left) == str.charAt(right)){left--;right++;}else{return false;}}}}return true;}
}

八：判断子序列

392. 判断子序列

class Solution {public boolean isSubsequence(String s, String t) {int n1 = s.length() , n2 = t.length();if(n1 > n2) return false;int cur1 = 0 , cur2 = 0;while(cur1 < n1 && cur2 < n2){if(cur1 < n1 && cur2 < n2 && s.charAt(cur1) == t.charAt(cur2)){cur1++;cur2++;}else{cur2++;}}if(cur1 == n1 && cur2 <= n2){return true;}return false;}
}