头像

2323301456




离线:2天前


最近来访(4)
用户头像
neiLi
用户头像
木棉觉
用户头像
yxc的小迷妹
用户头像
yxc

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100000;
    static int head;
    static int e[] = new int[N];//存储结点
    static int ne[] = new int[N];//存储next指针
    static int idx;//当前结点

    //初始化
    public static void init() {
        head = -1;
        idx = 0;
    }

    public static void main(String[] args) throws IOException {
        init();
        //输入操作次数
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        while (num-- > 0) {
            String[] s = br.readLine().split(" ");
            if (s[0].equals("H")) {
                int val = Integer.parseInt(s[1]);
                H(val);
            }
            if (s[0].equals("I")) {
                int k = Integer.parseInt(s[1]);
                int val = Integer.parseInt(s[2]);
                I(k - 1, val);
            }
            if (s[0].equals("D")) {
                int k = Integer.parseInt(s[1]);
                if (k == 0) head = ne[head];
                else D(k - 1);
            }
        }
        for (int i = head; i != -1; i=ne[i]) System.out.print(e[i]+" ");
    }

    //头部插入操作
    public static void H(int val) {
        //将当前位置赋值为val
        e[idx] = val;
        //当前位置指向head指向的位置,也就是第一个结点
        ne[idx] = head;
        //head指向当前的位置
        head = idx;
        //将idx移到下一位,因为新添加了一个位置
        idx++;
    }

    //在k后面加入val
    public static void I(int k, int val) {
        //将当前位置赋值为val
        e[idx] = val;
        //当前位置指向k的下一个位置
        ne[idx] = ne[k];
        //k的下一个位置指向当前位置
        ne[k] = idx;
        //将idx移到下一位,因为新添加了一个位置
        idx++;
    }

    //删除k之后的元素操作
    public static void D(int k) {
        //将k的下一个指向k的下一个的下一个
        ne[k] = ne[ne[k]];
    }
}



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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<pair> list = new ArrayList<>();
        Scanner sc = new Scanner(System.in);
        //1.输入区间个数
        int n = sc.nextInt();
        //2.保存所有区间
        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            list.add(new pair(l, r));
        }
        //3.对列表中的区间进行合并
        System.out.println(merge(list));
    }

    //合并方法
    public static int merge(List<pair> list) {
        //将所有新的区间放入新的列表中
        List<pair> res = new ArrayList();
        //以左端点进行排序,如果左端点相同以右端点排序
        list.sort(new Comparator<pair>() {
            @Override
            public int compare(pair o1, pair o2) {
                if (o1.getL() == o2.getL()) {
                    return o1.getR() - o2.getR();
                }
                return o1.getL() - o2.getL();
            }
        });
        //定义初始区间
        int l = Integer.MIN_VALUE;
        int r = Integer.MIN_VALUE;
        //从最左端开始,如果这个区间的左端点大于上一个初始区间的右端点说明没有重合,则将这个区间放到res列表中
        for (pair p : list) {
            if (p.getL() > r) {
                //如果左右端点不相同说明不是初始化的值
                if (l != Integer.MIN_VALUE) res.add(new pair(l, r));
                l = p.getL();
                r = p.getR();
            } else r = Math.max(r, p.getR());
        }
        if (l != Integer.MIN_VALUE) {
            res.add(new pair(l, r));
        }
        return res.size();
    }
}

//区间对象
class pair {
    private int l;
    private int r;

    public pair(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public int getL() {
        return l;
    }

    public int getR() {
        return r;
    }

}


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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //1.读取存储的对数和查询个数
        int n = sc.nextInt();//n次操作
        int m = sc.nextInt();//m次查询
        int N = 300010;
        int[] a = new int[N];
        int[] s = new int[N];
        //存储所有待离散化的值
        List<Integer> alls = new ArrayList<>();//alls用来存储坐标
        List<pairs> add = new ArrayList<>();//add用来存储输入的添加的值
        List<pairs> query = new ArrayList<>();//用来存储查询的值
        //2.存储所有坐标及其对应的值
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            add.add(new pairs(x, c));
            alls.add(x);
        }
        //3.存储所有询问
        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);
        }
        //4.排序
        Collections.sort(alls);
        int last=last(alls);
        alls=alls.subList(0,last);//保存去重后的list
        //5.根据二分的结果将add的坐标及其对应的数添加到原数组a中
        //保证a数组和alls数组中的对应关系
        for(pairs p:add){
            int index=find(p.first,alls);
            a[index]+=p.second;
        }
        //6.根据题目要求求前缀和,输出两点间的前缀和
        for (int i = 1; i <= alls.size(); i++) s[i]=s[i-1]+a[i];
        for(pairs p:query){
            int l=find(p.first,alls);
            int r=find(p.second,alls);
            System.out.println(s[r]-s[l-1]);
        }
    }
    //构造去重函数,返回最后一个数字的位置
    public static int last(List<Integer> list) {
        int num = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || list.get(i).equals(list.get(i - 1)) == false) {
                list.set(num, list.get(i));
                num++;
            }
        }
        return num;
    }
    //二分找到插入的值的位置,返回位置
    public static int find(int x,List<Integer> list){
        int l=0,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;
    }
}

