Tire Tree

高效实现字符串的存储与查询

class TrieTree {
  final static int N = 10010;
  static int idx = 0;
  static int[] cnt = new int[N];
  static int[][] son = new int[N][26];
  
  public void insert(String str) {
    int p = 0;
    char[] s = str.toCharArray();
    
    for (int i = 0; i < s.length; i++) {
      int u = s[i] - 'a';
      if (son[p][u] == 0) son[p][u] = ++idx;
      p = son[p][u];
    }
    cnt[p]++;
  }
  
  public int query(String str) {
    int p = 0;
    char[] s = str.toCharArray();
    for (int i = 0; i < s.length; i++) {
      int u = s[i] - 'a';
      if (son[p][u] == 0) return 0;
      p = son[p][u];
    }
    return cnt[p];
  }
}

并查集

O(1) 时间复杂度查找点属于的集合

class UnionAndFound {
  final static int N = 10010;
  
  int[] p = new int[N], size = new int[N];
  
  // 路径压缩优化
  public int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
  }
  
  // 点集合并
  public void insert(int a, int b) {
    p[find(a)] = find(b);
    size[find(b)] += size[find(a)];
  }
}

堆

public class Heap {
  final static int N = 10010;
  static int size = 0;
  final static int[] h = new int[N];
  // ph[] 映射插入点在堆上的位置，hp[] 映射堆上某个点是插入的第 N 个点
  final static int[] ph = new int[N], hp = new int[N];

  /**
  * @param a 堆上的某个位置 a
  * @param b 堆上的某个位置 b
  */
  private static void swap(int a, int b) {
    // 点位置交换
    Tools.swap(ph, hp[a], hp[b]);
    // 点的 idx 属性交换
    Tools.swap(hp, a, b);
    // 点的值交换
    Tools.swap(h, a, b);
  }

  private static void up(int idx) {
    while (idx >> 1 > 0 && h[idx] < h[idx >> 1]) {
      swap(idx, idx >> 1); idx >>= 1;
    }
  }

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

  public static void insert(int value) {
    h[++size] = value;
    up(size);
  }

  public static int removeFirst() {
    int ret = h[1];
    h[1] = h[size--];
    down(1);
    return ret;
  }

  public int getMin() {
    return h[1];
  }

  public static int remove(int index) {
    int ret = h[index];
    h[index] = h[size--];
    up(index);
    down(index);
    return ret;
  }

  public static void change(int index, int value) {
    h[index] = value;
    down(index);
    up(index);
  }

  public static void main(String[] args) {
    //Scanner cin = new Scanner(System.in);
    //int n = cin.nextInt(), m = cin.nextInt();

    // init
    //for (int i = 0; i < n; i++) h[i] = cin.nextInt();
    //size = n;

    // O(N) 时间复杂度建堆
    //for (int i = n / 2; i > 0; i--) down(i);

    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt(), idx = 0;

    while (n-- > 0) {
      String op = cin.next();
      int k, x;
      // 插入元素
      if (op.startsWith("I")) {
        x = cin.nextInt();
        // 堆大小++ 序号++
        size++;    idx++;
        ph[idx] = size; hp[size] = idx;
        h[size] = x;
        // 输出最小值
      } else if (op.startsWith("PM")) {
        System.out.println(h[1]);
        // 删除最小值
      } else if (op.startsWith("DM")) {
        swap(1, size);
        size--;
        down(1);
        // 删除第 K 个插入的数
      } else if (op.startsWith("D")) {
        k = cin.nextInt();
        // 拿到该点在堆中的下标
        k = ph[k];
        swap(k, size--);
        down(k); up(k);
        // 修改第 K 个数
      } else {
        k = cin.nextInt(); x= cin.nextInt();
        k = ph[k];
        change(k, x);
      }
    }
  }
}

• 参考来源
  • ACWing - 算法基础课