左神算法：调整搜索二叉树中两个错误的节点（Java版）

万次阅读

2020-12-22 18:23:46

本题来自左神《程序员代码面试指南》“调整搜索二叉树中两个错误的节点”题目。

题目

原问题：

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回。

已知二叉树中所有节点的值都不一样，给定二叉树的头节点 head，返回一个长度为 2 的二叉树节点类型的数组 errs，errs[0] 表示一个错误节点，errs[1] 表示另一个错误节点。

进阶问题：

如果在原问题中得到了这两个错误节点，我们当然可以通过交换两个节点的节点值的方式让整棵二叉树重新成为搜索二叉树。但现在要求你不能这么做，而是在结构上完全交换两个节点的位置，请实现调整的函数。

题解

原问题

原问题——找到这两个错误节点。

如果对所有的节点值都不一样的搜索二叉树进行中序遍历，那么出现的节点值会一直升序。因此，如果有两个节点位置错了，就一定会出现降序。

如果在中序遍历时节点值出现了 两次降序，第一个错误的节点为 第一次降序时较大的节点，第二个错误的节点为 第二次降序时较小的节点。
如果在中序遍历时节点值只出现了 一次降序，第一个错误的节点为 这次降序时较大的节点，第二个错误的节点为 这次降序时较小的节点。

所以，寻找两个错误节点的过程 可以总结为：第一个错误节点为第一次降序时较大的节点，第二个错误节点为最后一次降序时较小的节点。

因此，只要改写一个基本的 中序遍历，就可以完成原问题的要求，改写递归、非递归或者 Morris 遍历都可以。

找到两个错误节点的过程请参看如下代码中的 getTwoErrNodes 方法。

public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}
// Morris 遍历
public static Node[] getTwoErrNodes(Node head) {
    Node[] errs = new Node[2];
    if (head == null) {
        return errs;
    }
    Stack<Node> stack = new Stack<Node>();
    Node pre = null;
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        } else {
            head = stack.pop();
            if (pre != null && pre.value > head.value) {
                errs[0] = errs[0] == null ? pre : errs[0];
                errs[1] = head;
            }
            pre = head;
            head = head.right;
        }
    }
    return errs;
}

进阶问题

进阶问题——在结构上交换这两个错误节点。若要在结构上交换两个错误节点，首先应该 找到两个错误节点各自的父节点，再随便改写一个二叉树的遍历即可。

找到两个错误节点各自父节点 的过程请参看如下代码中的 getTwoErrParents 方法，该方法返回长度为 2 的 Node 类型的数组 parents，parents[0] 表示第一个错误节点的父节点，parents[1] 表示第二个错误节点的父节点。

public static Node[] getTwoErrParents(Node head, Node e1, Node e2) {
    Node[] parents = new Node[2];
    if (head == null) {
        return parents;
    }
    Stack<Node> stack = new Stack<Node>();
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        } else {
            head = stack.pop();
            if (head.left == e1 || head.right == e1) {
                parents[0] = head;
            }
            if (head.left == e2 || head.right == e2) {
                parents[1] = head;
            }
            head = head.right;
        }
    }
    return parents;
}

找到两个错误节点的父节点之后：

第一个错误节点记为 e1

e1 的父节点记为 e1P
e1 的左孩子节点记为 e1L
e1 的右孩子节点记为 e1R

第二个错误节点记为 e2

e2 的父节点记为 e2P
e2 的左孩子节点记为 e2L
e2 的右孩子节点记为 e2R

在结构上交换两个节点，实际上就是把两个节点互换环境。简单地讲，就是 让 e2 成为 e1P 的孩子节点，让 e1L 和 e1R 成为 e2 的孩子节点；让 e1 成为 e2P 的孩子节点，让 e2L 和 e2R 成为 e1 的孩子节点。

但这只是简单地理解，在实际交换的过程中有 很多情况 需要我们做特殊处理。

比如，如果 e1 是头节点，则意味着 e1P 为 null，那么让 e2 成为 e1P 的孩子节点时，关于 e1P的任何 left 指针或 right 指针操作都会发生错误，因为 e1P 为 null 则根本没有 Node 类型节点的结构。
再如，如果 e1 本身就是 e2 的左孩子节点，即 e1==e2L，那么让 e2L 成为 e1 的左孩子节点时，e1 的 left 指针将指向 e2L，将会指向自己，这会让整棵二叉树发生严重的结构错误。

换句话说，我们必须理清楚 e1 及其上下环境之间的关系，e2 及其上下环境之间的关系，以及两个环境之间是否有联系。有以下三个问题和一个特别注意是必须关注的。

问题一：e1 和e2 是否有一个是头节点？如果有，谁是头节点？
问题二：e1 和e2 是否相邻？如果相邻，谁是谁的父节点？
问题三：e1 和e2 分别是各自父节点的左孩子节点还是右孩子节点？
特别注意：因为是在中序遍历时先找到e1，后找到e2，所以e1 一定不是e2 的右孩子节点，e2 也一定不是e1 的左孩子节点。

以上三个问题与特别注意之间相互影响，情况非常复杂。经过仔细整理，共有 14 种情况，每一种情况在调整 e1 和 e2 各自的拓扑关系时都有特殊处理。

