nSum 问题
如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，比如输入 nums = [1,3,5,6], target = 9，那么算法返回两个元素 [3,6]。
Java版nSum模板及4Sum调用示例：
public List<List<Integer>> fourSum(int[] nums, int target) {
// 排序
Arrays.sort(nums);
return nSum(nums, 4, 0, target);
}
// parameter1: 数组 parameter2: n parameter3: 数组中的起始位置 parameter4: 当前的目标
private List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
int len = nums.length;
// 存放结果的list
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (n < 2 || len < n)
return res;
// 当n == 2 时，最基本的双指针
if (n == 2) {
int small = start, big = len - 1;
while (small < big) {
int left = nums[small], right = nums[big];
int sum = left + right;
// 总和等于目标时，
if (sum == target) {
// 结果list添加新的值
res.add(new ArrayList<Integer>(Arrays.asList(left, right)));
// 去掉左边重复的元素
while (small < big && nums[small] == left)
small++;
// 去掉右边重复的元素
while (small < big && nums[big] == right)
big--;
} else if (sum > target) {
// 右指针向左移动 并去掉右边重复的元素
while (small < big && nums[big] == right)
big--;
} else if (sum < target) {
// 左指针向右移动 并去掉左边重复的元素
while (small < big && nums[small] == left)
small++;
}
}
} else {
// 当n != 2 时 准备进行递归调用
int i = start;
// 对start之后的每一个元素递归
while (i < len) {
int now = nums[i];
List<List<Integer>> sub = nSum(nums, n - 1, i + 1, target - now);
// 把当前值和递归结果合并，并加到res中
for (List<Integer> s : sub) {
s.add(now);
res.add(s);
}
// 对当前值进行去重
while (i < len && nums[i] == now)
i++;
}
}
return res;
}字符串匹配
Rabin-Karp 算法
利用滑动窗口，将窗口内中的字符串匹配成数字（哈希）
// Rabin-Karp 指纹字符串查找算法
int rabinKarp(String txt, String pat) {
// 位数
int L = pat.length();
// 进制（只考虑 ASCII 编码）
int R = 256;
// 取一个比较大的素数作为求模的除数
long Q = 1658598167;
// R^(L - 1) 的结果
long RL = 1;
for (int i = 1; i <= L - 1; i++) {
// 计算过程中不断求模，避免溢出
RL = (RL * R) % Q;
}
// 计算模式串的哈希值，时间 O(L)
long patHash = 0;
for (int i = 0; i < pat.length(); i++) {
patHash = (R * patHash + pat.charAt(i)) % Q;
}
// 滑动窗口中子字符串的哈希值
long windowHash = 0;
// 滑动窗口代码框架，时间 O(N)
int left = 0, right = 0;
while (right < txt.length()) {
// 扩大窗口，移入字符
windowHash = ((R * windowHash) % Q + txt.charAt(right)) % Q;
right++;
// 当子串的长度达到要求
if (right - left == L) {
// 根据哈希值判断是否匹配模式串
if (windowHash == patHash) {
// 当前窗口中的子串哈希值等于模式串的哈希值
// 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突
if (pat.equals(txt.substring(left, right))) {
return left;
}
}
// 缩小窗口，移出字符
windowHash = (windowHash - (txt.charAt(left) * RL) % Q + Q) % Q;
// X % Q == (X + Q) % Q 是一个模运算法则
// 因为 windowHash - (txt[left] * RL) % Q 可能是负数
// 所以额外再加一个 Q，保证 windowHash 不会是负数
left++;
}
}
// 没有找到模式串
return -1;
}KMP 算法
- 每次匹配不成功时，应该回退到哪？(回退到影子状态的位置)(影子状态是与当前状态有相同的前缀的状态)
- 影子状态怎么确定？(前进或回退到影子状态下出现该字符的状态)
// dp[j][c] 表示状态j下，出现字符c时，应该转移到的状态（只与pat有关）
private int [][] dp;
public int strStr(String txt, String pat) {
kmp(pat);
int M = pat.length(), N = txt.length();
// 从状态0开始
int j = 0;
for(int i = 0; i < N; i++){
// 状态的转移
j = dp[j][txt.charAt(i)];
// 当状态转移到最后，说明匹配成功
if(j == M){
// 返回初始下标
return i - M + 1;
}
}
return -1;
}
public void kmp(String pat){
int M = pat.length();
dp = new int [M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 定义影子状态，（与当前j状态有相同的前缀）
int X = 0;
// 状态从1开始
for(int j = 1; j < M; j++){
for(char c = 0; c < 256; c++){
// 当与字符匹配时，状态向前移
if(c == pat.charAt(j)){
dp[j][c] = j + 1;
}
// 否则回退到影子状态下出现字符c的状态
else{
dp[j][c] = dp[X][c];
}
}
// 更新影子状态(前进或回退到影子状态下出现该字符的状态)
X = dp[X][pat.charAt(j)];
}
}单调栈
输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1
输入数组[2,1,2,4,3] ------->结果数组[4,2,4,-1,-1]
int[] nextGreaterElement(int[] nums) {
int n = nums.length;
// 存放答案的数组
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
// 倒着往栈里放
for (int i = n - 1; i >= 0; i--) {
// 判定个子高矮
// 单调栈的精髓
while (!s.isEmpty() && s.peek() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的更大元素
res[i] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i]);
}
return res;
}
