02数组+字符串+滑动窗口+前缀和与差分+双指针（D2_字符串（D2_刷题练习））
目录
1. 最长公共前缀
1.1. 题目描述
1.2. 解题方案
方案一：纵向对比
方案二：横向对比
方案三：最值对比
方案四：分治
方案五：二分
1.3. 知识归纳
2. 左旋转字符串（简单）
2.1. 题目描述
2.2. 解题思路
方法一：字符串切片
方法二：列表遍历拼接
方法三：字符串遍历拼接
3. 表示数值的字符串（中等）
3.1. 题目描述
3.2. 解题思路
方法一：确定有限状态自动机
4. 把字符串转换成整数（中等）
4.1. 题目描述
4.2. 解题思路
5. 交替合并字符串（简单）
5.1. 题目描述
5.2. 解题思路
方法一：双指针
6. 字符串的最大公因子（简单）
6.1. 题目描述
6.2. 解题思路
方法一：枚举
方法二：枚举优化
方法三：数学
7. 反转字符串中的元音字母（简单）
7.1. 题目描述
7.2. 解题思路
方法一：双指针
8. 递增的三元子序列（中等）
8.1. 题目描述
8.2. 解题思路
方法一：双向遍历
方法二：贪心
9. 压缩字符串（中等）
9.1. 题目描述
9.2. 解题思路
方法一：双指针
10. 反转字符串中的单词（中等）
10.1. 题目描述
10.2. 解题思路
方法一：使用语言特性
方法二：自行编写对应的函数
方法三：双端队列
11. 字符串变形（简单）
11.1. 题目描述
11.2. 解题思路
方法一：双逆转（推荐使用）
方法二：分割字符串+栈（扩展思路）
12. 最长公共前缀
12.1. 题目描述
12.2. 解题思路
方法一：遍历查找(推荐使用)
13. 验证IP地址
13.1. 题目描述
13.2. 解题思路
方法一：分割字符串比较法（推荐使用）
方法二：正则表达式（扩展思路）
14. 大数加法
14.1. 题目描述
14.2. 解题思路
方法一：模拟法（建议使用）
15. 无重复字符的最长子串
15.1. 题目描述
15.2. 解题思路
方法一：滑动窗口
16. 找到字符串中所有字母异位词（中等）
16.1. 题目描述
16.2. 解题思路
方法一：滑动窗口
方法二：优化的滑动窗口
17. 定长子串中元音的最大数目（中等）
17.1. 题目描述
17.2. 解题思路
方法一：滑动窗口
18. 判断是否为回文字符串
18.1. 题目描述
18.2. 解题思路
方法一：首尾依次比较法（推荐使用）
方法二：反转字符串比较法（扩展思路）
19. 最小覆盖子串（较难）
19.1. 题目描述
19.2. 解题思路
方法一：哈希表匹配（推荐使用）
20. 反转字符串（入门）
20.1. 题目描述
20.2. 解题思路
解法一
解法二
解法三
1. 最长公共前缀
1.1. 题目描述
1.2. 解题方案
对于一个问题，采用一题多解，才能深刻理解其考察的知识点，进行举一反三。
最长公共前缀，可横向对比 / 竖向对比 / 最值对比 / 分治 / 二分方法来完成题解。
方案一：纵向对比
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() || strs[j].charAt(i) != ch) return strs[0].substring(0, i);
}
}
return strs[0];
}方案二：横向对比
// idea6:横向扫描（暴力之一）
public String longestCommonPrefix6(String[] strs) {
String prefix = strs[0];
for (String s : strs) prefix = compareStr(prefix, s);
return prefix;
}
private String compareStr(String s1, String s2) {
int idx = 0;
while (idx < s1.length() && idx < s2.length() && s1.charAt(idx) == s2.charAt(idx)) ++idx;
return s1.substring(0, idx);
}方案三：最值对比
public String longestCommonPrefix3(String[] strs) {
String min = strs[0], max = strs[0];
for (String str : strs) {
// bug1:字符串的compare和integer的不一样，并非-1 / 0 / 1，而是长度相减作为返回值。
if (min.compareTo(str) > 0) min = str;
if (max.compareTo(str) < 0) max = str;
}
return compareStr(min, max);
}
private String compareStr(String s1, String s2) {
int idx = 0;
while (idx < s1.length() && idx < s2.length() && s1.charAt(idx) == s2.charAt(idx)) ++idx;
return s1.substring(0, idx);
}方案四：分治
private String partition(String[] strs, int left, int right) {
if (left == right) return strs[left];
int mid = left + (right - left >> 1);
String s1 = partition(strs, left, mid);
String s2 = partition(strs, mid + 1, right);
return compareStr(s1, s2);
}
private String compareStr(String s1, String s2) {
int idx = 0;
while (idx < s1.length() && idx < s2.length() && s1.charAt(idx) == s2.charAt(idx)) ++idx;
return s1.substring(0, idx);
}方案五：二分
public String longestCommonPrefix5(String[] strs) {
String s = strs[0];
// 有可能需要idx = 0的位置，所以也会需要s.len的位置。
int low = 0, high = s.length();
// 用二分法去快速寻找公共前缀的右边界。
while (low < high) {
int mid = low + (high - low + 1 >> 1);// 为了low不越界，这里必须+1防止死循环。
String midStr = s.substring(0, mid);
if (isMatchAll(strs, midStr)) low = mid;
else high = mid - 1;
}
return s.substring(0, low);
}
private boolean isMatchAll(String[] strs, String str) {
for (String s : strs) {
if (s.length() < str.length() || !str.equals(s.substring(0, str.length()))) return false;
}
return true;
}1.3. 知识归纳
最长公共前缀，可横向对比 / 竖向对比 / 最值对比 / 分治 / 二分方法来完成题解。
对于分治来讲，可多线程操作加快速度；
对于二分，考察对抽象二分的理解，将二分规则进行抽象。
2. 左旋转字符串（简单）
2.1. 题目描述
2.2. 解题思路
方法一：字符串切片
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}方法二：列表遍历拼接
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
for(int i = n; i < s.length(); i++)
res.append(s.charAt(i));
for(int i = 0; i < n; i++)
res.append(s.charAt(i));
return res.toString();
}
}方法三：字符串遍历拼接
class Solution {
public String reverseLeftWords(String s, int n) {
String res = "";
for(int i = n; i < s.length(); i++)
res += s.charAt(i);
for(int i = 0; i < n; i++)
res += s.charAt(i);
return res;
}
}3. 表示数值的字符串（中等）
3.1. 题目描述
3.2. 解题思路
方法一：确定有限状态自动机
class Solution {
public boolean isNumber(String s) {
Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();
Map<CharType, State> initialMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_SPACE, State.STATE_INITIAL);
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
}};
transfer.put(State.STATE_INITIAL, initialMap);
Map<CharType, State> intSignMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
}};
transfer.put(State.STATE_INT_SIGN, intSignMap);
Map<CharType, State> integerMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_POINT, State.STATE_POINT);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_INTEGER, integerMap);
Map<CharType, State> pointMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_POINT, pointMap);
Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
}};
transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);
Map<CharType, State> fractionMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_FRACTION, fractionMap);
Map<CharType, State> expMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
}};
transfer.put(State.STATE_EXP, expMap);
Map<CharType, State> expSignMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
}};
transfer.put(State.STATE_EXP_SIGN, expSignMap);
Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_EXP_NUMBER, expNumberMap);
Map<CharType, State> endMap = new HashMap<CharType, State>() {
{
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_END, endMap);
int length = s.length();
State state = State.STATE_INITIAL;
for (int i = 0; i < length; i++) {
CharType type = toCharType(s.charAt(i));
if (!transfer.get(state).containsKey(type)) {
return false;
} else {
state = transfer.get(state).get(type);
}
}
return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
}
public CharType toCharType(char ch) {
if (ch >= '0' && ch <= '9') {
return CharType.CHAR_NUMBER;
} else if (ch == 'e' || ch == 'E') {
return CharType.CHAR_EXP;
} else if (ch == '.') {
return CharType.CHAR_POINT;
} else if (ch == '+' || ch == '-') {
return CharType.CHAR_SIGN;
} else if (ch == ' ') {
return CharType.CHAR_SPACE;
} else {
return CharType.CHAR_ILLEGAL;
}
}
enum State {
STATE_INITIAL,
STATE_INT_SIGN,
STATE_INTEGER,
STATE_POINT,
STATE_POINT_WITHOUT_INT,
STATE_FRACTION,
STATE_EXP,
STATE_EXP_SIGN,
STATE_EXP_NUMBER,
STATE_END
}
enum CharType {
CHAR_NUMBER,
CHAR_EXP,
CHAR_POINT,
CHAR_SIGN,
CHAR_SPACE,
CHAR_ILLEGAL
}
}4. 把字符串转换成整数（中等）
4.1. 题目描述
请问什么是有符号整数？
有符号整数，就是int，因为有正负之分，所以16位的第一位表示正负，0为正，1为负所以能表示的范围
是-32768～+32767（-2e15～2e15-1）而无符号整数，就是定义为unsigned int，因为第一位不用代
表正负了，没有符号，全是正的啊，所以16位全为有效位，所以范围是0～65535（0～2e16-1）
4.2. 解题思路
class Solution {
public int strToInt(String str) {
char[] c = str.trim().toCharArray();
if(c.length == 0) return 0;
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 1, sign = 1;
if(c[0] == '-') sign = -1;
else if(c[0] != '+') i = 0;
for(int j = i; j < c.length; j++) {
if(c[j] < '0' || c[j] > '9') break;
if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[j] - '0');
}
return sign * res;
}
}若不使用trim() / strip() 方法，而从头开始遍历字符串，则可以将空间复杂度降低至 O(1) ，代码如下：
class Solution {
public int strToInt(String str) {
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 0, sign = 1, length = str.length();
if(length == 0) return 0;
while(str.charAt(i) == ' ')
if(++i == length) return 0;
if(str.charAt(i) == '-') sign = -1;
if(str.charAt(i) == '-' || str.charAt(i) == '+') i++;
for(int j = i; j < length; j++) {
if(str.charAt(j) < '0' || str.charAt(j) > '9') break;
if(res > bndry || res == bndry && str.charAt(j) > '7')
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (str.charAt(j) - '0');
}
return sign * res;
}
}5. 交替合并字符串（简单）
5.1. 题目描述
5.2. 解题思路
方法一：双指针
class Solution {
public String mergeAlternately(String word1, String word2) {
int m = word1.length(), n = word2.length();
int i = 0, j = 0;
StringBuilder ans = new StringBuilder();
while (i < m || j < n) {
if (i < m) {
ans.append(word1.charAt(i));
++i;
}
if (j < n) {
ans.append(word2.charAt(j));
++j;
}
}
return ans.toString();
}
}
6. 字符串的最大公因子（简单）
6.1. 题目描述
什么是最大公因数 最大公因数的解释
1、最大公因数，也称为最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
2、a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最
大公约数也有同样的记号。
求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
6.2. 解题思路
方法一：枚举
class Solution {
// 字符串最大公因子
public String gcdOfStrings(String str1, String str2) {
// 获取两个字符串长度
int len1 = str1.length(), len2 = str2.length();
// 从长度小的开始枚举
for (int i = Math.min(len1, len2); i >= 1; --i) {
// 前缀串的长度必然是两个字符串长度的约数才能满足条件
if (len1 % i == 0 && len2 % i == 0) {
// 截取子串
String X = str1.substring(0, i);
// 检测子串是否能被两个字符串整除
if (check(X, str1) && check(X, str2)) {
return X;
}
}
}
return "";
}
public boolean check(String t, String s) {
int lenx = s.length() / t.length();
StringBuffer ans = new StringBuffer();
for (int i = 1; i <= lenx; ++i) {
ans.append(t);
}
return ans.toString().equals(s);
}
}
方法二：枚举优化
class Solution {
// 字符串最大公因子
public String gcdOfStrings(String str1, String str2) {
// 获取两个字符串长度
int len1 = str1.length(), len2 = str2.length();
// 截取子串（截取到最大公因子）
String T = str1.substring(0, gcd(len1, len2));
// 检测子串是否能被两个字符串整除
if (check(T, str1) && check(T, str2)) {
return T;
}
return "";
}
public boolean check(String t, String s) {
int lenx = s.length() / t.length();
StringBuffer ans = new StringBuffer();
for (int i = 1; i <= lenx; ++i) {
ans.append(t);
}
return ans.toString().equals(s);
}
// 求最大公因子
public int gcd(int a, int b) {
int remainder = a % b;
while (remainder != 0) {
a = b;
b = remainder;
remainder = a % b;
}
return b;
}
}
方法三：数学
class Solution {
// 字符串最大公因子
public String gcdOfStrings(String str1, String str2) {
// 两个字符串相连不相等，直接返回空串
if (!str1.concat(str2).equals(str2.concat(str1))) {
return "";
}
//
return str1.substring(0, gcd(str1.length(), str2.length()));
}
// 截取子串（截取到最大公因子）
public int gcd(int a, int b) {
int remainder = a % b;
while (remainder != 0) {
a = b;
b = remainder;
remainder = a % b;
}
return b;
}
}
7. 反转字符串中的元音字母（简单）
7.1. 题目描述
7.2. 解题思路
方法一：双指针
class Solution {
public String reverseVowels(String s) {
int n = s.length();
char[] arr = s.toCharArray();
int i = 0, j = n - 1;
while (i < j) {
while (i < n && !isVowel(arr[i])) {
++i;
}
while (j > 0 && !isVowel(arr[j])) {
--j;
}
if (i < j) {
swap(arr, i, j);
++i;
--j;
}
}
return new String(arr);
}
public boolean isVowel(char ch) {
return "aeiouAEIOU".indexOf(ch) >= 0;
}
public void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
8. 递增的三元子序列（中等）
8.1. 题目描述
8.2. 解题思路
方法一：双向遍历
class Solution {
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
if (n < 3) {
return false;
}
int[] leftMin = new int[n];
leftMin[0] = nums[0];
for (int i = 1; i < n; i++) {
leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
}
for (int i = 1; i < n - 1; i++) {
if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
return true;
}
}
return false;
}
}
方法二：贪心
class Solution {
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
if (n < 3) {
return false;
}
int first = nums[0], second = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
int num = nums[i];
if (num > second) {
return true;
} else if (num > first) {
second = num;
} else {
first = num;
}
}
return false;
}
}
9. 压缩字符串（中等）
9.1. 题目描述
9.2. 解题思路
方法一：双指针
class Solution {
public int compress(char[] chars) {
int n = chars.length;
int write = 0, left = 0;
for (int read = 0; read < n; read++) {
if (read == n - 1 || chars[read] != chars[read + 1]) {
chars[write++] = chars[read];
int num = read - left + 1;
if (num > 1) {
int anchor = write;
while (num > 0) {
chars[write++] = (char) (num % 10 + '0');
num /= 10;
}
reverse(chars, anchor, write - 1);
}
left = read + 1;
}
}
return write;
}
public void reverse(char[] chars, int left, int right) {
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
}
}
10. 反转字符串中的单词（中等）
10.1. 题目描述
10.2. 解题思路
方法一：使用语言特性
class Solution {
public String reverseWords(String s) {
// 除去开头和末尾的空白字符
s = s.trim();
// 正则匹配连续的空白字符作为分隔符分割
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
}
方法二：自行编写对应的函数
class Solution {
public String reverseWords(String s) {
StringBuilder sb = trimSpaces(s);
// 翻转字符串
reverse(sb, 0, sb.length() - 1);
// 翻转每个单词
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder trimSpaces(String s) {
int left = 0, right = s.length() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s.charAt(left) == ' ') {
++left;
}
// 去掉字符串末尾的空白字符
while (left <= right && s.charAt(right) == ' ') {
--right;
}
// 将字符串间多余的空白字符去除
StringBuilder sb = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if (c != ' ') {
sb.append(c);
} else if (sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
++left;
}
return sb;
}
public void reverse(StringBuilder sb, int left, int right) {
while (left < right) {
char tmp = sb.charAt(left);
sb.setCharAt(left++, sb.charAt(right));
sb.setCharAt(right--, tmp);
}
}
public void reverseEachWord(StringBuilder sb) {
int n = sb.length();
int start = 0, end = 0;
while (start < n) {
// 循环至单词的末尾
while (end < n && sb.charAt(end) != ' ') {
++end;
}
// 翻转单词
reverse(sb, start, end - 1);
// 更新start，去找下一个单词
start = end + 1;
++end;
}
}
}
方法三：双端队列
class Solution {
public String reverseWords(String s) {
int left = 0, right = s.length() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s.charAt(left) == ' ') {
++left;
}
// 去掉字符串末尾的空白字符
while (left <= right && s.charAt(right) == ' ') {
--right;
}
Deque<String> d = new ArrayDeque<String>();
StringBuilder word = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if ((word.length() != 0) && (c == ' ')) {
// 将单词 push 到队列的头部
d.offerFirst(word.toString());
word.setLength(0);
} else if (c != ' ') {
word.append(c);
}
++left;
}
d.offerFirst(word.toString());
return String.join(" ", d);
}
}
11. 字符串变形（简单）
11.1. 题目描述
11.2. 解题思路
方法一：双逆转（推荐使用）
Java代码实现:
import java.util.*;
public class Solution {
public String trans(String s, int n) {
if(n==0)
return s;
StringBuffer res=new StringBuffer();
for(int i = 0; i < n; i++){
//大小写转换
if(s.charAt(i) <= 'Z' && s.charAt(i) >= 'A')
res.append((char)(s.charAt(i) - 'A' + 'a'));
else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
res.append((char)(s.charAt(i) - 'a' + 'A'));
else
//空格直接复制
res.append(s.charAt(i));
}
//翻转整个字符串
res = res.reverse();
for (int i = 0; i < n; i++){
int j = i;
//以空格为界，二次翻转
while(j < n && res.charAt(j) != ' ')
j++;
String temp = res.substring(i,j);
StringBuffer buffer = new StringBuffer(temp);
temp = buffer.reverse().toString();
res.replace(i,j,temp);
i = j;
}
return res.toString();
}
}
方法二：分割字符串+栈（扩展思路）
java代码实现：
import java.util.*;
public class Solution {
public String trans(String s, int n) {
if(n==0)
return s;
StringBuffer res=new StringBuffer();
for (int i = 0; i < n; i++){
//大小写转换
if(s.charAt(i) <= 'Z' && s.charAt(i) >= 'A')
res.append((char)(s.charAt(i) - 'A' + 'a'));
else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
res.append((char)(s.charAt(i) - 'a' + 'A'));
else
//空格直接复制
res.append((char)(s.charAt(i)));
}
Stack<String> temp=new Stack<String>();
for (int i = 0; i < n; i++){
int j = i;
//以空格为界，分割单词
while(j < n && res.charAt(j) != ' ')
j++;
//单词进栈
temp.push((String)(res.substring(i, j)));
i = j;
}
//排除结尾空格的特殊情况
if(s.charAt(n - 1) == ' ')
res = new StringBuffer(" ");
else
res = new StringBuffer();
//栈遵循先进后厨，单词顺序是反的
while(!temp.empty()){
res.append(temp.peek());
temp.pop();
if(!temp.empty())
res.append(" ");
}
return res.toString();
}
}
12. 最长公共前缀
12.1. 题目描述
12.2. 解题思路
方法一：遍历查找(推荐使用)
Java代码实现:
import java.util.*;
public class Solution {
public String longestCommonPrefix (String[] strs) {
int n = strs.length;
//空字符串数组
if(n == 0)
return "";
//遍历第一个字符串的长度
for(int i = 0; i < strs[0].length(); i++){
char temp = strs[0].charAt(i);
//遍历后续的字符串
for(int j = 1; j < n; j++)
//比较每个字符串该位置是否和第一个相同
if(i == strs[j].length() || strs[j].charAt(i) != temp)
//不相同则结束
return strs[0].substring(0, i);
}
//后续字符串有整个字一个字符串的前缀
return strs[0];
}
}
13. 验证IP地址
13.1. 题目描述
13.2. 解题思路
方法一：分割字符串比较法（推荐使用）
java代码实现:
import java.util.*;
public class Solution {
boolean isIPv4 (String IP) {
if(IP.indexOf('.') == -1){
return false;
}
String[] s = IP.split("\\.");
//IPv4必定为4组
if(s.length != 4)
return false;
for(int i = 0; i < s.length; i++){
//不可缺省，有一个分割为零，说明两个点相连
if(s[i].length() == 0)
return false;
//比较数字位数及不为零时不能有前缀零
if(s[i].length() < 0 || s[i].length() > 3 || (s[i].charAt(0)=='0' && s[i].length() != 1))
return false;
int num = 0;
//遍历每个分割字符串，必须为数字
for(int j = 0; j < s[i].length(); j++){
char c = s[i].charAt(j);
if (c < '0' || c > '9')
return false;
//转化为数字比较，0-255之间
num = num * 10 + (int)(c - '0');
if(num < 0 || num > 255)
return false;
}
}
return true;
}
boolean isIPv6 (String IP) {
if (IP.indexOf(':') == -1) {
return false;
}
String[] s = IP.split(":",-1);
//IPv6必定为8组
if(s.length != 8){
return false;
}
for(int i = 0; i < s.length; i++){
//每个分割不能缺省，不能超过4位
if(s[i].length() == 0 || s[i].length() > 4){
return false;
}
for(int j = 0; j < s[i].length(); j++){
//不能出现a-fA-F以外的大小写字符
char c = s[i].charAt(j);
boolean expr = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F') ;
if(!expr){
return false;
}
}
}
return true;
}
String solve(String IP) {
if(isIPv4(IP))
return "IPv4";
else if(isIPv6(IP))
return "IPv6";
return "Neither";
}
}
方法二：正则表达式（扩展思路）
Java代码实现:
import java.util.regex.Pattern;
public class Solution {
String solve(String IP) {
//正则表达式限制0-255 且没有前缀0 四组齐全
String ipv4="(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])";
Pattern ipv4_pattern = Pattern.compile(ipv4);
//正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个
String ipv6="([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}";
Pattern ipv6_pattern = Pattern.compile(ipv6);
//调用正则匹配函数
if (ipv4_pattern.matcher(IP).matches())
return "IPv4";
else if (ipv6_pattern.matcher(IP).matches())
return "IPv6";
else return "Neither";
}
}
14. 大数加法
14.1. 题目描述
14.2. 解题思路
方法一：模拟法（建议使用）
Java代码实现:
import java.util.*;
public class Solution {
public String solve (String s, String t) {
//若是其中一个为空，返回另一个
if(s.length()<=0)
return t;
if(t.length()<=0)
return s;
//让s为较长的，t为较短的
if(s.length() < t.length()){
String temp = s;
s = t;
t = temp;
}
int carry = 0; //进位标志
char[] res = new char[s.length()];
//从后往前遍历较长的字符串
for(int i = s.length() - 1; i >= 0; i--){
//转数字加上进位
int temp = s.charAt(i) - '0' + carry;
//转较短的字符串相应的从后往前的下标
int j = i - s.length() + t.length();
//如果较短字符串还有
if(j >= 0)
//转数组相加
temp += t.charAt(j) - '0';
//取进位
carry = temp / 10;
//去十位
temp = temp % 10;
//修改结果
res[i] = (char)(temp + '0');
}
String output = String.valueOf(res);
//最后的进位
if(carry == 1)
output = '1' + output;
return output;
}
}
15. 无重复字符的最长子串
15.1. 题目描述
15.2. 解题思路
方法一：滑动窗口
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
16. 找到字符串中所有字母异位词（中等）
16.1. 题目描述
16.2. 解题思路
方法一：滑动窗口
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLen; ++i) {
++sCount[s.charAt(i) - 'a'];
++pCount[p.charAt(i) - 'a'];
}
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s.charAt(i) - 'a'];
++sCount[s.charAt(i + pLen) - 'a'];
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
}
方法二：优化的滑动窗口
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
for (int i = 0; i < pLen; ++i) {
++count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s.charAt(i) - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
--count[s.charAt(i) - 'a'];
if (count[s.charAt(i + pLen) - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
++count[s.charAt(i + pLen) - 'a'];
if (differ == 0) {
ans.add(i + 1);
}
}
return ans;
}
}
17. 定长子串中元音的最大数目（中等）
17.1. 题目描述
17.2. 解题思路
方法一：滑动窗口
class Solution {
public int maxVowels(String s, int k) {
int n = s.length();
int vowel_count = 0;
for (int i = 0; i < k; ++i) {
vowel_count += isVowel(s.charAt(i));
}
int ans = vowel_count;
for (int i = k; i < n; ++i) {
vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
ans = Math.max(ans, vowel_count);
}
return ans;
}
public int isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
}
}
18. 判断是否为回文字符串
18.1. 题目描述
18.2. 解题思路
方法一：首尾依次比较法（推荐使用）
Java代码实现:
import java.util.*;
public class Solution {
public boolean judge (String str) {
//首指针
int left = 0;
//尾指针
int right = str.length() - 1;
//首尾往中间靠
while(left < right){
//比较前后是否相同
if(str.charAt(left) != str.charAt(right))
return false;
left++;
right--;
}
return true;
}
}
方法二：反转字符串比较法（扩展思路）
import java.util.*;
public class Solution {
public boolean judge (String str) {
StringBuffer temp = new StringBuffer(str);
//反转字符串
String s = temp.reverse().toString();
//比较字符串是否相等
if(s.equals(str))
return true;
return false;
}
}
19. 最小覆盖子串（较难）
19.1. 题目描述
19.2. 解题思路
方法一：哈希表匹配（推荐使用）
Java代码实现：
import java.util.*;
public class Solution {
//检查是否有小于0的
boolean check(int[] hash) {
for (int i = 0; i < hash.length; i++) {
if (hash[i] < 0)
return false;
}
return true;
};
public String minWindow (String S, String T) {
int cnt = S.length() + 1;
//记录目标字符串T的字符个数
int[] hash = new int[128];
for(int i = 0; i < T.length(); i++)
//初始化哈希表都为负数，找的时候再加为正
hash[T.charAt(i)] -= 1;
int slow = 0, fast = 0;
//记录左右区间
int left = -1, right = -1;
for(; fast < S.length(); fast++){
char c = S.charAt(fast);
//目标字符匹配+1
hash[c]++;
//没有小于0的说明都覆盖了，缩小窗口
while(check(hash)){
//取最优解
if(cnt > fast - slow + 1){
cnt = fast - slow + 1;
left = slow;
right = fast;
}
c = S.charAt(slow);
//缩小窗口的时候减1
hash[c]--;
//窗口缩小
slow++;
}
}
//找不到的情况
if(left == -1)
return "";
return S.substring(left, right + 1);
}
}
20. 反转字符串（入门）
20.1. 题目描述
20.2. 解题思路
解法一
import java.util.*;
public class Solution {
public String solve (String str) {
char[] ans = str.toCharArray();
int len = str.length();
for(int i = 0 ; i < len ;i++)
{
ans[i] = str.charAt(len-1-i);
}
return new String(ans);
}
}解法二
import java.util.*;
public class Solution {
public String solve (String str) {
char[] cstr = str.toCharArray();
int len = str.length();
for(int i = 0 ; i < len/2 ;i++)
{
char t = cstr[i];
cstr[i] = cstr[len-1-i];
cstr[len-1-i]=t;
}
return new String(cstr);
}
}解法三
直接调用库函数
import java.util.*;
public class Solution {
public String solve (String str) {
StringBuffer sb =new StringBuffer(str);//此方法针对的是io流，不能针对字符串。
return sb.reverse().toString();
}
}