字符串
KMP
KMP由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母
KMP应用在字符串匹配上,KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
什么是前缀表?记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。也叫最长公共前后缀。next数组就是一个前缀表（prefix table）
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
前缀表工作原理：字符串（aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了
前缀表使用解释
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，发现不匹配，此时就要从头匹配了。
但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。
前缀表与next数组，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。
KMP实现√
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：输入：haystack = "sadbutsad", needle = "sad" 输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：输入：haystack = "leetcode", needle = "leeto" 输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
O(n+m)
// 方法一
class Solution {
//前缀表（不减一）Java实现
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
int[] next = new int[needle.length()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && needle.charAt(j) != haystack.charAt(i))
j = next[j - 1];
if (needle.charAt(j) == haystack.charAt(i))
j++;
if (j == needle.length())
return i - needle.length() + 1;
}
return -1;
}
private void getNext(int[] next, String s) {
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i))
j = next[j - 1];
if (s.charAt(j) == s.charAt(i))
j++;
next[i] = j;
}
}
}
459重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1: 输入: "abab" 输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2: 输入: "aba" 输出: False
示例 3: 输入: "abcabcabcabc" 输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
class Solution {
public void getNext(int[] next, String s) {
next[0] = 0;
int j = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = next[j - 1];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
next[i] = j;
}
}
//next[len - 1] 存储的是字符串的最后一个字符的前缀和后缀相同的最大长度。
//如果它不为 0 且 len % (len - next[len - 1]) == 0，则说明字符串 s 由重复的子串构成。
public boolean repeatedSubstringPattern(String s) {
if (s.length() == 0) {
return false;
}
int[] next = new int[s.length()];
getNext(next, s);
int len = s.length();
if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {
return true;
}
return false;
}
}
t560和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 输入：nums = [1,1,1], k = 2 输出：2
示例 输入：nums = [1,2,3], k = 3 输出：2
思路：前缀和。当我们在数组中向前移动时逐步增加 pre（当前的累积和）。
对于每个新的pre值，检查pre-k 是否在 Map 中：这个检查的意义在于，如果pre-k存在于Map中，
说明之前在某个点的累积和是pre-k。由于当前的累积和是pre，
这意味着从那个点到当前点的子数组之和恰好是k（因为 pre - (pre - k) = k）。
时间复杂度O(n)，n为数组的长度。遍历数组的时间复杂度为 O(n)，
中间利用哈希表查询删除的复杂度均为 O(1)，总时间复杂度为 O(n)
空间复杂度O(n)，n为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，空间复杂度O(n)
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap < Integer, Integer > mp = new HashMap < > ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}
t239滑动窗口最大值
给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
| 滑动窗口的位置 | 最大值 |
|---|---|
| [1 3 -1] -3 5 3 6 7 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 7 |
- PriorityQueue默认是小顶堆，需要自己实现大顶堆重写compare。初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。
时间复杂度O(nlogn)，n是数组nums的长度。
在最坏情况下，数组nums中的元素单调递增，最终优先队列中包含了所有元素，
没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，总时间复杂度为O(nlogn)。
空间复杂度O(n)，优先队列额外需要使用的空间
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
//降序，大顶堆，栈顶最大
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {//把0->k-1加入到pq，[nums[i],i]
pq.offer(new int[]{nums[i], i});
}
//-k+1是k缩为1个
int[] ans = new int[n - k + 1];//k到n个
ans[0] = pq.peek()[0];//最大
for (int i = k; i < n; ++i) {//把k-n-1加入pq
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {//移除索引不在滑动窗口内的元素
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
t76最小覆盖子串
给你字符串s 、t 。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
时间复杂度：最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，
对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，
设字符集大小为 C，则渐进时间复杂度为 O(C⋅∣s∣+∣t∣)。
空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，
我们设字符集大小为 C ，则渐进空间复杂度为 O(C)。
class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
//存储每个字符出现的次数
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {//右指针记录每个字符出现的次数
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {//满足出现次数后，尝试缩小窗口宽度
if (r - l + 1 < len) {//左右指针的距离小于长度，
len = r - l + 1;//长度修改为左右指针的距离
ansL = l;
ansR = l + len;
}
if (ori.containsKey(s.charAt(l))) {//减少字符出现次数
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;//左指针右移1
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {//检查每个字符出现次数是否足够
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
344反转字符串√
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
// 第二种方法用temp来交换数值更多人容易理解些
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while(l < r){
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}
}
541反转字符串II√
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
//每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += 2 * k){
int start = i;
//判断尾数够不够k个来取决end指针的位置，k个对应索引k-1
int end = Math.min(ch.length - 1, start + k - 1);
//用异或运算反转
while(start < end){
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
return new String(ch);
}
}
替换数字
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
如果想把这道题目做到极致，就不要只用额外的辅助空间了！
首先扩充数组到每个数字字符替换成 "number" 之后的大小
例如 字符串 "a5b" 的长度为3，那么 将 数字字符变成字符串"number"后长度为8
然后从后向前替换数字字符，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾
为什么要从后向前填充？
不用申请新数组。
避免从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题
public class Main {
public static String replaceNumber(String s) {
int count = 0; // 统计数字的个数
int sOldSize = s.length();
for (int i = 0; i < s.length(); i++) {
if(Character.isDigit(s.charAt(i))){
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"number"之后的大小
char[] newS = new char[s.length() + count * 5];
int sNewSize = newS.length;
// 将旧字符串的内容填入新数组
System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize);
// 从后先前将空格替换为"number"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; j--, i--) {
if (!Character.isDigit(newS[j])) {
newS[i] = newS[j];
} else {
newS[i] = 'r';
newS[i - 1] = 'e';
newS[i - 2] = 'b';
newS[i - 3] = 'm';
newS[i - 4] = 'u';
newS[i - 5] = 'n';
i -= 5;
}
}
return new String(newS);
};
}
151.翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：输入: "the sky is blue" 输出: "blue is sky the"
示例 2：输入: " hello world! " 输出: "world! hello"
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
将整个字符串都反转过来，单词本身也倒序了，那么再把单词反转一下，单词不就正过来了
移除多余空格
将整个字符串反转
将每个单词反转
举个例子，源字符串为："the sky is blue "
移除多余空格 : "the sky is blue"
字符串反转："eulb si yks eht"
单词反转："blue is sky the"
这样我们就完成了翻转字符串里的单词。
class Solution {
public String reverseWords(String s) {
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}