头像

TSNA

无组织


访客:665

离线:1小时前



TSNA
20小时前

题目描述

初始化n个值每个值都属于自己的集合,然后每次给定两个值,进行和合并和查询两个值是不是同一个区间,是的话输出yes,否则输出n.

输入样例

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例

Yes
No
Yes

算法1

(并查集) $O(n)$
思路:
    1. 暴力的话,合并可以将集合a中元素全部加到b中,当a中元素多的时候很费时间,是否同一个集合的话belong(a)
     == belong(b),判断还算简单
    2. 非暴力 即并查集的做法O(1)
        - 并查集专门就是搞区间的合并和判断是不是属于一个区间
        - 大概可以把集合想象成多颗树,合并的话只需要将某个树的树根放到要合并的树的根的下面 p[x] = y
        - 判断是否是同一个集合,直接一直递归找当前节点的父节点直到找到根,find(x)
        - 如何优化查找?路径压缩
            - 让每次查找的每个节点都指向根节点,所有只要递归几次就可以了

1.png

时间复杂度: $O(n)$

参考文献:y总

Java代码

import java.io.*;

public class Main {
    static int N = 100010;
    static int[] p = new int[N];// 存储每个节点的父节点
    // 核心代码
    // 找到当前节点的根节点 + 路径压缩
    static int find(int x){
        if (p[x] != x){// 如果父节点不等于根节点
            int t = find(p[x]);// 查找当前节点的父节点的父节点 直到找到根节点
            return t;
        }
        return x;// 返回根节点
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);

        // 初始化集合 每个节点的父节点是自己
        // 注意 根节点的父节点也是自己
        for (int i = 1; i <= n; i++) p[i] = i;
        while (m-- > 0){
            s1 = br.readLine().split(" ");
            int x = Integer.parseInt(s1[1]);
            int y = Integer.parseInt(s1[2]);
            if ("M".equals(s1[0])) {// 集合合并
                // 找到x,y的根节点 让x的根节点的父节点 = y的根节点
                p[find(x)] = find(y);
            }else {// 查询是否是同一个集合
                if (find(x) == find(y)){
                    // 根节点相同
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }

        br.close();
    }
}

优雅的代码

import java.io.*;

public class Main{
    static int[] p = new int[100010];

    static int find(int x){
        if (p[x] != x) return find(p[x]);
        return x;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        for (int i = 1; i <= n; i++) p[i] = i;

        while (m-- > 0){
            s = br.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            int y = Integer.parseInt(s[2]);
            if ("M".equals(s[0])) p[find(x)] = find(y);
            else {
                if (find(x) == find(y)) System.out.println("Yes");
                else System.out.println("No");
            }
        }

        br.close();
    }
}



活动打卡代码 AcWing 836. 合并集合

TSNA
20小时前
import java.io.*;

public class Main{
    static int[] p = new int[100010];

    static int find(int x){
        if (p[x] != x) return find(p[x]);
        return x;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        for (int i = 1; i <= n; i++) p[i] = i;


        while (m-- > 0){
            s = br.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            int y = Integer.parseInt(s[2]);
            if ("M".equals(s[0])) p[find(x)] = find(y);
            else {
                if (find(x) == find(y)) System.out.println("Yes");
                else System.out.println("No");
            }
        }

        br.close();
    }
}



TSNA
1天前

题目描述

给定一组数组,然后随意两个异或,找到最大的输出。

输入样例

3
1 2 3

输出样例

3

算法1

(trie数) $O(nlogn)$
思路
    1. 首先暴力的做法就是两层for循环,第一层就是遍历整个数组,第二层就是让他们异或,找到最大
    2. 如果优化?
        - 数组的二进制表示形式最长31位,然后找异或最大的,比如我们要找1000 0000 0000 0000 0000 0000 0000 0000 
        是不是应该先找高位30位(0开始)是1相反的是0,异或是1,肯定是比与1异或等于0是大的,因为高位是1肯定比
        高位是0的大,所以我们可以依次找,类似于一个树,如果没有相反的就用有的值,这样我们就可以用trie解决 

时间复杂度:$O(nlogn)$

参考文献:y总

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int M = 31 * N;// 最大节点数
    static int[][] son = new int[M][2];
    static int idx;
    static int[] a = new int[N];

