4.1-4.5算法刷题笔记(17道题)

4.1-4.5算法刷题笔记

    • 1. 区间和
    • 2. 区间合并
    • 3. 用队列实现栈(queueMain = queueTemp;)
    • 4. 最小栈
  • 1. 单链表模板
    • 5. 单链表
  • 2. 双链表模板
    • 6. 双链表
  • 3. 模拟栈
    • 7. 模拟栈(一个数组即可)
    • 8. 表达式求值
  • 4. 队列 tt = -1,hh = 0;
    • 9. 模拟队列
  • 5. 单调栈
    • 10. 单调栈
  • 6. 单调队列
    • 11. 滑动窗口最大值
  • 7. KMP
    • 12. KMP字符串
  • 8. Trie树
    • 13. Trie字符串统计
    • 14. 最大异或对
  • 9. 并查集 find merge
    • 15. 合并集合
    • 16. 连通块中点的数量(每个集合有多少个元素)
    • 17. 食物链

1. 区间和

原题链接

在这里插入图片描述

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        pair[] add = new pair[n+2];
        pair[] query = new pair[m];
        List<Integer> arrayMap = new ArrayList<>(n+m*2);
        int[] sum = new int[n+m*2];
        for (int i = 0; i < n; i++) {
            add[i] = new pair();
            add[i].l = scanner.nextInt();
            add[i].r = scanner.nextInt();
            arrayMap.add(add[i].l);
        }
        for (int i = 0; i < m; i++) {
            query[i] = new pair();
            query[i].l = scanner.nextInt();
            query[i].r = scanner.nextInt();
            arrayMap.add(query[i].l);
            arrayMap.add(query[i].r);
        }
        arrayMap = new ArrayList<>(new HashSet<>(arrayMap));
        Collections.sort(arrayMap);
        for (int i = 0; i < n; i++) {
            sum[arrayMapIndexOf(add[i].l,arrayMap)] += add[i].r;
        }
        for (int i = 0; i < arrayMap.size(); i++) {
            if(i != 0) {
                sum[i] += sum[i-1];
            }
        }
        for (int i = 0; i < query.length; i++) {
            int l = arrayMapIndexOf(query[i].l,arrayMap);
            int r = arrayMapIndexOf(query[i].r,arrayMap);
            if (l == 0) {
                System.out.print(sum[r] + "\n");
            } else {
                System.out.print(sum[r]-sum[l-1] + "\n");
            }
        }
    }
    
    static class pair {
        int l;
        int r;
    }
    
    private static int arrayMapIndexOf(int k,List<Integer> arrayMap) {
        int l = 0,r = arrayMap.size()-1;
        while (l < r) {
            int mid = (l+r+1) >> 1;
            if (arrayMap.get(mid) <= k) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}

2. 区间合并

原题链接

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        pair[] range = new pair[n];
        for (int i = 0; i < n; i++) {
            range[i] = new pair();
            range[i].l = scanner.nextInt();
            range[i].r = scanner.nextInt();
        }
        Arrays.sort(range,new Comparator<pair>(){
          @Override
          public int compare(pair o1,pair o2) {
              if (o1.l == o2.l) {
                  return o1.r - o2.r;
              } else {
                  return o1.l - o2.l;
              }
          }
        });
        int st = (int)-2e9-1;
        int ed = (int)-2e9-1;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (ed < range[i].l) {
                st = range[i].l;
                ed = range[i].r;
                cnt++;
            } else {
                ed = Math.max(ed,range[i].r);
            }
        }
        System.out.print(cnt);
    }
    
    static class pair {
        int l;
        int r;
    }
    
}

3. 用队列实现栈(queueMain = queueTemp;)

