AcWing-算法基础课笔记（java）-数据结构

单链表

模板

//单链表类
public class SingleLinkedList {
	private final static int N = 100010;//数据规模为10W
	private static int head;// 头节点
	private static int[] val = new int[N];// 数据值
	private static int[] next = new int[N];// next域，通过val[]函数的索引查询它的索引所代表的数据的next域的索引
	private static int index;// val[]非空数据的最后一个数据的下一位索引（即val[0~length-1]有值，val[length]是空的）

	// 初始化单链表，构造函数
	public SingleLinkedList() {
		head = -1;// 没有头节点
		index = 0;// 新加入的数据应该添加到val[0]
	}

	// 插入头节点
	public void insertHead(int x) {
		val[index] = x;// 添加新数据到val[]数组最后一个位置（最后一个位置模拟头节点）
		next[index] = head;// 新插入的数据的next域是原来的头节点，新插入的数据做新的头节点
		head = index++;// 将新插入的数据的索引赋值成新的头节点，模拟在单链表的头部插入数据，index++用于下一次插入做准备
	}

	// 删除头节点
	private void removeHead() {
		head = next[head];
		// 将头节点的next域赋值给头节点，即原头节点数据不会再被查询，index插入新的节点时也不会涉及到该节点
	}

	// 遍历所有数据打印输出
	private void printData() {
		// 初始化是head = -1，因此链表最后一个节点的next[] = -1
		for (int i = head; i != -1; i = next[i]) {
			System.out.print(val[i] + " ");
		}
	}
}

题解-826.单链表

import java.util.Scanner;

public class Main{
	private final static int N = 100010;//数据规模为10W
	private static int head;//头节点
	private static int[] val = new int[N];//数据值
	private static int[] next = new int[N];//next域，通过val[]函数的索引查询它的索引所代表的数据的next域的索引
	private static int index;//val[]非空数据的最后一个数据的下一位索引（即val[0~length-1]有值，val[length]是空的）
	
	//初始化单链表，构造函数
	public static void initSingleLinkedList(){
		head = -1;//没有头节点
		index = 0;//新加入的数据应该添加到val[0]
	}
	
	// 插入头节点
	public static void insertHead(int x) {
		val[index] = x;// 添加新数据到val[]数组最后一个位置（最后一个位置模拟头节点）
		next[index] = head;// 新插入的数据的next域是原来的头节点，新插入的数据做新的头节点
		head = index++;// 将新插入的数据的索引赋值成新的头节点，模拟在单链表的头部插入数据，index++用于下一次插入做准备
	}
	
	//插入节点（在第 k个插入的数后插入一个数）
	private static void insert(int k,int x) {
		val[index] = x;//将数据添加到数组末端
		next[index] = next[k];//将index位置数据的next更新为原来第k个数据的next域
		next[k] = index++;//将原来第k个数据的next域更新为新插入的index。index++
	}
	
	// 删除头节点
	private static void removeHead() {
		head = next[head];
		// 将头节点的next域赋值给头节点，即原头节点数据不会再被查询，index插入新的节点时也不会涉及到该节点
	}
	
	//删除第k个插入的数后面的一个数（第 k个插入的数并不是指当前链表的第 k 个数）
	private static void remove(int k) {//k > 0，k == 0时是插入头节点
		//由于删除操作并不会删除插入的数据，只是被删除的位置不能被访问到，因此val[k-1]就是所谓的第k个插入的数
		next[k] = next[next[k]];//将第k个数的next域更新
	}
	
	//遍历所有数据打印输出
	private static void printData() {
		//初始化是head = -1，因此链表最后一个节点的next[] = -1
		for(int i = head;i != -1;i = next[i]) {
			System.out.print(val[i] + " ");
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		initSingleLinkedList();//初始化单链表
		while(m-- > 0) {
			String s = sc.next();//操作名
			switch(s) {
				case "H"://头节点插入
					int x = sc.nextInt();
					insertHead(x);
					break;
				case "D"://删除当 k为 0时，表示删除头结点
					int k = sc.nextInt();
					if(k == 0) removeHead();
					else remove(k - 1);
					break;
				case "I"://第k个数后面插入(k > 0)
					int k1 = sc.nextInt();
					int x1 = sc.nextInt();
					insert(k1 - 1,x1);
					break;
			}
		}
		printData();
	}
}

双链表

解析

使用数组模拟双链表

数组下标：节点的地址，val[]：节点值，left[]：左节点地址，right[]：右节点地址
初始化：right[0] = 1，left[1] = 0表示左、右边界，index = 2为下一个新节点的地址

对于数据在最左侧、最右侧插入的解析：

在第k个插入的数左、右侧插入一个数，删除第k个插入的数据：参考大佬题解

题解-827.双链表

import java.util.Scanner;

public class Main {
	private static final int N = 100010;// 数据范围10W
	private static final int[] val = new int[N];// 数据值
	private static final int[] left = new int[N];// 左节点索引
	private static final int[] right = new int[N];// 右节点索引
	private static int index;

