# 排序算法

## 冒泡排序

``````public class Main {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int e = arr.length - 1; e > 0; e--) {
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
}``````

## 选择排序

``````public class Main {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
}``````

## 插入排序

``````public class Main {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
}``````

## 归并排序

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序

2）让其整体有序的过程里用了排外序方法

``````public class Main {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
}``````

### 小和问题

``````public class Main {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}

public static int mergeSort(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return mergeSort(arr, l, mid)
+ mergeSort(arr, mid + 1, r)
+ merge(arr, l, mid, r);
}

public static int merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
// 这里计算右边比左边某个值大的个数然后乘以左边值
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
}``````

## 堆排序

``````public class Main {
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
// 从下往上调整
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) /2);
index = (index - 1)/2 ;
}
}
// 从上往下调整
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
}``````

## 荷兰国旗问题

1.给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

``````public class Main {
/**
* 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
* 要求额外空间复杂度O(1)，时间复杂度O(N)
*
* l 指向小于等于num的最右下标，默认为-1
* 1. 若arr[i] <= num, 则arr[i]跟arr[l+1]进行交换, 交换后l++, i++
* 2. 若arr[i] > num, 则i++
*
* [小于等于num][大于num][待遍历]
* 所以当遇到arr[i] <= num, 则将小于等于num的后一个与arr[i]进行交换
*/
public static void NetherlandsFlag1(int[] arr, int num) {
int l = -1;
int i = 0;
while (i < arr.length) {
if (arr[i] <= num) {
swap(arr,i,l+1);
l++;
i++;
} else {
i++;
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}``````

2.给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度 O(N)

``````public class Main {
/**
* 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
* 要求额外空间复杂度O(1)，时间复杂度 O(N)
*
* int l = -1, r = arr.length
* l 指向小于num的最右下标, r指向大于num的最左下标
* 主要分成四个区间
* [小于num][等于num][待遍历][大于num]
* 1. 若arr[i] < num, 则arr[i]与[l+1]交换, i++, l++
* 2. 若arr[i] = num, 则i++
* 3. 若arr[i] > num, 则arr[i]与arr[r-1]交换, r--, 这一步主要是把大于num的数移到右边, 此时i不变
*/
public static void NetherlandsFlag(int[] arr, int num) {
int l = -1, r = arr.length;
int i = 0;
while (i < r) {
if (arr[i] < num) {
swap(arr, i, l+1);
i++;l++;
} else if (arr[i] == num){
i++;
} else {
swap(arr, i, r - 1);
r--;
}
}
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}``````

## 快速排序

``````
public class Main {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
//
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}

public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
}``````

# 链表问题

## 反转链表

``````class Solution {
ListNode pre = null;
ListNode next = null;
}
return pre;
}
}``````

## 判断链表是否为回文

1->2->3，返回false。

1.遍历链表，将数据依次入栈

2.遍历链表并将栈中的数据依次出栈，比较这两个数是否相等

1.使用快慢

``````class Solution {
return true;
}
// a -> b -> c -> null
// a -> b -> c -> d -> null
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
// mid 保存链表的中点位置
ListNode mid = n1;
// n1指向中点位置的下一个节点
n1 = n1.next;
mid.next = null;

// 反转n1
n1 = reverseList(n1);
// n3指向右边链表反转后的头结点
ListNode n3 = n1;
// n2指向链表的头结点

boolean res = true;
// 开始比较
while (n3 != null) {
if (n3.val != n2.val) {
res = false;
break;
}
n3 = n3.next;
n2 = n2.next;
}

// 比较完成之后还需要将链表连起来
// 反转n1
n1 = reverseList(n1);
//
mid.next = n1;

return res;
}
}``````

## 将单向链表按某值划分成左边小、中间相等、右边大的形式

1.将单链表的节点放入到数组中

2.组数组中使用荷兰国旗问题来划分值

3.然后将数组中的节点依次串起来

``````Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node bH = null; // big head
Node bT = null; // big tail``````

## 链表相交