e1 是头节点，e1 是e2 的父节点，此时e2 只可能是e1 的右孩子节点。
e1 是头节点，e1 不是e2 的父节点，e2 是e2P 的左孩子节点。
e1 是头节点，e1 不是e2 的父节点，e2 是e2P 的右孩子节点。
e2 是头节点，e2 是e1 的父节点，此时e1 只可能是e2 的左孩子节点。
e2 是头节点，e2 不是e1 的父节点，e1 是e1P 的左孩子节点。
e2 是头节点，e2 不是e1 的父节点，e1 是e1P 的右孩子节点。
e1 和e2 都不是头节点，e1 是e2 的父节点，此时e2 只可能是e1 的右孩子节点，e1 是e1P 的左孩子节点。
e1 和e2 都不是头节点，e1 是e2 的父节点，此时e2 只可能是e1 的右孩子节点，e1 是e1P 的右孩子节点。
e1 和e2 都不是头节点，e2 是e1 的父节点，此时e1 只可能是e2 的左孩子节点，e2 是e2P 的左孩子节点。
e1 和e2 都不是头节点，e2 是e1 的父节点，此时e1 只可能是e2 的左孩子节点，e2 是e2P的右孩子节点。
e1 和e2 都不是头节点，谁也不是谁的父节点，e1 是e1P 的左孩子节点，e2 是e2P 的左孩子节点。
e1 和e2 都不是头节点，谁也不是谁的父节点，e1 是e1P 的左孩子节点，e2 是e2P 的右孩子节点。
e1 和e2 都不是头节点，谁也不是谁的父节点，e1 是e1P 的右孩子节点，e2 是e2P 的左孩子节点。
e1 和e2 都不是头节点，谁也不是谁的父节点，e1 是e1P 的右孩子节点，e2 是e2P 的右孩子节点。

当 情况1 至 情况3 发生时，二叉树新的头节点应该为 e2，当 情况4 至 情况6 发生时，二叉树新的头节点应该为 e1，其他情况发生时，二叉树的头节点不用发生变化。

从结构上调整两个错误节点的全部过程请参看如下代码中的 recoverTree 方法。

代码

含测试用例

package chapter_3_binarytreeproblem;

import java.util.Stack;