    static void insert(int x){// 拆入节点
        int p = 0;// 从根节点开始
        for (int i = 30; i >= 0; i--){
            int u = x >> i & 1;// 求二进制中第i的值
            if (son[p][u] == 0) son[p][u] = ++idx;// 插入当前节点
            p = son[p][u];// 获取当前节点
        }
    }

    static int query(int x){
        int p = 0;// 从根节点开始
        int res = 0;
        for (int i = 30; i >= 0; i--){
            int u = x >> i & 1;// x的二进制表示的第i位的值
            if (son[p][u ^ 1] != 0){// 当前位的值的相反位 存在
                p = son[p][u ^ 1];
                res = res * 2 + u ^ 1;
            }else {
                p = son[p][u];
                res = res * 2 + u;
            }
        }
        return res;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        String[] s = scan.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
        }

        int res = 0;// 存储结果  最小是0
        for (int i = 0; i < n; i++){
            insert(a[i]);
            int t = query(a[i]);
            res = Math.max(res, a[i] ^ t);
        }
        System.out.println(res);
        scan.close();
    }
}




活动打卡代码 AcWing 143. 最大异或对

TSNA
1天前
import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int[][] son =  new int[31 *N][2];
    static int[] a = new int[N];
    static int idx;

    static void insert(int x){
        int p = 0;
        for (int i = 30; i >= 0; i--){
            int u = x >> i & 1;
            if (son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
    }

    static int query(int x){
        int p = 0;
        int res = 0;
        for (int i = 30; i >= 0; i--){
            int u = x >> i & 1;
            if (son[p][u ^ 1] == 0){
                p = son[p][u];
                res = res * 2 + u;
            }else {
                p = son[p][u ^ 1];
                res = res * 2 + u ^ 1;
            }
        }
        return res;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        String[] s = scan.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
        }

        int res = 0;// 存储结果  最小是0
        for (int i = 0; i < n; i++){
            insert(a[i]);
            int t = query(a[i]);
            res = Math.max(res, a[i] ^ t);
        }
        System.out.println(res);
        scan.close();
    }
}



TSNA
1天前

trie树

  1. trie树的作用是高效的查询和存储字符串的

题目描述

插入字符串和查询字符串拆入的个数

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

算法1

(trie) $O(n)$
思路
    - 以树的形式拆入,如果是最后一个节点要做一个标记
    - 以树的形式查询

3.png

时间复杂度:$O(n)$