``````public class Solution {
return null;
}
int count = 0;
while (curA.next != null) {
curA = curA.next;
count++;
}
while (curB.next != null) {
curB = curB.next;
count--;
}
if (curA != curB) {
return null;
}
count = Math.abs(count);
while (count > 0) {
curA = curA.next;
count--;
}
while (curA != curB) {
curA = curA.next;
curB = curB.next;
}
return curA;
}
}``````

## 环形链表

``````public class Solution {
return false;
}
while (f.next != null && f.next.next != null) {
s = s.next;
f = f.next.next;
if (s == f) {
return true;
}
}
return false;
}
}``````

``````public class Solution {
return null;
}
ListNode s = head; // 慢指针
ListNode f = head; // 快指针
while (f.next != null && f.next.next != null) {
s = s.next;
f = f.next.next;
if (s == f) {
break;
}
}
if (s == f) {
// 运行到这里，说明肯定有环，将快指针指向头结点
// 最终s和f相遇的节点就是入环的节点
while (s != f) {
s = s.next;
f = f.next;
}
return s;
} else {
return null;
}
}
}``````

# 二叉树

## 二叉树遍历

### 前序遍历-递归

``````public class Main {
public static void preOrderRecur(Node head) {
return;
}
}
}``````

### 前序遍历-非递归

``````public class Main {
public static void preOrderUnRecur(Node head) {
System.out.print("pre-order: ");
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty()) {
}
}
}
}
System.out.println();
}
}``````

### 中序遍历-递归

``````public class Main {
public static void inOrderRecur(Node head) {
return;
}
}
}``````

### 中序遍历-非递归

``````public class Main {
public static void inOrderUnRecur(Node head) {
System.out.print("in-order: ");
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
} else {
}
}
}
System.out.println();
}
}``````

### 后序遍历-递归

``````public class Main {
public static void posOrderRecur(Node head) {
return;
}
}
}``````

### 后序遍历-非递归

``````public class Main {
public static void posOrderUnRecur1(Node head) {
System.out.print("pos-order: ");
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
while (!s1.isEmpty()) {
}
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
}``````

## 判断是否是搜索二叉树

``````public class Main {
public static int preValue = Integer.MIN_VALUE;
public static boolean isBST(Node head) {
return true;
}
if (!leftIsBst) {
return false;
}
// 判断当前值是否大于前一个值
return false;
} else {
}
}
}``````

1.左边孩子是搜索二叉树

2.右孩子是搜索二叉树

3.左孩子的最大值小于头结点

4.右孩子的最小值大于头结点

``````public class Main {
public static class ReturnType {
public boolean isBST;
public int min;
public int max;
public ReturnType(boolean minisBST, int min, int max) {
this.isBST = isBST;
this.min = min;
this.max = max;
}
}
public static boolean isBST(Node head) {
}
private static ReturnType process(Node x) {
if (x == null) {
return null;
}
boolean isBST = true;
int min = x.value;
int max = x.value;
ReturnType leftData = process(x.left);
ReturnType rightData = process(x.right);
if (leftData != null) {
min = Math.min(min, leftData.min);
max = Math.max(max, leftData.max);
}
if (rightData != null) {
min = Math.min(min, rightData.min);
max = Math.max(max, rightData.max);
}

if (leftData != null
&&
(!leftData.isBST || leftData.max >= x.value)
) {
isBST = false;
}

if (rightData != null
&&
(!rightData.isBST || x.value >= rightData.min)
) {
isBST = false;
}

return new ReturnType(isBST, min, max);
}
}``````

## 判断完全二叉树

1.使用宽度遍历

2.如果遇到某个节点，左孩子为空，右孩子不为空，则返回false

3.在2条件不违规时，如果遇到了第一个左右孩子不双全的情况，接下来遇到的所有节点都是叶子节点

