字典樹，即Trie樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串(但不僅限于字符串)，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。
它的優(yōu)點(diǎn)是:最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
基本性質(zhì)
1.節(jié)點(diǎn)本身不存完整單詞
2.從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對應(yīng)的字符串；
3.每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)路徑代表的字符都不相同
trie核心思想是空間換時(shí)間
利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的
節(jié)點(diǎn)的內(nèi)部實(shí)現(xiàn)
實(shí)現(xiàn)Trie
Trie（發(fā)音類似 "try"）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和檢索字符串?dāng)?shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景，例如自動補(bǔ)完和拼寫檢查。
請你實(shí)現(xiàn) Trie 類：
Trie() 初始化前綴樹對象。
void insert(String word) 向前綴樹中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前綴樹中，返回 true（即，在檢索之前已經(jīng)插入）；否則，返回 false 。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。
示例：
輸入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出
[null, null, true, false, true, null, true]
解釋
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
向 Trie 樹中插入鍵
我們通過搜索 Trie 樹來插入一個(gè)鍵。我們從根開始搜索它對應(yīng)于第一個(gè)鍵字符的鏈接。有兩種情況：
鏈接存在。沿著鏈接移動到樹的下一個(gè)子層。算法繼續(xù)搜索下一個(gè)鍵字符。
鏈接不存在。創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將它與父節(jié)點(diǎn)的鏈接相連，該鏈接與當(dāng)前的鍵字符相匹配。
重復(fù)以上步驟，直到到達(dá)鍵的最后一個(gè)字符，然后將當(dāng)前節(jié)點(diǎn)標(biāo)記為結(jié)束節(jié)點(diǎn)，算法完成。
class Trie {
class TrieNode {
//結(jié)點(diǎn)數(shù)
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
public TrieNode(){
links = new TrieNode[R];
}
public boolean containsKey(char ch){
return links[ch - 'a'] != null;
}
public TrieNode get(char ch){
return links[ch - 'a'];
}
public void put(char ch, TrieNode node){
links[ch - 'a'] = node;
}
public void setIsEnd(){
isEnd = true;
}
public boolean isEnd(){
return isEnd;
}
}
private TrieNode root;
public Trie(){
root = new TrieNode();
}
//Inserts a word into the trie
public void insert(String word){
TrieNode node = root;
for (int i = 0;i<word.length();i++){
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)){
node.put(currentChar,new TrieNode());
}
node = node.get(currentChar);
}
node.setIsEnd();
}
//search a prefix or whole word in trie and returns the node when search ends
private TrieNode searchPrefix(String word){
TrieNode node = root;
for (int i = 0;i<word.length();i++){
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)){
node = node.get(curLetter);
}else{
return null;
}
}
return node;
}
//returns if the word is in the trie
public boolean search(String word){
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix){
TrieNode node = searchPrefix(prefix);
return node != null;
}
}
單詞搜索II
給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)單詞（字符串）列表 words，找出所有同時(shí)在二維網(wǎng)格和字典中出現(xiàn)的單詞。
單詞必須按照字母順序，通過 相鄰的單元格 內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。
示例 1：
輸入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
輸出：["eat","oath"]
示例 2：
輸入：board = [["a","b"],["c","d"]], words = ["abcb"]
輸出：[]
并查集
Quick Union Ranks
Path Halving Path Spliting
/**
* 項(xiàng)目名稱：Arithmetic
* 類 名 稱：UnionFind_QU_Rank
* 類 描 述：TODO
* 創(chuàng)建時(shí)間：2021/4/27 7:53 PM
* 創(chuàng) 建 人：cloud
*/
public class UnionFind_QU_Rank extends UnionFind_QU {
private int[] ranks;
public UnionFind_QU_Rank(int capacity) {
super(capacity);
ranks = new int[capacity];
//以i為根節(jié)點(diǎn)的這棵樹的高度
for (int i=0;i<ranks.length;i++){
ranks[i] = 1;
}
}
public void union(int v1,int v2){
int p1 = parents[v1];
int p2 = parents[v2];
if (p1 == p2) return;
if (ranks[p1] < ranks[p2]){
parents[p1] = p2;
}else if(ranks[p1] > ranks[p2]){
parents[p2] = p1;
}else{
parents[p1] = p2;
ranks[p2] ++;
}
}
}
省份數(shù)量
有 n 個(gè)城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。
省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。
給你一個(gè) n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個(gè)城市和第 j 個(gè)城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。
返回矩陣中 省份 的數(shù)量。
輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2
import org.junit.Test;
/**
* 項(xiàng)目名稱：Arithmetic
* 類 名 稱：UnionFind0
* 類 描 述：TODO
* 創(chuàng)建時(shí)間：2021/4/27 10:50 PM
* 創(chuàng) 建 人：cloud
*/
public class Solution0{
public class UnionFind0 {
public int[] parents;
public int sizes;//集合數(shù)量
public UnionFind0(int n) {
parents = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
}
sizes = n;
}
//快速查找根節(jié)點(diǎn):路徑壓縮，使路徑上所有節(jié)點(diǎn)都指向根節(jié)點(diǎn)，從而降低樹的高度
public int find(int v) {
rangeCheck(v);
if (parents[v] != v) {
parents[v] = find(parents[v]);
}
return parents[v];
}
//是不是相同的集合，聯(lián)通的點(diǎn)
public boolean isSame(int v1, int v2) {
return find(v1) == find(v2);
}
//合并v1,v2
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
if (p1 != p2) {
parents[p1] = p2;
sizes--;
}
}
//檢查邊界
public void rangeCheck(int v) {
if (v < 0 || v > parents.length) {
throw new IllegalArgumentException("v is out of bounds");
}
}
}
public int findCircleNum(int[][] isConnected) {
//初始化并查集
UnionFind0 unionFind0 = new UnionFind0(isConnected.length);
for (int i = 0; i < isConnected.length; i++) {
for (int j = i + 1; j < isConnected.length; j++) {
if (isConnected[i][j] == 1) {
unionFind0.union(i, j);
}
}
}
return unionFind0.sizes;
}
@Test
public void testCombineFindSet() {
// int[][] isConnected = {{1,1,0},{1,1,0},{0,0,1}};
// System.out.println(findCircleNum(isConnected));
// int[][] isConnected1 = {{1,0,0},{0,1,0},{0,0,1}};
// System.out.println(findCircleNum(isConnected1));
int[][] isConnected2 = {{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1}};
System.out.println(findCircleNum(isConnected2));
}
}
島嶼數(shù)量
public class UnionFind1{
//根節(jié)點(diǎn)數(shù)組
public int[] parents;
//集合數(shù)量
public int sizes;
UnionFind1(int capacity){
parents = new int[capacity];
for (int i = 0;i<capacity;i++){
parents[i] = i;
}
sizes = capacity;
}
//檢查邊界
public void rangeCheck(int v){
if (v < 0 || v > parents.length)
throw new IllegalArgumentException("v is out of bounds");
}
//路徑減半:將一條線上面的所有節(jié)點(diǎn)都指向祖父節(jié)點(diǎn)，壓縮了樹的高度
public int find(int v){
rangeCheck(v);
while(v !=parents[v]){
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
//快速合并兩個(gè)集合，集合的根節(jié)點(diǎn)中一方指向另外一方
public void union(int v1,int v2){
int p1 = find(v1);
int p2 = find(v2);
//同一個(gè)集合，不需要合并
if (p1 == p2) return;
if (p1 != p2){
parents[p1] = p2;
sizes--;
}
}
}
//島嶼數(shù)量，集合數(shù)量
public int numIslands(char[][] grid) {
//如果是一行一列
if (grid.length == 0 || grid == null) return 0;
int row = grid.length;
int col = grid[0].length;
int water = 0;//水域(0)個(gè)數(shù)
UnionFind1 unionFind1 = new UnionFind1(row * col);
for (int i = 0;i<row;i++){
for (int j = 0 ;j<col;j++){
if (grid[i][j] == '0') water++;
else{
//"1"的島嶼 注意:方向數(shù)組d是上下左右搜索的常用手法
int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] dir:directions){
int x = i+dir[0];
int y = j+dir[1];
//判斷是否越界
if (x>=0 && y>=0 && x<row && y<col && grid[x][y] == '1'){
//合并
unionFind1.union(i*col+j,x*col+y);
}
}
}
}
}
return unionFind1.sizes - water;
}
被圍繞的區(qū)域
給你一個(gè) m x n 的矩陣 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。
輸入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
輸出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解釋：被圍繞的區(qū)間不會存在于邊界上，換句話說，任何邊界上的 'O' 都不會被填充為 'X'。 任何不在邊界上，或不與邊界上的 'O' 相連的 'O' 最終都會被填充為 'X'。如果兩個(gè)元素在水平或垂直方向相鄰，則稱它們是“相連”的。
示例 2：
輸入：board = [["X"]]
輸出：[["X"]]
思路:我們的思路是把所有邊界上的 OO 看做一個(gè)連通區(qū)域。遇到 OO 就執(zhí)行并查集合并操作，這樣所有的 OO 就會被分成兩類
和邊界上的 OO 在一個(gè)連通區(qū)域內(nèi)的。這些 OO 我們保留。
不和邊界上的 OO 在一個(gè)連通區(qū)域內(nèi)的。這些 OO 就是被包圍的，替換。
由于并查集我們一般用一維數(shù)組來記錄，方便查找 parants，所以我們將二維坐標(biāo)用 node 函數(shù)轉(zhuǎn)化為一維坐標(biāo)。
class Solution {
public class UnionFind2{
//根節(jié)點(diǎn)數(shù)組
public int[] parents;
UnionFind2(int capacity){
parents = new int[capacity];
for (int i=0;i<capacity;i++){
parents[i] = i;
}
}
public int find(int v){
checkRange(v);
//路徑減半
while (parents[v] != v){
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
public void union(int v1,int v2){
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2)return;
parents[p1] = p2;
}
public boolean isConnected(int v1,int v2){
return find(v1) == find(v2);
}
public void checkRange(int v){
if (v < 0 || v > parents.length)
throw new IllegalArgumentException("v is out of bound");
}
}
public int row;
public int column;
public void solve(char[][] board) {
row = board.length;
column = board[0].length;
if (row == 0 || column == 0) return;
UnionFind2 unionFind2 = new UnionFind2(row * column + 1);
//標(biāo)記邊界連通為一個(gè)區(qū)域
int dummy = row * column;
for (int i = 0;i<row;i++)
for (int j = 0;j<column;j++){
if (board[i][j] == 'O'){
//處于邊界的位置，則連通為一個(gè)
if (i == 0 || i == row - 1 || j == 0 || j == column-1)
unionFind2.union(node(i,j),dummy);
//不在邊界位置的0，上下左右合并
else{
//上下左右合并聯(lián)通
if (i > 0 && board[i-1][j] == 'O'){
unionFind2.union(node(i,j),node(i-1,j));
}
if (i < row - 1 && board[i+1][j] == 'O'){
unionFind2.union(node(i,j),node(i+1,j));
}
if (j > 0 && board[i][j -1] == 'O'){
unionFind2.union(node(i,j),node(i,j-1));
}
if (j < column - 1 && board[i][j+1] == 'O'){
unionFind2.union(node(i,j),node(i,j+1));
}
}
}
}
for (int i = 0;i<row;i++)
for (int j=0;j<column;j++){
if (unionFind2.isConnected(node(i,j),dummy)){
board[i][j] = 'O';
}else{
board[i][j] = 'X';
}
}
}
public int node(int i,int j){
return i*column +j;
}
}
