头像

Gra




离线:7小时前


新鲜事 原文

Gra
19小时前
想问问 ACWing 上哪一道题是关于「权重并查集」并有 y 总讲解的。



Gra
2天前
import java.util.*;
import java.io.*;

class Main {
    static int N = 1010;
    static int[] heap = new int[N];
    static int size = 1;
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());
        String[] s = reader.readLine().split(" ");
        for (int j = 1; j <= n; j++) heap[j] = Integer.parseInt(s[j - 1]);
        size = n;

        getLog(writer);

        // 判断是否为大根堆
        boolean isMax = true;
        for (int k = 1; k <= n; k++) {
            int root = heap[k];
            int left = k * 2 <= size ? heap[k * 2] : Integer.MIN_VALUE;
            int right = k * 2 + 1 <= size ? heap[k * 2 + 1] : Integer.MIN_VALUE;
            if (root < left || root < right) {
                isMax = false;
                break;
            }
        }
        if (isMax) {
            writer.write("Max Heap");
        }

        // 判断是否为小根堆
        boolean isMin = true;
        for (int k = 1; k <= n; k++) {
            int root = heap[k];
            int left = k * 2 <= size ? heap[k * 2] : Integer.MAX_VALUE;
            int right = k * 2 + 1 <= size ? heap[k * 2 + 1] : Integer.MAX_VALUE;
            if (root > left || root > right) {
                isMin = false;
                break;
            }
        }
        if (isMin) {
            writer.write("Min Heap");
        }

        // 都不是
        if (!isMax && !isMin) {
            writer.write("Not Heap");  
        } 

        reader.close();
        writer.flush();
        writer.close();
    }

    private static void getLog(BufferedWriter writer) throws IOException {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(1, size, list, writer);
    }

    private static void dfs(int i, int n, ArrayList<Integer> list, BufferedWriter writer) throws IOException {
        if (i * 2 > n) {
            if (i <= n) list.add(heap[i]);
            for (int item : list) {
                writer.write(item + " ");
            }
            writer.write("\n");
            return;
        }

        list.add(heap[i]);

        if (i * 2 + 1 <= n) {
            ArrayList<Integer> copy2 = new ArrayList<>(list);
            dfs(i * 2 + 1, n, copy2, writer);   
        }

        if (i * 2 <= n) {
            ArrayList<Integer> copy1 = new ArrayList<>(list);
            dfs(i * 2, n, copy1, writer);   
        }
    }
}



Gra
3天前
import java.util.*;
import java.io.*;

class Main {
    static int N = 100009;
    static int[] minHeap = new int[N];
    static int size = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

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

        s = reader.readLine().split(" ");
        // O(n) 的建堆方式
        // 由于 up 和 down 都是和树的高度成正比,所以时间复杂度是 O(logN) 的
        // 如果采用每次插入都进行一次 up 或者 down 的话,建堆的时间复杂度是 O(NlogN) 的
        // 而下面是 O(n) 的建堆方式:先全部插入,再从 n / 2 down 到 1 
        for (int i = 1; i <= n; i++) {
            minHeap[++size] = Integer.parseInt(s[i - 1]);
        }
        for (int i = n / 2; i > 0; i--) {
            down(i);
        }

        while (m > 0) {
            writer.write(minHeap[1] + " ");    
            minHeap[1] = minHeap[size--];
            down(1);
            m--;
        }

        reader.close();
        writer.flush();
        writer.close();
    }

    private static void down(int x) {
        int u = x;
        if (x * 2 <= size && minHeap[x * 2] < minHeap[u]) u = x * 2;
        if (x * 2 + 1 <= size && minHeap[x * 2 + 1] < minHeap[u]) u = x * 2 + 1;
        if (x != u) {
            swap(x, u);
            down(u);
        }
    }

    private static void swap(int a, int b) {
        int tmp = minHeap[a];
        minHeap[a] = minHeap[b];
        minHeap[b] = tmp;
    }
}



Gra
3天前

当处理 F (朋友)的时候,直接合并
处理 E (敌人)的时候,先使用 map 进行记录,然后再一次性合并,注意使用 map 记录的时候需要双向记录(互为敌人关系)

例如题目的例子,当处理完输入的时候,应该有如下的映射关系
1 : [2,4]
2 : [1]
4 : [1]

import java.util.*;
import java.io.*;

class Main {
    static int N = 10009;
    static int[] p = new int[N];
    static Map<Integer, Set<Integer>> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }

        int m = Integer.parseInt(reader.readLine());
        for (int i = 0; i < m; i++) {
            String[] s = reader.readLine().split(" ");
            if (s[0].equals("F")) {
                int p = Integer.parseInt(s[1]);
                int q = Integer.parseInt(s[2]);
                meger(p, q);            
            } else if (s[0].equals("E")) {
                int p = Integer.parseInt(s[1]);
                int q = Integer.parseInt(s[2]);

                Set<Integer> pSet = map.getOrDefault(p, new HashSet<Integer>());
                pSet.add(q);
                map.put(p, pSet);

                Set<Integer> qSet = map.getOrDefault(q, new HashSet<Integer>());
                qSet.add(p);
                map.put(q, qSet);
            }
        }

        process();
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= n; i++) {
             set.add(find(i));
        }
        writer.write(set.size() + " ");

        reader.close();
        writer.flush();
        writer.close();
    }

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

    private static void meger(int a, int b) {
        p[find(a)] = p[find(b)];
    }

    private static void process() {
        Set<Integer> keys = map.keySet();
        for (Integer key : keys) {
            List<Integer> list = new ArrayList<>(map.get(key));
            if (list.size() == 1) continue;
            for (int i = 0; i < list.size() - 1; i++) {
                meger(list.get(i), list.get(i + 1));
            }
        }
    }
}