//构造pair对象,存储一堆有关联的数组
class pairs {
    int first;
    int second;

    public pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}



import java.util.Scanner;

public class Main {
    //给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入数字个数
        int n = sc.nextInt();
        while (n-- > 0) {
            int x = sc.nextInt();
            int res=0;
            while (x>0) {
                x-=lowbit(x);
                res++;
            }
            System.out.print(res+" ");
        }
    }
    //lowbit求最后一位1
    public static int lowbit(int n) {
        return n & -n;
    }

}



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

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        //输入两个数组的个数
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        //输入两个数组
        int []a=new int[m];
        int []b=new int[n];
        for(int i=0;i<m;i++)a[i]=sc.nextInt();
        for(int i=0;i<n;i++)b[i]=sc.nextInt();

        //
        int i=0,j=0;
        while(i<m&&j<n){
            if(a[i]==b[j])i++;
            j++;
        }
        if(i==m) System.out.println("Yes");
        else System.out.println("No");

    }
}





import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入数组长度和待求值
        int m = sc.nextInt();
        int n = sc.nextInt();
        long x = sc.nextInt();
        //输入两个升序排列的数组
        long[] A = new long[m];
        long[] B = new long[n];
        for (int i = 0; i < m; i++) A[i] = sc.nextInt();
        for (int i = 0; i < n; i++) B[i] = sc.nextInt();

        for (int i = 0,j=n-1; i < m; i++) {
            while (A[i] + B[j] > x&&0<=j) j--;
            if(A[i] + B[j] == x) {
                System.out.println(i + " " + j);
                break;
            }
        }

    }
}



import java.util.Scanner;

public class Main {
    static int N=100010;
    public static void main(String[] args) {
        //输入整数个数和整数序列
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //2.模板
        //1 2 2 3 5
        //定义max用于比较哪个更大
        int max=0;
        //定义s数组用于记录每个数的数量,判断是否重复
        int s[]=new int[N];
        //首先对i进行移动,并进行判断
        for (int i = 0, j = 0; i < n; i++) {
            //当某个数字出现给相应位置++
            s[arr[i]]++;
            //如果重复即s[]>1,则对j进行移动
            while(s[arr[i]]>1) {
                //减掉j原位置的个数,防止出现累加现象
                s[arr[j]]--;
                //移动j
                j++;
            }
            //将这次得到的距离和之前得到的距离进行比较,返回更大的一个
            max=Math.max(max,i-j+1);
        }
        System.out.println(max);
    }
}


活动打卡代码 AcWing 798. 差分矩阵

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //1.输入行数列数和查询次数
        int x = sc.nextInt();
        int y = sc.nextInt();
        int q = sc.nextInt();
        //2.多层循环输入多维数组
        int[][] arr = new int[x + 2][y + 2];
        for (int i = 1; i <= x; i++)
            for (int j = 1; j <= y; j++)
                arr[i][j] = sc.nextInt();
        //3.求b数组
        int[][] b = new int[x + 2][y + 2];
        b[0][0] = arr[0][0];
        for (int i = 1; i <= x; i++)
            for (int j = 1; j <= y; j++)
                //求差分就是求前缀和的逆向操作
                b[i][j] = arr[i][j] - arr[i][j - 1] - arr[i - 1][j] + arr[i - 1][j - 1];
        while (q-- > 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int c = sc.nextInt();
            b[x1][y1] += c;
            b[x2 + 1][y1] -= c;
            b[x1][y2 + 1] -= c;
            b[x2 + 1][y2 + 1] += c;
        }
        //输出加了之后的a数组
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + b[i][j];
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }
}


活动打卡代码 AcWing 797. 差分


import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //输入a数组个数和查询次数
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //防止越界
        int[] arr = new int[n + 2];
        //输入a数组
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        //获取a数组对应的b数组
        int[] b = new int[n + 2];
        b[1] = arr[1];
        for (int i = 2; i <= n; i++) {
            b[i] = arr[i] - arr[i - 1];
        }
        //对b数组进行操作
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int c=sc.nextInt();
            b[l]+=c;
            b[r+1]-=c;
        }
        //新的a数组
        for (int i = 1; i <= n; i++) arr[i] = arr[i - 1] + b[i];
        for(int i=1;i<=n;i++) System.out.print(arr[i]+" ");
        System.out.println("");
    }
}



活动打卡代码 AcWing 796. 子矩阵的和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //输入二维数组的维数和查询次数
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int arr[][] = new int[n + 1][m + 1];
        int s[][] = new int[n + 1][m + 1];
        //输入二维数组
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                arr[i][j] = sc.nextInt();
        //计算s的值来替代数组中的值
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];
//                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

        //计算q个值并输出
        while (q-- > 0) {
            int x1, y1, x2, y2;
            x1 = sc.nextInt();
            y1 = sc.nextInt();
            x2 = sc.nextInt();
            y2 = sc.nextInt();
            //公式:s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
            int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(res);
        }
    }
}