原题链接

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    public Queue<Integer> queueMain;
    public Queue<Integer> queueTemp;

    public MyStack() {
        queueMain = new LinkedList<>();
        queueTemp = new LinkedList<>();
    }

    public void push(int x) {
        queueMain.add(x);
    }

    public int pop() {
        int x = 0;
        while (!queueMain.isEmpty()) {
            x = queueMain.poll();
            if (!queueMain.isEmpty()) {
                queueTemp.add(x);
            }
        }
        queueMain = queueTemp;
        queueTemp = new LinkedList<>();
        return x;
    }

    public int top() {
        int x = 0;
        while (!queueMain.isEmpty()) {
            x = queueMain.poll();
            queueTemp.add(x);
        }
        queueMain = queueTemp;
        queueTemp = new LinkedList<>();
        return x;
    }

    public boolean empty() {
        return queueMain.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

4. 最小栈

原题链接

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int getMin() {
        return B.peek();
    }
}

1. 单链表模板

5. 单链表

acwing链接
力扣

class MyLinkedList {
    int size;
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        index = Math.max(0, index);
        size++;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

import java.util.*;

public class Main {
    static int[] e = new int[100010];
    static int[] ne = new int[100010];
    static int idx,head;
    public static void init() {
        idx = 0;
        head = -1;
    }
    
    public static void add_head(int x) {
        e[idx] = x;
        ne[idx] = head;
        head = idx++;
    } 
    
    public static void add(int k,int x) {
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }
    
    public static void remove(int k) {
        ne[k] = ne[ne[k]];
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        init();
        while(m -- > 0){
            String s = scan.next();
            char op = s.charAt(0);
            if(op == 'H'){
                int x = scan.nextInt();
                add_head(x);
            }else if(op == 'D'){
                int k = scan.nextInt();
                if(k == 0) head = ne[head];
                else remove(k-1);
            }else {
                int k = scan.nextInt();
                int x = scan.nextInt();
                add(k-1,x);
            }
        }
        for(int i = head;i != -1;i = ne[i] ){
            System.out.print(e[i] +  " ");
        }
    }
}

2. 双链表模板

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

6. 双链表

原题链接
在这里插入图片描述

import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int[] e = new int[N];
    static int[] r = new int[N];
    static int[] l = new int[N];
    static int idx;

    //删除第k位插入的数
    public static void remove(int k){
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }
    //这是在第k位数后面插入一个数x
    public static void add_all(int k,int x){
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        l[r[k]] = idx;
        r[k] = idx++;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();

        r[0] = 1;l[1] = 0;idx = 2;

        while(m -- > 0){
            String s = scan.next();
            char op = s.charAt(0);
            if(op == 'L'){
                int x = scan.nextInt();
                add_all(0,x);
            }else if(op == 'R'){
                int x = scan.nextInt();
                add_all(l[1],x);
            }else if(op == 'D'){
                int k = scan.nextInt();
                remove(k + 1);
            }else if(s.equals("IR")){
                int k  = scan.nextInt();
                int x = scan.nextInt();
                add_all(k + 1,x);
            }else {
                int k = scan.nextInt();
                int x = scan.nextInt();
                add_all(l[k+1],x);
            }
        }
       for(int i = r[0];i != 1; i= r[i]){
            System.out.print(e[i]  + " ");
        }
    }
}

3. 模拟栈

7. 模拟栈(一个数组即可)

原题链接
在这里插入图片描述

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int[] stl = new int[100010];
        int tt = 0;

        while(m -- > 0){
            String s = scan.next();
            if(s.equals("push")){
                int x= scan.nextInt();
                stl[++tt] = x;
            }else if(s.equals("pop")){
                tt--;
            }else if(s.equals("empty")){
                if(tt > 0){
                    System.out.println("NO");
                }else System.out.println("YES");
            }else{
                System.out.println(stl[tt]);
            }

        }
    }
} 

8. 表达式求值