public class Problem_10_RecoverBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node[] getTwoErrNodes(Node head) {
        Node[] errs = new Node[2];
        if (head == null) {
            return errs;
        }
        Stack<Node> stack = new Stack<Node>();
        Node pre = null;
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if (pre != null && pre.value > head.value) {
                    errs[0] = errs[0] == null ? pre : errs[0];
                    errs[1] = head;
                }
                pre = head;
                head = head.right;
            }
        }
        return errs;
    }

    public static Node[] getTwoErrParents(Node head, Node e1, Node e2) {
        Node[] parents = new Node[2];
        if (head == null) {
            return parents;
        }
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if (head.left == e1 || head.right == e1) {
                    parents[0] = head;
                }
                if (head.left == e2 || head.right == e2) {
                    parents[1] = head;
                }
                head = head.right;
            }
        }
        return parents;
    }

    public static Node recoverTree(Node head) {
        Node[] errs = getTwoErrNodes(head);
        Node[] parents = getTwoErrParents(head, errs[0], errs[1]);
        Node e1 = errs[0];
        Node e1P = parents[0];
        Node e1L = e1.left;
        Node e1R = e1.right;
        Node e2 = errs[1];
        Node e2P = parents[1];
        Node e2L = e2.left;
        Node e2R = e2.right;
        if (e1 == head) {
            if (e1 == e2P) { // 情况一
                e1.left = e2L;
                e1.right = e2R;
                e2.right = e1;
                e2.left = e1L;
            } else if (e2P.left == e2) { // 情况二
                e2P.left = e1;
                e2.left = e1L;
                e2.right = e1R;
                e1.left = e2L;
                e1.right = e2R;
            } else { // 情况三
                e2P.right = e1;
                e2.left = e1L;
                e2.right = e1R;
                e1.left = e2L;
                e1.right = e2R;
            }
            head = e2;
        } else if (e2 == head) {
            if (e2 == e1P) { // 情况四
                e2.left = e1L;
                e2.right = e1R;
                e1.left = e2;
                e1.right = e2R;
            } else if (e1P.left == e1) { // 情况五
                e1P.left = e2;
                e1.left = e2L;
                e1.right = e2R;
                e2.left = e1L;
                e2.right = e1R;
            } else { // 情况六
                e1P.right = e2;
                e1.left = e2L;
                e1.right = e2R;
                e2.left = e1L;
                e2.right = e1R;
            }
            head = e1;
        } else {
            if (e1 == e2P) {
                if (e1P.left == e1) { // 情况七
                    e1P.left = e2;
                    e1.left = e2L;
                    e1.right = e2R;
                    e2.left = e1L;
                    e2.right = e1;
                } else { // 情况八
                    e1P.right = e2;
                    e1.left = e2L;
                    e1.right = e2R;
                    e2.left = e1L;
                    e2.right = e1;
                }
            } else if (e2 == e1P) {
                if (e2P.left == e2) { // 情况九
                    e2P.left = e1;
                    e2.left = e1L;
                    e2.right = e1R;
                    e1.left = e2;
                    e1.right = e2R;
                } else { // 情况十
                    e2P.right = e1;
                    e2.left = e1L;
                    e2.right = e1R;
                    e1.left = e2;
                    e1.right = e2R;
                }
            } else {
                if (e1P.left == e1) {
                    if (e2P.left == e2) { // 情况十一
                        e1.left = e2L;
                        e1.right = e2R;
                        e2.left = e1L;
                        e2.right = e1R;
                        e1P.left = e2;
                        e2P.left = e1;
                    } else { // 情况十二
                        e1.left = e2L;
                        e1.right = e2R;
                        e2.left = e1L;
                        e2.right = e1R;
                        e1P.left = e2;
                        e2P.right = e1;
                    }
                } else {
                    if (e2P.left == e2) { // 情况十三
                        e1.left = e2L;
                        e1.right = e2R;
                        e2.left = e1L;
                        e2.right = e1R;
                        e1P.right = e2;
                        e2P.left = e1;
                    } else { // 情况十四
                        e1.left = e2L;
                        e1.right = e2R;
                        e2.left = e1L;
                        e2.right = e1R;
                        e1P.right = e2;
                        e2P.right = e1;
                    }
                }
            }
        }
        return head;
    }

    // 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();
    }

    // for test
    public static boolean isBST(Node head) {
        if (head == null) {
            return false;
        }
        Stack<Node> stack = new Stack<Node>();
        Node pre = null;
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if (pre != null && pre.value > head.value) {
                    return false;
                }
                pre = head;
                head = head.right;
            }
        }
        return true;
    }
    // for test
    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(7);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.right.left = new Node(6);
        head.right.right = new Node(8);
        head.left.left.left = new Node(1);
        printTree(head);
        System.out.println(isBST(head));

        // 情况1, 7 -> e1, 5 -> e2
        System.out.println("situation 1");
        Node head1 = new Node(7);
        head1.left = new Node(3);
        head1.right = new Node(5);
        head1.left.left = new Node(2);
        head1.left.right = new Node(4);
        head1.right.left = new Node(6);
        head1.right.right = new Node(8);
        head1.left.left.left = new Node(1);
        printTree(head1);
        System.out.println(isBST(head1));
        Node res1 = recoverTree(head1);
        printTree(res1);
        System.out.println(isBST(res1));

        // 情况2, 6 -> e1, 5 -> e2
        System.out.println("situation 2");
        Node head2 = new Node(6);
        head2.left = new Node(3);
        head2.right = new Node(7);
        head2.left.left = new Node(2);
        head2.left.right = new Node(4);
        head2.right.left = new Node(5);
        head2.right.right = new Node(8);
        head2.left.left.left = new Node(1);
        printTree(head2);
        System.out.println(isBST(head2));
        Node res2 = recoverTree(head2);
        printTree(res2);
        System.out.println(isBST(res2));

        // 情况3, 8 -> e1, 5 -> e2
        System.out.println("situation 3");
        Node head3 = new Node(8);
        head3.left = new Node(3);
        head3.right = new Node(7);
        head3.left.left = new Node(2);
        head3.left.right = new Node(4);
        head3.right.left = new Node(6);
        head3.right.right = new Node(5);
        head3.left.left.left = new Node(1);
        printTree(head3);
        System.out.println(isBST(head3));
        Node res3 = recoverTree(head3);
        printTree(res3);
        System.out.println(isBST(res3));

        // 情况4, 5 -> e1, 3 -> e2
        System.out.println("situation 4");
        Node head4 = new Node(3);
        head4.left = new Node(5);
        head4.right = new Node(7);
        head4.left.left = new Node(2);
        head4.left.right = new Node(4);
        head4.right.left = new Node(6);
        head4.right.right = new Node(8);
        head4.left.left.left = new Node(1);
        printTree(head4);
        System.out.println(isBST(head4));
        Node res4 = recoverTree(head4);
        printTree(res4);
        System.out.println(isBST(res4));

        // 情况5, 5 -> e1, 2 -> e2
        System.out.println("situation 5");
        Node head5 = new Node(2);
        head5.left = new Node(3);
        head5.right = new Node(7);
        head5.left.left = new Node(5);
        head5.left.right = new Node(4);
        head5.right.left = new Node(6);
        head5.right.right = new Node(8);
        head5.left.left.left = new Node(1);
        printTree(head5);
        System.out.println(isBST(head5));
        Node res5 = recoverTree(head5);
        printTree(res5);
        System.out.println(isBST(res5));

        // 情况6, 5 -> e1, 4 -> e2
        System.out.println("situation 6");
        Node head6 = new Node(4);
        head6.left = new Node(3);
        head6.right = new Node(7);
        head6.left.left = new Node(2);
        head6.left.right = new Node(5);
        head6.right.left = new Node(6);
        head6.right.right = new Node(8);
        head6.left.left.left = new Node(1);
        printTree(head6);
        System.out.println(isBST(head6));
        Node res6 = recoverTree(head6);
        printTree(res6);
        System.out.println(isBST(res6));

        // 情况7, 4 -> e1, 3 -> e2
        System.out.println("situation 7");
        Node head7 = new Node(5);
        head7.left = new Node(4);
        head7.right = new Node(7);
        head7.left.left = new Node(2);
        head7.left.right = new Node(3);
        head7.right.left = new Node(6);
        head7.right.right = new Node(8);
        head7.left.left.left = new Node(1);
        printTree(head7);
        System.out.println(isBST(head7));
        Node res7 = recoverTree(head7);
        printTree(res7);
        System.out.println(isBST(res7));

        // 情况8, 8 -> e1, 7 -> e2
        System.out.println("situation 8");
        Node head8 = new Node(5);
        head8.left = new Node(3);
        head8.right = new Node(8);
        head8.left.left = new Node(2);
        head8.left.right = new Node(4);
        head8.right.left = new Node(6);
        head8.right.right = new Node(7);
        head8.left.left.left = new Node(1);
        printTree(head8);
        System.out.println(isBST(head8));
        Node res8 = recoverTree(head8);
        printTree(res8);
        System.out.println(isBST(res8));

        // 情况9, 3 -> e1, 2 -> e2
        System.out.println("situation 9");
        Node head9 = new Node(5);
        head9.left = new Node(2);
        head9.right = new Node(7);
        head9.left.left = new Node(3);
        head9.left.right = new Node(4);
        head9.right.left = new Node(6);
        head9.right.right = new Node(8);
        head9.left.left.left = new Node(1);
        printTree(head9);
        System.out.println(isBST(head9));
        Node res9 = recoverTree(head9);
        printTree(res9);
        System.out.println(isBST(res9));

        // 情况10, 7 -> e1, 6 -> e2
        System.out.println("situation 10");
        Node head10 = new Node(5);
        head10.left = new Node(3);
        head10.right = new Node(6);
        head10.left.left = new Node(2);
        head10.left.right = new Node(4);
        head10.right.left = new Node(7);
        head10.right.right = new Node(8);
        head10.left.left.left = new Node(1);
        printTree(head10);
        System.out.println(isBST(head10));
        Node res10 = recoverTree(head10);
        printTree(res10);
        System.out.println(isBST(res10));

        // 情况11, 6 -> e1, 2 -> e2
        System.out.println("situation 11");
        Node head11 = new Node(5);
        head11.left = new Node(3);
        head11.right = new Node(7);
        head11.left.left = new Node(6);
        head11.left.right = new Node(4);
        head11.right.left = new Node(2);
        head11.right.right = new Node(8);
        head11.left.left.left = new Node(1);
        printTree(head11);
        System.out.println(isBST(head11));
        Node res11 = recoverTree(head11);
        printTree(res11);
        System.out.println(isBST(res11));

        // 情况12, 8 -> e1, 2 -> e2
        System.out.println("situation 12");
        Node head12 = new Node(5);
        head12.left = new Node(3);
        head12.right = new Node(7);
        head12.left.left = new Node(8);
        head12.left.right = new Node(4);
        head12.right.left = new Node(6);
        head12.right.right = new Node(2);
        head12.left.left.left = new Node(1);
        printTree(head12);
        System.out.println(isBST(head12));
        Node res12 = recoverTree(head12);
        printTree(res12);
        System.out.println(isBST(res12));

        // 情况13, 6 -> e1, 4 -> e2
        System.out.println("situation 13");
        Node head13 = new Node(5);
        head13.left = new Node(3);
        head13.right = new Node(7);
        head13.left.left = new Node(2);
        head13.left.right = new Node(6);
        head13.right.left = new Node(4);
        head13.right.right = new Node(8);
        head13.left.left.left = new Node(1);
        printTree(head13);
        System.out.println(isBST(head13));
        Node res13 = recoverTree(head13);
        printTree(res13);
        System.out.println(isBST(res13));

        // 情况14, 8 -> e1, 4 -> e2
        System.out.println("situation 14");
        Node head14 = new Node(5);
        head14.left = new Node(3);
        head14.right = new Node(7);
        head14.left.left = new Node(2);
        head14.left.right = new Node(8);
        head14.right.left = new Node(6);
        head14.right.right = new Node(4);
        head14.left.left.left = new Node(1);
        printTree(head14);
        System.out.println(isBST(head14));
        Node res14 = recoverTree(head14);
        printTree(res14);
        System.out.println(isBST(res14));

    }
}

