2022-05-28 20:10 已编辑电子科技大学 Java

关注

数据结构

KMP

代码

public class Code01_KMP {

	public static int getIndexOf(String s, String m) {
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		char[] str1 = s.toCharArray();
		char[] str2 = m.toCharArray();
		int i1 = 0;//做比较的位置
		int i2 = 0;
		int[] next = getNextArray(str2);
		while (i1 < str1.length && i2 < str2.length) {
			if (str1[i1] == str2[i2]) {
				i1++;
				i2++;
			} else if (next[i2] == -1) {//也可以写成 i2==0，表示跟字串2开头的一个字符都不相等，只能调整str1的比较位
				i1++;
			} else {
				i2 = next[i2];
			}
		}
		return i2 == str2.length ? i1 - i2 : -1;
	}

	public static int[] getNextArray(char[] ms) {
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		int[] next = new int[ms.length];
		next[0] = -1;
		next[1] = 0;
		int i = 2;
		int cn = 0;//cn表示正在拿哪个位置的字符与i-1位置上的字符比较，cn位置上的字符即ms[cn].
        //怎么确定这个位置呢？就是看ms[i-1]的值
        //初始化为0是因为，最开始ms[i-1]=ms[1]=0;
		while (i < next.length) {
			if (ms[i - 1] == ms[cn]) {//此时的ms[cn]也表示以0位置字符为前缀的最长相同段，的下一个字符,cn是ms[i-1]的值
            //为什么是i-1，因为next[i]与i位置字符完全没关系，只与它前面所有字符有关，看的是以i-1位置字符为后缀的字符串，与0位置为前缀的字符串，相等的最大长度
				next[i++] = ++cn;
			} else if (cn > 0) {//还能往前跳
				cn = next[cn];
			} else {
				next[i++] = 0;
			}
		}
		return next;
	}

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

	}

}

双指针

双指针技巧汇总（含滑动窗口）

并查集

适于 “没有顺序，但有关系” 的情形，如岛屿问题lc.ofeer.105（关系就是相邻）、最长序列链接（关系就是数值连续/不要求在数组中按顺序，如果有顺序，则可以用滑动窗口）

代码模板：E:\桌面\kkys\左神算法资料\基础提升班\1.1 课前预习（课件+源码）\提升班第一课代码\class01\Code04_UnionFind

岛屿问题

lc.ofeer.105

labuladong文章！

代码模板： 用infect方法渲染，找到某位置为1，则计一次数，之后把他，即它的周围所有位置感染为2（非1即可），避免重复计数 alt alt

链表

判断是否为环形链表

leetcode评论区

求环形链表入环结点

alt

两单链表（有环或无环）是否相交问题

均无环（Y字型）
一个链表有环、一个无环（不可能）
蜗牛型🐌（和情况1类似，只是把第一循环的终止节点由末尾，改在入环节点）
🐱型（返回左耳或右耳都对，都叫第一个相交的节点）：从其中一个入环节点继续往前走，如果行至一圈途中遇到了另一个节点，就说明相交

删除链表的倒数第N个结点

fast指针先走n步（此处fast是一步一步走的，只是为了说明双指针，取这个名字）然后fast、slow一起走，fast走到最后一个结点时，slow走到待删除结点的前一个结点

奇下标+偶下标

4个指针，拉拉链（+2步）

（奇拉链头、奇拉链、偶拉链、偶拉链头）

回文结构（）

左神代码：基础班第四课class04

栈：先入栈，然后将弹出元素与链表从头挨个儿比较
（1）用快慢指针找到中心位置，注意偶数情况

（2）将右半部分链表反转（用3个指针）

（3）左右两半数值比较，用boolean类的flag指示

（4）将右半部分还原（即还原链表原始样子）

旋转链表

先遍历一遍，得到链表长度，顺便将链表首尾相连成环

确定循环后链表的头点点位置，拆环

队列和栈