原题链接

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        //以字符串形式输入表达式
        String s = scan.next();
        //map来添加运算符号进去,定义优先级
        Map<Character,Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);

        Stack<Character> op = new Stack<>();//存运算符号
        Stack<Integer> num = new Stack<>();//存数字

        for(int i = 0 ; i < s.length(); i ++ ){
            char c = s.charAt(i);
            //判断c字符是不是数字
            if(Character.isDigit(c)){
                int x = 0,j = i;
                //数字可能会是多位数,
                while(j < s.length() && Character.isDigit(s.charAt(j))){
                    x = x * 10 + s.charAt(j) - '0';
                    j++;
                }
                num.push(x);//将数字x存入数字栈栈顶
                i = j - 1;//重新赋值i
            }else if(c == '('){
                op.push(c); // 将左括号存入字符栈栈顶
            }else if(c == ')'){
                //如果栈顶不等于左括号,一直计算下去;
                while(op.peek() != '('){
                    eval(op,num);
                }
                op.pop(); // 将左括号弹出栈顶
            }else { //如果是正常字符
                while(!op.empty() && op.peek() != '(' && map.get(op.peek()) >= map.get(c)){
                    eval(op,num);
                }
                op.push(c);
            }
        }
        while(!op.empty()) eval(op,num);
        System.out.println(num.peek());
    }
    public static void eval(Stack<Character> op,Stack<Integer> num){
        int b = num.pop();
        int a = num.pop();

        char c = op.pop();
        if(c == '+'){
           num.push(a+b);
        }else if(c == '-'){
            num.push(a-b);
        }else if(c == '*'){
            num.push(a*b);
        }else {
            num.push(a/b);
        }
    }
}

4. 队列 tt = -1,hh = 0;

9. 模拟队列

原题链接

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        //队列是在tt队尾插入元素,队头hh弹出元素
        int[] dl = new int[100010];
        int hh = 0;
        int tt = -1;
        while(m -- > 0){
            String s = scan.next();
            if(s.equals("push")){
                int x = scan.nextInt();
                dl[++tt] =  x;
            }else if(s.equals("pop")){
                hh++;
            }else if(s.equals("empty")){
                if(hh <= tt) System.out.println("NO");
                else System.out.println("YES");
            }else {
                System.out.println(dl[hh]);
            }
        }
    }
}

5. 单调栈

常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

10. 单调栈

力扣链接
原题链接

原题链接

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n+2];
        int[] st = new int[n+2];
        int tt = 0;
        for (int i = 0; i < n; i++) nums[i] = scanner.nextInt();
        
        for (int i = 0; i < n; i++) {
            while (tt != 0 && st[tt-1] >= nums[i]) {
                tt--;
            }
            if (tt == 0) {
                System.out.print(-1 + " ");
            } else {
                System.out.print(st[tt-1] + " ");
            }
            st[tt++] = nums[i];
        }
    }
}

6. 单调队列

11. 滑动窗口最大值

力扣链接
原题链接
原题链接

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] q = new int[nums.length];
        int hh = 0, tt = -1;
        int[] ans = new int[nums.length-k+1];
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (hh <= tt && q[hh] + k <= i) {
                hh++;
            }
            while (hh <= tt && x >= nums[q[tt]]) {
                tt--;
            }
            q[++tt] = i;
            if (i+1 >= k) {
                ans[i-k+1] = nums[q[hh]];
            }
        }
        return ans;
    }
}

7. KMP

12. KMP字符串

力扣链接
acwing链接

class Solution {
    public int strStr(String haystack, String needle) {
        int[] ne = new int[haystack.length()+2];
        ne[0] = -1;
        for (int i = 1,j = -1; i < needle.length(); i++) {
            while (j != -1 && needle.charAt(j+1) != needle.charAt(i)) {
                j = ne[j];
            }
            if (needle.charAt(j+1) == needle.charAt(i)) {
                j++;
            }
            ne[i] = j;
        }
        int ans = 0;
        for (int i = 0,j = -1; i < haystack.length(); i++) {
            while (j != -1 && haystack.charAt(i) != needle.charAt(j+1)) {
                j = ne[j];
            }
            if (haystack.charAt(i) == needle.charAt(j+1)) {
                j++;
            }
            if (j == needle.length()-1) {
                return i-needle.length()+1;
            }
        }
        return -1;
    }
}

8. Trie树

13. Trie字符串统计

力扣链接
acwing链接

class Trie {

    public int N,idx;
    public int[][] song;
    public int[] cnt;
    public char[] str;

    public Trie() {
        N = 100010;idx = 0;
        song = new int[N][26];
        cnt  = new int[N];
        str = new char[N];
    }
    