参考文献:y总

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[][] son = new int[N][26];// 存储所有子节点
    static int[] cnt = new int[N]; // 已当前节点结尾的字符串的个数
    static int idx;// 当前节点

    static int insert(char[] str){
        int p = 0;// 0 代表根节点 也代表的是最后一个叶子节点
        for (int i = 0; i < str.length; i++){// 遍历字符串
            int u = str[i] - 'a';
            if (son[p][u] == 0) son[p][u] = ++idx;// 不存在的话,创建一个节点
            p = son[p][u];// 获取当前节点
        }
        return cnt[p]++;
    }

    static int query(char[] str){
        int p = 0;
        for (int i = 0; i < str.length; i++){
            int u = str[i] - 'a';
            if (son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        while (n-->0){
            String[] s = scan.nextLine().split(" ");
            if (s[0].equals("I")){
                insert(s[1].toCharArray());
            }else{
                System.out.println(query(s[1].toCharArray()));
            }
        }
    }
}




活动打卡代码 AcWing 835. Trie字符串统计

TSNA
1天前
import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int[][] son = new int[N][26];
    static int idx;
    static int[] cnt = new int[N];

    static int insert(char[] str){
        int p = 0;
        for (int i = 0; i < str.length; i++){
            int u = str[i] - 'a';
            if (son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        return cnt[p]++;
    }

    static int query(char[] str){
        int p = 0;
        for (int i = 0; i < str.length; i++){
            int u = str[i] - 'a';
            if (son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        while (n-->0){
            String[] s = scan.nextLine().split(" ");
            if (s[0].equals("I")){
                insert(s[1].toCharArray());
            }else {
                System.out.println(query(s[1].toCharArray()));
            }
        }
    }
}



TSNA
1天前

题目描述

给两个字符串p和s,从s中找p,如果找到了就返回起始下标,从0开始,相当于字符串匹配。

输入样例

3
aba
5
ababa

输出样例

0 2

算法1

(kmp) $O(n)$

思路:
- 先暴力,然后优化。
暴力的话,遍历s,然后在遍历q,双重循环遍历,直到找到相等的
- 怎么优化?
每次比较到不相同的时候,是不是不需要从头比较?是不是可以找到一个当前点j的最大后缀和前缀相等即ne[j]的位置,只需要从ne[j]的位置重新比较即可。

时间复杂度:$O(n)$

参考文献:y总

Java 代码

import java.io.*;

public class Main {
    static int N = 100010;
    static int M = 1000010;
    static char[] p = new char[N];
    static char[] s = new char[M];
    static int[] ne = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String s_01 = br.readLine();
        for (int i = 1; i <= n; i++)
            p[i] =  s_01.charAt(i - 1);
        int m = Integer.parseInt(br.readLine());
        String s_02 = br.readLine();
        for (int i = 1; i <= m; i++)
            s[i] =  s_02.charAt(i - 1);

        // 求next数组 i=0 是0
        // i = 1不用算,ne[1] = 0
        for (int i = 2, j = 0; i <= n; i++){
            // 当前字符不匹配的时候 j退回ne
            while (j != 0 && p[i] != p[j + 1]) j = ne[j];
            if (p[i] == p[j + 1]) j++;// 当前字符匹配 j++
            ne[i] = j;// 赋值
        }

        // kmp 匹配过程
        // i从1开始,每次和j+1比较
        for (int i = 1, j = 0; i <= m; i ++){
            // 当前字符不匹配 则退回到ne[j] 接着比
            while (j != 0 && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j++;// 单个字符匹配成功 j++
            if (j == n){// 全部字符匹配成功
                bw.write(i - n + " ");
                j = ne[j];
            }
        }

        bw.flush();
        bw.close();;
        br.close();;
    }
}


时间复杂度是O(n),不太清楚,有大佬看见的话,求解释,谢谢!



活动打卡代码 AcWing 831. KMP字符串

TSNA
1天前
import java.io.*;

public class Main {
    static int N = 100010;
    static int M = 1000010;
    static char[] p = new char[N];
    static char[] s = new char[M];
    static int[] ne = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String s_01 = br.readLine();
        for (int i = 1; i <= n; i++)
            p[i] =  s_01.charAt(i - 1);
        int m = Integer.parseInt(br.readLine());
        String s_02 = br.readLine();
        for (int i = 1; i <= m; i++)
            s[i] =  s_02.charAt(i - 1);

        // 求next数组 i=0 是0
        for (int i = 2, j = 0; i <= n; i++){
            // 当前字符不匹配的时候 j退回ne
            while (j != 0 && p[i] != p[j + 1]) j = ne[j];
            if (p[i] == p[j + 1]) j++;// 当前字符匹配 j++
            ne[i] = j;// 赋值
        }

        // kmp 匹配过程
        for (int i = 1, j = 0; i <= m; i ++){
            // 当前字符不匹配 则退回到ne[j] 接着比
            while (j != 0 && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j++;// 单个字符匹配成功 j++
            if (j == n){// 全部字符匹配成功
                bw.write(i - n + " ");
                j = ne[j];
            }
        }

        bw.flush();
        bw.close();;
        br.close();;
    }
}



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

TSNA
5天前
import java.io.*;

public class Main{
    static int N = 1000010;
    static int hh = 0, tt = -1;
    static int[] a = new int[N];
    static int[] q = new int[N];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s_01 = br.readLine().split(" ");
        int n = Integer.parseInt(s_01[0]);
        int k = Integer.parseInt(s_01[1]);

        String[] s_02 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(s_02[i]);

        for (int i = 0; i < n; i++){
            if (hh <= tt && i - k + 1 > q[hh]) hh++;
            while (hh <= tt && a[q[tt]] >= a[i]) tt--;
            q[++tt] = i;
            if (i >= k - 1) System.out.print(a[q[hh]] + " ");
        }

        System.out.println();


        for (int i = 0; i < n; i++){
            if (hh <= tt && i - k + 1 > q[hh]) hh++;
            while (hh <= tt && a[q[tt]] <= a[i]) tt--;
            q[++tt] = i;
            if (i >= k - 1) System.out.print(a[q[hh]] + " ");
        }
    }
}



TSNA
5天前

题目描述

给一个数组,然后来一个滑动窗口,窗口每次向右滑动1个,求每次滑动窗口中的最大值和最小值。

输入样例

8 3
1 3 -1 -3 5 3 6 7

输出样例

-1 -3 -3 -3 3 3
3 3 5 5 6 7

算法1

(暴力枚举) $O(n)$

思路:
1. 滑动窗口滑出的是队头,插入的是队尾,正好符合队列
2. 暴力:扫描数组,每次遍历滑动窗口的所有值,求出最大最小
3. 优化:发现当求窗口最小值的时候,当窗口元素是 -1 3 -2 的时候,-2 < 3 并且在3的后面,所以有-2在的窗口,3 永远不会出现,所以可以直接把它删除了,每次遍历数组的时候都这样删除,那么队列中存放的肯定是递增的,所以每次只需要取出队头即可。
4. 求最大值正好相反,当窗口元素是 4 -2 5 的时候,5>-2 并且在-2的后面,所以有5在的窗口,-2 永远不会出现,所以可以直接把它删除了,那么队列中存放的肯定是递增的,所以每次只需要取出队头即可。

时间复杂度:$O(n)$

参考文献:y总

Java 代码

import java.io.*;

public class Main {
    static int N = 1000010;
    static int[] a = new int[N];// 存储数组的值
    static int[] q = new int[N];// 队列 存放数组的下标 模拟滑动窗口
    static int hh = 0,tt = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str_01 = br.readLine().split(" ");
        int n = Integer.parseInt(str_01[0]);
        int k = Integer.parseInt(str_01[1]);

        String[] str_02 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(str_02[i]);

        // 处理最大值和最小值
        for (int i = 0; i < n; i++){
            // 保持队列的窗口大小等于滑动窗口的大小k
            // i 终止坐标 i - k + 1 起始坐标
            if (hh <= tt && i - k + 1 > q[hh]) hh++;

            // 删除不必要的元素
            // 如果队尾元素存放的下标对应的值 大于当前插入的值 说明队尾对应的值后面都不会用了
            // 此时队列存放的a下标对应的值 是严格单调递增的
            while (hh <= tt && a[q[tt]] >= a[i]) tt--;

            // 插入当前值的下标
            q[++tt] = i;

            // 当 i >= k - 1 才会输出  只需要输出队头即可
            if (i >= k -1) bw.write(a[q[hh]] + " ");
        }

        bw.write("\n");

        // 处理最大值
        for (int i = 0; i < n; i++){
            if (hh <= tt && i - k + 1 > q[hh]) hh++;
            while (hh <= tt && a[q[tt]] <= a[i]) tt--;
            q[++tt] = i;
            if (i >= k -1) bw.write(a[q[hh]] + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}