``````public class Main {
public static boolean isCBT(Node head) {
return true;
}
// 判断是否遇到第一个不双全的节点
boolean leaf = false;
Node l = null;
Node r = null;
while (!queue.isEmpty()) {
if (
// 遇到第一个左右孩子不双全的情况后，如果后面的节点还存在非叶子节点，则返回false
(leaf && (l != null || r != null))
||
// 左孩子为空，右孩子不为空，直接返回false
(l == null && r != null)
) {
return false;
}
if (l != null) {
}
if (r != null) {
}
// 第一次遇到左右孩子不双全的情况
if (l == null || r == null) {
leaf = true;
}
}
return true;
}
}``````

## 判断满二叉树

``````public class Main {
public static class ReturnData {
public int height;
public int nodes;
public ReturnData(int height, int nodes) {
this.nodes = nodes;
this.height = height;
}
}
public static boolean isFullTree(Node head) {
int heigth = result.height;
int nodes = result.nodes;
return nodes == (1 << heigth - 1); // nodes == 2 ^ n - 1
}
private static ReturnData process(Node x) {
if (x == null) {
return new ReturnData(0, 0);
}
ReturnData left = process(x.left);
ReturnData right = process(x.right);
int heigth = Math.max(left.height, right.height) + 1;
int nodes = left.nodes + right.nodes + 1;
return new ReturnData(heigth, nodes);
}
}``````

## 判断平衡二叉树

1.左子树与右子树的高度差不超过1

``````public class Main {
public static boolean isBalanced(Node head) {
}

public static class ReturnType {
public boolean isBalanced;
public int height;

public ReturnType(boolean isB, int hei) {
isBalanced = isB;
height = hei;
}
}

public static ReturnType process(Node x) {
if (x == null) {
return new ReturnType(true, 0);
}
ReturnType leftData = process(x.left);
ReturnType rightData = process(x.right);
int height = Math.max(leftData.height, rightData.height) + 1;
// 左右孩子都是平衡树
// 左右孩子高度差不能超过1
boolean isBalanced = leftData.isBalanced && rightData.isBalanced
&& Math.abs(leftData.height - rightData.height) < 2;
return new ReturnType(isBalanced, height);
}
}``````

## 二叉树的最近公共祖先

``````class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 保存所有节点的父节点
HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
// 父节点的头结点等于它自己
parentMap.put(root, root);
// 设置各节点的父元素
setParentNode(root, parentMap);

// 用来保存 o1 往上走经过的节点
Set<TreeNode> set1 = new HashSet<>();
TreeNode cur = p;
while (cur != parentMap.get(cur)) { // 头结点的父节点等于自己，一直从o1走到父节点
cur = parentMap.get(cur);
}

// 此时遍历o2的父节点，如果父节点存在set1里面，则这个就是他们的最低公共父节点
cur = q;
while (cur != parentMap.get(cur)) {
if (set1.contains(cur)) {
return cur;
}
cur = parentMap.get(cur);
}
// 最后一个肯定就是父节点了
return root;
}

private void setParentNode(TreeNode head, HashMap<TreeNode,TreeNode> parentMap) {
return;
}
}
}``````

``````class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果 root 为空 或者 遇到 p 或者遇到 q 则直接返回 root
// 这里相当于遇到空时返回空，遇到p 、 q时就返回 p 、 q
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
// 说明 p 和 q都已经遇到了，那么此时的 root 就是公共节点
return root;
}
// 这里有三种情况
// 1. left == null && right == null
// 2. left != null && right == null
// 3. left == null && right != null
// 如果存在不为空的，则返回不为空的那个
return left != null ? left : right;
}
}``````

# 前缀树

``````
class TrieNode {
public int path;
public int end;
public TrieNode[] nexts; // 这里也可以用Map数据结构

public TrieNode() {
this.path = 0;
this.end = 0;
this.nexts = new TrieNode[26];
}
}

class Trie {
public TrieNode root;
public Trie() {
root = new TrieNode();
}

public void insert(String word) {
if (word == null) {
return;
}
char[] chars = word.toCharArray();
TrieNode node = root;
node.path++;

for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.path++;
}
node.end++;
}
// word 这个单词之前加入过几次
public int search(String word) {
if (word == null) {
return 0;
}
char[] chars = word.toCharArray();
TrieNode node = root;
for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.end;
}
// 所有加入的字符串中，有几个是以 pre 这个字符串作为前缀的
public int prefixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] chars = pre.toCharArray();
TrieNode node = root;
for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.path;
}