    public void insert(String word) {
        char[] str = word.toCharArray();
        int p = 0; //下标0表示头结点,根节点
        for(int i = 0 ; i < str.length; i ++ ){
            // 将字符串每个字符都转化成数字;0-25
            int u = str[i] - 'a'; 
            //如果这个的儿子分支没有字符,说明这条分支还没有这个字符插入过
            //就新建一个然后赋值为然后把【idx】下标赋值上去,作为每个分支的专属坐标
            if(song[p][u] == 0) song[p][u] = ++idx;
            //然后将p往下前进一层
            p = song[p][u];
        }
        //最后停在那一层的那个数字就做标记,说明这是一个字符串的结束。
        cnt[p]++;
    }
    
    public boolean search(String word) {
        char[] str = word.toCharArray();
        int p = 0;//从根节点开始,下标是0表示根节点,头结点
        for(int i = 0 ; i < str.length; i ++){
            int u = str[i] - 'a'; // 将字符串每个字符都转化成数字0-25
            //如果这个点上面没有标记,就说明没有存入过这个字符,所以返回0
            if(song[p][u] == 0) return false;
            //如果这个点上面能寻找到这个字符,就让他往下一层继续寻找;
            p = song[p][u];
        }
        //最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。
        return cnt[p] != 0;
    }
    
