Union Find    集合合并，查找元素在集合里面

数组实现

int[] pre;    public int find(int x) {        int r = x;        while (r != pre[r]) {            r = pre[r];        }        int i = x, j;        while (pre[i] != r) {            j = pre[i];            pre[i] = r;            i = j;        }        return r;    }    public void union(int x, int y) {        int fx = find(x);        int fy = find(y);        if (fx != fy) {            pre[fx] = fy;        }    }

hashMap实现

class UnionFind 
      
       {    private Map
       
         map = new HashMap<>();        public UnionFind(Set
        
          set) {        for (T t : set) {            map.put(t, t);        }    }        public T find(T x) {        T r = x;        if (r != map.get(r)) {            r = map.get(r);        }                T i = x, j;        while (i != r) {            j = map.get(i);            map.put(i, r);            i = j;        }        return r;    }        public void union(T x, T y) {        T fx = find(x);        T fy = find(y);        if (fx != fy) {            map.put(fx, fy);        }    }}
        
       
      

 1，找无向图的联通块。 bfs

找出无向图中所有的连通块。图中的每个节点包含一个label属性和一个邻接点的列表。（一个无向图的连通块是一个子图，其中任意两个顶点通过路径相连，且不与整个图中的其它顶点相连。）您在真实的面试中是否遇到过这个题？ Yes样例给定图:A------B  C \     |  |   \    |  |   \   |  |    \  |  |      D   E返回 {A,B,D}, {C,E}。其中有 2 个连通块，即{A,B,D}, {C,E}标签 相关题目

class UndirectedGraphNode {         int label;         ArrayList
      
        neighbors;         UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList
       
        (); }     }     public List
        
         
          > connectedSet(ArrayList
          
            nodes) {                 List
           
            
             > result = new ArrayList<>(); if (nodes == null || nodes.size() == 0) { return result; } Map
             
               map = new HashMap<>(); for (UndirectedGraphNode node : nodes) { map.put(node, false); } for (UndirectedGraphNode node : nodes) { if (!map.get(node)) { find(node, result, map); } } return result; } private void find(UndirectedGraphNode node, List
              
               
                > result, Map
                
                  map) { ArrayList
                 
                   list = new ArrayList<>(); Queue
                  
                    queue = new LinkedList<>(); queue.offer(node); map.put(node, true); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { UndirectedGraphNode cur = queue.poll(); list.add(cur.label); for (UndirectedGraphNode neighbor : cur.neighbors) { if (!map.get(neighbor)) { map.put(neighbor, true); queue.offer(neighbor); } } } } result.add(list); }
                  
                 
                
               
              
             
            
           
          
         
        
       
      

2 Find the Weak Connected Component in the Directed Graph

class DirectedGraphNode {              int label;              ArrayList
      
        neighbors;              DirectedGraphNode(int x) { label = x; neighbors = new ArrayList
       
        (); }          }     public List
        
         
          > connectedSet2(ArrayList
          
            nodes) {         List
           
            
             > result = new ArrayList<>(); if (nodes == null || nodes.size() == 0) { return result; } Set
             
               set = new HashSet<>(); for (DirectedGraphNode node : nodes) { set.add(node.label); } UnionFind uf = new UnionFind(set); for (DirectedGraphNode node : nodes) { for (DirectedGraphNode neighbor : node.neighbors) { uf.union(node.label, neighbor.label); } } Map
              
               > map = new HashMap<>(); for (DirectedGraphNode node : nodes) { int parent = uf.find(node.label); if (!map.containsKey(parent)) { map.put(parent, new ArrayList
               
                ()); } else { map.get(parent).add(node.label); } } for (List
                
                  list : map.values()) { result.add(list); } return result; }
                
               
              
             
            
           
          
         
        
       
      

3 Number of Islands

