Algorithm 10 Advanced Data Structures (Java implementation)

Time: 2021.10.4-2021.10.10

Trie tree (dictionary tree)

A trie tree, also known as a dictionary or prefix tree, is an ordered data structure for statistics, sorting, and storing strings. Unlike a binary lookup tree, keywords are not stored directly in a node, but are determined by the node’s position in the tree.

All descendants of a node have the same prefix, which is the string corresponding to the node, and the root node corresponds to the empty string. In general, not all nodes have corresponding values. Only leaf nodes and some internal nodes have corresponding keys with relevant values.

Trie trees take advantage of common string prefixes to reduce storage space and query time, thus minimizing unnecessary string comparisons and being very efficient string lookup data structures.

Check and set

Union Find, also known as Disjiont Set, is applied to the Set of N elements and query problems. In this application scenario, we usually start by making each element form a single element Set, and then merge the sets of elements belonging to the same group in a certain order. In between, you repeatedly find which collection an element is in. Although this problem is not complicated, it can not be solved by common data structure when facing huge amount of data, and searching set is the best algorithm to solve this problem.

Forest implementation

Use forests to store relationships between sets, where different elements belonging to the same set have the same root node representing the set.

When searching which set an element belongs to, that is, the element is traversed to the root node and the set represented by the root node is returned. In the traversal process, the optimization algorithm of path compression is used to make the shape of the whole tree more flat, so as to optimize the time complexity of the query.

When merging, the two subtrees are merged into one tree, and the root node of one subtree points to the root node of another subtree. During the merging, a smaller subtree can be merged into a larger one according to the size of the subtree, so that the tree size is more balanced and the time complexity of future queries is optimized.

Line segment tree

A line segment tree is a balanced binary search tree (complete binary tree) that divides a line segment interval into some unit intervals. For every non-leaf node [a,b] in the line segment tree, the interval represented by its left son is [A,(a+b)/2], and the interval represented by its right son is [(a+b)/2+1,b]. The final number of leaf nodes is N, corresponding to the array subscript. Generally, the operations of line segment tree include establishment, query, insertion, and update. The time complexity of establishment scale N is O(NlogN), and the time complexity of other operations is O(logN).

1. LeetCode208 implements Trie (prefix tree)

LeetCode official solution

public class Trie {
    public class TrieNode{
    public int path;
    public int end;
    public HashMap<Character, TrieNode> next;

    public TrieNode(a){
        path = 0;
        end = 0;
        next = newHashMap<>(); }}private TrieNode root;
    public Trie(a){
        root = new TrieNode();
    }

    public void insert(String word){
        if(word == null || word.equals(""))  return ;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(! node.next.containsKey(ch)) { node.next.put(ch,new TrieNode());
            }
            node = node.next.get(ch);
            node.path++;
        }
        node.end++;
    }

    public boolean search(String word){
        if(word == null || word.equals("")) return false;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(! node.next.containsKey(ch))return false;
            node = node.next.get(ch);
        }
        if(node.end == 0) return false;
        return true;
    }
    
    public boolean startsWith(String word){
        if(word == null || word.equals("")) return false;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(! node.next.containsKey(ch))return false;
            node = node.next.get(ch);
        }
        return true; }}/** * 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); * /
Copy the code

2. LeetCode211 add and search word-data structure design

LeetCode antithesis:

 // Prefix tree Trie + DFS recursion
class WordDictionary {

    // Prefix tree node
    private class TrieNode {
        TrieNode[] path;
        boolean end; // Whether word exists that ends with the current character
        public TrieNode(a) {
            path = new TrieNode[26]; // Word contains only 26 lowercase letters}}private TrieNode root;

    public WordDictionary(a) {
        root = new TrieNode();
    }

    public void addWord(String word) {
        if (word == null || word.length() == 0) return;
        // Attach word to prefix tree:
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            // No road, no road, no road
            if (cur.path[c - 'a'] = =null) cur.path[c - 'a'] = new TrieNode();
            cur = cur.path[c - 'a'];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        if (word == null || word.length() == 0) return false;
        return search(word.toCharArray(), 0, root);
    }

    / / DFS recursion
    // The current character is chars[I], and the current prefix tree node is cur
    // return: [I...] Can you match it
    private boolean search(char[] chars, int i, TrieNode cur) {
        if (cur == null) return false;

        char curChar = chars[i];
        if (i == chars.length-1) { // This is the last character
            if(curChar ! ='. ') { // The last character is not a dot, and needs to be strictly matched in the prefix tree (there is a corresponding path, and this path has end)
                return cur.path[curChar - 'a'] != null && cur.path[curChar - 'a'].end;
            } else { // The last character is a dot, as long as there is a path with an end
                for (TrieNode path : cur.path) {
                    if(path ! =null && path.end) return true;
                }
                return false; }}// This is not the last character, there is more than one character to match:
        if(curChar ! ='. ') { // It is not a point, it needs to be strictly matched in the prefix tree (there are corresponding paths, and can be matched later)
            return cur.path[curChar - 'a'] != null && search(chars, i+1, cur.path[curChar - 'a']);
        }
        // curChar == '.', as long as there is a path that can be matched later
        for (TrieNode path : cur.path) {
            if (search(chars, i+1, path)) return true;
        }
        return false; }}Copy the code

3. Number of LeetCode547 provinces

Method 1: DFS (LeetCode official Solution)

For each city, if the city has not been visited, the depth-first search starts from the city, and the cities directly connected to the city are obtained through the matrix isConnected. These cities belong to the same connected component as the city, and then the depth-first search continues for these cities. Until all cities of the same connected component are visited, a province can be obtained. After traversing all the cities, the total number of connected components can be obtained, that is, the total number of provinces.

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true; dfs(isConnected, visited, provinces, j); }}}}Copy the code

Method 2: and search set (LeetCode official solution)

class UnionFind {
    // Record the parent node
    private Map<Integer,Integer> father;
    // Record the number of sets
    private int numOfSets = 0;
    
    public UnionFind(a) {
        father = new HashMap<Integer,Integer>();
        numOfSets = 0;
    }
    
    public void add(int x) {
        if(! father.containsKey(x)) { father.put(x,null); numOfSets++; }}public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY){
            father.put(rootX,rootY);
            numOfSets--;
        }
    }
    
    public int find(int x) {
        int root = x;
        
        while(father.get(root) ! =null){
            root = father.get(root);
        }
        
        while(x ! = root){int original_father = father.get(x);
            father.put(x,root);
            x = original_father;
        }
        
        return root;
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int getNumOfSets(a) {
        returnnumOfSets; }}class Solution {
    public int findCircleNum(int[][] isConnected) {
        UnionFind uf = new UnionFind();
        for(int i = 0; i < isConnected.length; i++){ uf.add(i);for(int j = 0; j < i; j++){if(isConnected[i][j] == 1){ uf.merge(i,j); }}}returnuf.getNumOfSets(); }}Copy the code

4. LeetCode307 field and retrieval – array can be modified