左神算法初级班第七节

1. 并查集结构
2. 岛问题
3. 何为前缀树？如何生成前缀树？
4. 贪心策略
   （from左神算法初级班第七节）

1.并查集结构

优点（两个功能非常快）：

• 1）查询两个元素是否是一个集合
• 2）两个各自所在的集合合并成一个集合
  list和set无法在很低的时间复杂度下完成。

1）查询两个元素是否是一个结合？

• 每个结合的第一个节点有一个指针指会自己（代表节点）
• 每个节点指向父节点
• 查询两个元素是否是一个集合，向上找到两个元素的代表节点(头结点），如果两个代表节点是同一节点，则两个元素在同一个集合中。
  

2）两个各自所在的集合合并成一个集合

• 那个集合少就挂到多的集合的底下。

3）优化：

• 查询操作后，将查询路径打平（如图）。
  

4）代码：

public static class UnionFindSet {public HashMap<Node, Node> fatherMap;//key：child，value：父节点。查找节点的父节点public HashMap<Node, Integer> sizeMap;//某一个节点所在的集合有多少节点public UnionFindSet(List<Node> nodes) {makeSet(nodes);}public void makeSets(List<Node> nodes) {fatherMap = new HashMap<Node, Node>();sizeMap = new HashMap<Node, Integer>();fatherMap.clear();sizeMap.clear();for (Node node : nodes) {fatherMap.put(node, node);//每一个node形成一个集合sizeMap.put(node, 1);//每个节点添加大小}}private Node findHead(Node node) {//方法一用递归找代表节点，变扁平结构Node father = fatherMap.get(node);if (father != node) {//拿到头结点father = findHead(father);}fatherMap.put(node, father);//将每个节点的father节点都设置为头结点return father;}private Node findHead2(Node node) {//方法二使用栈结构实现变偏平结构Stack<Node> stack = new Stack<Node>();Node cur = node;Node parent = fatherMap.get(cur);while(cur!=parent) {stack.push(cur);cur = parent;parent = fatherMap.get(cur);}while(!stack.isEmpty()) {fatherMap.put(stack.pop(),parent);}return parent;}public boolean isSameSet(Node a, Node b) {return findHead(a) == findHead(b);//查询代表节点是否为同一节点（是，则在同一个集合中，否则，则不是在同一个集合中}public void union(Node a, Node b) {if (a == null || b == null) {return;}Node aHead = findHead(a);Node bHead = findHead(b);if (aHead != bHead) {int aSetSize= sizeMap.get(aHead);//拿sizeint bSetSize = sizeMap.get(bHead);if (aSetSize <= bSetSize) {//比较两个集合的size大小，小的挂到大的集合底下fatherMap.put(aHead, bHead);sizeMap.put(bHead, aSetSize + bSetSize);} else {fatherMap.put(bHead, aHead);sizeMap.put(aHead, aSetSize + bSetSize);}}}}

2.岛问题

问题：一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个 矩阵中有多少个岛？
举例：
0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
这个矩阵中有三个岛。

方法：

• 遇到1，进入感染方法，感染其上下左右的1，将附近的1改成2。
• 遇到0或者2直接跳过。
• 记录遇到1的次数

代码：

public static int countIslands(int[][] m) {if (m == null || m[0] == null) {return 0;}int N = m.length;int M = m[0].length;int res = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (m[i][j] == 1) {res++;infect(m, i, j, N, M);//遇到1，进入感染方法中}}}return res;}public static void infect(int[][] m, int i, int j, int N, int M) {//感染方法，将上下左右的1，感染成2if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {//碰到边界，如果是0或者2，感染停止return;}m[i][j] = 2;//将本来的位置感染成2infect(m, i + 1, j, N, M);//去感染上下左右的1infect(m, i - 1, j, N, M);infect(m, i, j + 1, N, M);infect(m, i, j - 1, N, M);}

进阶问题：多个CPU如何快速解决？
一个矩阵拆成两块，感染后合并成一个。

• 保留信息，每个被感染的感染中心和矩阵的边界
• 当合并时，查找两个边界的集合是否是同一集合，不是的话，size-1，并且将两个集合合并（并查集）
• 如果是同一集合则跳过。

合并示意图：

3.何为前缀树？如何生成前缀树？

1）什么是前缀树？

2）生成前缀树

• 查询子字符串
• 查询以某字符串结尾的字符串，以及加了几次。
• 给定一个字符串，查有多少字符串以其为前缀

public class Code_01_TrieTree {public static class TrieNode {public int path;public int end;//标记有多少是以该位置结束的字符串public TrieNode[] nexts;public TrieNode() {path = 0;end = 0;nexts = new TrieNode[26];//1个节点有26条路}}public static class Trie {private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {//前缀树if (word == null) {return;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {//a~z条路，找到相应的路加进去index = chs[i] - 'a';if (node.nexts[index] == null) {//有没有走向当前字符的路？node.nexts[index] = new TrieNode();//没有就建立出来}node = node.nexts[index];node.path++;//增加,路过+1}node.end++;//标记有条路在这结尾}public void delete(String word) {if (search(word) != 0) {char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {//找到这条路index = chs[i] - 'a';if (--node.nexts[index].path == 0) {//没有这条路，所以没有这个字符串node.nexts[index] = null;return;}node = node.nexts[index];//向下走}node.end--;//删除其结尾。}}public int search(String word) {if (word == null) {return 0;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];//找到最后节点}return node.end;//返回以这个节点结束的字符串有几个}public int prefixNumber(String pre) {if (pre == null) {return 0;}char[] chs = pre.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {//查找到底index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.path;//返回有多少以这个节点为前缀的字符串}}
public static void main(String[] args) {Trie trie = new Trie();System.out.println(trie.search("zuo"));trie.insert("zuo");System.out.println(trie.search("zuo"));trie.delete("zuo");System.out.println(trie.search("zuo"));trie.insert("zuo");trie.insert("zuo");trie.delete("zuo");System.out.println(trie.search("zuo"));trie.delete("zuo");System.out.println(trie.search("zuo"));trie.insert("zuoa");trie.insert("zuoac");trie.insert("zuoab");trie.insert("zuoad");trie.delete("zuoa");System.out.println(trie.search("zuoa"));System.out.println(trie.prefixNumber("zuo"));}
}

4.贪心策略

问题：给定一个字符串数组，把所有字符串拼接起来，得到最小序或者拼出最小序。（本题目只是贪心策略中的比较策略）
例如：[“abc”，“b”，“cd”]

贪心策略：定一个指标，把每个指标分出优先顺序。（有很多种优先策略）

• 策略要求传递性

1）字典序（其中一种比较排序策略）：
原则：

• 长度相同时，直接从头开始比较
• 长度不相等时，将短的字符串补0或者其他，补齐长度再进行比较

2）按照某种策略来比较排序（使用比较器）：

import java.util.Arrays;
import java.util.Comparator;public class Code_05_LowestLexicography {public static class MyComparator implements Comparator<String> {@Overridepublic int compare(String a, String b) {//比较原则return (a + b).compareTo(b + a);}}public static String lowestString(String[] strs) {if (strs == null || strs.length == 0) {return "";}Arrays.sort(strs, new MyComparator());String res = "";for (int i = 0; i < strs.length; i++) {res += strs[i];}return res;}public static void main(String[] args) {String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };System.out.println(lowestString(strs1));String[] strs2 = { "ba", "b" };System.out.println(lowestString(strs2));}
}