这是我用于分享和复习算法笔记的地方，此篇主要是围绕关于数据结构的一些算法题。我在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]];
}
}
附上我的视频，(●'◡'●)
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];
}
}
附上我的视频，用于复习。
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();
}
}
附上我的视频，用于复习~~。：)
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];
}
}我也录视频用于记录，方便复习啦。
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 ;
}
}附上我的视频用于复习捏····
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] = '.';
}
}
}
}附上我的视频用于复习捏····
我书写这篇文章的初衷就是总结学习的进度，遗忘之际可以拿出来翻看，如有不对的地方还望指正，多多海涵。
甘公网安备