模拟散列表
单链表
import java.io.*;
import java.util.Scanner;
public class dlb {
private static int N=100010;
private static int head;
private static int[] e=new int[N];
private static int[] ne=new int[N];
private static int idx;
private static void init(){
head=-1;
idx=0;
}
private static void addtohead(int val){
e[idx]=val;
ne[idx]=head;
head=idx;
idx++;
}
private static void remove(int k){
ne[k]=ne[ne[k]];
}
private static void add(int k,int val){
e[idx]=val;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
public static void main(String[] args)throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int m=Integer.parseInt(br.readLine());
init();
while(m-->0){
String[] s=br.readLine().split(" ");
if(s[0].equals("H")){
int val=Integer.parseInt(s[1]);
addtohead(val);
} else if (s[0].equals("I")) {
int k=Integer.parseInt(s[1]);
int val=Integer.parseInt(s[2]);
add(k-1,val);
}else{
int k=Integer.parseInt(s[1]);
if(k==0){
head=ne[head];
}else remove(k-1);
}
}
for(int i=head;i!=-1;i=ne[i]){
System.out.print(e[i]+" ");
}
}
}
拉链法
import java.io.*;
import java.util.*;
public class a1 {
static int n;
static int N=100003;
static int[] h=new int[N];
static int[] e=new int[N];
static int[] ne=new int[N];
static int idx;
static void insert(int x){
int k=(x%N+N)%N;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
static boolean find(int x){
int k=(x%N+N)%N;
for(int i=h[k];i!=-1;i=ne[i]){
if(e[i]==x)return true;
}
return false;
}
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
int n= sc.nextInt();
Arrays.fill(h,-1);
while(n-->0){
String op= sc.next();
int x=sc.nextInt();
if(op.equals("I"))insert(x);
else {
if(find(x)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}
开放寻址法
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.io.*;
import java.math.*;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.io.*;
import java.math.*;
public class a2 {
static int N=200000+3;
static int nu=0x3f3f3f3f;
static int h[]=new int[N];
static int n;
static int find(int x){
int t=(x%N+N)%N;
while(h[t]!=nu&&h[t]!=x){
t++;
if(t==N)t=0;
}
return t;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
Arrays.fill(h,nu);
int n=sc.nextInt();
while (n-->0){
String op= sc.next();
int x= sc.nextInt();
if(op.equals("I"))h[find(x)]=x;
else {
if(h[find(x)]==nu) System.out.println("No");
else System.out.println("Yes");
}
}
}
}
广度优先搜索
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class BFS {
static int N = 110, row, col;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static char[][] a = new char[N][N];
static int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static void main(String[] args) throws Exception {
int m = Integer.valueOf(br.readLine());
while (m-- > 0) {
int n = Integer.valueOf(br.readLine());
row = col = n;
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < n; j++) {
a[i][j] = s.charAt(j);
}
}
String[] ss = br.readLine().split(" ");
int x1 = Integer.valueOf(ss[0]);
int y1 = Integer.valueOf(ss[1]);
int x2 = Integer.valueOf(ss[2]);
int y2 = Integer.valueOf(ss[3]);
if (bfs(x1, y1, x2, y2)) System.out.println("YES");
else System.out.println("NO");
}
}
public static boolean bfs(int x1, int y1, int x2, int y2) {
Queue<int[]> q = new LinkedList<>();
if (a[x1][y1] == '#' || a[x2][y2] == '#') return false;
if (x1 == x2 && y1 == y2) return true;
q.offer(new int[]{x1, y1});
boolean[][] st = new boolean[row][col];
st[x1][y1] = true;
while (!q.isEmpty()) {
int[] poll = q.poll();
for (int i = 0; i < 4; i++) {
int nx = dir[i][0] + poll[0];
int ny = dir[i][1] + poll[1];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (st[nx][ny] || a[nx][ny] == '#') continue;
st[nx][ny] = true;
if (nx == x2 && ny == y2) return true;
q.offer(new int[]{nx, ny});
}
}
return false;
}
}
深度优先搜索
import java.io.*;
import java.util.*;
class DFS{
static int N=110,row,col;
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static char[][] a=new char[N][N];
static int[][] dir=new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
public static void main(String[] args)throws Exception {
int m=Integer.valueOf(br.readLine());
while(m-->0){
int n=Integer.valueOf(br.readLine());
row=col=n;
for(int i=0;i<n;i++){
String s=br.readLine();
for(int j=0;j<n;j++){
a[i][j]=s.charAt(j);
}
}
String[] ss=br.readLine().split(" ");
int x1=Integer.valueOf(ss[0]);
int y1=Integer.valueOf(ss[1]);
int x2=Integer.valueOf(ss[2]);
int y2=Integer.valueOf(ss[3]);
boolean[][] st=new boolean[n][n];
if(a[x1][y1]=='#'||a[x2][y2]=='#') System.out.println("NO");
else if (x1==x2&&y1==y2) {
System.out.println("YES");
}else if(dfs(x1,y1,x2,y2,st)){
System.out.println("YES");
}else System.out.println("NO");
}
}
public static boolean dfs(int x1,int y1,int x2,int y2,boolean[][] st){
for(int i=0;i<4;i++){
int nx=x1+dir[i][0];
int ny=y1+dir[i][1];
if(nx<0||nx>=row||ny<0||ny>=col)continue;
if(st[nx][ny]||a[nx][ny]=='#')continue;
st[nx][ny]=true;
if(nx==x2&&ny==y2)return true;
if(dfs(nx,ny,x2,y2,st))return true;
}
return false;
}
}
并查集
import java.util.Arrays;
import java.util.Scanner;
public class bcj {
static int inf=0x3f3f3f3f;
static int maxn=10051005;
static int m,n,k,ans;
static int[] p=new int[maxn];
static Scanner sc=new Scanner(System.in);
static boolean[] vis=new boolean[maxn];
public static void init(){
Arrays.fill(vis,false);
for (int i = 1; i <= n * m; i++) {
p[i]=i;
}
}
public static int find(int x){
if(x!=p[x]){
return p[x]=find(p[x]);
}return x;
}
public static void join(int x, int y){
int xx=find(x);
int yy=find(y);
if(xx!=yy)p[yy]=xx;
}
public static void main(String[] args) {
m= sc.nextInt();
n= sc.nextInt();
k= sc.nextInt();
init();
while (k-->0){
int x,y;
x= sc.nextInt();
y= sc.nextInt();
join(x,y);
}
for(int i=1;i<=m*n;i++){
vis[find(i)]=true;
}
for (int i = 1; i <= n * m; i++) {
if(vis[i])ans++;
}
System.out.println(ans);
}
}
扫雷
小明最近迷上了一款名为《扫雷》的游戏。
其中有一个关卡的任务如下：
在一个二维平面上放置着 nn 个炸雷，第 ii 个炸雷 (xi,yi,ri)(xi,yi,ri) 表示在坐标 (xi,yi)(xi,yi) 处存在一个炸雷，它的爆炸范围是以半径为 riri 的一个圆。
为了顺利通过这片土地，需要玩家进行排雷。
玩家可以发射 mm 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 jj 个排雷火箭 (xj,yj,rj)(xj,yj,rj) 表示这个排雷火箭将会在 (xj,yj)(xj,yj) 处爆炸，它的爆炸范围是以半径为 rjrj 的一个圆，在其爆炸范围内的炸雷会被引爆。
同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。
现在小明想知道他这次共引爆了几颗炸雷？
你可以把炸雷和排雷火箭都视为平面上的一个点。
一个点处可以存在多个炸雷和排雷火箭。
当炸雷位于爆炸范围的边界上时也会被引爆。
输入格式
输入的第一行包含两个整数 n、mn、m。
接下来的 nn 行，每行三个整数 xi,yi,rixi,yi,ri，表示一个炸雷的信息。
再接下来的 mm 行，每行三个整数 xj,yj,rjxj,yj,rj，表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
数据范围
对于 40%40% 的评测用例：0≤x,y≤109,0≤n,m≤103,1≤r≤100≤x,y≤109,0≤n,m≤103,1≤r≤10，
对于 100%100% 的评测用例：0≤x,y≤109,0≤n,m≤5×104,1≤r≤100≤x,y≤109,0≤n,m≤5×104,1≤r≤10。
输入样例：
2 1
2 2 4
4 4 2
0 0 5
输出样例：
2
样例解释
示例图如下，排雷火箭 11 覆盖了炸雷 11，所以炸雷 11 被排除；炸雷 11 又覆盖了炸雷 22，所以炸雷 22 也被排除。
难度：中等 |
时/空限制：1s / 256MB |
总通过数：984 |
总尝试数：4743 |
来源：第十三届蓝桥杯省赛C++B组 |
算法标签 |
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
class Main {
static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static final int N = 50010, M = 99997;
static Circle[] cirs = new Circle[N];
static long[] h = new long[M];
static int[] id = new int[M];
static boolean[] st = new boolean[M];
static int n, m;
static class Circle {
public int x;
public int y;
public int r;
public Circle(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
}
public static void dfs(int x, int y, int r) {
st[find(x, y)] = true;
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if (sqr(i - x) + sqr(j - y) <= sqr(r)) {
int t = find(i, j);
if (id[t] != 0 && !st[t]) {
dfs(i, j, cirs[id[t]].r);
}
}
}
}
}
public static long getkey(int x, int y) {
return (long) x * 10000001 + y;
}
public static int find(int x, int y) {
long key = getkey(x, y);
int t = (int) ((key % M + M) % M);
while (h[t] != -1 && h[t] != key) {
if (++t == M) t = 0;
}
return t;
}
public static long sqr(int n) {
return n * n;
}
public static void main(String[] args) throws Exception {
String[] ss = br.readLine().split(" ");
n = Integer.parseInt(ss[0]);
m = Integer.parseInt(ss[1]);
Arrays.fill(h, -1);
for (int i = 1; i <= n; i++) {
ss = br.readLine().split(" ");
int x = Integer.parseInt(ss[0]);
int y = Integer.parseInt(ss[1]);
int r = Integer.parseInt(ss[2]);
cirs[i] = new Circle(x, y, r);
int t = find(x, y);
if (h[t] == -1) h[t] = getkey(x, y);
if (id[t] == 0 || cirs[id[t]].r < r) {
id[t] = i;
}
}
while (m-- != 0) {
ss = br.readLine().split(" ");
int x = Integer.parseInt(ss[0]);
int y = Integer.parseInt(ss[1]);
int r = Integer.parseInt(ss[2]);
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if (sqr(i - x) + sqr(j - y) <= sqr(r)) {
int t = find(i, j);
if (id[t] != 0 && !st[t]) {
dfs(i, j, cirs[id[t]].r);
}
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (st[find(cirs[i].x, cirs[i].y)]) ans++;
}
System.out.println(ans);
}
}