    public boolean startsWith(String prefix) {
        char[] str = prefix.toCharArray();
        int p = 0;//从根节点开始,下标是0表示根节点,头结点
        for(int i = 0 ; i < str.length; i ++){
            int u = str[i] - 'a'; // 将字符串每个字符都转化成数字0-25
            //如果这个点上面没有标记,就说明没有存入过这个字符,所以返回0
            if(song[p][u] == 0) return false;
            //如果这个点上面能寻找到这个字符,就让他往下一层继续寻找;
            if (i == str.length-1) {
                return song[p][u] != 0;
            }
            p = song[p][u];
        }
        //最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。
        return false;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
import java.util.Scanner;
public class Main{
    static int N = 100010,idx = 0;
    static int[][] song = new int[N][26];
    static int[] cnt  = new int[N];
    static char[] str = new char[N];
    public static  void insert(char[] str){
        int p = 0; //下标0表示头结点,根节点
        for(int i = 0 ; i < str.length; i ++ ){
            // 将字符串每个字符都转化成数字;0-25
            int u = str[i] - 'a'; 
            //如果这个的儿子分支没有字符,说明这条分支还没有这个字符插入过
            //就新建一个然后赋值为然后把【idx】下标赋值上去,作为每个分支的专属坐标
            if(song[p][u] == 0) song[p][u] = ++idx;
            //然后将p往下前进一层
            p = song[p][u];
        }
        //最后停在那一层的那个数字就做标记,说明这是一个字符串的结束。
        cnt[p]++;
    }
    public static int query(char[] str){
        int p = 0;//从根节点开始,下标是0表示根节点,头结点
        for(int i = 0 ; i < str.length; i ++){
            int u = str[i] - 'a'; // 将字符串每个字符都转化成数字0-25
            //如果这个点上面没有标记,就说明没有存入过这个字符,所以返回0
            if(song[p][u] == 0) return 0;
            //如果这个点上面能寻找到这个字符,就让他往下一层继续寻找;
            p = song[p][u];
        }
        //最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。
        return cnt[p];
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String sss = scan.nextLine();
        while(n -- > 0){
            String s = scan.nextLine();
            String[] st = s.split(" ");
            String s1 = st[0];
            String s2 = st[1];
            if(s1.equals("I")){
                insert(s2.toCharArray());
            }else{
                System.out.println(query(s2.toCharArray()));
            }

        }
    }
}

14. 最大异或对

力扣链接
acwing链接

class Solution {

    public static int N,idx;
    public static int[][] song;

    public static void add(int x){
        int p = 0;//从头结点开始
        for(int i = 30 ; i >= 0 ; i -- ){ //因为每一个数的二进制是有31位组成,所以需要从大开始遍历
            int u = x >> i & 1;//每一个数的二进制31个二进制每一位看0还是1
            if(song[p][u] == 0) song[p][u] = ++idx;//判断这一层是空的,就创建,然后赋值下标
            p = song[p][u];//然后让往下前进一层
        }
    }
    //查询
    public static int query(int x){
        int p = 0,res = 0;//从根节点0开始。res进就算异或后的最大值
        for(int i = 30; i>= 0 ; i --){
            int u = x >> i & 1;
            if(song[p][1-u] != 0){ //如果该节点的u是0,则判断一下在这一层有没有跟他相反的0-1,1-0,如果相反对应位置有数
                res += (1 << i);//res就将该二进制位对应异或之后的最优解1每一位顺次加起来。因为是异或相反数就是1,这是最优解
                p = song[p][1-u];//然后往最优解那边前进一层。
            }else{//否则就不是最优解的0匹配1,1匹配0,所以就异或之后的值是0
                //res += (0 << i);因为是0所以可以省略,
                p = song[p][u];//然后让他往不优解那边前进一层。
            }
        }
        return res;//最后返回异或之后的最大值res
    }

    public int findMaximumXOR(int[] nums) {
        N = 3100010;idx = 0;
        song = new int[N][2];
        int n = nums.length;
        for(int i = 0 ; i < n ; i ++ ){
            add(nums[i]);
        }
        int res  = 0;
        for(int i = 0 ; i < n ; i ++ ){
            //因为输入的是字符串所以需要转成整形。然后每一次比较res的值谁大,然后将最大值重新赋值给res
            res = Math.max(res,query(nums[i]));
        }
        return res;
    }
}
import java.io.*;
public class Main{
    static int N = 3100010,idx = 0;
    static int[][] song = new int[N][2];
    //插入
    public static void add(int x){
        int p = 0;//从头结点开始
        for(int i = 30 ; i >= 0 ; i -- ){ //因为每一个数的二进制是有31位组成,所以需要从大开始遍历
            int u = x >> i & 1;//每一个数的二进制31个二进制每一位看0还是1
            if(song[p][u] == 0) song[p][u] = ++idx;//判断这一层是空的,就创建,然后赋值下标
            p = song[p][u];//然后让往下前进一层
        }
    }
    //查询
    public static int query(int x){
        int p = 0,res = 0;//从根节点0开始。res进就算异或后的最大值
        for(int i = 30; i>= 0 ; i --){
            int u = x >> i & 1;
            if(song[p][1-u] != 0){ //如果该节点的u是0,则判断一下在这一层有没有跟他相反的0-1,1-0,如果相反对应位置有数
                res += (1 << i);//res就将该二进制位对应异或之后的最优解1每一位顺次加起来。因为是异或相反数就是1,这是最优解
                p = song[p][1-u];//然后往最优解那边前进一层。
            }else{//否则就不是最优解的0匹配1,1匹配0,所以就异或之后的值是0
                //res += (0 << i);因为是0所以可以省略,
                p = song[p][u];//然后让他往不优解那边前进一层。
            }
        }
        return res;//最后返回异或之后的最大值res
    }
    public static void main(String[] args)throws IOException{
        BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(re.readLine());
        String[] s = re.readLine().split(" ");
        for(int i = 0 ; i < n ; i ++ ){
            add(Integer.parseInt(s[i]));
        }
        int res  = 0;
        for(int i = 0 ; i < n ; i ++ ){
            //因为输入的是字符串所以需要转成整形。然后每一次比较res的值谁大,然后将最大值重新赋值给res
            res = Math.max(res,query(Integer.parseInt(s[i])));
        }
        wt.write(res +" ");//最后输出res,因为快输出输出的是字符串,所以需要在后面加上“ ”;
        wt.close();


    }
}

9. 并查集 find merge

15. 合并集合

在这里插入图片描述

原题链接
原题链接


import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int[] p = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); // 全部有n个数
        int m = scan.nextInt(); // 读入m个操作
        //将n个数每个数各自都在一个集合里面。都指向自己,说明现在有多少个集合
        for(int i = 1 ; i <= n ; i ++) p[i] = i; 
        while(m -- > 0){
            String s = scan.next();
            int a = scan.nextInt();
            int b = scan.nextInt();
            //合并集合
            if(s.equals("M")) p[find(a)] = find(b); //将a集合的根节点即祖先指向b集合的祖先 
            else{ //是否同个集合
                if(find(a) == find(b))System.out.println("Yes"); //如果两个集合的祖先相同说明两个集合在同个集合中。
                else System.out.println("No"); //否则相反
            }
        }
    }
    //并查集的核心操作,寻找根节点祖先 + 路径压缩
    public static int find(int x){
        // 如果这个集合的父节点指向的不是自己,说明不是根节点,递归寻找,
        //最后找到根节点之后,把路径上的所有集合都指向根节点、
        if(p[x] != x) p[x] = find(p[x]); 
        return p[x]; // 最后返回根节点
    }
}