public class Solution {    /**     * @param grid a boolean 2D matrix     * @return an integer     */    int m;    int n;    int[] dx = {
    0, 0, 1, -1};    int[] dy = {-1, 1, 0, 0};    public int numIslands(boolean[][] grid) {        if (grid == null || grid.length == 0 || grid[0].length == 0) {            return 0;        }        int islands = 0;        m = grid.length;        n = grid[0].length;        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j]) {                    islands++;                    bfs(grid, i, j);                }            }        }        return islands;    }    void bfs(boolean[][] grid, int i, int j) {        Queue
      
        queue = new LinkedList<>();        queue.offer(i * n + j);        while (!queue.isEmpty()) {            int size = queue.size();            for (int k = 0; k < size; k++) {                int cur = queue.poll();                int x = cur / n;                int y = cur % n;                grid[x][y] = false;                for (int h = 0; h < 4; h++) {                    int nx = x + dx[h];                    int ny = y + dy[h];                    if (isValue(grid, nx, ny)) {                        queue.offer(nx * n + ny);                    }                }            }        }    }    boolean isValue(boolean[][] grid, int x, int y) {        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y];    }}
      

public class Solution {    /**     * @param grid a boolean 2D matrix     * @return an integer     */    int m;    int n;    int[] dx = {
    0, 0, 1, -1};    int[] dy = {-1, 1, 0, 0};    public int numIslands(boolean[][] grid) {        if (grid == null || grid.length == 0 || grid[0].length == 0) {            return 0;        }        int islands = 0;        m = grid.length;        n = grid[0].length;        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j]) {                    islands++;                    dfs(grid, i, j);                }            }        }        return islands;    }    void dfs(boolean[][] grid, int i, int j) {        if (!isValue(grid, i, j)) return;        grid[i][j] = false;        for (int k = 0; k < 4; k++) {            int x = i + dx[k];            int y = j + dy[k];            dfs(grid, x, y);        }    }    boolean isValue(boolean[][] grid, int x, int y) {        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y];    }}

4 3 Number of Islands 2

描述 笔记 数据 评测给定 n，m，分别代表一个2D矩阵的行数和列数，同时，给定一个大小为 k 的二元数组A。起初，2D矩阵的行数和列数均为 0，即该矩阵中只有海洋。二元数组有 k 个运算符，每个运算符有 2 个整数 A[i].x, A[i].y，你可通过改变矩阵网格中的A[i].x]，[A[i].y] 来将其由海洋改为岛屿。请在每次运算后，返回矩阵中岛屿的数量。 注意事项0 代表海，1 代表岛。如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。您在真实的面试中是否遇到过这个题？ Yes样例给定 n = 3, m = 3， 二元数组 A = [(0,0),(0,1),(2,2),(2,1)].返回 [1,1,2,2].

public class Jdbct {     class Point {              int x;              int y;              Point() { x = 0; y = 0; }              Point(int a, int b) { x = a; y = b; }         }     public List
      
        numIslands2(int m, int n, Point[] operators) {         List
       
         result = new ArrayList<>();         if (operators == null || operators.length == 0) {             return result;         }         int[][] island = new int[m][n];         Set
        
          set = new HashSet<>();         for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 set.add(i * n + j);             }         }         int[] dx = {-1, 1, 0, 0};         int[] dy = {
    0, 0, -1, 1};         UnionFind uf = new UnionFind(set);         int count = 0;         for (Point point : operators) {             int x = point.x;             int y = point.y;             if (island[x][y] == 0) {                 island[x][y] = 1;                 count++;                 for (int i = 0; i < 4; i++) {                     int newX = x + dx[i];                     int newY = y + dy[i];                     if (newX >= 0 && newX < m && newY >= 0 && newY < n && island[newX][newY] == 1){                         int x_father = uf.find(x * n + y);                         int newX_father = uf.find(newX * n + newY);                         if (x_father != newX_father) {                             count--;                             uf.union(x * n + y, newX * n + newY);                         }                     }                 }             }             result.add(count);         }         return result;     }}class UnionFind {    private Map
         
           map = new HashMap<>();        public UnionFind(Set
          
            set) {        for (int t : set) {            map.put(t, t);        }    }        public int find(int x) {        int r = x;        if (r != map.get(r)) {            r = map.get(r);        }                int i = x, j;        while (i != r) {            j = map.get(i);            map.put(i, r);            i = j;        }        return r;    }        public void union(int x, int y) {        int fx = find(x);        int fy = find(y);        if (fx != fy) {            map.put(fx, fy);        }    }}
          
         
        
       
      

