这是我用于分享和复习算法笔记的地方，此篇主要是围绕关于数据结构的一些算法题。我在AcWing上刷题，可以和我一起:)AcWing 826. 单链表原址解题过程import java.io.*; import java.util.*; public class Main { private static final int N = 100010; private static final int[] e = new int[N]; private static final int[] ne = new int[N]; private static int idx; private static int head; public static void main(String[] args) throws IOException{ init(); //单链表 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); while(n -- > 0) { arrStr = br.readLine().split(" "); String let = arrStr[0]; if("H".equals(let)) { int x = Integer.parseInt(arrStr[1]); addToHead(x); } if("D".equals(let)) { int k = Integer.parseInt(arrStr[1]); if(k == 0) head = ne[head]; else remove(k - 1); } if("I".equals(let)) { int k = Integer.parseInt(arrStr[1]); int x = Integer.parseInt(arrStr[2]); add(k - 1, x); } } for(int i = head ;i != -1;i= ne[i]) System.out.print(e[i] + " "); br.close(); } private static void init() { //初始化的方法 idx = 0; head = -1; } //将x插入到头结点 private static void addToHead(int x ) { e[idx] = x; ne[idx] = head; head = idx ++; } //将x插入到下标为k的结点后,尾插法 private static void add(int k,int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx ++; } //删除下标为k后面的结点删除 private static void remove(int k) { ne[k] = ne[ne[k]]; } } 附上我的视频，(●'◡'●)[video title="单链表 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/%E5%8D%95%E9%93%BE%E8%A1%A8.mkv " container="b8fo4ln3enn" subtitle=" " poster=" "] [/video]AcWing 829. 模拟队列原址解题过程import java.io.*; import java.util.*; public class Main { private static final int N = 100010; private static final int[] q = new int[N]; private static int hh = 0;//队头 private static int tt = -1;//队尾 //往队尾插入元素，队头弹出元素 public static void main(String[] args) throws IOException{ //829. 模拟队列 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arrStr = br.readLine().split(" "); int m = Integer.parseInt(arrStr[0]); while(m-- > 0) { arrStr = br.readLine().split(" "); String str = arrStr[0]; switch(str) { case "push": int x = Integer.parseInt(arrStr[1]); insert(x); break; case "pop": popFirst(); break; case "empty": String res = isEmpty(); System.out.println(res); break; default : int ans = query(); System.out.println(ans); } } br.close(); } //队尾插入 private static void insert(int x ) { q[++tt] = x; } //队头弹出 private static void popFirst() { hh++; } //判断队列是否为空 private static String isEmpty() { return hh > tt ? "YES": "NO"; } //查询对头元素 队尾元素q[tt] private static int query() { return q[hh]; } } 附上我的视频，用于复习。[video title="模拟队列 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/%E9%98%9F%E5%88%97.mkv " container="b9rk5gti6ee" subtitle=" " poster=" "] [/video]AcWing 831. KMP字符串原址解题过程 import java.util.*; import java.io.*; public class Main { private static final int N = 1000010; private static final int[] ne = new int[N]; public static void main(String[] args) throws IOException{ //831. KMP字符串 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); String str = br.readLine(); char[] p = new char[n + 5]; for(int i = 1 ;i <= n ; i++) p[i] = str.charAt(i - 1); arrStr = br.readLine().split(" "); int m = Integer.parseInt(arrStr[0]); str = br.readLine(); char[] s = new char[m + 5]; for(int i = 1; i <= m; i++) s[i] = str.charAt(i - 1); kmp(p,n,s,m); bw.flush(); br.close(); bw.close(); } private static void kmp(char[] p ,int n ,char[] s,int m) throws IOException{ BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //next最大公共前后缀字符串的创建 for(int i = 2 ,j = 0 ; i <= n; i++) { while(j > 0 && p[i] != p[j+1]) j = ne[j]; if(p[i] == p[j +1]) j++; ne[i] = j; } //kmp匹配 for(int i= 1,j = 0 ; i <= m ; i++) { while( j > 0 &&s[i] != p[j + 1] ) j = ne[j]; if(s[i] == p[j + 1]) j++; //匹配到模式串尾了的处理输出 if(j == n) { bw.write(i - n + " "); //继续 j = ne[j]; } } bw.flush(); bw.close(); } } 附上我的视频，用于复习~~。：)[video title="KMP字符串 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/KMP.mkv " container="bbm9bo70lpz" subtitle=" " poster=" "] [/video]AcWing 837. 连通块中点的数量原址解题过程import java.io.*; import java.util.*; public class Main{ //并查集的额外拓展，查询某个集合中元素的个数 private static final int N = 100010; private static final int[] p = new int[N]; //创建一个记录集合中元素个数的数组，等效于连通块中点的数量 private static final int[] size = new int[N]; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); int m = Integer.parseInt(arrStr[1]); for(int i = 1;i <= n ; i++) { p[i] = i; //初始化每个集合的元素个数为1 size[i] = 1; } while( m-- > 0 ){ arrStr = br.readLine().split(" "); String str = arrStr[0]; if("C".equals(str)){ int a = Integer.parseInt(arrStr[1]); int b = Integer.parseInt(arrStr[2]); merge(a,b); } if("Q1".equals(str)){ int a = Integer.parseInt(arrStr[1]); int b = Integer.parseInt(arrStr[2]); String ans = find(a) == find(b) ? "Yes" : "No"; bw.write(ans + "\n"); } if("Q2".equals(str)){ int a = Integer.parseInt(arrStr[1]); bw.write(size[find(a)] + "\n"); } } bw.flush(); br.close(); bw.close(); } private static void merge(int a,int b ){ int aP = find(a); int bP = find(b); if(aP == bP) return ; //将a中(集合的个数)连接块中点的数量赋值给b,合并,size记录每个集合的祖先节点 size[find(b)] += size[find(a)]; p[aP] = bP; } private static int find(int x){ if(p[x] != x) p[x] = find(p[x]); return p[x]; } }我也录视频用于记录，方便复习啦。[video title="并查集 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/%E5%B9%B6%E6%9F%A5%E9%9B%86.mkv " container="bxd9bcw90pj" subtitle=" " poster=" "] [/video]AcWing 840. 模拟散列表原址解题过程import java.io.*; import java.util.*; public class Main{ private static final int N = 100003; private static final Integer[] h = new Integer[N]; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); Arrays.fill(h,null); while(n-- > 0){ arrStr = br.readLine().split(" "); String str = arrStr[0]; int x = Integer.parseInt(arrStr[1]); if("I".equals(str)) h[find(x)] = x; if("Q".equals(str)){ String ans = h[find(x)] != null ? "Yes" : "No"; bw.write(ans + "\n"); } } bw.flush(); br.close(); bw.close(); } private static int find(int x){ int k = (x % N + N ) % N; while(h[k] != null && h[k] != x){ k++; if(k == N) k = 0; } return k ; } }附上我的视频用于复习捏····[video title="两种哈希表的实现介绍 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/%E5%93%88%E5%B8%8C%E8%A1%A8.mkv " container="by96joo7ml" subtitle=" " poster=" "] [/video]AcWing 843. n-皇后问题原址解题过程按行枚举import java.io.*; import java.util.*; public class Main{ private static final int N = 20; private static final char[][] path = new char[N][N]; private static final boolean[] col = new boolean[N]; private static final boolean[] dg = new boolean[N]; private static final boolean[] udg = new boolean[N]; private static int n; public static void main(String[] args) throws IOException{ BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out)); n = Integer.parseInt(br.readLine()); for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ path[i][j] = '.'; } } dfs(0,br,bw); bw.flush(); br.close(); bw.close(); } private static void dfs(int u,BufferedReader br ,BufferedWriter bw)throws IOException{ if(u == n){ for(int i = 0 ; i <n ;i ++){ for(int j =0 ; j<n ; j ++){ bw.write(path[i][j]); } bw.write("\n"); } bw.write("\n"); return; } for(int i = 0 ; i < n ; i ++){ if(!col[i] && !dg[u + i] && !udg[u - i + n]){ path[u][i] = 'Q'; col[i] = dg[u + i] = udg[u - i + n] = true; dfs(u + 1,br,bw); col[i] = dg[u + i] = udg[u - i + n] = false; path[u][i] = '.'; } } } }附上我的视频用于复习捏····[video title="n皇后问题 " url="https://img.kaijavademo.top/typecho/uploads/2023/10/videos/n%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98.mkv " container="b45ozgltrzh" subtitle=" " poster=" "] [/video]我书写这篇文章的初衷就是总结学习的进度，遗忘之际可以拿出来翻看，如有不对的地方还望指正，多多海涵。