输出结果：

Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 1
Binary Tree:
                                         v8v       
                        v5v       
                                         ^6^       
       H7H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 2
Binary Tree:
                                         v8v       
                        v7v       
                                         ^5^       
       H6H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 3
Binary Tree:
                                         v5v       
                        v7v       
                                         ^6^       
       H8H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 4
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H3H       
                                         v4v       
                        ^5^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 5
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H2H       
                                         v4v       
                        ^3^       
                                         ^5^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 6
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H4H       
                                         v5v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 7
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v3v       
                        ^4^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 8
Binary Tree:
                                         v7v       
                        v8v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 9
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^2^       
                                         ^3^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 10
Binary Tree:
                                         v8v       
                        v6v       
                                         ^7^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 11
Binary Tree:
                                         v8v       
                        v7v       
                                         ^2^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^6^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 12
Binary Tree:
                                         v2v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^8^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 13
Binary Tree:
                                         v8v       
                        v7v       
                                         ^4^       
       H5H       
                                         v6v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true
situation 14
Binary Tree:
                                         v4v       
                        v7v       
                                         ^6^       
       H5H       
                                         v8v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

false
Binary Tree:
                                         v8v       
                        v7v       
                                         ^6^       
       H5H       
                                         v4v       
                        ^3^       
                                         ^2^       
                                                          ^1^       

true

更多相关内容

单向链表在O(1)时间内删除一个节点

千次阅读 2016-06-05 12:36:23

单向链表在O(1)时间内删除一个节点

欢迎来踩

关于留言板 - 码到城攻多数文章不支持留言，此处为统一留言处https://www.codecomeon.com/posts/1/

说删链表节点，第一时间想到就是遍历整个链表，找到删除节点的前驱，改变节点指向，删除节点，但是，这样删除单链表的某一节点，时间复杂度就是O(n),不符合要求；

时间复杂度是O(n)的做法就不说了，看看O(1)的写法，看图：

删除节点，需要找到被删节点的前驱，上面的说明，交换数据后，要删的节点转换为被删节点的后一个节点，此时被删节点前驱可以知道，删除就很简单了

给出被删节点指针，O(1)时间内就可以有此方法删除节点，但是，如果，被删节点是链表最后一个节点，以上方法明显不在适用，不得不从头遍历：

这时就得从头遍历，只为找最后一个节点的前驱，就这唯一一个节点，找它的时间复杂度就是O(n)，但平均时间复杂度为：

（（n-1）*O(1)+O(n)）/n

结果还是O(1),复合要求的，又但是，这里没有考虑要删除的节点是否在链表中，如果要判断有没有在链表中，又得遍历，结果时间复杂度有不在是O(1),

为了保证时间，被删的节点有没有在链表中，只能由人为的去控制；以下是代码段：

	//在O(1)时间内，删除一个节点，函数如下
	void DeleteNodeNumone(ListNode** phead,ListNode* pToBeDelete)
	{
		if (*phead == nullptr || pToBeDelete == nullptr)
			return;

		//删除非尾节点
		if (pToBeDelete->_next != nullptr)
		{
			ListNode* temp = pToBeDelete->_next;
			pToBeDelete->_data = temp->_data;
			pToBeDelete->_next = temp->_next;

			delete temp;
			temp = nullptr;
		}

		//只有一个节点
		else if (*phead == pToBeDelete)
		{
			delete pToBeDelete;
			pToBeDelete = nullptr;
			*phead = nullptr;
		}

		//最后一种，删除节点是尾节点
		else
		{
			ListNode* cur = *phead;
			while (cur->_next != pToBeDelete)
			{
				cur = cur->_next;
			}
			delete pToBeDelete;
			pToBeDelete = nullptr;
			cur->_next = nullptr;
		}
	}

