有N个人，要将他们分成两组，然后一个二维int数组dislikes表示哪些人不能
放在一起，问最后能否分组成功。
思路：邻接表+染色法
建邻接表，将每个人及其排斥的人做一个一对多的关系表。可以把每个dislike看做一条边，这样每条边端点的两个人是不能在一起的。
使用染色法，使用一个一维的 colors 数组，大小为 N+1，初始化是0，由于只有两组，可以用1和 -1 来区分。那么开始遍历图中的结点，对于每个遍历到的结点，如果其还未被染色，对其用颜色1进行尝试染色，然后遍历所有与它不合的人，检查这些人的染色情况，如果染色相同，说明在同一个集合里了，不合题意，返回false；如果还未染色，用相反的颜色-1给它染色。
时间复杂度：O(N+E), E = dislikes.length，空间复杂度：O(N)。
1class Solution {
2 public boolean possibleBipartition(int N, int[][] dislikes) {
3 // 建立一个一对多的关系
4 Map<Integer, Set<Integer>> graph = new HashMap<>();
5 for(int [] d : dislikes){
6 // 不存在的时候才创建新的HashSet。同时放第一个元素和第二个元素，最后每个人都能对应一个set
7 graph.putIfAbsent(d[0], new HashSet<Integer>());
8 graph.putIfAbsent(d[1], new HashSet<Integer>());
9
10 graph.get(d[0]).add(d[1]);
11 graph.get(d[1]).add(d[0]);
12 }
13
14 int [] color = new int[N + 1];
15 for(int i = 1; i <= N; i++){ // 遍历N个人
16 if(color[i] == 0 && graph.containsKey(i)){
17 color[i] = 1; // 染色
18 LinkedList<Integer> que = new LinkedList<>();
19 que.add(i);
20 while(!que.isEmpty()){ // 找与i排斥的人
21 int cur = que.poll();
22 for(int nei : graph.get(cur)){
23 if(color[nei] == 0){ // 未染色的
24 color[nei] = -color[cur];// 将其赋值为当前的相反数
25 que.add(nei);
26 }else if(color[nei] == color[cur]){
27 return false;
28 }
29 }‘
30 }
31 }
32 }
33 return true;
34 }
35}
889. Construct Binary Tree from Preorder and Postorder Traversal
根据前序和后序序列重建树，并且树的结点的值是唯一的，都是正整数。
思路：用递归
1. 前序序列的第一个数是树的根节点，后序序列的最后一个点是根节点；
2. 前序序列的根节点右边的点是左子树的根节点，也就是第二个点；
3. 后序序列的根节点左边的点的右子树的根节点，也就是倒数第二个点；
4. 根据pre找到的左子树根节点，从后往前遍历后序序列post，在post中找出相同的点，然后可以将post一分为二，左边是左子树，右边是左右子树，然后得出左子树的长度，在pre中找到左子树的右边界；
5. 递归/拆分/缩小范围。
时间复杂度：O(N²)，空间复杂度：O(N)。
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10class Solution {
11 public TreeNode constructFromPrePost(int[] pre, int[] post) {
12 return constructFromPreAndPost(pre, 0, pre.length - 1, post, 0, post.length - 1);
13 }
14
15 private TreeNode constructFromPreAndPost(int[] pre, int preLeft, int preRight, int[] post, int postLeft, int postRight){
16 if(preLeft > preRight || postLeft > postRight){
17 return null;
18 }else if(preLeft == preRight){
19 return new TreeNode(pre[preLeft]);
20 }
21 TreeNode root = new TreeNode(pre[preLeft]);
22 for(int i = postRight - 1; i >= postLeft; i--){//从后往前遍历后序序列
23 if(post[i] == pre[preLeft + 1]){//前序序列根节点后面的是左子树的根节点
24 root.left = constructFromPreAndPost(pre, preLeft + 1, preLeft + 1 + i - postLeft, post, postLeft, i);//减掉根节点后，preLeft+1~x的元素和postLeft~i的元素和个数都是一样的，都是左子树的元素值，所以左子树在前序序列的右边是preLeft+1+i-postLeft
25 root.right = constructFromPreAndPost(pre, preLeft + 2 + i - postLeft, preRight, post, i + 1, postRight - 1);//后序序列的根节点前面的一个是右子树的根节点,i + 1 ~postRight - 1是右子树，然后在前序序列里，左边是
26 }
27 // 若不满足上面的if, i往左继续一步步走，知道满足if的条件。
28 }
29 return root;
30 }
31}
890. Find and Replace Pattern
给一个字符串数组words和一个字符串pattern，且 pattern.length = words[i].length，让找出words中和pattern队列一样的字符串集合，如"abb", "mee", "aqq"是队形一样的字符串
思路：做法有一点巧妙。
首先写一个方法，传入一个字符串参数，将其字符和对应的index存入HashMap, 然后用一个int数组posArr来存位置，关键在于，这个key在Map里存在才存，不存在的话直接取出来保存入posArr，为什么说关键呢，因为如果一个字符串里用相同的字符，那么取出的index是相同的，都是这个字符第一次出现的位置，这样的话就能在这个数组记录了相同的字符，也是posArr里值相同的都表示同一个字符。也就是说abb和mee得到的posArr是一样的，都是{0, 1, 1}，这样我们就能得出哪些字符串和pattern是排列形式相同的。
时间复杂度：O(N*K)，N= words.length, K=pattern.length()。
空间复杂度：O(N)。
1class Solution {
2 public List<String> findAndReplacePattern(String[] words, String pattern) {
3 int[] patternPos = getStrPos(pattern);// 先得到pattern的位置数组，pattern="abb"的话，patternPos={0,1,1};
4 List<String> retList = new ArrayList<>();
5 for (String word : words) { // 遍历words，分别将word转成pos数组，然后一一和pattern的位置数组比
6 if (Arrays.equals(getStrPos(word), patternPos)) {// 如两数组相等
7 retList.add(word);
8 }
9 }
10 return retList;
11 }
12
13 private int[] getStrPos(String str) {// 将字符串转成位置数组
14 Map<Character, Integer> posMap = new HashMap<>();
15 char[] arr = str.toCharArray();
16 int[] posArr = new int[arr.length];
17 for (int i = 0; i < arr.length; i++) {
18 posMap.putIfAbsent(arr[i], i);
19 posArr[i] = posMap.get(arr[i]);// 关键！根据字符反找位置
20 }
21 return posArr;
22 }
23}