	// 双链表初始化
	public static void initDoubleLinkedList() {
		left[1] = 0;// 双链表的尾节点（反向遍历不会超出数组索引）
		right[0] = 1;// 双链表的头节点（正向遍历不会超出数组索引）
		index = 2;
	}

	// 1.在最左侧插入一个数
	public static void insertL(int x) {
		val[index] = x;
		right[index] = right[0];
		left[index] = 0;
		left[right[0]] = index;
		right[0] = index++;
	}

	// 2.在最右侧插入一个数
	public static void insertR(int x) {
		val[index] = x;
		right[index] = 1;
		left[index] = left[1];
		right[left[1]] = index;
		left[1] = index++;
	}

	// 3.将第k个插入的数删除（初始化时index = 2，因此调用函数时k = k + 1）
	public static void removeK(int k) {
		right[left[k]] = right[k];
		left[right[k]] = left[k];
	}

	// 4.在第k个插入的数左侧插入一个数（初始化时index = 2，因此调用函数时k = k + 1）
	public static void insertKL(int k, int x) {
		insertKR(left[k], x);
	}

	// 5.在第k个插入的数右侧插入一个数（初始化时index = 2，因此调用函数时k = k + 1）
	public static void insertKR(int k, int x) {
		val[index] = x;
		right[index] = right[k];
		left[index] = k;
		left[right[k]] = index;
		right[k] = index++;
	}
	
	//正向遍历打印数据
	public static void printData() {
		for(int i = right[0];i != 1;i = right[i]) {
			System.out.print(val[i] + " ");
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		initDoubleLinkedList();//初始化
		while(m-- > 0) {
			String s = sc.next();
			int k,x;
			switch(s) {
				case "L"://在链表最左端插入数据
					x = sc.nextInt();
					insertL(x);
					break;
				case "R"://在链表最右端插入
					x = sc.nextInt();
					insertR(x);
					break;
				case "D"://将第k个插入的数据删除
					k = sc.nextInt();
					removeK(k + 1);
					break;
				case "IL"://在第k个插入的数据的左侧插入一个数
					k = sc.nextInt();
					x = sc.nextInt();
					insertKL(k + 1,x);
					break;
				case "IR"://在第k个插入的数据的右侧插入一个数
					k = sc.nextInt();
					x = sc.nextInt();
					insertKR(k + 1,x);
					break;
			}
		}
		printData();
	}
}

栈

模板

使用数组模拟栈

private static final int N = 100010;//数据范围
private static final int[] st = new int[N];//栈数组
private static int tt = 0;//栈顶指针，初始化为指向指向索引0，索引0的位置上不会存入元素

//压栈
public static void push(int x) {
	st[++tt] = x;
}

//弹栈
public static void pop() {
	tt--;
}

//是否为空栈，true表示是空栈
public static boolean isEmpty() {
	return tt <= 0;//数组st从索引为1的位置开始存入元素
}

//获取栈顶元素
public static int getTop() {
	return st[tt];
}

题解-828.模拟栈

使用数组模拟栈

所有操作保证合法，即不会在栈为空的情况下进行 pop 或 query 操作。不会出现索引异常操作

import java.util.Scanner;

public class Main{
	private static final int N = 100010;//数据范围
	private static final int[] st = new int[N];//栈数组
	private static int tt = 0;//栈顶指针，初始化为指向指向索引0，索引0的位置上不会存入元素
	
	//压栈
	public static void push(int x) {
		st[++tt] = x;
	}
	
	//弹栈
	public static void pop() {
		tt--;
	}
	
	//是否为空栈，true表示是空栈
	public static boolean isEmpty() {
		return tt <= 0;//数组st从索引为1的位置开始存入元素
	}
	