完整测试代码：

#pragma once
typedef int DataType;

class ListNode 
{
public:
	ListNode(const DataType& x)
		:_data(x)
		, _next(NULL)
	{}

public:
	DataType _data;
	ListNode* _next;
};

class Slist
{
public:
	Slist()
		:_head(NULL)
		, _tail(NULL)
	{}
	~Slist()
	{
		//析构函数，删除节点，删除全部
		Destory();
	}

	void Destory()
	{
		ListNode* begin = _head;
		while (begin)
		{
			ListNode* del = begin;
			begin = begin->_next;
			delete del;
		}
	}

public:
	//尾插
	void PushBack(const DataType& x)
	{
		if (_head == NULL)
		{
			_head = new ListNode(x);

			_tail = _head;
		}
		else
		{
			_tail->_next = new ListNode(x);
			_tail = _tail->_next;
		}
	}

	//查找
	ListNode* Find(const DataType& x)
	{
		ListNode* tmp = _head;
		while (tmp)
		{
			if (tmp->_data == x)
				return tmp;
			else
			{
				tmp = tmp->_next;
			}
		}
		return NULL;
	}

	//

	//在O(1)时间内，删除一个节点，函数如下
	void DeleteNodeNumone(ListNode** phead,ListNode* pToBeDelete)
	{
		if (*phead == nullptr || pToBeDelete == nullptr)
			return;

		//删除非尾节点
		if (pToBeDelete->_next != nullptr)
		{
			ListNode* temp = pToBeDelete->_next;
			pToBeDelete->_data = temp->_data;
			pToBeDelete->_next = temp->_next;

			delete temp;
			temp = nullptr;
		}

		//只有一个节点
		else if (*phead == pToBeDelete)
		{
			delete pToBeDelete;
			pToBeDelete = nullptr;
			*phead = nullptr;
		}

		//最后一种，删除节点是尾节点
		else
		{
			ListNode* cur = *phead;
			while (cur->_next != pToBeDelete)
			{
				cur = cur->_next;
			}
			delete pToBeDelete;
			pToBeDelete = nullptr;
			cur->_next = nullptr;
		}
	}

	void print()
	{
		ListNode* begin = _head;
		while (begin)
		{
			cout << begin->_data << "->";
			begin = begin->_next;
		}
		cout << "NULL" << endl;
	}


public:
	ListNode* _head;
	ListNode* _tail;
};
void Test()
{
	Slist s1;
	s1.PushBack(5);
	s1.PushBack(2);
	s1.PushBack(3);
	s1.PushBack(2);
	s1.PushBack(1);
	s1.PushBack(6);
	s1.PushBack(7);
	s1.PushBack(9);
	s1.print();

	ListNode* num =s1.Find(9);

	s1.DeleteNodeNumone(&s1._head, num);

	s1.print();
}

测试结果：

赐教！

收起

展开全文

链表删除

Linux集群下各节点的时间同步
千次阅读 2018-05-18 11:39:40
所有节点不能连接外网一些命令说明： date命令： date :查看当前时间， date -s 09:38:40 :设置当前时间 ntpdate命令： ntpdate -u 210.72.145.44 :网络时间同步命令注意：若不加上-u参数，...
一般而言分三种情况：1，各节点可以连接外网 2.集群中某个节点可以连接外网 3.所有节点不能连接外网

一些命令说明：

    date命令：

    date :查看当前时间，

    date -s 09:38:40 :设置当前时间

    ntpdate命令：

    ntpdate -u 210.72.145.44 :网络时间同步命令

    注意：若不加上-u参数，会出现以下提示： no server suitable for synchronization found

    -u：从man ntpdate中可以看出-u参数可以越过防火墙与主机同步；

    210.72.145.44：中国国家授时中心的官方服务器。

    ntp常用服务器：

    中国国家授时中心：210.72.145.44

    NTP服务器(上海) ：ntp.api.bz

    美国：time.nist.gov
    复旦：ntp.fudan.edu.cn
    微软公司授时主机(美国) ：time.windows.com
    台警大授时中心(台湾)：asia.pool.ntp.org

    经测试中国国家授时中心与NTP上海服务器可以正常同步时间，注意需要加上-u参数！

    当所有节点都可以联网，在各节点采用上面命令即可，
    如果节点太多,在主节点上用for循环既可：
    for i in`seq 1 82`;do ssh node$i "ntpdate -u ntp.api.bz"
    注意 1-82是集群中的计算节点，并且集群已经配置好了ssh.

第二种情况：连不上外网，比如：自己搭建的用来学习的集群中所有机器需要同步时间：

思路：可以把其中一台配置为时间服务器，其他机器通过定时任务来同步时间

Linux自带了ntp服务 -- /etc/init.d/ntpd，这个服务不仅可以设置让本机和某台/某些机器做时间同步，

他本身还可以扮演一个time server的角色，让其他机器和他同步时间。配置文件就是/etc/ntp.conf。

step1:
        因为实验室集群有83个节点，node100是主节点，所以可以把node100作为time server，node100本身不和其他机器

        时间同步，就是取本地时间。所以，先把node100机器的时间调准了：

        node100是可以联网的，可以采用上面的方式设置时间，如果不能联网，可以用如下命令手动设置：

            date -s 18/05/2018             -----设置指日期

            date -s 11:12:00     ----设置具体时间

        用如下两条命令把设置的时间写到硬件时间中去（也就是CMOS里面的时间）。

        clock -w

        hwclock --systohc
