头像

Ycr




离线:1个月前


最近来访(3)
用户头像
isYu
用户头像
zhn1219
用户头像
davidditao

活动打卡代码 AcWing 154. 滑动窗口

Ycr
1个月前

import java.io.*;

class Main{
    static int N = 1000010;
    static int n , k ;
    static int h,t;
    static int[]q = new int[N];
    static int[]a = new int[N];

    public static void main(String[]args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        String[]st = bf.readLine().split(" ");
        n = Integer.parseInt(st[0]);
        k = Integer.parseInt(st[1]);
        String[]str = bf.readLine().split(" ");
        for(int i = 0 ; i < n ; i++) a[i] = Integer.parseInt(str[i]);

        h = 0 ; t = -1;
        for(int i = 0 ; i < n ; i++){
            if(h <= t && q[h] < i - k + 1) h++;//判断队头是否还能留在窗口内
            while(h <= t && a[q[t]] >= a[i]) t--;//求最小值 所以队尾大的出队
            q[++t] = i;//当前下标入队
            if(i >= k - 1) wt.print(a[q[h]] + " ");
        }

        wt.println();

        h = 0 ; t = -1;
        for(int i = 0 ; i < n ; i++){
            if(h <= t && q[h] < i - k + 1) h++;//判断队头是否还能留在窗口内
            while(h <= t && a[q[t]] <= a[i]) t--;//求最大值 所以队尾小的出队
            q[++t] = i;//当前下标入队
            if(i >= k - 1) wt.print(a[q[h]] + " ");
        }
        wt.flush();
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 830. 单调栈

Ycr
1个月前
import java.io.*;

class Main{
    public static void main(String[]args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        String[] s = in.readLine().split(" ");
        int[] stk = new int[100010];
        int tt = 0;

        for(int i = 0 ; i < n ; i++){
            int x = Integer.parseInt(s[i]);
            //如果栈是空的或栈顶元素大于等于x,那么就说明栈顶这个数明显没有x好,
            //因为比较的是左边 最近最小 的数,所以就把stk[tt]弹出了;
            while(tt!=0 && stk[tt] >= x){
                tt--;
            }

            //如果弹出操作完了之后,栈不是空的,就输出栈顶元素,
            if(tt != 0) System.out.print(stk[tt]+" ");
            //否则就是栈是空的,输出-1
            else System.out.print("-1" + " ");
            //最后将x插入栈顶;
            stk[++tt] = x;
        }
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 829. 模拟队列

Ycr
1个月前
import java.io.*;

class Main{
    static int N = 100010;
    static int[] queue ;
    static int tt;
    static int hh;

    public static void init(){
        queue = new int[N];
        tt = -1;
        hh = 0;
    }

    public static void main(String[]args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(in.readLine());
        init();
        while(m-- > 0){
            String[]s = in.readLine().split(" ");
            if(s[0].equals("push")){
                int x = Integer.parseInt(s[1]);
                queue[++tt] = x;
            }else if(s[0].equals("pop")) hh ++;
            else if(s[0].equals("empty"))System.out.println(hh <= tt ? "NO" : "YES");
            else {
                System.out.println(queue[hh]);
            }
        }
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 828. 模拟栈

Ycr
1个月前
import java.io.*;

class Main{

    static int N = 100010;
    static int stk[];
    static int top;

    public static void init(){
        stk = new int[N];
        top = -1;
    }

    public static void push(int x){
        stk[++top] = x; 
    }

    public static int pop(){
        return stk[top--];
    }

    public static boolean empty(){
        return top == -1 ? true : false;
    }

    public static int query(){
        return stk[top];
    }

    public static void main(String[]args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(in.readLine());
        init();
        while(m-- > 0){
            String[] s = in.readLine().split(" ");
            String op = s[0];

            if(op.equals("push")){
                int x = Integer.parseInt(s[1]);
                push(x);
            }else if(op.equals("pop")){
                pop();
            }else if(op.equals("query")){
                System.out.println(query());
            }else {
                String x = empty() ? "YES" : "NO";
                System.out.println(x);
            }
        }

    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 827. 双链表

Ycr
1个月前
import java.io.*;

class Main{
    static int N = 100010;
    static int[] l = new int[N];
    static int[] r = new int[N];
    static int[] e = new int[N];
    static int idx;

    static void init(){
        //初始区间 0 -> 1  作为边界
        //因为无法再使用0号位和1号位来存储数据 所以初始化idx = 2
        r[0] = 1;
        l[1] = 0;
        idx = 2;
    }

    static void add(int k , int x){//在k号位置之后插入x
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        l[r[k]] = idx;
        r[k] = idx;
        idx++;
    }

    static void delete(int k){
        l[r[k]] = l[k];
        r[l[k]] = r[k];
    }

    public static void main(String[]args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(in.readLine());

        init();
        while(m-- > 0){
            String[]arr = in.readLine().split(" ");
            String op = arr[0];
            if(op.equals("L")){//在链表最左端插入x
                int x = Integer.parseInt(arr[1]);
                add(0,x);//在0号位置之后插入x

            }else if(op.equals("R")){//在链表最右端插入x
                int x = Integer.parseInt(arr[1]);
                add(l[1],x);
            }

            else if(op.equals("D")){//删除第k个插入的值(下标为k+1)
                int k = Integer.parseInt(arr[1]);
                delete(k+1);
            }

            else if(op.equals("IL")){//在第k个插入的数左边插入x 
                //等价于在 l[k+1]后插入 x
                int k = Integer.parseInt(arr[1]);
                int x = Integer.parseInt(arr[2]);
                add(l[k+1],x);
            }

            else{//在第k个插入的数右边插入x
                int k = Integer.parseInt(arr[1]);
                int x = Integer.parseInt(arr[2]);
                add(k+1,x);
            }
        }

        for(int i = r[0] ; i != 1; i = r[i]) System.out.print(e[i] +" ");
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 826. 单链表

Ycr
1个月前
import java.io.*;
import java.util.Scanner;

public class Main {
    private static int N = 100010;  // 数据规模为 10w

    private static int head;                // 表示头结点的下标
    private static int[] e = new int[N];    // 表示结点 i的值
    private static int[] ne = new int[N];   // 表示结点 i的 next指针是多少
    private static int idx;                 // 表示存储当前结点已经使用结点的下一个结点

    // 初始化数据
    private static void init() {
        head = -1;  // 没有头结点
        idx = 0;    // 没有存入数据
    }

    // 将 val插到头结点
    private static void addToHead(int val) {
        e[idx] = val;   // 赋值
        ne[idx] = head; // 插入之前头结点的前面
        head = idx;     // 更新头结点信息
        idx++;          // idx向右移动
    }

    // 将下标是 k的点后面的点删掉
    private static void remove(int k) {
        ne[k] = ne[ne[k]];  // 让下标为 k的结点指向 下个结点的下个结点
    }

    // 将 val插入下标为 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 reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());

        init();     // 初始化操作

        // 进行 m次操作
        while (m-- > 0) {
            String[] s = reader.readLine().split(" ");

            if (s[0].equals("H")) {  // 插入头结点操作, 不能使用 ==, 要使用 equals()

                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);    // 第 k个结点的下标为 k-1, 所以插入到下标为 k-1结点的后面
            } else {    // s[0] == "D", 删除操作
                int k = Integer.parseInt(s[1]);

                if (k == 0) {  // 题意: k = 0, 删除头结点
                    head = ne[head];
                } else
                    remove(k - 1);  // 第 k个结点的下标为 k-1, 所以是删除到下标为 k-1后面的后面
            }
        }

        // 打印输出
        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 803. 区间合并

Ycr
1个月前
import java.util.*;

class Main{
    int N = 100010;
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Pair> list = new ArrayList<>();

        for(int i = 0 ; i < n ; i++){
            list.add(new Pair(sc.nextInt(),sc.nextInt() ) );
        }

        Collections.sort(list);

        List<Pair> res = new ArrayList<>();

        meger(list,res);

        System.out.print(res.size());
    }

    public static void meger(List<Pair> list, List<Pair> res){
        int st = Integer.MIN_VALUE,ed = Integer.MIN_VALUE;

        for(Pair p : list){
            if(p.first > ed){
                if(ed != Integer.MIN_VALUE){//不是开始区间
                    res.add(new Pair(st,ed));
                }
                st = p.first;
                ed = p.second;
            }else{
                ed = Math.max(p.second,ed);
            }
        }

        if(ed != Integer.MIN_VALUE) res.add(new Pair(st,ed));
    }
}

class Pair implements Comparable<Pair>{
    public Integer first,second;
    public Pair(int first , int second){
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(Pair a){
        return this.first.compareTo(a.first);
    }
}


//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 802. 区间和

Ycr
1个月前

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //n次操作
        int m = sc.nextInt(); //m次询问
        int N = 300010; //因为需要将所有x,l,r存在数组中,这样就是n + 2m <= 300000
        int[] a = new int[N]; //从1开始,需要通过x找到离散量,然后+1,
        int[] s = new int[N]; //前缀和来做,所以需要从1开始记录a

        List<Integer> alls = new ArrayList<>(); //将所有的使用到的数存在alls中,比如x,l,r
        //但其中会有先后顺序的差别,以及重复,所以需要排序和去重
        List<Pairs> add = new ArrayList<>(); //用来存n次操作
        List<Pairs> query = new ArrayList<>(); //用来存m次询问

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            add.add(new Pairs(x, c));
            alls.add(x); //存入alls中,为后续操作做准备
        }

        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            query.add(new Pairs(l, r));
            alls.add(l);
            alls.add(r);
        }
        //到此为止,alls中存好了所有会被用到的数轴上的点,可以进行离散化操作
        // 1. 排序 2. 去重
        Collections.sort(alls);
        int unique = unique(alls);
        alls = alls.subList(0, unique); //将去重后的List保存下来,或者此处也可以将unique作为最后一个数,用r作为二分

        for (Pairs item:add) {
            int index = find(item.first, alls);
            a[index] += item.second;
        }

        //求前缀和
        for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

        for (Pairs item:query) {
            int l = find(item.first, alls);
            int r = find(item.second, alls);
            System.out.println(s[r] - s[l - 1]);
        }
    }

    //去重
    static int unique(List<Integer> list) {
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || list.get(i).equals( list.get(i - 1) ) == false ) {
                list.set(j, list.get(i));
                j++;
            }  
        }
        return j;
    } 

    static int find(int x, List<Integer> list) {
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1; //因为要考虑到前缀和
    }
}

class Pairs {
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Ycr
1个月前
import java.util.Scanner;

class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i = 0 ; i < n ; i++){
            int x = sc.nextInt();
            int j = 0;
            while(x != 0){
                x -= (x & (-x));
                j++;
            }
            System.out.print(j + " ");
        }
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2816. 判断子序列

Ycr
1个月前
import java.util.Scanner;

class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int a[] = new int[n];
        int b[] = new int[m];

        for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt();
        for(int i = 0 ; i < m ; i++) b[i] = sc.nextInt();

        boolean ys = false;

        for(int i = 0 , j = 0 ; i < n && j < m ; j++ ){
            if(a[i] == b[j]) i++;
            if(i == n) {System.out.print("Yes"); ys = true; break;}
        }
        if(!ys)
        System.out.print("No");
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~