	//获取栈顶元素
	public static int getTop() {
		return st[tt];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		while(m-- > 0) {
			String s = sc.next();
			switch(s) {
				case "push":
					int x = sc.nextInt();
					push(x);
					break;
				case "pop":
					pop();
					break;
				case "empty":
					if(isEmpty()) System.out.println("YES");
					else System.out.println("NO");
					break;
				case "query":
					System.out.println(getTop());
					break;
			}
		}
	}
}

题解-3302.表达式求值

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;

public class Main{
	public static Stack<Integer> num = new Stack<>();//操作数栈
	public static Stack<Character> operator = new Stack<>();//运算符栈
	
	public static void calculate() {
		int a = num.pop();//弹出右操作数
		int b = num.pop();//左操作数
		char c = operator.pop();//弹出运算符
		switch(c) {//数学运算
			case '+':num.push(b + a);break;
			case '-':num.push(b - a);break;
			case '*':num.push(b * a);break;
			case '/':num.push(b / a);break;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Character,Integer> map = new HashMap<>();//用于存储运算符的优先级
		map.put('+', 1);//加、减的优先级为1
		map.put('-', 1);
		map.put('*', 2);//乘除的优先级为2
		map.put('/', 2);
		String s = br.readLine();//读入算式
		int length = s.length();//算式长度
		for(int i = 0;i < length;i++) {
			char c = s.charAt(i);//遍历读取字符串s的每个字符
			if(Character.isDigit(c)) {//数字，获取完整的多位数字
				int x = 0;//用于存储多位数字
				int j = i;//用于判断当前字符的下一位字符的类型
				while(j < length && Character.isDigit(s.charAt(j))) {
					x = x * 10 + (s.charAt(j++) - '0');//s.charAt(j++) - '0'将字符数字转换为int类型
					//x初始为0，如果j的字符是数字，将上一位字符数字升高一位。j++获取下一位字符
				}
				num.push(x);//数字压栈
				i = j - 1;//s.charAt(j)非数字，由于有i++，j - 1防止跳过一个字符
			}else if(operator.isEmpty() || c == '(') {//运算符栈空、左括号优先级最高，直接压栈
				operator.push(c);
			}else if(c == ')') {//弹栈，直到弹出第一个左括号
				while(operator.peek() != '(')
					calculate();//计算()中的内容，函数中会弹出()内的运算符以及操作数
				operator.pop();//弹出'('
			}else{//比较优先级，operator弹栈，直到自己的优先级比栈顶元素的优先级高，或者栈顶元素是'('
				while(!operator.isEmpty() && operator.peek() != '(' && map.get(c) <= map.get(operator.peek()))
					calculate();//计算优先级高的算式步骤
				operator.push(c);
			}
		}
		//运算符剩余运算符全部计算、弹栈，进行剩余算式步骤的计算
		while(!operator.isEmpty()) calculate();
		System.out.println(num.pop());	
	}
}

队列

模板

数组模拟队列

//模拟队列
private static class SimulatedQueue{
	public static final int N = 100010;//数据范围
	public static int[] q = new int[N];//数据存储
	public static int head = 0;//队头指针，当head > tail时，表示队列为空
	public static int tail = -1;//队尾指针，始终指向队尾元素，初始化指向队首的前一个
	
	//向队尾插入一个数
	public static void push(int x) {
		q[++tail] = x;//先++找空白位置，再读入数据
	}
	
	//从队头弹出一个数
	public static void pop() {
		head++;
	}
	
	//判断队列是否为空
	public static boolean isEmpty() {
		return head > tail;//空为true，尾指针始终指向最后一个元素，最后一个元素出队时，head = tail + 1
	}
	
	//查询队头元素
	public static int peek() {
		return q[head];
	}
	//查询队尾元素
	public static int peekTail() {
		return q[tail];
	}
}

题解-829.模拟队列

import java.util.Scanner;

public class Main {
	public static final int N = 100010;// 数据范围
	public static int[] q = new int[N];// 数据存储
	public static int head = 0;// 队头指针，当head > tail时，表示队列为空
	public static int tail = -1;// 队尾指针，始终指向队尾元素，初始化指向队首的前一个

	// 向队尾插入一个数
	public static void push(int x) {
		q[++tail] = x;// 先++找空白位置，再读入数据
	}

	// 从队头弹出一个数
	public static void pop() {
		head++;
	}

