基础算法-数据结构
数据结构
单链表（静态链表）
idx表示当前以及用到了那个点，head表示头节点的下标。
初始化时，将head指向-1，idx指向0.
插入x到头节点：
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
插入x到下标k的后面：
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
删掉下标是k的点
{
ne[k] = ne[ne[k]]
}
例题：
实现：
import java.io.*;
import java.util.stream.*;
import java.util.Arrays;
public class Main{
private static int idx = 0;
private static int head = -1;
private static int[] e = new int[100010];
private static int[] ne = new int[100010];
private static void insertToHead(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
private static void remove(int k){
if(k == 0){
head = ne[head];
}else{
k--;
ne[k] = ne[ne[k]];
}
}
private static void insert(int x, int k){
k--;
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
public static void main(String[] args) throws Exception{
var bf = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(bf.readLine());
while(m > 0){
m--;
String[] vals = Stream.of(bf.readLine().split(" ")).map(String::new).toArray(String[]::new);
if(vals[0].equals("H")){
int v = Integer.parseInt(vals[1]);
insertToHead(v);
}else if(vals[0].equals("D")){
int v = Integer.parseInt(vals[1]);
remove(v);
}else if(vals[0].equals("I")){
int v = Integer.parseInt(vals[1]);
int f = Integer.parseInt(vals[2]);
insert(f, v);
}
}
int st = head;
while(st != -1){
System.out.print(e[st] + " ");
st = ne[st];
}
}
}
双链表（静态双链表）
思路：
l[n]保存每个节点的左指向
r[n]保存每个节点的右指向。
以0作为头指针，1作为尾指针。
初始化
init{
r[0] = 1;
l[1] = 0;
idx = 2;
}
例题：
实现：
import java.util.stream.*;
import java.io.*;
import java.util.*;
public class Main{
private static final int N = 100010;
private static int[] l = new int[N];
private static int[] r = new int[N];
private static int[] e = new int[N];
// 0 为头节点, 1为尾节点
private static int idx = 2;
static{
l[1] = 0;
r[0] = 1;
}
private static void insert(int k, int v){
e[idx] = v;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
private static void remove(int k){
k++;
l[r[k]] = l[k];
r[l[k]] = r[k];
}
public static void main(String[] args) throws Exception{
var bf = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(bf.readLine());
while(m > 0){
m--;
String[] strargs = Stream.of(bf.readLine().split(" ")).map(String::new).toArray(String[]::new);
//System.out.println(Arrays.toString(strargs));
if("L".equals(strargs[0])){
int v = Integer.parseInt(strargs[1]);
insert(0,v);
}else if("R".equals(strargs[0])){
int v = Integer.parseInt(strargs[1]);
insert(l[1],v);
}else if("D".equals(strargs[0])){
int v = Integer.parseInt(strargs[1]);
remove(v);
}else if("IL".equals(strargs[0])){
int v1 = Integer.parseInt(strargs[1]);
int v2 = Integer.parseInt(strargs[2]);
insert(l[v1 + 1],v2);
}else if("IR".equals(strargs[0])){
int v1 = Integer.parseInt(strargs[1]);
int v2 = Integer.parseInt(strargs[2]);
insert(v1 + 1,v2);
}
// for(int i = 0; i < 10; i++){
// System.out.println(e[i] + " " + l[i] + " " + r[i]);
// }
// System.out.println("==================");
}
int st = r[0];
while(st != 1){
System.out.print(e[st] + " ");
st = r[st];
}
}
}
模拟栈、队列
栈：先进后出
{
int stk[N];
int top = 0;
//插入：
stk[++top] = x;
//弹出
top--;
}
队列：先入先出
例题
实现：
import java.io.*;
import java.util.stream.*;
public class Main{
private static int N = 100010;
private static int[] stack = new int[N];
private static int top = -1;
private static void push(int x){
stack[++top] = x;
}
private static void pop(){
top--;
}
private static boolean isEmpty(){
return top == -1;
}
private static int query(){
return stack[top];
}
public static void main(String[] args) throws IOException{
var bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bf.readLine());
while(n > 0){
n--;
String[] vals = bf.readLine().split(" ");
if("push".equals(vals[0])){
int v = Integer.parseInt(vals[1]);
push(v);
}else if("pop".equals(vals[0])){
pop();
}else if("query".equals(vals[0])){
int v = query();
System.out.println(v);
}else if("empty".equals(vals[0])){
System.out.println(isEmpty()?"YES":"NO");
}
}
}
}
KMP
非常头疼的一个算法。。。
例题： KMP
代码：
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
var bf = new BufferedReader(new InputStreamReader(System.in));
var writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(bf.readLine());
String p = bf.readLine();
int m = Integer.parseInt(bf.readLine());
String s = bf.readLine();
int[] next = buildNext(p);
int j = -1;
for(int i = 0; i < s.length(); i++){
while(j != -1 && p.charAt(j + 1) != s.charAt(i)){
j = next[j];
}
if(p.charAt(j + 1) == s.charAt(i)){
j++;
}
if(j == n -1){
writer.write(i - j + " ");
j = next[j];
}
}
writer.close();
bf.close();
}
private static int[] buildNext(String p){
int[] next = new int[p.length()];
next[0] = -1;
int j = -1;
for(int i = 1; i < p.length(); i++){
while(j != -1 && p.charAt(j + 1) != p.charAt(i)){
j = next[j];
}
if(p.charAt(j + 1) == p.charAt(i)){
j++;
}
next[i] = j;
}
return next;
}
}
投递华为等公司10个岗位 >