Gra
3天前
import java.util.*;
import java.io.*;

class Main {
    static int N = 100009;
    static int[] p = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        // 一定要先初始化,让 n 个数的 father 指针先指向自己,代表每个数刚开始都是自己一个集合
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }

        int m = Integer.parseInt(s[1]);
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            if (s[0].equals("M")) {
                int a = Integer.parseInt(s[1]);
                int b = Integer.parseInt(s[2]);
                meger(a, b);            
            } else if (s[0].equals("Q")) {
                int a = Integer.parseInt(s[1]);
                int b = Integer.parseInt(s[2]);
                boolean ans = query(a, b);
                writer.write(ans ? "Yes" : "No");
                writer.write("\n");
            }
        }
        reader.close();
        writer.flush();
        writer.close();
    }

    // 含义为,让 a 节点的祖宗节点的 father 指针指向 b 节点的祖宗节点
    private static void meger(int a, int b) {
        p[find(a)] = p[find(b)];
    }

    // 返回 x 的祖宗节点
    private static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private static boolean query(int a, int b) {
        return find(a) == find(b);
    }
}



Gra
3天前
import java.util.*;
import java.io.*;

class Main {
    static int N = 100009;
    static int[][] trie;
    static int[] count;
    static int idx;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(reader.readLine());
        for (int i = 0; i < t; i++) {
            trie = new int[N][10];
            count = new int[N];
            idx = 0;
            int n = Integer.parseInt(reader.readLine());
            int[][] arr = new int[n][11];
            for (int j = 0; j < n; j++) {
                String[] s = reader.readLine().split("");
                // System.out.println(Arrays.toString(s));
                int len = s.length;
                int[] ints = new int[len];
                for (int k = 0; k < len; k++) {
                    ints[k] = Integer.parseInt(s[k]);
                }
                arr[j] = ints;
            }   

            // sort:将数组长度小的排在前面,长度相同的则无所谓
            Arrays.sort(arr, (int[] a, int[] b) -> {
                int aLen = a.length;
                int bLen = b.length;
                if (aLen == bLen) {
                    return 0;
                } else {
                    return aLen > bLen ? 1 : -1;
                }
            });

            boolean b = insert(arr);
            writer.write(b ? "YES" : "NO");
            writer.write("\n");
        }
        reader.close();
        writer.flush();
        writer.close();
    }

    private static boolean insert(int[][] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int[] ints = arr[i];
            // System.out.println(Arrays.toString(ints));
            int len = ints.length;
            int p = 0;
            for (int j = 1; j <= len; j++) {
                int u = ints[j - 1];
                if (trie[p][u] != 0) {
                    if (count[trie[p][u]] != 0) return false;
                } else {
                    trie[p][u] = ++idx;
                }
                p = trie[p][u];
            }
            count[p]++;
        }
        return true;
    }
}



Gra
3天前
import java.util.*;
import java.io.*;

class Main {
    static int N = 1000009;
    static int[][] trie = new int[N][26];
    static int[] count = new int[N];
    static int idx = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i++) {
            String str = reader.readLine();
            insert(str);
        }
        for (int i = 1; i <= m; i++) {
            String str = reader.readLine();           
            writer.write(preCnt(str) + " ");
            writer.write("\n");
        }
        reader.close();
        writer.flush();
        writer.close();
    }

    private static void insert(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) trie[p][u] = ++idx;
            p = trie[p][u];
        }
        count[p]++;
    }

    private static int preCnt(String s) {
        int ans = 0;
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] != 0) {
                p = trie[p][u];
                ans += count[p];
            } else {
                break;
            }
        }
        return ans;
    }
}



Gra
5天前
class FrontMiddleBackQueue {

    private List<Integer> list;

    public FrontMiddleBackQueue() {
        list = new ArrayList<Integer>(4000);
    }

    public void pushFront(int val) {
        if (list.isEmpty()) {
            pushBack(val);
        } else {
            list.add(0, val);
        } 
    }

    public void pushMiddle(int val) {
        if (list.isEmpty()) {
            pushBack(val);
        } else {
            int size = list.size();
            if (size % 2 != 0) {
                size -= 1;                
            }
            int target = size / 2;
            list.add(target, val);
        }
    }

    public void pushBack(int val) {
        list.add(val);
    }

    public int popFront() {
        if (list.isEmpty()) return -1;
        Integer i = list.remove(0);
        return i;
    }

    public int popMiddle() {
        if (list.isEmpty()) return -1;
        int size = list.size() - 1;
        int target = size / 2;
        Integer i = list.remove(target);
        return i;
    }

    public int popBack() {
        if (list.isEmpty()) return -1;
        Integer i = list.remove(list.size() - 1);
        return i;
    }
}



Gra
5天前
class Solution {
    public ListNode mergeInBetween(ListNode n1, int a, int b, ListNode n2) {
        ListNode last = n2;
        while (last.next != null) {
            last = last.next;
        }

        ListNode prev = null;
        ListNode tmpA = n1;
        while (a > 0) {
            prev = tmpA;
            tmpA = tmpA.next;
            a--;
        }
        ListNode tmpB = n1;
        while (b > 0) {
            tmpB = tmpB.next;
            b--;
        }
        ListNode head = n1;
        prev.next = n2;
        last.next = tmpB.next;
        return head;
    }
}



Gra
5天前
class Solution {
    public int maxRepeating(String s, String w) {
        int n = s.length();
        Set<String> set = new HashSet();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                set.add(s.substring(i, j));
            }
        }
        int ans = 0;
        String t = w;
        while (set.contains(t)) {
            ans++;
            t = t + w;
        }
        return ans;
    }
}