	// 判断队列是否为空
	public static boolean isEmpty() {
		return head > tail;// 空为true，尾指针始终指向最后一个元素，最后一个元素出队时，head = tail + 1
	}

	// 查询队头元素
	public static int peek() {
		return q[head];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		while(m-- > 0) {
			String s = sc.next();
			switch(s) {
				case "push":
					int x = sc.nextInt();
					push(x);
					break;
				case "pop":
					pop();
					break;
				case "empty":
					if(isEmpty()) System.out.println("YES");
					else System.out.println("NO");
					break;
				case "query":
					System.out.println(peek());
					break;
			}
		}
	}
}

单调栈

单调栈的思想

利用不断迭代的方式，将当前的元素x与栈顶元素进行比较，按照单调性性质来决定是哪种操作：

栈顶元素弹栈（x > 栈顶元素时，压栈；否则弹栈，直至 x > 栈顶元素）
将当前元素压栈（保持单调性：栈中元素始终是单调递增的）

模板

while(m-- > 0) {  
	int x = sc.nextInt();
    while (!st.empty() && st.query() >= x) {  //栈非空，query获取栈顶元素
        st.pop(); //x > 栈顶元素 时，压栈；否则弹栈，直至 x > 栈顶元素
    }  
    // ... 
    st.push(x);  
}

题解-830.单调栈

import java.util.Scanner;

public class Main {
	public static int[] st = new int[100010];
	public static int tt = 0;//栈顶指针，索引0的位置上不会存入元素
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		while(m-- > 0) {
			int x = sc.nextInt();
			//x > 栈顶元素 时，压栈；否则弹栈，直至 x > 栈顶元素
			while(tt != 0 && st[tt] >=  x) tt--;
			if(tt == 0) System.out.print("-1 ");//栈空
			else System.out.print(st[tt] + " ");
			st[++tt] = x;
		}
	}
}

单调队列

大佬的代码

图解：求最小值

求最小值：如果遍历到的数据和队尾数据相等？？？？
直接入队-> 不大于队尾数据的都直接入队
原因：

虽然两个数据值相同（假设两个数据为x1，x2，x1 = x2），但是两个数据在原数组的位置是不一样的，因此，滑动窗口会先后经过两个数据；
如果只有x1先进入队列，x2遇见x1导致x1被弹出，当x1滑出滑动窗口之后，队头的x2会出队（如果队列存储的是数据a[x2]，而不是数据的索引时，会发生接下来的情况），可能导致接下来的几个滑动窗口的最小值发生错误

注意：队列存储的是数据的索引，否则在确定队头是否出队的时候可能产生歧义

模板

常见模型：找出滑动窗口中的最大值、最小值

Deque<Integer> q = new ArrayDeque<>();//双向队列，存储下标
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] a = new int[n + 1];//原始数据
StringBuilder s1 = new StringBuilder();//答案数据串

//获取最小值（队列递增），队首始终最小
for(i = 1;i <= n;i++) {
	//当队列非空、遍历到的数据 < 队尾元素，队尾出队
	while(q.size() > 0 && a[q.peekLast()] > a[i]) q.pollLast();
	q.add(i);
	//如果队头滑出窗口，将对头出队
	if(i > k && q.peekFirst() == i - k) q.pollFirst();
	//窗口形成，开始输出答案
	if(i >= k) s1.append(a[q.peekFirst()] + " ");
}
bw.write(s1+"\n");

q = new ArrayDeque<>();//清空队列
s1 = new StringBuilder();//清空答案串

//获取最大值（队列递减），队首始终最大
for(i = 1;i <= n;i++) {
	//当队列非空、遍历到的数据 > 队尾元素，队尾出队
	while(q.size() > 0 && a[q.peekLast()] < a[i]) q.pollLast();
	q.add(i);
	//如果队头滑出窗口，将对头出队
	if(i > k && q.peekFirst() == i - k) q.pollFirst();
	//窗口形成，开始输出答案
	if(i >= k) s1.append(a[q.peekFirst()] + " ");
}

题解-154.滑动窗口

注意输入输出的加速
使用双向队列：基于循环数组(ArrayDeque)实现

读取数据：BufferedReader + InputStreamReader
输出数据：StringBuilder + BufferedWriter + OutputStreamWriter

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	public static void main(String[] args) throws IOException {
		Deque<Integer> q = new ArrayDeque<>();//双向队列，存储下标
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int k = Integer.parseInt(s[1]);
		int[] a = new int[n + 1];//原始数据
		int i;
		String[] arr = br.readLine().split(" ");
		//读取数据，数组a从1开始存储数据，方便计算窗口的位置
		for(i = 1;i <= n;i++) a[i] = Integer.parseInt(arr[i - 1]);
		
		StringBuilder s1 = new StringBuilder();//答案数据串
		
		//获取最小值（队列递增），队首始终最小
		for(i = 1;i <= n;i++) {
			//当队列非空、遍历到的数据 < 队尾元素，队尾出队
			while(q.size() > 0 && a[q.peekLast()] > a[i]) q.pollLast();
			q.add(i);
			//如果队头滑出窗口，将对头出队
			if(i > k && q.peekFirst() == i - k) q.pollFirst();
			//窗口形成，开始输出答案
			if(i >= k) s1.append(a[q.peekFirst()] + " ");
		}
		bw.write(s1+"\n");
		
		q = new ArrayDeque<>();//清空队列
		s1 = new StringBuilder();//清空答案串
		
		//获取最大值（队列递减），队首始终最大
		for(i = 1;i <= n;i++) {
			//当队列非空、遍历到的数据 > 队尾元素，队尾出队
			while(q.size() > 0 && a[q.peekLast()] < a[i]) q.pollLast();
			q.add(i);
			//如果队头滑出窗口，将对头出队
			if(i > k && q.peekFirst() == i - k) q.pollFirst();
			//窗口形成，开始输出答案
			if(i >= k) s1.append(a[q.peekFirst()] + " ");
		}
		bw.write(s1+"\n");
		bw.flush();
		br.close();
		bw.close();
	}
}