// 所有加入的字符串中，有几个是以 pre 这个字符串作为前缀的
public void delete(String pre) {
if (search(pre) == 0) {
return;
}
char[] chars = pre.toCharArray();
int index = 0;
TrieNode node = root;
node.path--;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if (--node.nexts[index].path == 0) {
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
}``````

# 第二章

## 并查集

``````public class UnionFindSet<V> {
// 将样本包一层
class Element<V> {
public V value;
public Element(V value) {
this.value = value;
}
}

// 通过样本元素找到对应的 Element
private Map<V, Element> elementMap;
// Element 指向的父元素
private Map<Element, Element> fatherMap;
// 父Element下集合的大小
private Map<Element, Integer> sizeMap;

public UnionFindSet(List<V> list) {
this.elementMap = new HashMap<>();
this.fatherMap = new HashMap<>();
this.sizeMap = new HashMap<>();
// 初始化
for (V v : list) {
Element element = new Element(v);
elementMap.put(v, element);
fatherMap.put(element, element);
sizeMap.put(element, 1);
}
}

// 这个栈用来保存 element 查找父元素的路径
// 主要是有了为一个优化: 将一个长链表扁平化
// 比如:a -> b -> c -> d, 如传进来 element = a
// 那么 path = a、b、c, element = d
// 最后链表变成这样 a -> d, b -> d, c -> d
Stack<Element> path = new Stack<>();
while (element != fatherMap.get(element)) {
path.push(element);
element = fatherMap.get(element);
}
while (!path.isEmpty()) {
fatherMap.put(path.pop(), element);
}
return element;
}
// 判断a、b两个元素是否是同一个集合
public boolean isSameSet(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
}
return false;
}
public boolean union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
// 找到元素a的父元素
// 找到元素b的父元素
Element big = sizeMap.get(aH) >= sizeMap.get(bH) ? aH : bH;
Element small = big == aH ? bH : aH;
// 小集合的父元素指向大集合的父元素
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(big) + sizeMap.get(small));
sizeMap.remove(small);
}
return false;
}

public static void main(String[] args) {
List<String> list = new ArrayList<>();
UnionFindSet<String> unionFindSet = new UnionFindSet<>(list);
unionFindSet.union("A", "B");
System.out.println(unionFindSet.isSameSet("A", "C"));
unionFindSet.union("B", "C");
System.out.println(unionFindSet.isSameSet("A", "C"));
}
}``````

## 例题

### 岛屿数量

``````class Solution {
public int numIslands(char[][] grid) {
int N = grid.length;
int M = grid[0].length;
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (grid[i][j] == '1') {
res++;
infect(i, j, N, M, grid);
}
}
}
return res;
}

private void infect(int i, int j, int N, int M, char[][] grid) {
if (i < 0 || i >= N || j < 0 || j >= M || grid[i][j] != '1') {
return;
}
grid[i][j] = '2';
// 向下
infect(i + 1, j , N, M, grid);
// 向上
infect(i - 1, j , N, M, grid);
// 向右
infect(i, j + 1, N, M, grid);
// 向左
infect(i, j - 1 , N, M, grid);

}
}``````

[进阶]如何设计一个并行算法解决这个问题

## KMP