step2:
            将node100配置成一个time server，修改 /etc/ntp.conf ，
            1. 注释掉原来的restrict default ignore这一行，这一行本身是不响应任何的ntp更新请求，

                其实也就是禁用了本机的ntp server的功能，所以需要注释掉。

            2. 加入下面3行：

       restrict 10.10.10.0 mask 255.255.255.0 nomodify notrap

            （注释:用于让10.10.10.0/24网段上的机器能和本机做时间同步）

                    server 127.127.1.0 # local clock
                    fudge 127.127.1.0 stratum 10

                    后两行是让本机的ntpd和本地硬件时间同步。

            3./etc/init.d/ntpd restart或者 service ntpd restart

            4.chkconfig ntpd on 设置开机自启动

            5.修改iptables配置，将tcp和udp 123端口开放，这是ntp需要的端口，在/etc/services中可以查到这个端口
```
    vim /etc/sysconfig/iptables 
    按类似如下的图片修改
    
```
step3:
            这样node100就成为一台time server了，现在我们配置其他的所有机器（这里我们用定时任务来定时同步时间）

             下面的可以不用做，也可以做：

            首先关掉这台机器上的ntpd服务：

    service ntpd stop(本次关掉)

    chkconfig ntpd off(再关掉开机自启动)；
收起
展开全文
【 C 】在单链表中插入一个新节点的尝试（一）
万次阅读 2018-09-11 23:11:50
根据《C和指针》中讲解链表的知识，记录最终写一个在单链表中插入一个新节点的函数的过程，这个分析过程十分的有趣，准备了两篇博文，用于记录这个过程。链表是以结构体和指针为基础的，所以结构体和指针是需要...
根据《C和指针》中讲解链表的知识，记录最终写一个在单链表中插入一个新节点的函数的过程，这个分析过程十分的有趣，准备了两篇博文，用于记录这个过程。

链表是以结构体和指针为基础的，所以结构体和指针是需要首先掌握的知识，掌握之后，最后要明白这个问题：结构体的自引用

这时候就可以尝试链表的学习了。记得去年学习链表的时候觉得特别新奇，并使用之写了一个蹩脚的学生信息管理系统，当然不值一提，可惜没有趁热打铁继续下去，也许不是坏事，醒悟的时候还不算晚！

先介绍下链表吧：

链表（linked list）就是一些包含数据的节点的集合。这些节点是用结构体定义的，如下：
```
typedef struct NODE{
    struct NODE *link;
    int value;

} Node;
```
使用typedef定义了一个结构类型的别称Node，称为节点。

链表中的每个节点通过指针（也叫链）链接一起。程序通过指针访问链表中的节点。通常节点是动态分配的，但是有时你也能看到由节点数组创建的链表。即使在这种情况下，程序也是通过指针来遍历链表的。我们关注的是动态内存分配来创建节点。

在单链表中，每个节点包含一个指向链表下一个节点的指针。链表最后一个节点的指针字段的值为NULL，提示链表后面不再有其他节点。在你找到链表的第一个节点后，指针就可以带你访问剩余的所有节点。为了记住链表的起始位置，可以使用一个根指针（root pointer）。根指针指向链表的第一个节点。注意根指针只是一个指针，它不包含任何数据。

下面是一个单链表的图：

从上面的图中可以看出，这些节点相邻在一起，这是为了显示链表所提供的逻辑顺序。事实上，链表中的节点可能分布于内存中的各个地方。对于一个处理链表的程序而言，各节点在物理上是否相邻并没有什么区别，因为程序始终用指针（链）从一个节点移动到另一个节点。

但链表可以通过链从开始位置遍历链表直到结束位置，但链表无法从相反的方向进行遍历。

上面显示的链表中，节点根据数据的值按升序链接在一起。对于有些应用程序而言，这种顺序非常重要，比如根据一天的时间安排约会。对于那些不要求排序的应用程序，当然也可以创建无序的单链表。

下面正式进入正题：在单链表中插入一个新节点的第一次尝试：

如何才能把一个新节点插入到一个有序的单链表中呢？

假定我们有一个新值，比如12，想把它插入到上面提到的那个链表中。从概念上讲，是很容易做到的，从链表的起始位置开始，跟随指针直到找到第1个值大于12的节点，然后把这个新值插入到那个节点之前的位置。

实际的算法比较有趣：我们按顺序访问链表，当到达内容为15的节点（第一个值大于12的节点）时就停下来。我们知道这个新值应该添加到这个节点之前，但前一个节点的指针必须进行修改以实现这个插入。但是我们已经越过了这个节点，无法返回。解决这个问题的办法是始终保存一个指向链表当前节点之前的那个节点的指针。

了解这么多，我们就可以开始实践了：

首先定义一个头文件：
```
typedef struct NODE{
    struct NODE *link;
    int value;

} Node;
```
存放于sll_node.h的头文件中。

下面开发一个函数，把一个节点插入到一个有序的单链表中，后面并做出详细分析：
```
//插入到一个有序的单链表。函数的参数是一个指向链表第一个节点的指针以及需要插入的值
#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"   //这个头文件是前面自己创建的

#define FALSE 0
#define TRUE 1

int sll_insert( Node *current, int new_value )
{
    Node *previous;
    Node *new;                //需要插入的新节点
    
    //寻找正确的插入位置，方法是顺序访问链表，直到到达其值大于或等于新插入的节点的值
    
    while( current->value < new_value )
    {
        previous = current; //始终保存当前节点之前的那个节点
        current = current->link; //当前节点移动到下一个节点
    }
    
    //为新节点分配内存，并把新值存储到新节点中，如果内存分配失败，函数返回FALSE
    
    new = ( Node *)malloc( sizeof( Node ) );
    if( new == NULL )
    {
        return FALSE;
    }
    new->value = new_value;
    
    //把新节点插入到链表中，并返回TRUE
    new->link = current; //新节点的指针指向当前节点
    previous->link = new; //前一个节点的指针指向新节点
    return TRUE;

}
```
我们用下面的方法调用这个函数：

result = sll_insert( root, 12 );

下面跟踪代码的执行过程：

首先传递给函数的参数是root变量的值，它是指向链表的第一个节点的指针。当函数刚刚执行时，链表的状态如下：

