03-并查集應(yīng)用-二叉樹任意兩節(jié)點(diǎn)尋找最近祖先-子矩陣最大累加和

年輕即出發(fā)...

簡書：http://www.itdecent.cn/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源碼：https://github.com/zqtao2332

個(gè)人網(wǎng)站：http://www.zqtaotao.cn/ （停止維護(hù)更新內(nèi)容）

QQ交流群：606939954

? 咆哮怪獸一枚...嗷嗷嗷...趁你現(xiàn)在還有時(shí)間，盡你自己最大的努力。努力做成你最想做的那件事，成為你最想成為的那種人，過著你最想過的那種生活。也許我們始終都只是一個(gè)小人物，但這并不妨礙我們選擇用什么樣的方式活下去，這個(gè)世界永遠(yuǎn)比你想的要更精彩。

最后：喜歡編程，對生活充滿激情

本節(jié)內(nèi)容預(yù)告

實(shí)例1：島問題和并查集

實(shí)例2：并查集應(yīng)用-二叉樹任意兩節(jié)點(diǎn)尋找最近祖先

實(shí)例3：子矩陣最大累加和

實(shí)例1：島問題和并查集

島問題和并查集的基本知識，已經(jīng)在簡書中記錄過。

原文：http://www.itdecent.cn/p/98ceadaf039a

實(shí)例2：并查集應(yīng)用-二叉樹任意兩節(jié)點(diǎn)尋找最近祖先

如下的Node類是標(biāo)準(zhǔn)的二叉樹節(jié)點(diǎn)結(jié)構(gòu):

    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;
        }
    }

一個(gè)Query類的實(shí)例表示一條查詢語句,表示想要查詢01節(jié)點(diǎn)和02節(jié)點(diǎn)的最近公共祖先節(jié)點(diǎn).

給定一棵二叉樹的頭節(jié)點(diǎn)head,并給定所有的查詢語句,即一個(gè)Query類型的數(shù)組 Queryl ques,

請返回Node類型的數(shù)組Node[] ans,

ans[j]代表ques[j]這條查詢的答案,即 ques[i].01和ques[j].02的最近公共祖先

【要求】

如果二叉樹的節(jié)點(diǎn)數(shù)為N,查詢語句的條數(shù)為M,整個(gè)處理過程的時(shí)間復(fù)雜度要求達(dá)到O(N+M).

1、將所有的請求都存儲進(jìn)哈希表，同時(shí)存儲進(jìn)每一個(gè)請求的反請求。

另外一個(gè)indexMap 來存儲請求和反請求對應(yīng)的是第幾個(gè)請求

一個(gè)請求 (4,9) 
同時(shí)在哈希表中存進(jìn)這個(gè)請求和反請求
(4,9)     (9,4)

再看indexMap
假設(shè)有：(2,3)  (5,1)  (4,9)  (7,2)

只有是同一個(gè)請求，無論是反請求還是原請求，都記錄相同的index，如(4,9) ,存的都是2號請求。


這是一個(gè)二叉樹，當(dāng)遍歷大4 的時(shí)候，9還未出現(xiàn)，那么就暫時(shí)放棄(4,9)請求，等遍歷到9時(shí)進(jìn)行(9,4)的請求。

2、排除一些可以直接給定查詢答案的query

  if (o1 == o2 || o1 == null || o2 == null) {
        ans[i] = o1 != null ? o1 : o2;
  }
  
  query的o1 或者 o2 為空，或者都為空處理

3、并查集處理祖先

