字符串相关算法题
1. 字符串相加
给定两个字符串形式的非负整数
num1和num2，计算它们的和。
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
// 三个变量 carry i j：倒着来
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
// while循环条件 注意｜｜
while (carry == 1 || i >= 0 || j >= 0) {
// 注意"0"
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
// 老生长谈了
// 加的时候
str.append((x + y + carry) % 10);
// 注意进位
carry = (x + y + carry) / 10;
}
// 别忘了反转
// 反转
return str.reverse().toString();
}
}43. 字符串相乘
给定两个以字符串形式表示的非负整数
num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。>输入: num1 = "123", num2 = "456" >输出: "56088"
class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
if (len1 == 0 || len2 == 0) return "0";
int[] mul = new int[len1 + len2];
for (int i = len1 - 1; i >= 0; i--){
for (int j = len2 - 1; j >= 0; j--){
int n = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + mul[i + j + 1];
mul[i + j + 1] = n % 10;
mul[i + j] += n / 10;
}
}
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < len1 + len2 - 1 && mul[i] == 0) i++;
while (i < len1 + len2) sb.append(mul[i++]);
return sb.toString();
}
}2. 反转字符串(660)
写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
>输入：["h","e","l","l","o"] >输出：["o","l","l","e","h"]>输入：["H","a","n","n","a","h"] >输出：["h","a","n","n","a","H"]
// 利用while反转交换
class Solution {
public void reverseString(char[] s) {
int p1 = 0, p2 = s.length - 1;
while(p1 < p2){
swap(s, p1++, p2--);
}
}
public void swap(char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}3. 无重复字符的最长子串(2862)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
>输入: s = "abcabcbb" >输出: 3 >解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。>输入: s = "bbbbb" >输出: 1 >解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。>输入: s = "pwwkew" >输出: 3 >解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
// map 加双指针。map来保留索引，类似于滑动窗
Map<Character, Integer> map = new HashMap<>();
for (int i = 0, j = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}4.1、左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
>输入 >"abcXYZdef",3 >返回值 >"XYZdefabc"
public String LeftRotateString(String str, int n) {
if (n >= str.length())
return str;
char[] chars = str.toCharArray();
// 分三步反转
// 1. n之前反转
reverse(chars, 0, n - 1);
// 2. n之后反转
reverse(chars, n, chars.length - 1);
// 3. 全部反转
reverse(chars, 0, chars.length - 1);
return new String(chars);
}
private void reverse(char[] chars, int i, int j) {
while (i < j)
swap(chars, i++, j--);
}
private void swap(char[] chars, int i, int j) {
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}4.2、翻转单词顺序列
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
>输入 >"nowcoder. a am I" >返回值 >"I am a nowcoder."
正确的解法应该是和书上一样，先旋转每个单词，再旋转整个字符串。
public String ReverseSentence(String str) {
int n = str.length();
char[] chars = str.toCharArray();
int i = 0, j = 0;
// 双指针，滑窗，，注意边界。
while (j <= n) {
// 关键是这个判断边界
if (j == n || chars[j] == ' ') {
// 反转
reverse(chars, i, j - 1);
// 下个单词的索引开头
i = j + 1;
}
// 继续走
j++;
}
// 全反转
reverse(chars, 0, n - 1);
return new String(chars);
}
private void reverse(char[] c, int i, int j) {
while (i < j)
swap(c, i++, j--);
}
private void swap(char[] c, int i, int j) {
char t = c[i];
c[i] = c[j];
c[j] = t;
}5、把字符串转成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
>输入 >"+2147483647" >返回值 >2147483647
public class T49 {
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
// 注意第一个字符是否是-
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// 跳过第一个字符
if (i == 0 && (c == '+' || c == '-')) /* 符号判定 */
continue;
// 防止非法输入
if (c < '0' || c > '9') /* 非法输入 */
return 0;
// 正常操作，注意“0”
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
}5. 最长回文子串(1478)
给你一个字符串
s，找到s中最长的回文子串>输入：s = "babad" >输出："bab" >解释："aba" 同样是符合题意的答案。>输入：s = "cbbd" >输出："bb">输入：s = "ac" >输出："a">输入：s = "a" >输出："a"
中心扩展
- 两种情况
- 奇数长度
- 偶数长度
- 取最长，求起始和结束位置
- 用substring即可
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return s;
int start = 0, end = 0; // 记录起始位置
for (int i = 0; i < s.length(); i++) {
// 两种情况 以i为中心，以i和i+1为中心
int len1 = expand(s, i - 1, i + 1); // 中心扩展
int len2 = expand(s, i, i + 1);
int len = Math.max(len1, len2); // 取最长的长度
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
// 这里要注意
return r - l - 1;
}
}本博客所有文章除特别声明外，大部分为学习心得，欢迎与博主联系讨论