KMP

主串：s。
模式串：p。
前缀：字符串的除去最后一个字符的全部头组合。
后缀：字符串的除去第一个字符的全部尾组合。
部分匹配值：前缀和后缀的最长共有元素的长度。
next数组：是“部分匹配值表”，存储的是每一个下标对应的“部分匹配值”。

next数组

定义：

解释&模拟
next[j] ，是模式串的子串p[1,j]串中前缀和后缀相同的最大长度（部分匹配值），即 p[1,next[j]] = p[j - next[j] + 1, j]。

模板代码模拟：

模板

// s[]是主串，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = next[j];
    if (p[i] == p[j + 1]) j ++ ;
    next[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = next[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)//模式串匹配完了
    {
        j = next[j];
        // 匹配成功后的逻辑
    }
}

题解-831.KMP字符串

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static char[] s;//主串
	public static char[] p;//模式串
	public static int[] next;//匹配值数组
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		p = new char[n + 1];//模式串初始化
		String pp = br.readLine();//模式串
		int m = Integer.parseInt(br.readLine());
		s = new char[m + 1];//主串初始化
		String ss = br.readLine();//主串
		
		int i,j;
		for(i = 0;i < n;i++) {
			p[i + 1] = pp.charAt(i);
		}
		for(i = 0;i < m;i++) {
			s[i + 1] = ss.charAt(i);
		}

		//求next数组，初始化全为0，next[1] = 0，所以不用写
		next = new int[n + 1];
		for(i = 2,j = 0;i <= n;i++) {//p[n + 1]
			while(j > 0 && p[i] != p[j + 1]) j = next[j];
			if(p[i] == p[j + 1]) j++;
			next[i] = j;
		}
		
		StringBuilder ans = new StringBuilder();//答案
		//匹配过程s[1~m]，p[0~n]，p的起始位置是0，但是实际上p[0]没有数据
		for(i = 1,j = 0;i <= m;i++) {
			while(j > 0 && s[i] != p[j + 1]) j = next[j];
			if(s[i] == p[j + 1]) j++;
			if(j == n) {
				//输出所有出现位置的起始下标（下标从 0开始计数），由于s、p从1开始存储，所以(i-1)-(n-1)==i-n
				ans.append((i - n) + " ");
				j = next[j];//当主串找到了一个匹配的部分串，这个匹配的部分串的尾部可以做下一个匹配的部分串的前缀
			}
		}
		
		bw.write(ans + "\n");
		bw.flush();
		br.close();
		bw.close();
	}
}

更新中...

posted @ 2025-02-06 19:09 idle_life 阅读(34) 评论(0) 收藏举报

刷新页面返回顶部

idlelife