2_1_并查集查找設(shè)置祖先節(jié)點(diǎn).png
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @description: 并查集應(yīng)用-二叉樹任意兩個(gè)節(jié)點(diǎn)尋找最近祖先
 */
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;
        }
    }

    // 主函數(shù)
    public static Node[] tarJanQuery(Node head, Query[] quries) {
        Node[] ans = new Tarjan().query(head, quries);
        return ans;
    }

    // Tarjan算法實(shí)現(xiàn)處理流程
    public static class Tarjan {
        private HashMap<Node, LinkedList<Node>> queryMap; // 所有的查詢，如與4有關(guān)的查詢(4,8),(4,7)
        private HashMap<Node, LinkedList<Integer>> indexMap; // 結(jié)果應(yīng)該存儲在返回?cái)?shù)組中的位置，即標(biāo)識是第幾個(gè)查詢

        // 祖先集 key: 當(dāng)前并查集的代表節(jié)點(diǎn) value：代表節(jié)點(diǎn)的祖先節(jié)點(diǎn)
        // 存儲所有節(jié)點(diǎn)所在的并查集的代表節(jié)點(diǎn)，和對應(yīng)的祖先節(jié)點(diǎn)
        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]; // 結(jié)果數(shù)組
            setQueries(ques, ans);

            sets.makeSets(head);

            setAnswers(head, ans);

            return ans;
        }

        // 初始化查詢，將查詢放入查詢集合中，同時(shí)存放反向查詢
        public void setQueries(Query[] queries, Node[] ans) {
            Node o1 = null; // 一個(gè)查詢要查的兩個(gè)點(diǎn)
            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); // 結(jié)果應(yīng)該保存到哪個(gè)位置

                queryMap.get(o2).add(o1); // 增加一個(gè)反查詢，為了方便找答案
                indexMap.get(o2).add(i); // 因?yàn)閷?shí)際上都是一個(gè)查詢，放在相同位置
            }
        }

        // 遞歸遍歷每一個(gè)節(jié)點(diǎn)，然后查詢
        private void setAnswers(Node head, Node[] ans) {
            if (head == null) return;

            // 左 右


            ancestorMap.put(sets.findFather(head), head); // 設(shè)置當(dāng)前并查集的代表節(jié)點(diǎn)的祖先節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)

            setAnswers(head.right, ans); // 同理右邊部分
            sets.union(head.right, head);
        

            LinkedList<Node> nList = queryMap.get(head); // 取出當(dāng)前節(jié)點(diǎn)的所有查詢
            // 如：當(dāng)前節(jié)點(diǎn)是4  和它有關(guān)的查詢 (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()) { // 當(dāng)前查詢集不為空
                node = nList.poll(); // 彈出的是6 --> (4,6) 查詢
                index = iList.poll();

                nodeFather = sets.fatherMap.get(node);// 找到 6 所在的并查集代表節(jié)點(diǎn)
                if (ancestorMap.containsKey(nodeFather)) {
                    // 祖先集中是否存在代表節(jié)點(diǎn)的祖先節(jié)點(diǎn)
                    // 這里可以解釋前面為什么要添加反向查詢，因?yàn)橛行┎樵冊诓樵?                    ans[index] = ancestorMap.get(nodeFather);
                }
            }
        }
    }

    // 實(shí)現(xiàn)Tarjan類中使用的并查集結(jié)構(gòu)
    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("===============");

            // 生成查詢數(shù)組
            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算法結(jié)合并查集解決所有查詢問題
            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("===============");
            }

        }
    }
}

實(shí)例3：子矩陣最大累加和

給定一個(gè)矩陣matrix,其中的值有正、有負(fù)、有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、一個(gè)N * N 矩陣可以構(gòu)成的子矩陣約為 N的4次方

  • 選擇兩個(gè)點(diǎn)構(gòu)成矩陣
  • 左上角選點(diǎn) (C(N,1), C(N,1)) 都是從 N 選擇一個(gè)，所以是 N的二次方，同理右下角 N的2次方

2、一個(gè)N * N 矩陣可以構(gòu)成的正方形子矩陣約為N的3次方

  • 任意從左上角選擇開始點(diǎn)：N的二次方
  • 正方形的邊長 1、2、3.... N 共有N種

思路：

開始之前先看一下之前針對數(shù)組中求得最大累加和的問題

http://www.itdecent.cn/p/a1ce2907220e 過程在實(shí)例3。

  1. 如果ar中沒有正數(shù),產(chǎn)生的最大累加和一定是數(shù)組中的最大值。
  2. 如果arr中有正數(shù),從左到右遍歷arr,用變量cur記錄每一步的累加和,遍歷到正數(shù) cur增加,遍歷到負(fù)數(shù)cur減少。當(dāng)curk < 0時(shí),說明累加到當(dāng)前數(shù)出現(xiàn)了小于0的結(jié)果,那么累加的這一部分肯定不能作為產(chǎn)生最大累加和的子數(shù)組的左邊部分,此時(shí)令cur = 0,表示重新從下一個(gè)數(shù)開始累加。當(dāng)cur>= 0時(shí),每一次累加都可能是最大的累加和,所以,用另外一個(gè)變量max全程跟蹤記錄cur出現(xiàn)的最大值即可。

矩陣求解

將矩陣化為數(shù)組求取子數(shù)組對大累加和問題。

假設(shè)一個(gè) 2 * 4 的矩陣

-2 3 -5 7

1 4 -1 -3

如何求必須含有2行元素的子矩陣中的最大累加和?

可以把兩列的元素累加,然后得到累加數(shù)組[-1,7-6,4],

接下來求這個(gè)累加數(shù)組的最大累加和,結(jié)果是7,也就是說,必須含有2行元素的子矩陣中的最大和為7.

矩陣關(guān)鍵

  1. 用求累加數(shù)組的最大累加和的方式得到每一步的最大子矩陣的累加和。
  2. 每一步的累加數(shù)組可以利用前一步求出的累加數(shù)組很方便地更新得到。
  3. 如果矩陣大小為MxN的,以上全部過程的時(shí)間復(fù)雜度為 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; // 累加數(shù)組

        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]; // 累加數(shù)組為新數(shù)組
                    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));
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容