这张图没有显示root变量，因为函数不能访问它。它的值的一份拷贝作为形参current传递给函数，但函数不能访问root。现在current->value是5，小于12，所以循环再次执行。

当我们回到循环的顶部时，current和previous指针都向前移动了一个节点。

现在current->value的值是10，小于12，因此循环体继续执行，结果如下：

现在current->value的值是15大于12，所以退出循环。

此时，重要的是previous指针，因为它指向我们必须加以修改以插入新值的那个节点。但首先，我们必须得到一个新节点，用于容纳新值。下面这张图显示了新值被赋值到新节点之后链表的状态。

把这个新节点链接到链表中需要两个步骤。

首先，new->link = current;

也就是使新节点指向将称为链表下一个节点的节点，也就是我们找到的第一个值大于12的那个节点。在这个步骤之后，链表的内容为：

第二个步骤是让previous指针所指向的节点修改为指向这个新节点。下面这个语句执行这个任务：

previous->link = new;

这个步骤之后，链表的状态如下：

然后函数返回，链表最终的样子如下：

从根节点开始，随各个节点的link字段逐个访问链表，我们可以发现这个新节点已被正确地插入链表中。

最后，不得不提的是现实是否就是这么如意？

可以思考一下，如果试图把20插入链表，也就是new_value = 20,这个程序还能正常工作吗？

这里把循环提出来：

while( current->value < new_value )
{
previous = current; //始终保存当前节点之前的那个节点
current = current->link; //当前节点移动到下一个节点
}

你会发现，while循环会越过链表的尾部，并对一个NULL指针执行间接访问操作。这是不合法的。

为了解决这个问题，我们必须对current的值进行测试，在执行current->value之前确保它不是一个NULL指针：

将while语句的中条件换成如下：

while( current != NULL & current->value < new_value )

{

...

}

就解决了上述问题。

最后呢？提出下一篇博文要讲的内容，就是试试把3这个值插入链表，看看会发生什么？下篇博文见！

下篇博文地址：【 C 】在单链表中插入一个新节点的尝试（二）
收起
展开全文
PQ节点-PV节点-平衡节点
千次阅读 2020-12-22 19:25:31

在一些情况下，系统中某些发电厂送出的功率在一定时间内为固定时，该发电厂也作为PQ节点，因此，电力系统中绝大多数节点属于这一类型。 #PV节点节点的有功功率P和电压幅值V是给定的，节点的无功功率Q和电压相位δ是...

收起
k8s node节点停机维护，pod如何迁移？
千次阅读 2020-09-01 08:48:22

需求 k8s集群中的node节点要升级内存，以应对服务迁入、...其实事实并非如此，k8s在等待5分钟后，会自动将停机node节点上的pod自动迁移到其他node节点上。具体过程如下： # 1.模拟node节点停机，停止kubelet systemctl

收起

pod迁移
两个链表的第一个公共节点
万次阅读 多人点赞 2018-09-02 15:34:28

看到这个题目，容易想到的方法是使用蛮力法解决：在第一个链表上顺序遍历每一个节点，每遍历到一个节点，就在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点与第一个链表上的节点一样，则说明两个链表...

收起

链表算法
el-tree加载完成后默认触发点击事件非默认选中（上）选中第一个节点点击
千次阅读 热门讨论 2020-03-13 23:07:49

最近工作使用Vue+Element UI来进行开发，遇到部门树功能的时候选择了el-tree组件来展示，功能都完成了，但需要在加载完成后默认点击第一个节点，从而查询右侧对应的部门人员信息，但官方没有提供默认触发node-click...

收起
Hbase启动后，在主节点只有Hmaster，而在slave节点上没有Hregionserver
千次阅读 2017-10-06 14:24:46

当所有问题都排查，配置没有错误的情况下，查了网上，一般都是集群时间不同步的问题。...sudo date -s 13:50:00 #这个时间是当下的标准时间，手工调节3台电脑的时间基本一致重新启动服务后，成功！

收起

集群 hbase
给出描述的n个节点，求其邻居节点以及判断两个节点是否有直接联系
千次阅读 2018-06-23 14:00:27

具体描述：txt文件中存储n个节点直接的联系，形如1,2表示节点1和节点2直接联系，或者说他们是邻居。有很多组这样的数据，要求将这些节点读出来进行存储。然后实现输入节点号，输出它的邻居节点。以及输入两个节点ID...

收起

HashMap
12. Zookeeper 实战一: 监控节点动态上下线
万次阅读 2019-08-27 16:15:39

利用Zookeeper 临时型节点特性(当断开连接时, 创建的临时性节点自动销毁), 可实现监听集群节点动态上下线的功能. 所谓监听监听节点动态上下线是指, 当有节点新增或删除时, 监听端都会收到信息. zookeeper 实现的监听...

收起
在单链表的第i个位置后插入一个节点(面试题)
万次阅读 2018-08-01 16:24:53

