03-并查集应用-二叉树任意两节点寻找最近祖先-子矩阵最大累加和
2019-08-04 本文已影响0人
囧么肥事
年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：岛问题和并查集
实例2：并查集应用-二叉树任意两节点寻找最近祖先
实例3：子矩阵最大累加和
实例1：岛问题和并查集
岛问题和并查集的基本知识，已经在简书中记录过。
原文：https://www.jianshu.com/p/98ceadaf039a
实例2：并查集应用-二叉树任意两节点寻找最近祖先
如下的Node类是标准的二叉树节点结构:
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
再定义Query类如下:
public static class Query {
public Node o1;
public Node o2;
public Query(Node o1, Node o2) {
this.o1 = o1;
this.o2 = o2;
}
}
一个Query类的实例表示一条查询语句,表示想要查询01节点和02节点的最近公共祖先节点.
给定一棵二叉树的头节点head,并给定所有的查询语句,即一个Query类型的数组 Queryl ques,
请返回Node类型的数组Node[] ans,
ans[j]代表ques[j]这条查询的答案,即 ques[i].01和ques[j].02的最近公共祖先
【要求】
如果二叉树的节点数为N,查询语句的条数为M,整个处理过程的时间复杂度要求达到O(N+M).
1、将所有的请求都存储进哈希表，同时存储进每一个请求的反请求。
另外一个indexMap 来存储请求和反请求对应的是第几个请求
一个请求 (4,9)
同时在哈希表中存进这个请求和反请求
(4,9) (9,4)
再看indexMap
假设有：(2,3) (5,1) (4,9) (7,2)
只有是同一个请求，无论是反请求还是原请求，都记录相同的index，如(4,9) ,存的都是2号请求。
这是一个二叉树，当遍历大4 的时候，9还未出现，那么就暂时放弃(4,9)请求，等遍历到9时进行(9,4)的请求。
2、排除一些可以直接给定查询答案的query
if (o1 == o2 || o1 == null || o2 == null) {
ans[i] = o1 != null ? o1 : o2;
}
query的o1 或者 o2 为空，或者都为空处理
3、并查集处理祖先
2_1_并查集查找设置祖先节点.png
import java.util.HashMap;
import java.util.LinkedList;
/**
* @description: 并查集应用-二叉树任意两个节点寻找最近祖先
*/
public class Code_08_TarjanAndUnionSetsForQueryTreeNodeAncestorNode {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class Query {
public Node o1;
public Node o2;
public Query(Node o1, Node o2) {
this.o1 = o1;
this.o2 = o2;
}
}
// 主函数
public static Node[] tarJanQuery(Node head, Query[] quries) {
Node[] ans = new Tarjan().query(head, quries);
return ans;
}
// Tarjan算法实现处理流程
public static class Tarjan {
private HashMap<Node, LinkedList<Node>> queryMap; // 所有的查询，如与4有关的查询(4,8),(4,7)
private HashMap<Node, LinkedList<Integer>> indexMap; // 结果应该存储在返回数组中的位置，即标识是第几个查询
// 祖先集 key: 当前并查集的代表节点 value：代表节点的祖先节点
// 存储所有节点所在的并查集的代表节点，和对应的祖先节点
private HashMap<Node, Node> ancestorMap;
private UnionSets sets; // 并查集
public Tarjan() {
queryMap = new HashMap<>();
indexMap = new HashMap<>();
ancestorMap = new HashMap<>();
sets = new UnionSets();
}
public Node[] query(Node head, Query[] ques) {
Node[] ans = new Node[ques.length]; // 结果数组
setQueries(ques, ans);
sets.makeSets(head);
setAnswers(head, ans);
return ans;
}
// 初始化查询，将查询放入查询集合中，同时存放反向查询
public void setQueries(Query[] queries, Node[] ans) {
Node o1 = null; // 一个查询要查的两个点
Node o2 = null;
for (int i = 0; i < ans.length; i++) {
o1 = queries[i].o1;
o2 = queries[i].o2;
// 排除一些可以直接给定查询答案的query
if (o1 == o2 || o1 == null || o2 == null) {
ans[i] = o1 != null ? o1 : o2;
}
if (!queryMap.containsKey(o1)) { // 原查询初始化
queryMap.put(o1, new LinkedList<>());
indexMap.put(o1, new LinkedList<>());
}
if (!queryMap.containsKey(o2)) { // 反向查询初始化
queryMap.put(o2, new LinkedList<Node>());
indexMap.put(o2, new LinkedList<Integer>());
}
queryMap.get(o1).add(o2);
indexMap.get(o1).add(i); // 结果应该保存到哪个位置
queryMap.get(o2).add(o1); // 增加一个反查询，为了方便找答案
indexMap.get(o2).add(i); // 因为实际上都是一个查询，放在相同位置
}
}
// 递归遍历每一个节点，然后查询
private void setAnswers(Node head, Node[] ans) {
if (head == null) return;
// 左 右
ancestorMap.put(sets.findFather(head), head); // 设置当前并查集的代表节点的祖先节点为当前节点
setAnswers(head.right, ans); // 同理右边部分
sets.union(head.right, head);
LinkedList<Node> nList = queryMap.get(head); // 取出当前节点的所有查询
// 如：当前节点是4 和它有关的查询 (4,6) (4,9) 返回的是{6, 9}
LinkedList<Integer> iList = indexMap.get(head);
int index = 0;
Node node = null;
Node nodeFather = null;
while (nList != null && !nList.isEmpty()) { // 当前查询集不为空
node = nList.poll(); // 弹出的是6 --> (4,6) 查询
index = iList.poll();
nodeFather = sets.fatherMap.get(node);// 找到 6 所在的并查集代表节点
if (ancestorMap.containsKey(nodeFather)) {
// 祖先集中是否存在代表节点的祖先节点
// 这里可以解释前面为什么要添加反向查询，因为有些查询在查询
ans[index] = ancestorMap.get(nodeFather);
}
}
}
}
// 实现Tarjan类中使用的并查集结构
public static class UnionSets {
public HashMap<Node, Node> fatherMap;
public HashMap<Node, Integer> rankMap;
public UnionSets() {
fatherMap = new HashMap<>(); // (B,A)
rankMap = new HashMap<>();
}
public void makeSets(Node head) {
fatherMap.clear();
rankMap.clear();
preOrderMake(head);
}
private void preOrderMake(Node head) {
if (head == null) {
return;
}
fatherMap.put(head, head);
rankMap.put(head, 0);
preOrderMake(head.left);
preOrderMake(head.right);
}
public Node findFather(Node n) {
Node father = fatherMap.get(n);
if (father != n) {
father = findFather(father);
}
fatherMap.put(n, father);
return father;
}
public void union(Node a, Node b) {
if (a == null || b == null) {
return;
}
Node aFather = findFather(a);
Node bFather = findFather(b);
if (aFather != bFather) {
int aFrank = rankMap.get(aFather);
int bFrank = rankMap.get(bFather);
if (aFrank < bFrank) {
fatherMap.put(aFather, bFather);
} else if (aFrank > bFrank) {
fatherMap.put(bFather, aFather);
} else {
fatherMap.put(bFather, aFather);
rankMap.put(aFather, aFrank + 1);
}
}
}
}
public static class ForTest {
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
head.right.right.left = new Node(8);
printTree(head);
System.out.println("===============");
// 生成查询数组
Query[] qs = new Query[7];
qs[0] = new Query(head.left.right, head.right.left);
qs[1] = new Query(head.left.left, head.left);
qs[2] = new Query(head.right.left, head.right.right.left);
qs[3] = new Query(head.left.left, head.right.right);
qs[4] = new Query(head.right.right, head.right.right.left);
qs[5] = new Query(head, head);
qs[6] = new Query(head.left, head.right.right.left);
// Tarjan算法结合并查集解决所有查询问题
Node[] ans = tarJanQuery(head, qs);
// 打印答案
for (int i = 0; i != ans.length; i++) {
System.out.println("o1 : " + qs[i].o1.value);
System.out.println("o2 : " + qs[i].o2.value);
System.out.println("ancestor : " + ans[i].value);
System.out.println("===============");
}
}
}
}
实例3：子矩阵最大累加和
给定一个矩阵matrix,其中的值有正、有负、有0,返回子矩阵的最大累加和。
例如,矩阵matrix为:
-90 48 78
64-40 64
-81 -7 66
其中,最大累加和的子矩阵为:
48 78
-40 64
-7 66
所以返回累加和209.
例如, matrix为:
-1 -1 -1
-1 2 2
-1 -1 -1
其中,最大累加和的子矩阵为:
2 2
所以返回累加和4.
矩阵常识
1、一个N * N 矩阵可以构成的子矩阵约为 N的4次方
- 选择两个点构成矩阵
- 左上角选点 (C(N,1), C(N,1)) 都是从 N 选择一个，所以是 N的二次方，同理右下角 N的2次方
2、一个N * N 矩阵可以构成的正方形子矩阵约为N的3次方
- 任意从左上角选择开始点：N的二次方
- 正方形的边长 1、2、3.... N 共有N种
思路：
开始之前先看一下之前针对数组中求得最大累加和的问题
https://www.jianshu.com/p/a1ce2907220e 过程在实例3。
- 如果ar中没有正数,产生的最大累加和一定是数组中的最大值。
- 如果arr中有正数,从左到右遍历arr,用变量cur记录每一步的累加和,遍历到正数 cur增加,遍历到负数cur减少。当curk < 0时,说明累加到当前数出现了小于0的结果,那么累加的这一部分肯定不能作为产生最大累加和的子数组的左边部分,此时令cur = 0,表示重新从下一个数开始累加。当cur>= 0时,每一次累加都可能是最大的累加和,所以,用另外一个变量max全程跟踪记录cur出现的最大值即可。
矩阵求解
将矩阵化为数组求取子数组对大累加和问题。
假设一个 2 * 4 的矩阵
-2 3 -5 7
1 4 -1 -3
如何求必须含有2行元素的子矩阵中的最大累加和?
可以把两列的元素累加,然后得到累加数组[-1,7-6,4],
接下来求这个累加数组的最大累加和,结果是7,也就是说,必须含有2行元素的子矩阵中的最大和为7.
矩阵关键
- 用求累加数组的最大累加和的方式得到每一步的最大子矩阵的累加和。
- 每一步的累加数组可以利用前一步求出的累加数组很方便地更新得到。
- 如果矩阵大小为MxN的,以上全部过程的时间复杂度为 O(M^2 * N)
public class Code_09_SubMatrixMaxSum {
public static int maxSum(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
int[] helpArr = null; // 累加数组
for (int i = 0; i < m.length; i++) { // 0 ~ N-1
helpArr = new int[m[0].length];
for (int j = i; j <m.length; j++) { // i ~ N-1
cur = 0;
for (int k = 0; k < helpArr.length; k++) {
helpArr[k] += m[j][k]; // 累加数组为新数组
cur += helpArr[k];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
}
}
return max;
}
public static void main(String[] args) {
int[][] matrix = {{-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}};
System.out.println(maxSum(matrix));
}
}