16. 连通块中点的数量(每个集合有多少个元素)

在这里插入图片描述

原题链接

import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int[] p = new int[N];
    static int[] size = new int[N];//size用来存每个集合中数的个数
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 1 ; i <= n ;i ++){
            p[i] = i;
            size[i] = 1;// 一开始每个数是一个集合,各自都是个数为1;
        }
        while(m -- > 0){
            String s = scan.next();
            if(s.equals("C")){
                int a = scan.nextInt();
                int b = scan.nextInt();
                if(find(a) == find(b)) continue; // 这里需要特判一下,如果两个数是同个集合中的数,就结束;
                else{  
                    size[find(b)] += size[find(a)]; // 只有两个数的根节点,也就是祖先的size值才是有用的,
                    //两个集合中的赋值给另一个祖先的,即赋值给另一个祖先的这个祖先就是合并之后的两个集合的祖先
                    //  b的size[]  +  =a的size[] 因为b是合并之后的新祖先,所以要让b加上被合并的a
                    p[find(a)] = find(b); //合并操作,p[a]的祖先指向b,说明b是合并之后的祖先
                }

            }else if(s.equals("Q1")){
                int a = scan.nextInt();
                int b = scan.nextInt();
                if(find(a) == find(b))System.out.println("Yes");
                else System.out.println("No");
            }else{
                int a = scan.nextInt();
                //只有根节点的size才是有用的,则通过find(a)找到他的根节点然后输出根节点的size;
                System.out.println(size[find(a)]);
            }
        }
    }
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

17. 食物链

原题链接

法一: x,x+n,x+n+n merge(f[x+n],f[x])
思路:

  1. 因为有三种物种,A吃B,B吃C,C吃A
  2. 如果我们用一个数组存储,那么比如1吃2,那么我们让2的角标处的值标记成1,如果3吃2,那怎么标记?一个数组指定标记不过来。
  3. 那么我们想用三个数组存储,其实也存储不过来,因为角标就那么几个,
  4. 最好的方法就是,用x,x+n,x+n+n来表示
    比如1吃2,那么就可能有三种情况,
    A类中的1吃B类的2 : fa[1] = fa[2+n+n]
    B类中的1吃C类的2 : fa[1+n] = fa[2]
    C类中的1中A类的2 : fa[1+n+n] = fa[2+n];
    这样的话,就会有3*n个角标,就可以充分表达
    A中的1吃B中的2(B中的2用2+n表示)
    这样的话就不会出现数字冲突

A吃B
则让f[A] = B

/*

*/

#include <bits/stdc++.h>
using namespace std;
int fa[200000];
int n,m,k,x,y,ans;
int get(int x)
{
    if(x==fa[x]) 
        return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
    fa[get(x)]=get(y);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=3*n;i++) 
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&k,&x,&y);
        if(x>n || y>n) 
            ans++;
        else if(k==1)
        {
            if(get(x)==get(y+n) || get(x)==get(y+n+n)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.
                ans++;
            else
            {
                merge(x,y);
                merge(x+n,y+n);
                merge(x+n+n,y+n+n);
            }
        }
        else
        {
            if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x
                ans++;//都是假话
            else
            {
                merge(x,y+n+n);//y的捕食域加入x
                merge(x+n,y);//x的天敌域加入y
                merge(x+n+n,y+n);//x的捕食域是y的同类域.
            }
        }
    }
    cout<<ans<<endl;
}