/* 思路：面对这题，我们首先要冷静。可以先从常规想，既然要插入一个结点，可以把它分成两大... 第二大类：就是如果之前没提供节点，那么插入的节点就是这个链表唯一的节点，切记还有一种情况。 ...

收起
区块链每日问答之节点(1)
千次阅读 2022-01-18 21:51:13

比如说比特币网络，是一个公有链，用户在自己的联网电脑上运行比特币程序时，这个电脑就成为比特币区块链网络中的一个节点。是指下载了相关加密货币的节点软件，以参与对等网络的计算机。操作一个节点可以是普通钱包...

收起
二叉树中两个节点的最近公共祖先节点
万次阅读 多人点赞 2016-08-04 23:43:47

从树的根节点开始和两个节点作比较，如果当前节点的值比两个节点的值都大，则这两个节点的最近公共祖先节点一定在该节点的左子树中，则下一步遍历当前节点的左子树；如果当前节点的值比两个节点的值都小

收起
牛逼！Elasticsearch 集群更换节点角色有了更快的方式
千次阅读 2021-04-28 00:16:08

1、实战遇到的问题问题描述：如何在一个四个节点的集群中，将主节点中的数据分散到其他节点中去，最后主节点没有数据？问题细节：线上环境有4个节点，单节点为48核的物理机，252G的内存。数据每...

收起

分布式大数据
Slurm如何管理和使用节点资源
千次阅读 2019-10-31 15:35:21

Slurm管理和使用集群节点资源主要分为四个环节：分别是初始化节点资源、更新节点资源、测试节点资源可用、实际分配节点资源。 1.初始化节点资源 slurmctld初始化时解析节点配置文件，借助几个全局数据结构（select...

收起

Slurm
elasticsearch生产集群部署-3个节点集群部署
千次阅读 2018-09-19 21:38:00

1、在三个节点上都下载es 如果要安装es，首先就要从官网elastic.co/downloads/elasticsearch下载es的安装包，并且最新es版本要求有JDK 8以上的版本。 es安装包的目录结构大致如下： bin：存放es的一些可执行脚本...

收起

ELK日志分析系统
怎么计算一棵完全二叉树的节点个数
千次阅读 2018-03-13 22:00:58

题目：已知一棵完全二叉树，求其节点的个数要求：时间复杂度低于O(N)，N为这棵树的节点个数完全二叉树的概念就不多叙述了。讲讲思路：题目的要求是时间复杂度低于O(N)，所以遍历的方式就不用考虑了，根据完全二叉树...

收起

Java 完全二叉树
区块链全节点与区块链轻节点的区别
万次阅读 2019-04-22 14:29:28

因为区块链的冗余备份，要求所有节点都需保存全量的数据文件，在这个节点间，假设有用户用自己创建一个区块链节点来进行DApp的开发，可又不想参与共识，那对于这个用户而言，同步大量的数据是非常消耗时间的，而且...

收起
剑指Offer面试题13（java版）:在O(1)时间删除链表节点
千次阅读 2015-07-31 20:55:53

题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。在单向链表中删除一个节点，最常规的方法无疑是从链表的头结点开始，顺序遍历查找要删除的节点，并在链表中删除该节点。比如图a...

收起
Polkadot验证节点的安全性和可用性
万次阅读 2019-05-16 18:29:45

在本文中，我将在验证节点的安全性和可用性方面讨论两个主题。我知道，这里介绍的技巧仅仅涵盖了POS验证节点的“安全性和可用性”冰山一角。不过，我发现它们对于您的测试实例提供最小的安全性和可用性是有用的。 ...

收起
【面试题】在O(1)时间复杂度删除链表节点
千次阅读 2015-07-28 15:01:17

题目描述给定一个单链表中的表头和一...请在在O(1)时间复杂度删除该链表节点。并在删除该节点后，返回表头。样例给定 1->2->3->4，和节点 3，返回 1->2->4。(372) Delete Node in the Middle of Singly Linked List ...

收起
虚幻引擎4蓝图节点
千次阅读 多人点赞 2020-04-13 19:09:32

收集一些自己了解的蓝图节点，以便更好地学习。

收起

unreal
Pi Network节点教程
万次阅读 多人点赞 2021-01-08 00:58:57

文章目录1、简介2、Pi节点安装2.1、操作系统2.2、路由器设置2.3、Docker安装2.4、...Pi节点的安装设置过程稍复杂，在此做个总结。 2、Pi节点安装 2.1、操作系统 2.2、路由器设置 2.3、Docker安装 2.4、Pi Node安装 ...

收起
多节点服务器定时任务重复处理的问题
万次阅读 2017-08-20 23:02:50

项目中有使用Spring定时执行任务的需求，用户可以自定义时间（半小时或整点）去生成需要...一切功能表现正常，但是项目部署在服务器上后，用户反映在同一时间会收到两封相同的邮件。我们检查了代码和Spring Schedule本

收起

定时任务
区块链节点与主节点分别是什么？
万次阅读 2018-12-18 11:48:23

虽然币市低迷，但是区块链技术的发展却并未受到影响，本文将和大家分享一些区块链的基础知识，即节点和主节点分别是什么，我们如何参与及他们在区块链网络中执行的任务是什么？希望帮助大家更好的认识区块链技术。 ...

收起
无线网络传输问题：隐藏节点和暴露节点
千次阅读 2020-04-19 16:08:56

1.什么是隐藏节点和...冲突后发送节点要重传冲突的分组，这降低了信道的利用率。隐藏终端又可以分为隐发送终端和隐接收终端两种。在单信道条件下，隐发送终端可以通过在发送数据报文前的控制报文握手来解决。但...

收起
RNN之多层LSTM理解：输入，输出，时间步，隐藏节点数，层数
万次阅读 多人点赞 2019-02-28 16:37:39

从pytorch代码角度初次理解LSTM各种术语。 LSTM: ...hidden_size 隐层状态的维数：（每个LSTM单元或者时间步的输出的ht的维度，单元内部有权重与偏差计算） num_layers RNN层的个数：（在竖直...

收起

多层LSTM
在长度为n的()上，删除第一个元素，其算法的时间复杂度为O(n)
千次阅读 2020-04-04 14:00:11

在长度为n的（）上，删除第一个元素，其算法的时间复杂度为O(n) A.只有表头指针的不带表头结点的循环单链表 B.只有表尾指针的不带表头结点的循环单链表 C.只有表尾指针的带表头结点的循环单链表 D.只有表头指针的带...

收起

数据结构
三.minio 的分布式部署、单节点多磁盘、多节点模式
万次阅读 2021-08-06 15:44:26

由于硬盘分布在不同的节点上，分布式Minio避免了单点故障。在大数据领域，通常的设计理念都是无中心和分布式。Minio分布式模式可以帮助你搭建一个高可用的对象存储服务，你可以使用这些存储设备，而不用考虑其真实...

收起

minio