双指针
Java 代码模板
例题1238.日志统计
解题思路
排序+双指针
① 先将所有的点赞数量按照时间顺序排好
② 通过双指针i和j维护长度不大于d的区间，并记录该区间的中所有帖子获得的赞数
作者：小成同学
链接：https://www.acwing.com/solution/content/99878/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int N=100010;
static PIIs[] logs=new PIIs[N];//用于存储日志ts,id
static int[] cnt=new int[N];//用于存储每个id号获得的点赞数,后面代码为cnt[t]++
static boolean[] st=new boolean[N];//用于存储每个帖子是否热帖，所以用boolean类型
public static void main(String[] args)throws IOException
{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String[] s1=reader.readLine().split(" ");
int n=Integer.parseInt(s1[0]);
int d=Integer.parseInt(s1[1]);
int k=Integer.parseInt(s1[2]);
for(int i=0;i<n;i++){
String[] s2=reader.readLine().split(" ");
int t=Integer.parseInt(s2[0]);
int id=Integer.parseInt(s2[1]);
logs[i]=new PIIs(t,id);
}
Arrays.sort(logs,0,n);//以时刻第一，编号第二的原则进行排序
for(int i=0,j=0;i<n;i++){ //双指针算法，i在前，j在跟在后
int id=logs[i].id;//把每个获赞的帖子id存入
cnt[id]++;//获得一次赞，此时此刻++
while(logs[i].t-logs[j].t>=d){//i走在前面，j走在后面，如果第i条日志的时间与第j条日志的时间差大于d，则j往前走一步
cnt[logs[j].id]--;//原先的日志j就不包含在时间段内，则该id点赞数减一
j++;//j往前走一步，否则死循环
}
if(cnt[id]>=k) st[id]=true;//当获赞次数大于或等于k,说明是热帖
}
for(int i=0;i<=100000;i++)
{
if(st[i]){//当St[i]=true ,为热帖，打出来
System.out.println(i);
}
}
}
}
class PIIs implements Comparable<PIIs>
{
public int t,id;
public PIIs(int t,int id){
this.t=t;
this.id=id;
}
@Override
public int compareTo(PIIs o)
{
return Integer.compare(t,o.t);//按照初始时间大小
}
}
BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main{
static final int N=210;
static int R,C;//R行、每行C个字符
static char[][] g=new char[N][N];//接收地图
static int[][] dis=new int[N][N];//dis存储起点到每个点的路径长度，同时其还可以当作判重数组
static int dx[]={-1,0,1,0},dy[]={0,1,0,-1};//四个方向
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
private static int bfs(PII start,PII end) //bfs函数，传入迷宫的起点和终点坐标
{
Queue<PII> queue=new LinkedList<>();//建立一个队列
for(int i=0;i<R;i++) Arrays.fill(dis[i],-1); //先把距离都初始化为-1，-1表示不可到达
dis[start.x][start.y]=0;//表示起点已经走过来，且距离起点为0
queue.offer(start); //将起点线放入队列
//queue.add(start);
while(!queue.isEmpty())
{//当队列非空
PII t=queue.poll();//取出队头元素，并删除
for(int i=0;i<4;i++)//循环，让该点往上下左右四个方向走，扩展该点
{
//int dx[]={-1,0,1,0},dy[]={0,1,0,-1};//四个方向
int x=t.x+dx[i],y=t.y+dy[i];//坐标走到相应的地方
if(x<0||x>=R||y<0||y>=C) continue;//出界
if(g[x][y]=='#') continue; //障碍物
if(dis[x][y]!=-1) continue; //之前已经遍历过了
dis[x][y]=dis[t.x][t.y]+1;//如果能走到，则这个点距离起点的距离是上一个点距离起点的距离+1
if(end.x==x&& end.y==y) return dis[x][y]; //如果当前已经走到终点，直接返回当前dis
queue.offer(new PII(x,y)); //然后将新状态加入队尾
//queue.add(new PII(x,y));
}
}
return -1;//否则没有找到
}
public static void main(String[] args)throws IOException
{
int T=Integer.parseInt(br.readLine());
while(T-->0)
{
String s[]=br.readLine().split(" ");
R=Integer.parseInt(s[0]);//R行
C=Integer.parseInt(s[1]);//每行C个字符
for(int i=0;i<R;i++){
g[i]=br.readLine().toCharArray();//每行次读一，并将字符串转换为字符数组
}
PII start =null,end=null;//定义起点、终点
for(int i=0;i<R;i++){
// char[] charArray = br.readLine().toCharArray();
for(int j=0;j<C;j++){
//g[i][j]=charArray[j];
if(g[i][j]=='S') start=new PII(i,j);
else if(g[i][j]=='E') end=new PII(i,j);
}
}
int distance=bfs(start,end);
if(distance==-1)System.out.println("oop!");
else System.out.println(distance);
}
}
}
class PII{//对应C++中的Pairs<int,int>
int x;//每个点的横坐标
int y;//每个点的纵坐标
public PII(int x,int y){
this.x=x;
this.y=y;
}
}
BFS
Flood fill中bfs解法，从起点出发，向四周进行广度优先遍历搜索
时间复杂度 O(nm)
最多是nm个点
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int N=25;
static int m,n;
static char[][] g=new char[N][N];
static boolean[][] st=new boolean[N][N];//记录该点是否遍历过
static int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
static int bfs(int x,int y)
{
Queue<PIIs> q=new LinkedList<PIIs>();
q.add(new PIIs(x,y));
st[x][y]=true;
int cnt=1;
while(!q.isEmpty())
{
PIIs t=q.poll();
for(int i=0;i<4;i++)
{
int a=t.x+dx[i];
int b=t.y+dy[i];
if(a<0||a>=n||b<0||b>=m) continue;
if(g[a][b]!='.')continue;
if(st[a][b]) continue;
cnt++;
st[a][b]=true;
q.add(new PIIs(a,b));
}
}
return cnt;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
m=sc.nextInt();
n=sc.nextInt();
if(m==0&&n==0) break;
int x=0,y=0;
for(int i=0;i<n;i++)
{
Arrays.fill(st[i],false);
g[i]=sc.next().toCharArray();
//char[] charArray=sc.next().toCharArray();
for(int j=0;j<m;j++)
{
//g[i][j]=charArray[j];
if(g[i][j]=='@')
{
x=i;
y=j;
}
}
}
System.out.println(bfs(x,y));
}
}
}
class PIIs
{
public int x,y;
public PIIs(int x,int y)
{
this.x=x;
this.y=y;
}
}
DFS
Flood fill中dfs解法，从起点出发，向四周进行深度优先遍历搜索
时间复杂度 O(nm)
最多是nm个点
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 25;
static int m;
static int n;
static char[][] g = new char[N][N];
static boolean[][] st = new boolean[N][N];//记录该点是否遍历过
static int[] dx = new int[] {-1,0,1,0};
static int[] dy = new int[] {0,1,0,-1};
static int dfs(int x,int y)
{
int cnt = 1;
st[x][y] = true;
for(int i = 0;i < 4;i++)
{
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] != '.') continue;
if(st[a][b]) continue;
cnt += dfs(a,b);
}
return cnt;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext())
{
m = scan.nextInt();
n = scan.nextInt();
if(m == 0 && n == 0) break;
int x = 0;
int y = 0;
for(int i = 0;i < n;i ++)
{
Arrays.fill(st[i], false);
g[i]=scan.next().toCharArray();
//char[] charArray = scan.next().toCharArray();
for(int j = 0;j < m;j ++)
{
// g[i][j] = charArray[j];
if(g[i][j] == '@')
{
x = i;
y = j;
}
}
}
System.out.println(dfs(x,y));
}
}
}
