算法学习-基础数据结构

基础数据结构

一.栈

1.普通栈

套路：从前往后遍历 + 需要考虑相邻元素 + 有消除操作 = 栈。

2.单调栈

二.队列

1.普通队列

2.优先队列

三.Trie

使用场景：可以求某个字符串在众多字符串中出现的次数，以某个字符串为前缀出现的次数
Trie中，Trie数组是必须得，其他的根据业务场景决定(如：isEnd，count等)

模版1

class Trie {Trie[] children;boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(char c : word.toCharArray()){int index = c - 'a';if(node.children[index]==null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {Trie node = this;for(char c : word.toCharArray()){int index = c - 'a';if(node.children[index]==null){return false;}node = node.children[index];}return node.isEnd;}public boolean startsWith(String prefix) {Trie node = this;for(char c : prefix.toCharArray()){int index = c - 'a';if(node.children[index]==null){return false;}node = node.children[index];}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);*/

模版2

class Trie {Trie[] child = new Trie[26];int ref = -1;void insert(String word, int ref) {Trie node = this;for (char c : word.toCharArray()) {int index = c - 'a';if (node.child[index] == null) {node.child[index] = new Trie();}node = node.child[index];}node.ref = ref;}int search(String word) {Trie node = this;for (char c : word.toCharArray()) {int index = c - 'a';if (node.child[index] == null) {return -1;}node = node.child[index];//注意：判断都是在node = node.child[index];之后判断if (node.ref != -1) {return node.ref;}}return -1;}}

LeetCode例题

四.并查集

1.逆序思维，删除–合并
2.传递性

1.普通并查集

class UF{int[] parent;int[] size;int count ;UF(int n){parent = new int[n];size = new int[n];count = n;for(int i = 0;i<n;i++){parent[i] = i;size[i] = 1;}}void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP==rootQ){return;}if(size[rootP]>size[rootQ]){parent[rootQ] = rootP;size[rootP] += size[rootQ];}else{parent[rootP] = rootQ;size[rootQ] += size[rootP];}count--;}int find(int x){if(parent[x]!=x){parent[x] = find(parent[x]);}return parent[x];}boolean connect(int p,int q){return find(p)==find(q);}int size(int x){return size[x];}int count(){return count;}
}

2.map实现并查集

LeetCode例题

class Solution {public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {UF uf = new UF();for(List<String> str : similarPairs){uf.union(str.get(0),str.get(1));}int m = sentence1.length;int n = sentence2.length;if(m!=n){return false;}for(int i = 0;i<n;i++){if(!uf.connected(sentence1[i],sentence2[i])){return false;}}return true;}
}class UF{HashMap<String,String> map = new HashMap<>();void union(String p,String q){String rootP = find(p);String rootQ = find(q);if(!rootP.equals(rootQ)){map.put(rootP,rootQ);}}boolean connected(String p,String q){return find(p).equals(find(q));}String find(String x){while(map.containsKey(x)&&map.get(x)!=x){x = map.get(x);}return x;}
}

3.并查集结合map记录父结点信息

LeetCode例题

class Solution {public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {int n = s.length();UF uf = new UF(n);for(List<Integer> list : pairs){uf.union(list.get(0),list.get(1));}HashMap<Integer,PriorityQueue<Character>> map = new HashMap<>();for(int i = 0;i<n;i++){int j = uf.find(i);map.computeIfAbsent(j,k->new PriorityQueue<>()).offer(s.charAt(i));}StringBuilder sb = new StringBuilder();for(int i = 0;i<n;i++){PriorityQueue<Character> q = map.get(uf.find(i));sb.append(q.poll());}return sb.toString();}
}class UF{int[] parent;UF(int n){parent = new int[n];for(int i = 0;i<n;i++){parent[i] = i;}}void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP==rootQ){return;}parent[rootP] = rootQ;}int find(int x){if(x!=parent[x]){parent[x] = find(parent[x]);}return parent[x];}
}

4.公因数并查集

LeetCode例题

class Solution {public boolean canTraverseAllPairs(int[] nums) {UF uf = new UF(100001);if(nums.length==1){return true;}for(int num : nums){if(num==1){return false;}int t = num;for(int i = 2;i*i<=num;i++){if(num%i==0){uf.union(t,i);while(num%i==0){num /= i;}}if(num>1){uf.union(t,num);}}}int r = uf.find(nums[0]);for(int num : nums){if(uf.find(num)!=r){return false;}}return true;}
}class UF{int[] parent;UF(int n){parent = new int[n];for(int i = 0;i<n;i++){parent[i] = i;}}void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP==rootQ){return;}parent[rootP] = rootQ;}int find(int x){if(x!=parent[x]){parent[x] = find(parent[x]);}return parent[x];}
}

LeetCode3和4综合练习题

5.边权并查集

LeetCode例题

class Solution {public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {int n = equations.size();UF uf = new UF(2 * n);HashMap<String, Integer> map = new HashMap<>();int id = 0;for (int i = 0; i < n; i++) {List<String> equation = equations.get(i);String val1 = equation.get(0);String val2 = equation.get(1);if (!map.containsKey(val1)) {map.put(val1, id);id++;}if (!map.containsKey(val2)) {map.put(val2, id);id++;}uf.union(map.get(val1), map.get(val2), values[i]);}int queriesSize = queries.size();double[] res = new double[queriesSize];for (int i = 0; i < queriesSize; i++) {String val1 = queries.get(i).get(0);String val2 = queries.get(i).get(1);Integer id1 = map.get(val1);Integer id2 = map.get(val2);if (id1 == null || id2 == null) {res[i] = -1.0;} else {res[i] = uf.isConnected(id1, id2);}}return res;}
}class UF {int[] parent;double[] weight;UF(int n) {parent = new int[n];weight = new double[n];for (int i = 0; i < n; i++) {parent[i] = i;weight[i] = 1.0;}}void union(int p, int q, double value) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ) {return;}parent[rootP] = rootQ;weight[rootP] = weight[q] * value / weight[p];}int find(int x) {if (x != parent[x]) {int origin = parent[x];parent[x] = find(parent[x]);weight[x] *= weight[origin];}return parent[x];}double isConnected(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ) {return weight[p] / weight[q];}return -1.0;}
}

相关题目：
1.LeetCode
2.LeetCode
3.LeetCode