5 Surrounded Regions

public void surroundedRegions(char[][] board)    {        // Write your code here        if (board == null || board.length <= 1 || board[0].length <= 1)        {            return;        }        for (int i = 0; i < board[0].length; i++)        {            fill(board, 0, i);            fill(board, board.length - 1, i);        }        for (int i = 0; i < board.length; i++)        {            fill(board, i, 0);            fill(board, i, board[0].length - 1);        }        for (int i = 0; i < board.length; i++)        {            for (int j = 0; j < board[0].length; j++)            {                if (board[i][j] == 'O')                {                    board[i][j] = 'X';                }                else if (board[i][j] == '#')                {                    board[i][j] = 'O';                }            }        }    }    public void fill(char[][] board, int i, int j)    {        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {            return;        }        board[i][j] = '#';        fill(board, i + 1, j);        fill(board, i - 1, j);        fill(board, i, j - 1);        fill(board, i, j + 1);    }

6 Graph Valid Tree

public boolean validTree(int n, int[][] edges) {        // Write your code here        if (n == 0) {            return false;        }        if (edges.length != n - 1) {            return false;        }        Union u = new Union(n);        for (int i = 0; i < edges.length; i++){            if (u.find(edges[i][0]) == u.find(edges[i][1])){                return false;            }            u.union(edges[i][0], edges[i][1]);        }        return true;    }}class Union{    HashMap
      
        map = new HashMap<>();        public Union(int n){        for (int i = 0; i < n; i++){            map.put(i, i);        }    }    public int find(int x){        int r = map.get(x);                while (r != map.get(r)){            r = map.get(r);        }                int j = x, i;        while (r != j){            i = map.get(j);            map.put(j, r);            j = i;        }        return r;    }        public void union(int x, int y){        int fx = find(x), fy = find(y);        if (fx != fy){            map.put(x, fy);        }    }}
      

Trie   快速找到一个元素，一个字母一个字母查找

1 Implement Trie

class TrieNode {          public TrieNode[] children = new TrieNode[26];          public String item = "";                    // Initialize your data structure here.          public TrieNode() {          }      }            class Trie {          private TrieNode root;                public Trie() {              root = new TrieNode();          }                // Inserts a word into the trie.          public void insert(String word) {              TrieNode node = root;              for (char c : word.toCharArray()) {                  if (node.children[c - 'a'] == null) {                      node.children[c - 'a'] = new TrieNode();                  }                  node = node.children[c - 'a'];              }              node.item = word;          }                // Returns if the word is in the trie.          public boolean search(String word) {              TrieNode node = root;              for (char c : word.toCharArray()) {                  if (node.children[c - 'a'] == null) return false;                  node = node.children[c - 'a'];              }              return node.item.equals(word);          }                // Returns if there is any word in the trie          // that starts with the given prefix.          public boolean startsWith(String prefix) {              TrieNode node = root;              for (char c : prefix.toCharArray()) {                  if (node.children[c - 'a'] == null) return false;                  node = node.children[c - 'a'];              }              return true;          }      }

class TrieNode {    TrieNode[] children = new TrieNode[26];    boolean hasWord = false;    public void insert(String word, int index) {        if (word.length() == index) {            this.hasWord = true;            return;        }        int pos = word.charAt(index) - 'a';        if (children[pos] == null) {            children[pos] = new TrieNode();        }        children[pos].insert(word, index + 1);    }    public TrieNode find(String word, int index) {        if (word.length() == index) {            return this;        }        int pos = word.charAt(index) - 'a';        if (children[pos] == null) {            return null;        }        return children[pos].find(word, index + 1);    }}class Trie {    private TrieNode root;    public Trie() {        root = new TrieNode();    }    // Inserts a word into the trie.    public void insert(String word) {        root.insert(word, 0);    }    // Returns if the word is in the trie.    public boolean search(String word) {        TrieNode node = root.find(word, 0);        return (node != null && node.hasWord);    }    // Returns if there is any word in the trie    // that starts with the given prefix.    public boolean startsWith(String prefix) {        TrieNode node = root.find(prefix, 0);        return node != null;    }}

2 Word Search

public boolean exist(char[][] board, String word)     {        // write your code here        if (word == null || word.length() == 0)        {            return true;        }        if (board == null || board.length == 0 || board[0].length == 0)        {            return false;        }        for (int i = 0; i < board.length; i++)        {            for (int j = 0; j < board[0].length; j++)            {                if (check(board, word, new boolean[board.length][board[0].length], 0, i, j))                {                    return true;                }            }        }        return false;    }    private boolean check(char[][] board, String word, boolean[][] bs, int len, int i, int j) {        // TODO Auto-generated method stub        if (len == word.length())        {            return true;        }        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || bs[i][j]|| board[i][j] != word.charAt(len))        {            return false;        }        bs[i][j] = true;        boolean res = check(board, word, bs, len + 1, i + 1, j) ||                check(board, word, bs, len + 1, i - 1, j) ||                check(board, word, bs, len + 1, i, j + 1) ||                check(board, word, bs, len + 1, i, j - 1);        bs[i][j] = false;        return res;    }

3 Word Search II

public class Solution {    Set
      
        res = new HashSet
       
        ();    int m = 0, n = 0;    Trie trie = new Trie();    public List
        
          findWords(char[][] board, String[] words) {        m = board.length; n = board[0].length;        for (String s : words){            trie.insert(s);        }        boolean[][] visited = new boolean[m][n];        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++){                help(board, visited, "", i, j);            }        }        return new ArrayList<>(res);    }    public void help(char[][] board, boolean[][] visited, String item, int i, int j){        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) return;        item = item + board[i][j];        if (!trie.startsWith(item)) return;        if (trie.search(item)) res.add(item);        visited[i][j] = true;        help(board, visited, item, i - 1, j);        help(board, visited, item, i + 1, j);        help(board, visited, item, i, j - 1);        help(board, visited, item, i, j + 1);        visited[i][j] = false;    }}    class TrieNode {          public TrieNode[] children = new TrieNode[26];          public String item = "";                    // Initialize your data structure here.          public TrieNode() {          }      }            class Trie {          private TrieNode root;                public Trie() {              root = new TrieNode();          }                // Inserts a word into the trie.          public void insert(String word) {              TrieNode node = root;              for (char c : word.toCharArray()) {                  if (node.children[c - 'a'] == null) {                      node.children[c - 'a'] = new TrieNode();                  }                  node = node.children[c - 'a'];              }              node.item = word;          }                // Returns if the word is in the trie.          public boolean search(String word) {              TrieNode node = root;              for (char c : word.toCharArray()) {                  if (node.children[c - 'a'] == null) return false;                  node = node.children[c - 'a'];              }              return node.item.equals(word);          }                // Returns if there is any word in the trie          // that starts with the given prefix.          public boolean startsWith(String prefix) {              TrieNode node = root;              for (char c : prefix.toCharArray()) {                  if (node.children[c - 'a'] == null) return false;                  node = node.children[c - 'a'];              }              return true;          }      }
        
       
      

 4 Add and Search Word

public class WordDictionary {    private TrieNode root = new TrieNode();    // Adds a word into the data structure.    public void addWord(String word) {        // Write your code here        TrieNode node = root;        for (int i = 0; i < word.length(); i++){            char c = word.charAt(i);            if (node.children[c - 'a'] == null){                node.children[c - 'a'] = new TrieNode();            }            node = node.children[c - 'a'];        }        node.hasWord = true;    }    // Returns if the word is in the data structure. A word could    // contain the dot character '.' to represent any one letter.    public boolean search(String word) {        // Write your code here        return find(word, 0, root);    }    public boolean find(String word, int index, TrieNode now){        if (index == word.length()){            return now.hasWord;        }        char c = word.charAt(index);        if (c == '.'){            for (int i = 0; i < 26; i++){                if (now.children[i] != null){                    if (find(word, index + 1, now.children[i])){                        return true;                    }                }            }            return false;        } else if (now.children[c - 'a'] != null){            return find(word, index + 1, now.children[c - 'a']);        } else {            return false;        }    }}class TrieNode{    public TrieNode[] children;    public boolean hasWord;    public TrieNode(){        children = new TrieNode[26];        hasWord = false;    }}

Scan-Line  区间拆分

1 Number of Airplane in the sky

class Solution {    /**     * @param intervals: An interval array     * @return: Count of airplanes are in the sky.     */    public int countOfAirplanes(List
      
        airplanes) {         // write your code here        List
       
         list = new ArrayList
        
         ();        for (Interval i : airplanes){            list.add(new Point(i.start, 1));            list.add(new Point(i.end, 0));        }        Collections.sort(list, new Comparator
         
          () {            public int compare(Point p1, Point p2) {                if (p1.time == p2.time) {                    return p1.flag - p2.flag;                }                else {                    return p1.time - p2.time;                }            }        });        int count = 0, res = 0;        for (Point p : list){            if (p.flag == 1){                count++;            } else{                count--;            }            res = Math.max(count, res);        }        return res;    }        }class Point{    int time;    int flag;    Point(int time, int flag){        this.time = time;        this.flag = flag;    }}
         
        
       
      

heap定义：

 java的 PriorityQueue是一个小顶堆，用于找最大前K个严肃。sort可重写。在本博客下面一个地方有详细介绍。

1 Trapping Rain Water

public int trapRainWater(int[] heights) {    if (heights == null || heights.length == 0)    {        return 0;    }    int res = 0;    int l = 0;    int r = heights.length - 1;    int left_height = heights[l];    int right_height = heights[r];    while (l < r) {        if (left_height < right_height) {            l++;            if (left_height > heights[l]) {                res += left_height - heights[l];            } else {                left_height = heights[l];            }        } else {            r--;            if (right_height > heights[r]) {                res += right_height - heights[r];            } else {                right_height = heights[r];            }        }    }    return res;}

2 Trapping Rain Water II

public class Solution {    /**     * @param heights: a matrix of integers     * @return: an integer     */    class Point{        int x, y, h;        public Point(int x, int y, int h) {            this.x = x; this.y = y; this.h = h;        }    }    public int trapRainWater(int[][] heights) {        if (heights == null || heights.length == 0 || heights[0].length == 0) {            return 0;        }        int m = heights.length;        int n = heights[0].length;        int[] dx = {
    0, 0, -1, 1};        int[] dy = {-1, 1, 0, 0};        int res = 0;        Queue
      
        q = new PriorityQueue<>((p1, p2)->p1.h - p2.h);        boolean[][] visited = new boolean[m][n];        for (int i = 0; i < n; i++) {            q.add(new Point(0, i, heights[0][i]));            visited[0][i] = true;            q.add(new Point(m - 1, i, heights[m - 1][i]));            visited[m - 1][i] = true;                   }         for (int i = 0; i < m; i++) {            q.add(new Point(i, 0, heights[i][0]));            visited[i][0] = true;            q.add(new Point(i, n -1, heights[i][n - 1]));            visited[i][n - 1] = true;                   }        while (!q.isEmpty()) {            Point p = q.poll();            for (int k = 0; k < 4; k++) {                int newX = p.x + dx[k];                int newY = p.y + dy[k];                if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited[newX][newY]) {                    continue;                }                visited[newX][newY] = true;                q.add(new Point(newX, newY, Math.max(p.h, heights[newX][newY])));                res += Math.max(0, p.h - heights[newX][newY]);            }        }        return res;    }     }
      

 3 Building Outline

public List
      
        getSkyline(int[][] build) {        List
       
         res = new ArrayList<>();        List
        
          point = new ArrayList<>();        for (int i = 0; i < build.length; i++){            point.add(new int[]{build[i][0], build[i][2]});            point.add(new int[]{build[i][1], -build[i][2]});        }        Collections.sort(point, (a,b)->{            if (a[0] == b[0]) return b[1] - a[1];            return a[0] - b[0];        });        Queue
         
           q = new PriorityQueue<>((a,b)->(b - a));        int pre = 0, cur = 0;        for (int[] p : point){            if (p[1] > 0) {                q.offer(p[1]);                cur = q.peek();            } else {                q.remove(-p[1]);                cur = q.isEmpty() ? 0 : q.peek();            }            if (pre != cur){                res.add(new int[]{p[0], cur});                pre = cur;            }        }        return res;    }
         
        
       
      

 4 Heapify

private void siftdown(int[] A, int k) {        while (k < A.length) {            int smallest = k;            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {                smallest = k * 2 + 1;            }            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {                smallest = k * 2 + 2;            }            if (smallest == k) {                break;            }            int temp = A[smallest];            A[smallest] = A[k];            A[k] = temp;                        k = smallest;        }    }        public void heapify(int[] A) {        for (int i = A.length / 2; i >= 0; i--) {            siftdown(A, i);        } // for    }

5 Data Stream Median

public int[] medianII(int[] nums) {        // write your code here        Comparator
      
        comp = new Comparator
       
        (){            public int compare(Integer left, Integer right) {                return right - left;            }          };        int len = nums.length;        PriorityQueue
        
          minQ = new PriorityQueue<>();        PriorityQueue
         
           maxQ = new PriorityQueue<>(comp);        int[] res = new int[len];        res[0] = nums[0];        maxQ.add(nums[0]);        for (int i = 1; i < len; i++) {            int x = maxQ.peek();            if (nums[i] < x) {                maxQ.add(nums[i]);            } else {                minQ.add(nums[i]);            }            if (maxQ.size() > minQ.size() + 1){                minQ.add(maxQ.poll());            } else if (minQ.size() > maxQ.size()){                maxQ.add(minQ.poll());            }            res[i] = maxQ.peek();        }        return res;    }
         
        
       
      

6 Sliding Window Median   拆成两个步骤  1 加入一个元素，2删除一个元素， 求中位数

public ArrayList
      
        medianSlidingWindow(int[] nums, int k) {        // write your code here        ArrayList
       
         res = new ArrayList<>();        if (nums == null || nums.length == 0 || k <= 0) return res;        PriorityQueue
        
          max = new PriorityQueue<>((a,b)->(b - a));        PriorityQueue
         
           min = new PriorityQueue<>();        int mid = nums[0];        for (int i = 0; i < nums.length; i++) {            if (i != 0) {                if (nums[i] > mid) {                    min.add(nums[i]);                } else {                    max.add(nums[i]);                }            }            if (i >= k) {                if (mid == nums[i - k]) {                    if (max.size() > 0) {                        mid = max.poll();                    } else if (min.size() > 0) {                        mid = min.poll();                    }                } else if (mid > nums[i - k]) {                    max.remove(nums[i - k]);                } else {                    min.remove(nums[i - k]);                }            }            while (max.size() > min.size()) {                min.add(mid);                mid = max.poll();            }            while (min.size() > max.size() + 1) {                max.add(mid);                mid = min.poll();            }            if (i >= k - 1) {                res.add(mid);            }        }        return res;    }
         
        
       
      

7 sliding-window-maximum

public ArrayList
      
        maxSlidingWindow(int[] nums, int k) {        // write your code here        ArrayList
       
         res = new ArrayList<>();        if (nums == null || nums.length == 0 || k <= 0) {            return res;        }        Deque
        
          q = new ArrayDeque
         
          ();        for (int i = 0; i < nums.length; i++) {            while (!q.isEmpty() && nums[i] > q.peekLast()){                q.pollLast();            }            q.offer(nums[i]);            if (i > k - 1 && q.peekFirst() == nums[i - k]) {                q.pollFirst();            }            if (i >= k - 1) {                res.add(q.peekFirst());            }        }        r