``````public class KMP {
/**
* 判断 m 是否是 s 的子串并返回 m 首次出现在 s 的下标
* 比如 s = abcdefg
* 若 m = def, 则返回3; 若 m = bbb, 则返回 -1
* 这里需要知道一个概念:前缀子串跟后缀子串
* 比如字符串:abbabb_ , 计算下划线前的前缀子串与后缀子串
* 长度为1时:前缀 = a, 后缀 = b, 前缀 != 后缀
* 长度为2时:前缀 = ab, 后缀 = bb, 前缀 != 后缀
* 长度为3时:前缀 = abb, 后缀 = abb, 前缀 = 后缀
* 长度为4时:前缀 = abba, 后缀 = babb, 前缀 != 后缀
* 长度为5时:前缀 = abbab, 后缀 = bbabb, 前缀 != 后缀
* 长度为6时:前缀跟后缀不能等于整体
*
* KMP算法中会用到一个辅助数组next,
* 这个数组记录的就是子串字符串在下标为i位置时最长前缀与最长后缀相等时的前缀长度(或者后缀长度)
* 比如字符串 m = abbabbc
* 根据上面的例子可以知道, i = 6 时, 最长前缀等于最长后缀的长度为3, 因此next[6]=3
* next[0] = -1, 因为下标为0之前已经没有字符了, 所以规定next[0] = -1
* next[1] = 0, 因为下标为1之前只有一个字符,因为前缀跟后缀不能等于整体,所以next[1]=0
*
* 有了这个辅助数组,在进行字符匹配的时候就可以减少很多次重复匹配
* 比如 s = abbabbabbs, m = abbabbs
* 第一次: i1 = 6, i2 = 6, s[6] = a, m[6] = s, s[6] != m[6]
*        此时出现第一次不相等, 通过m的next数组可以知道
*        对于m, 下标为6时, 它的最长前缀等于最长后缀的长度为3, s[6] != m[6]时, 令 i2 = next[i2] = 3
*        此时 i1 = 6, i2 = 3
*/
public static int getIndexOf(String s, String m) {
if (s == null || m == null || s.length() < m.length()) {
return -1;
}
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
// 获取next数组
int[] next = getNextArray(str2);
// i1 记录 str1 的下标, i2 记录 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) { // next[i2] == -1, 说明已经没有前缀了, 只能让 str1 的下标往前走
i1++;
} else {
i2 = next[i2]; // i2 往前走
}
}
return i2 == str2.length ? i1 - i2 : -1;
}

/**
* next数组的计算逻辑
* next[0] = -1;
* next[1] = 0;
*/
private static int[] getNextArray(char[] str) {
if (str.length == 1) {
return new int[]{-1};
}
int[] next = new int[str.length];
next[0] = -1;
next[1] = 0;
int i = 2;
/**
* cn 代表了两个含义
* 1. 最长前缀等于最长后缀的长度
* 2. 与 i-1位置进行比较的下标
*    如果 str[cn] == str[i-1], 则next[i] = next[i-1]+1
*    如果 str[cn] != str[i-1] && cn > 0, 则 cn = next[cn]
*    如果 str[cn] != str[i-1] && cn <= 0, 则next[i] = 0
*/
int cn = next[i - 1];
while (i < str.length) {
if(str[cn] == str[i - 1]) {
next[i] = cn + 1;
i++;
/**
* 因为i已经加1了, 所以cn记录的应该是i加1之前的长度, 因此cn也要加1
* 相当于 cn = next[i-1]
*/
cn++;
} else if (cn > 0) {
cn = next[cn];
} else {
// cn 已经不能往前走了
next[i] = 0;
i++;
}
}
return next;
}

public static void main(String[] args) {
String str = "abcabcababaccc";
String match = "ababa";
System.out.println(getIndexOf(str, match));
System.out.println(str.indexOf(match));
}
}``````

## Manacher

Manacher算法，又叫“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

Index 0 1 2 3 4 5 6 7 8 9 10
# a # b # a # c # d #
radius 1 2 1 4 1 2 1 2 1 2 1

`#a#b#c#b#b#`为例。

i = 0时, 回文串为`#`, R = 0, C = 0

i = 1时, 回文串`#a#`, R = 2, C = 1

i = 2时, 回文串为`#`

i = 3时, 回文串为#`#a#b#a#`, R = 6, C = 3

……

