理论
思维导图
第一章 双指针
刷题第一章 双指针
344. 反转字符串
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char ch = s[left];
s[left] = s[right];
s[right] = ch;
left++;
right--;
}
}
}
541. 反转字符串 II
这道题看着是上面的进阶,其实每个啥,放这里了!
class Solution {
public String reverseStr(String s, int k) {
char[] chs = s.toCharArray();
int n = chs.length - 1;
int start = 0; // 2k长度的第一个点
while (start <= n) { // 当前起始点还在合法范围内
if (start + 2 * k - 1 <= n) { // 即接下来的长度>=2k
reverseString(chs, start, start + k - 1);
start += 2 * k;
} else if (start + k - 1 > n) { // 剩余字符少于 k 个,则将剩余字符全部反转
reverseString(chs, start, n);
break;
} else {
reverseString(chs, start, start + k - 1);
break;
}
}
return new String(chs);
}
public void reverseString(char[] s, int left, int right) {
while (left < right) {
char ch = s[left];
s[left] = s[right];
s[right] = ch;
left++;
right--;
}
}
}
但人家这官网写的代码,说实话,最近差的远
class Solution {
public String reverseStr(String s, int k) {
char[] a = s.toCharArray();
for (int start = 0; start < a.length; start += 2 * k) {
int i = start, j = Math.min(start + k - 1, a.length - 1);
while (i < j) {
char tmp = a[i];
a[i++] = a[j];
a[j--] = tmp;
}
}
return new String(a);
}
}
剑指 Offer 05. 替换空格
这道题太假,不想做了,复制官网代码。
需要从后向前传的那个题目,要输入是数组,且后面有足够空间。
这道题算是双指针吧!
class Solution {
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String newStr = new String(array, 0, size);
return newStr;
}
}
151. 翻转字符串里的单词
这道题怎么说,也不想做!
方法一:API调用
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;
}
}
}
剑指 Offer 58 - II. 左旋转字符串
反转字符串还有这个用处??真的很惊奇!!
class Solution {
public String reverseLeftWords(String s, int n) {
char[] chs = s.toCharArray();
reverse(chs, 0, n - 1);
reverse(chs, n, chs.length - 1);
reverse(chs, 0, chs.length - 1);
return new String(chs);
}
private void reverse(char[] chs, int left, int right) {
while (left < right) {
char ch = chs[left];
chs[left++] = chs[right];
chs[right--] = ch;
}
}
}
刷题第二站 快慢指针
第二章 字符串算法
刷题第一站 KMP算法
理论
KMP算法解决的是:文本串中是否出现过模式串
str1中的某个子串是否是str2,如果是,返回开始位置。不包含,返回-1.
28. 实现 strStr()
class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
if (needle.length() == 0) {
return 0;
}
if (haystack.length() == 0) {
return -1;
}
char[] str1 = haystack.toCharArray();
char[] str2 = needle.toCharArray();
int[] next = getNextArray(str2);
int i1 = 0, i2 = 0;
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] == -1) {
i1++;
} else {
i2 = next[i2];
}
}
return i2 == str2.length ? i1 - i2 : -1;
}
private int[] getNextArray(char[] str2) {
if (str2.length == 1) {
return new int[]{-1};
}
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i < next.length) {
if (str2[i - 1] == str2[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
}
459. 重复的子字符串
刷题第二站 马拉车算法
5. 最长回文子串
暴力解法
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(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 expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return right - left - 1;
}
}
动态规划
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
boolean[][] dp = new boolean[len][len];
int maxLen = 1;
int begin = 0;
// 初始化:所有长度为1的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
if (i != len - 1 && s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
begin = i;
maxLen = 2;
}
}
for (int i = len - 1 - 2; i >= 0; i--) {
for (int j = i + 2; j < len; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
if (dp[i][j] && maxLen < j - i + 1) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
Manacher算法
暂时略!!下面这个代码暂时未通过
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
char[] charArr = manacherString(s);
int[] pArr = new int[charArr.length];
int C = -1;
int R = -1;
int maxLen = 0, begin = 0;
for (int i = 0; i < charArr.length; i++) {
pArr[i] = R > i ? Math.min(pArr[2 * C - R], R - i) : 1;
while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
if (i + pArr[i] - 1 > R) {
R = i + pArr[i] - 1;
C = i;
}
if (pArr[i] * 2 - 1 > maxLen) {
maxLen = pArr[i] * 2 - 1;
begin = i - pArr[i] + 1;
}
}
return s.substring(begin / 2, begin / 2 + maxLen / 2 - 1);
}
public char[] manacherString(String str) {
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for (int i = 0; i < res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : str.charAt(index++);
}
return res;
}
}
647. 回文子串
下面是马拉车算法,中心扩展法也是很重要的,这里略!!
class Solution {
public int countSubstrings(String s) {
StringBuilder sb = new StringBuilder();
sb.append("#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
sb.append("#");
}
int[] pArr = new int[sb.length()];
int C = -1;
int R = -1;
int count = 0;
for (int i = 0; i < sb.length(); i++) {
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
while (i + pArr[i] < pArr.length && i - pArr[i] > -1) {
if (sb.charAt(i + pArr[i]) == sb.charAt(i - pArr[i])) {
pArr[i]++;
} else {
break;
}
}
if (i + pArr[i] - 1 > R) {
R = i + pArr[i] - 1;
C = i;
}
if (i % 2 == 1) {
count += (pArr[i]) / 2;
} else {
count += pArr[i] / 2;
}
}
return count;
}
}
680. 验证回文字符串 Ⅱ
class Solution {
public boolean validPalindrome(String s) {
if (s == null) return false;
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
break;
}
}
// 此时结束可能是right >= left;当然也可能是遇到不相等了
if (right <= left) return true;
// 下面是跳一个
boolean left_1 = true;
int a = left + 1, b = right;
while(a < b) {
if (s.charAt(a) == s.charAt(b)) {
a++;
b--;
} else {
left_1 = false;
break;
}
}
boolean right_1 = true;
a = left;
b = right - 1;
while(a < b) {
if (s.charAt(a) == s.charAt(b)) {
a++;
b--;
} else {
right_1 = false;
break;
}
}
return left_1 || right_1;
}
}
409. 最长回文串
class Solution {
public int longestPalindrome(String s) {
int[] count = new int[52];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
count[s.charAt(i) - 'a']++;
} else {
count[s.charAt(i) - 'A' + 26]++;
}
}
int res = 0;
for (int num : count) {
res += num / 2;
}
res <<= 1;
res = res < s.length()? res + 1 : res;
return res;
}
}
第三章 滑动窗口
刷题第一站 滑动窗口
3. 无重复字符的最长子串
以后滑动窗口模板尽量就用这个代码!!看看是否可行!!
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;
}
}
其它
刷题第一站
6. Z 字形变换
class Solution {
public String convert(String s, int numRows) {
if (numRows < 2) return s;
List<StringBuffer> list = new ArrayList<StringBuffer>();
for (int i = 0; i < numRows; i++) {
list.add(new StringBuffer());
}
int row = 0, flag = -1;
for (Character c : s.toCharArray()) {
list.get(row).append(c);
if (row == 0 || row == numRows - 1) {
flag = -flag;
}
row += flag;
}
StringBuffer res = new StringBuffer();
for (StringBuffer sb : list) {
res.append(sb);
}
return res.toString();
}
}