线性表有顺序存储和链式存储两种方式，而栈和队列都属于线性表，所以也有这两种方式

队列

alt

front指向队头元素，rear指向队尾元素的下一个位置（要浪费一个数组位置）

循环队列判断队空：rear==front
循环队列判断队满：(rear+1)%size==front
计算队列长度：(rear-front+size)%size

size是数组的长度，而不是队列的长度，满队列时，size=队列长度+1

leetcode模板中tail是指向最后一个元素的，且队空后，head和tail都要回到-1，也就是队空判断条件为head==-1（可以不按给的模板来）

队列用法： leetcode模板中前面加上

import java.util.LinkedList;
import java.util.Queue;

队列中方法add()与offer()的区别

两者都是往队列尾部插入元素，不同的是，当超出队列界限的时候，add（）方法是抛出异常让你处理，而offer（）方法是直接返回false

JAVA 栈，为什么要使用Deque，而不推荐使用Stack，Deque中ArrayDeque与LinkedList的区别?

csdn戳~

二叉树

疑点

为什么有时候要判断左右节点是否为空，再入队列，有时不用?

队列一般用于层序遍历中，用于得到最大宽度、判断是否为完全二叉树等。当空结点也算数时，如leetcode662，不用判断，直接入队；当不遍历空结点时，先判断再入队

递归序

先序遍历：递归序中，只打印第一次到达的数字

中序遍历：递归序中，只打印第二次到达的数字

后序遍历：递归序中，只打印第三次到达的数字

深度优先遍历=前序遍历

宽度优先遍历（层次遍历）

T98.判断搜索二叉树

法1：中序遍历(遍历后所得数组一定是有序的，从小到大)

法2：递归

T662.二叉树的最大宽度

包装（结点、所在层序、结点位置）
basecase : root为空，返回0
初始值（当前层1、位置1、结果1）
判断队列是否为空-出队-往队列中添加其左右孩子，计算位置-判断层数是否为当前统计层，得到最左位置-一层遍历完就是最右位置-计算输出max()

注：如果空位置也算宽度，那么直接将左右结点r入队，不用判断是否为空；否则，要先判断。

T958 判断完全二叉树

含义：在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。

思路：

层序遍历（用队列）
如果有一个结点只有右子树没有左子树，直接返回false
若上一步没有false，那么如果遇到了第一个左右子树不全的点（没有子、或者只有左没有右），设置flag，那么从该点往后所有的结点都必须是叶子节点（不能有孩子）

判断平衡二叉树

含义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1

思路：对每一个结点，要求：

其左树为平衡二叉树
其右树为平衡二叉树
其左树与右数高度差不超过1

递归，需要从左孩子和右孩子身上得到其高度和它是否为平衡二叉树的信息

T236.二叉树的最近公共祖先

思路：结点o1、o2的位置分两种情况

o1和o2在一条链上，o1或o2即为所求
o1和o2分开，不在一条链上

找已知父结点的二叉树的（中序）后继结点

思路：寻找某结点的后继结点，分三种情况

该结点有右树，其后继为右树上的最左结点
该结点没有右树，找它的父节点，如果它的父节点为它爷爷结点的左节点，则返回其爷爷结点
该结点是最后一个结点，没有后继结点

找搜索二叉树的（中序）后继结点

思路：

下一个节点的值一定不会小于节点p的值，而是大于或等于节点p的值中的所有节点中值最小的一个
从根节点开始，每到达一个节点就比较根节点的值和节点p的值
如果当前节点的值小于或等于节点p的值，那么节点p的下一个节点应该在它的右子树
如果当前节点的值大于或等于节点p的值，那么当前节点有可能是p的下一个节点，此时当前节点的值比节点p的值大，但节点p的下一个节点是所有比它大的节点中值最小的一个，因此接下来前往当前节点的左子树，确定是否能找到值更小，但仍然大于节点p的值的节点