法二:将有关系的都存储在一个部落,用到根节点的距离表示关系
二刷总结

  1. X吃Y 让x的祖宗等于y的祖宗 或者 y的祖宗等于x的祖宗都可以
  2. find查找函数中,具有压缩路径的作用,所以在写的时候,先找到此根节点,然后依次压缩,如下代码
    find中 d[x] += d[p[x]];
int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

不可以如下代码

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

  1. 在查询合并过程中,比如查询x的父节点,应该用一个变量记录下来,不能多次find,不然找不到x的原来父节点了
  2. 初始化 p[i] = i; d[i] = 0;
  3. 合并的时候,画图即可明白彼此的距离

具体过程如下:

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

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

    int res = 0;
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res ++ ;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)
            {
                if (px == py && (d[x] - d[y]) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/527958.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

视觉大模型--DAB-deter的深入理解

原理大家参考这篇文章&#xff0c;我主要是根据自己的理解和整个流程图以及代码进行对应&#xff0c;这样更有利于深入理解&#xff1a; 下图是解码器结构图&#xff0c;编码器没动和deter一样的 这张图片基本上说清了模型的结构和传递过程&#xff0c;红色代表切断梯度反向传…

用TensorBoard可视化PyTorch

一、TensorBoard与PyTorch配合使用的基本步骤 PyTorch可以直接与TensorBoard进行集成&#xff0c;因为TensorBoard是一个独立于TensorFlow之外的可视化工具。TensorBoard被设计为支持机器学习实验的可视化&#xff0c;如训练的进度和结果等。PyTorch中的torch.utils.tensorboa…

SSM党员管理系统

一、系统介绍 党员管理系统: 可以方便管理人员对党员管理系统的管理&#xff0c;提高信息管理工作效率及查询效率&#xff0c;有利于更好的为用户提供服务。 主要的模块包括&#xff1a; 1、后台功能&#xff1a; 管理员角色&#xff1a;首页、个人中心&#xff0c;党员管理…

“成像光谱遥感技术中的AI革命:ChatGPT在遥感领域中的应用“

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力。本文重点介绍ChatGPT在遥感中的应用&#xff0c;人工智能…

Vue-B站学习笔记

1. 路由配置 B站视频之Vue route文件下的index.js app.vue

云原生:5分钟了解一下Kubernetes是什么

在当今的云计算时代&#xff0c;容器化技术变得越来越重要。它能够帮助开发者更高效地部署和管理应用程序。而Kubernetes&#xff0c;作为容器编排领域的领军者&#xff0c;正逐渐成为企业构建和管理云原生应用的核心工具。 近期将持续为大家分享Kubernetes相关知识&#xff…

78、WAF攻防——菜刀冰蝎哥斯拉流量通讯特征绕过检测反制感知

文章目录 菜刀冰蝎哥斯拉 本节主要讲上传了后门&#xff0c;要是用webshell连接工具进行连接&#xff0c;而webshell连接工具特征可能被检测系统识别相关内容。 web防护软件&#xff1a; WEB应用防火墙——WAF入侵检测系统——IDS、HIDS威胁感知——天眼 感知威胁技术&#x…

基于单片机数码管20V电压表仿真设计

**单片机设计介绍&#xff0c;基于单片机数码管20V电压表仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机数码管20V电压表仿真设计的主要目的是通过单片机和数码管显示电路实现一个能够测量0到20V直流电压的电…

如何设计系统容量?

单位每年都会举行运动会&#xff0c;有一个2000m长跑的项目&#xff0c;大约每年报名人员为男选手40人&#xff0c;女选手20人&#xff0c;只有一条橡胶跑道。一次比赛10人齐跑&#xff0c;所以至少需要6场比赛。 2000米的完成时间要求是20分钟&#xff0c;超过20分钟不计数&a…

世强硬创获德佑威授权代理,拓展UV胶粘剂/PUR热熔胶等产品布局

随着下游应用市场产品不断更新迭代&#xff0c;以及企业的环保意识提高&#xff0c;企业对电子胶粘材料的性能要求越来越高&#xff0c;从而推动上游原厂的技术创新与升级&#xff0c;为国内提供更多高性能国产胶粘材料。 基于优良的口碑&#xff0c;世强先进&#xff08;深圳…

关于JVM-三色标记算法剖析

相关系列 深入理解JVM垃圾收集器-CSDN博客 深入理解JVM垃圾收集算法-CSDN博客 深入理解jvm执行引擎-CSDN博客 jvm优化原则-CSDN博客 jvm流程图-CSDN博客 三色标记产生的原因&#xff1f; 在并发标记的过程中&#xff0c;因为标记期间应用线程还在继续跑&#xff0c;对象间的引…

面试题:volatile

一旦一个共享变量&#xff08;类的成员变量、类的静态成员变量&#xff09;被volatile修饰之后&#xff0c;那么就具备了两层语义&#xff1a; 1. 保证线程间的可见性 保证了不同线程对这个变量进行操作时的可见性&#xff0c;即一个线程修改了某个变量的值&#xff0c;这新值…

Javascript进阶内容

1. 作用域 1.1 局部作用域 局部作用域分为函数作用域 和 块级作用域 块级作用域就是用 {} 包起来的&#xff0c;let、const声明的变量就是产生块作用域&#xff0c;var不会&#xff1b;不同代码块之间的变量无法互相访问&#xff0c;里面的变量外部无法访问 1.2 全局作用域…

安卓开机启动流程

目录 一、整体框架二、流程代码分析2.1 Boot ROM2.2 Boot Loader2.3 Kernel层Kernel代码部分 2.4 Init进程Init进程代码部分 2.5 zygote进程zygote代码部分 2.6 SystemServer进程SystemServer代码部分 2.7 启动Launcher与SystemUI 三、SystemServices3.1 引导服务3.2 核心服务3…

Linux|从 STDIN 读取 Awk 输入

简介 在之前关于 Awk 工具的系列文章中&#xff0c;主要探讨了如何从文件中读取数据。但如果你希望从标准输入&#xff08;STDIN&#xff09;中读取数据&#xff0c;又该如何操作呢&#xff1f; 在本文中&#xff0c;将介绍几个示例&#xff0c;展示如何使用 Awk 来过滤其他命令…

开创加密资产新纪元:深度解析ERC-314协议

随着加密资产市场的不断发展和区块链技术的日益成熟&#xff0c;新的协议和标准不断涌现&#xff0c;其中包括了ERC-314协议。本文将深入分析ERC-314协议的特点、功能以及对加密资产市场可能产生的影响。 1. ERC-314协议简介 ERC-314协议是一项建立在以太坊区块链上的新提案&a…

软件测试中的43个功能测试点总结

功能测试就是对产品的各功能进行验证&#xff0c;根据功能测试用例&#xff0c;逐项测试&#xff0c;检查产品是否达到用户要求的功能。针对web系统的常用测试方法如下&#xff1a; 1、页面链接检查&#xff1a; 每一个链接是否都有对应的页面&#xff0c;并且页面之间切换正…

设计模式之状态模式讲解

概念&#xff1a;又称为状态对象模式&#xff0c;该模式允许一个对象在其内部状态改变时改变其行为。状态模式的核心是封装&#xff0c;状态的变更引起行为的变动&#xff0c;从外部看来就好像该对象对应的类发生改变一样。 抽象状态&#xff1a;用以封装环境对象的一个特定状态…

thinkphp6使用阿里云SDK发送短信

使用composer安装sdk "alibabacloud/dysmsapi-20170525": "2.0.24"封装发送短信类 发送到的短信参数写在env文件里面的 #发送短信配置 [AliyunSms] AccessKeyId "" AccessKeySecret "" signName"" templateCode"&…

尚硅谷html5+css3(3)布局

1.文档流normal flow -网页是一个多层结构 -通过CSS可以分别为每一层设置样式 -用户只能看到最顶层 -最底层&#xff1a;文档流&#xff08;我们所创建的元素默认都是从文档流中进行排列&#xff09; <head><style>.box1 {background-color: blue;}/*它的父元…