``````// abcbdk s kdbcba
//
/**
*
* 假设以C为中心点的左边界为L, 右边界为R, 当前位置为i,
* i' = 2*C - i, i'是以 C 为中心的对称点, [][L][][i'][][C][][i][][R][]
* 求i`主要是为了加速, 因为i'在i的左侧, i'的回文半径是已经知道了的
* 假设以i'为中心的回文区域的左边界为pL, 以i为中心的回文区域的右边界为pR
*
* 1. i > R, radius[i] = 1, 然后尝试往外扩
* 2. i <= R 时有以下两种情况
*    2.1 如果i'的回文区域左界pL >= L, 如下所示
*      [][L][pL][i'][][C][][i][pR][R][]
*      因为 L 和 R 之间是以 C 为中心的回文串, 所以i的回文半径长度等于i'的回文半径长度
*      因此: [pL][L][][i'][][C][][i][][R][pR]
*      那么此时i的回文区域右边界pR > R, 但此时大于R范围的数据是不知道的, 所以需要从R之后的位置继续尝试
*      因此, radius[i] = R - i
*/
public class Manacher {
public int maxLcpsLength(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] charArray = manacherString(str);
// 回文半径数组
// 回文右边界再往右一个位置, 回文右边界有效位置为 R - 1
int R = -1;
// 中心点
int C = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < radius.length; i++) {
radius[i] = R > i ? Math.min(radius[2 * C - i], R - i) : 1;
while (i + radius[i] < charArray.length && i - radius[i] >= 0) {
} else {
break;
}
}
if (i + radius[i] > R) {
C = i;
}
}
return max - 1;
}

private char[] manacherString(String str) {
char[] charArray = str.toCharArray();
char[] res = new char[charArray.length * 2 + 1];
int index = 0;
for (int i = 0; i < res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : charArray[index++];
}
return res;
}

public static void main(String[] args) {
Manacher manacher = new Manacher();
String str1 = "abc1234321ab";
System.out.println(manacher.maxLcpsLength(str1));
}
}``````

## 滑动窗口

[4 3 5]4 3 3 6 7

4[3 5 4]3 3 6 7

4 3[5 4 3]3 6 7

4 3 5[4 3 3]6 7

4 3 5 4[3 3 6]7

4 3 5 4 3[3 6 7]

``````public class Main {
public static void main(String[] args)  {
int[] arr = new int[]{4,3,5,4,3,3,6,7};
int w = 3;
int[] result = new int[arr.length - w + 1];
int index = 0;
// 每次都将数据从双端队列dqueue的尾部放进去
// 如果当前需要放进去的数据大于等于尾部代表的数据, 则弹出当前尾部的数据直到当前需要放进去的数据小于尾部代表的数据
// 从头部开始存放的数据都是单调递减的
// 即 dqueue 的头部保存的是当前滑动窗口的最大值的数组下标
for (int i = 0; i < arr.length; i++) {
// 如果存在 arr[i] >= arr[dqueue.getLast()], 则需要将尾部数据弹出
while (!dqueue.isEmpty() && arr[i] >= arr[dqueue.getLast()]) {
dqueue.removeLast();
}
// 判断当前头部的下标是否已经过期了 0 1 2 3 4
if (dqueue.getFirst() == i - w) {
// 头部下标已经过期, 则直接弹出头部
dqueue.removeFirst();
}
if (i >= w - 1) {
result[index++] = arr[dqueue.getFirst()];
}
}
System.out.println(JSON.toJSON(result));
}
}``````

``````
public class Main {
public static void main(String[] args)  {
int[] arr = new int[]{4,3,5,1,4,5,6,7};
int w = 3;
int[] result = new int[arr.length - w + 1];
int index = 0;
// dqueue 保存的数据是单调递增的
for (int i = 0; i < arr.length; i++) {
while (!dqueue.isEmpty() && arr[i] <= arr[dqueue.getLast()]) {
dqueue.removeLast();
}
// 判断头部是否过期
if (dqueue.getFirst() == i - w) {
dqueue.removeFirst();
}
if (i >= w - 1) {
result[index++] = arr[dqueue.getFirst()];
}
}
System.out.println(JSON.toJSON(result));
}
}``````

7个月前 评论

1个月前 评论

1个月前 评论

62

5

14

16