代码随想录-day3
字符串
字符串的题目，通常涉及到对字符串进行各种操作，由于JAVA提供了非常多的库函数，所以在很多题目中我们可以使用库函数快速使这道题解决，但是这与我们训练算法和编码能力相违背。
所以我们在本章专题里面，主要是使用我们自己构造的函数对字符串进行，操作加深我们对字符串操作的理解，当我们训练熟悉后可以使用库函数直接执行。
344.反转字符串
题意：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路
在此我们考虑不使用额外空间的一种做法，我们可以使用一个在头，一个在尾部的双指针对字符串做一个反转。
每次双指针所指向的字符进行交换，当两个指针穿越的时候就表示已经处理完整个字符串。
代码
class Solution {
public void reverseString(char[] s) {
int n = s.length;
int l = 0, r = n - 1;
while (l < r) {
swap(s, l, r);
l ++;
r --;
}
}
public void swap(char[] s, int i, int j) {
if (i == j) return ; // 如果没有这行当交换相同元素时结果会是0
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
}
541. 反转字符串II
题意：给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路
本题逻辑并不能，但是存在多种情况，导致在编写代码的可能有多个if-else，并且对某个特点的情况存在遗漏。
为了解决这个问题，我们可以每次移动2k个区间，如何判断是否有要翻转的区间。
代码
class Solution {
public String reverseStr(String s, int k) {
char[] ca = s.toCharArray();
int n = ca.length;
for (int i = 0; i < n; i += 2 * k) {
if (i + k <= n) { // 剩余区间大于等于k
reverse(ca, i, i + k - 1);
continue;
}
reverse(ca, i, n - 1); // 剩余区间小于k
}
return new String(ca);
}
public void reverse(char[] s, int start, int end) {
for (int i = start, j = end; i < j; i ++, j --) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}
剑指Offer 05.替换空格
题意：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."
思路
如果不限制使用O（1）的空间，我们可以直接使用一个StringBuilder进行操作，这样的代码不能直接写成，在此我们继续讨论限制O(1)的空间复杂度进行操作。
我们可以先对字符串进行扩充，然后从后向前遍历。我们不在前面进行扩充的原因：如果在前面扩充，如果我们要添加一个元素，就得把一个元素往后移动，这样我们每次操作的时间复杂度就为O(n2)
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。 ——代码随想录
我们设置两个指针一个i指向原字符串的末尾，一个j指向扩充后的末尾，如果此时s[i] != ' '，我们把s[j] = s[i]。反之我们把空格替换为%20，j再往后移动2位。
代码
class Solution {
public String replaceSpace(String s) {
if (s == null || s.length() == 0) return s; // 空字符串跳过
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i ++ ) {
if (s.charAt(i) == ' ')
sb.append(" ");
}
if (sb.length() == 0) return s; // 没有空格
int oldSize = s.length();
s += sb.toString();
int newSize = s.length();
char[] ca = s.toCharArray();
for (int i = oldSize - 1, j = newSize - 1; i < j; i --, j --) {
if (ca[i] != ' ') {
ca[j] = ca[i];
} else {
ca[j] = '0';
ca[j - 1] = '2';
ca[j - 2] = '%';
j -= 2;
}
}
return new String(ca);
}
}
151.翻转字符串里的单词
题意：给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路
在之前，我们已经通过自己实现的reverse()对字符串进行了翻转，本题在之前翻转字符串的问题的基础上进行了扩展，我们要去掉字符串前后多余的空格和单词之前多余的空格。
值得注意的是，每个单词之间必须保留一个空格。然后在此基础上我们先翻转整个字符串，再翻转每个单词即可。
本题的重难点其实不在翻转，而是在去除空格。我们采用与之前“移除元素”那题的逻辑书写一个函数去除空格。
public char[] removeExtraSpaces(char[] s) {
int slow = 0; // 表示处理完的字符串的末尾
for (int fast = 0; fast < s.length; fast ++ ) {
if (s[fast] != ' ') {
if (slow != 0) s[slow ++] = ' '; // 如果不是第一个单词就先在前面加一个空格先
while (fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
char[] newChars = new char[slow];
System.arraycopy(s, 0, newChars, 0, slow); // 重设大小后拷贝
return newChars;
}
代码
class Solution {
public String reverseWords(String s) {
char[] ca = s.toCharArray();
ca = removeExtraSpaces(ca);
reverse(ca, 0, ca.length - 1);
for (int i = 0, j = 0; i <= ca.length; i ++ ) {
if (i == ca.length || ca[i] == ' ') { // 先特判最后一个单词
reverse(ca, j , i - 1);
j = i + 1; // j重新指向下一个单词的开头
}
}
return new String(ca);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i ++;
j --;
}
}
public char[] removeExtraSpaces(char[] s) {
int slow = 0;
for (int fast = 0; fast < s.length; fast ++ ) {
if (s[fast] != ' ') {
if (slow != 0) s[slow ++] = ' '; // 如果不是第一个单词就先在前面加一个空格先
while (fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
char[] newChars = new char[slow];
System.arraycopy(s, 0, newChars, 0, slow);
return newChars;
}
}
剑指Offer58-II.左旋转字符串
题意：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
思路
在本题中我们还是利用整体-局部翻转的方法来实现左旋转字符串的操作，通过简单的模拟我们不难得出：我们可以先翻转前k个字符串，再翻转剩下的字符，最后整体翻转即可实现左旋转的效果。
代码
class Solution {
public String reverseLeftWords(String s, int n) {
char[] ca = s.toCharArray();
reverse(ca, 0, n - 1);
reverse(ca, n, ca.length - 1);
reverse(ca, 0, ca.length - 1);
return new String(ca);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i ++;
j --;
}
}
}
28. 找出字符串中第一个匹配项的下标
题意：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
思路
本题是一道经典的KMP，KMP是为了快速找到一个字符串是否是另一个字符串的子串。为了实现KMP算法，我们必须要求一个前缀表，即next数组。