算法基提升础学习2

• 2021 年 12 月 7 日
• 筆記
• 算法

一、树形Dp

题

叉树节点间的最大距离问题

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路 径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最 大距离。

/**
 * @Author: 郜宇博
 */
public class TreeDp {
    public static void main(String[] args) {
        Node head2 = new Node(1);
        head2.left = new Node(2);
        head2.right = new Node(3);
        head2.right.left = new Node(4);
        head2.right.right = new Node(5);
        head2.right.left.left = new Node(6);
        head2.right.right.right = new Node(7);
        head2.right.left.left.left = new Node(8);
        head2.right.right.right.right = new Node(9);
        System.out.println(maxDistance(head2));
    }

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

        public Node(int value) {
            this.value = value;
        }
    }
    public static class Result{
        public int childMaxDistance;
        public int childHeight;

        public Result(int childMaxDistance, int childHeight) {
            this.childMaxDistance = childMaxDistance;
            this.childHeight = childHeight;
        }
    }
    /**
     * 获取节点间最大距离
     * 三种情况：
     * 一、最大距离不带本节点
     *  1.最大距离是从左数获取的
     *  2，是从右树获取的
     * 二、最大距离带本节点
     *  3.左子树Height+右子数Hight+1
     *
     *  此时需要三个参数：子树的最大距离，左子树的高，右子树的高
     *  因此需要额外定制一个返回类型包含该数的最大距离，该数的高
     *  从子树分别获取这两个返回值
     */
    public static int maxDistance(Node head){
        return process(head).childMaxDistance;
    }
    public static Result process(Node head){
        //空树
        if (head == null){
            return new Result(0,0);
        }
        //1.最大距离是从左数获取的
        Result p1 = process(head.left);
        //2.最大距离是从右数获取的
        Result p2 = process(head.right);
        //3.最大距离经过自己
        int maxDistanceP3 = p1.childHeight + p2.childHeight + 1;
        //从子树获取完信息，自己也要提供信息
        //高度
        int height = Math.max(p1.childHeight,p2.childHeight) + 1;
        //最大距离
        //就是这三个可能性中最大的
        int maxDistance = Math.max( maxDistanceP3,Math.max(p1.childMaxDistance,p2.childMaxDistance)  );
        return new Result(maxDistance,height);

    }

}

最大开心值

/**
 * @Author: 郜宇博
 */
public class MaxHappy {
    public static void main(String[] args) {


    }
    public static class Emplyee{
        public int happy;
        public List<Emplyee> nexts;

        public Emplyee(int happy) {
            this.happy = happy;
        }
    }

    /**
     * happy值最大：
     * 一、当本节点参加
     *      Happy = 本节点happy + 下级员工们不参加的MaxHappy
     * 二、当本节点不参加
     *      happy = 下级员工们参加的MaxHappy 和 不参加的MaxHappy 的较大值
     *
     * 因此需要构造返回类型有两个参数： 参加的maxHappy和不参加的maxHappy
     */
    public static class Result{
        public int comeMaxHappy;
        public int unComeMaxHappy;

        public Result(int comeMaxHappy, int unComeMaxHappy) {
            this.comeMaxHappy = comeMaxHappy;
            this.unComeMaxHappy = unComeMaxHappy;
        }
    }
    public static int maxHappy(Emplyee head){
        return Math.max( process(head).comeMaxHappy, process(head).unComeMaxHappy);
    }
    public static Result process(Emplyee emplyee){
        //base case
        if (emplyee == null){
            return new Result(0,0);
        }
        //基层员工
        if (emplyee.nexts == null){
            return new Result(emplyee.happy,0);
        }
        int UncomeHappy = 0;
        int comeHappy = 0;
        //获取各个员工的result
        for (Emplyee e: emplyee.nexts){
            Result result = process(e);
            //不参加
            //happy = 下级员工们参加的MaxHappy 和 不参加的MaxHappy 的较大值
            UncomeHappy += Math.max( result.comeMaxHappy,result.unComeMaxHappy);
            //参加
            //Happy = 本节点happy + 下级员工们不参加的MaxHappy
            comeHappy += emplyee.happy + result.unComeMaxHappy;
        }
        return new Result(comeHappy,UncomeHappy);
    }
}

二、Morris遍历

Morris遍历细节

假设来到当前节点cur，开始时cur来到头节点位置

1）如果cur没有左孩子，cur向右移动(cur = cur.right)

2）如果cur有左孩子，找到左子树上最右的节点mostRight：

​ a.如果mostRight的右指针指向空，让其指向cur， 然后cur向左移动(cur = cur.left)

​ b.如果mostRight的右指针指向cur，让其指向null， 然后cur向右移动(cur = cur.right) 3）

cur为空时遍历停止

public static void morrisTravel(Node head){
    if (head == null){
        return;
    }
    Node cur = head;
    Node mostRightNode;
    while (cur != null){
        mostRightNode = cur.left;
        //cur有左孩子
        if (mostRightNode != null){
            //找到左子树的最右节点，并且保证mostRight不会移动回cur
            while (mostRightNode.right != null && mostRightNode.right != cur){
                mostRightNode = mostRightNode.right;
            }
            //看mostRight是否有right
            if (mostRightNode.right == null){
                //没有right,则添加right指向cur
                mostRightNode.right = cur;
                //并且cur向左遍历
                cur = cur.left;
                //继续这一循环
                continue;
            }
            //指向了cur
            else {
                //断开连接
                mostRightNode.right = null;
                //cur向右移动
            }
        }
        //cur没有左孩子，cur向右移动
        cur = cur.right;
    }
}

先序遍历

//先序：能回来两次的节点，第一次打印，第二次不打印
//     只能到一次的节点，直接打印
public static void morrisPreTravel(Node head){
    if (head == null){
        return;
    }
    Node cur = head;
    Node mostRightNode;
    while (cur != null){
        mostRightNode = cur.left;
        //cur有左孩子
        //进入if:能回cur两次的
        if (mostRightNode != null){
            //找到左子树的最右节点，并且保证mostRight不会移动回cur
            while (mostRightNode.right != null && mostRightNode.right != cur){
                mostRightNode = mostRightNode.right;
            }
            //看mostRight是否有right
            if (mostRightNode.right == null){
                //第一次来到当前节点
                System.out.print(cur.value+" ");
                //没有right,则添加right指向cur
                mostRightNode.right = cur;
                //并且cur向左遍历
                cur = cur.left;
                //继续这一循环
                continue;
            }
            //指向了cur
            else {
                //第二次来到cur
                //不打印
                //断开连接
                mostRightNode.right = null;
                //cur向右移动
            }
        }
        //没有左子树的，走到else
        else {
            System.out.print(cur.value+" ");
        }
        //cur没有左孩子，cur向右移动
        cur = cur.right;
    }
}

中序

//中序：能回来两次的节点，第一次不打印，第二次打印
//     只能到一次的节点，直接打印
public static void morrisMediaTravel(Node head){
    if (head == null){
        return;
    }
    Node cur = head;
    Node mostRightNode;
    while (cur != null){
        mostRightNode = cur.left;
        //cur有左孩子
        //进入if:能回cur两次的
        if (mostRightNode != null){
            //找到左子树的最右节点，并且保证mostRight不会移动回cur
            while (mostRightNode.right != null && mostRightNode.right != cur){
                mostRightNode = mostRightNode.right;
            }
            //看mostRight是否有right
            if (mostRightNode.right == null){
                //没有right,则添加right指向cur
                mostRightNode.right = cur;
                //并且cur向左遍历
                cur = cur.left;
                //继续这一循环
                continue;
            }
            //指向了cur
            else {
                //第二次来到cur
                //不打印
                //断开连接
                mostRightNode.right = null;
                //cur向右移动
            }
        }
        System.out.print(cur.value+" ");
        //cur没有左孩子，cur向右移动
        cur = cur.right;
    }
}

后续

//后续：能回来两次的节点，第二次的手打印左树的右边界 逆序
//当while完成后，打印整棵树的右边界
public static void morrisLastTravel(Node head){
    if (head == null){
        return;
    }
    Node cur = head;
    Node mostRightNode;
    while (cur != null){
        mostRightNode = cur.left;
        //cur有左孩子
        //进入if:能回cur两次的
        if (mostRightNode != null){
            //找到左子树的最右节点，并且保证mostRight不会移动回cur
            while (mostRightNode.right != null && mostRightNode.right != cur){
                mostRightNode = mostRightNode.right;
            }
            //看mostRight是否有right
            if (mostRightNode.right == null){
                //没有right,则添加right指向cur
                mostRightNode.right = cur;
                //并且cur向左遍历
                cur = cur.left;
                //继续这一循环
                continue;
            }
            //指向了cur
            else {
                //第二次来到cur
                //不打印
                //断开连接
                mostRightNode.right = null;
                printEdge(cur.left);
                //cur向右移动
            }
        }
        //cur没有左孩子，cur向右移动
        cur = cur.right;
    }
    //while后，打印整棵树左树的右边界
    printEdge(head);
}
public static void printEdge(Node head) {
    Node tail = reverseEdge(head);
    Node cur = tail;
    while (cur != null) {
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    reverseEdge(tail);
}

public static Node reverseEdge(Node from) {
    Node pre = null;
    Node next = null;
    while (from != null) {
        next = from.right;
        from.right = pre;
        pre = from;
        from = next;
    }
    return pre;
}

题

判断是否为线索二叉树

可以根据中序遍历改编

//中序：能回来两次的节点，第一次不打印，第二次打印
//     只能到一次的节点，直接打印
public static boolean morrisMediaTravel(Node head){
    if (head == null){
        return true ;
    }
    Node cur = head;
    Node mostRightNode;
    int preNodeValue = Integer.MIN_VALUE;
    while (cur != null){
        mostRightNode = cur.left;
        //cur有左孩子
        //进入if:能回cur两次的
        if (mostRightNode != null){
            //找到左子树的最右节点，并且保证mostRight不会移动回cur
            while (mostRightNode.right != null && mostRightNode.right != cur){
                mostRightNode = mostRightNode.right;
            }
            //看mostRight是否有right
            if (mostRightNode.right == null){
                //没有right,则添加right指向cur
                mostRightNode.right = cur;
                //并且cur向左遍历
                cur = cur.left;
                //继续这一循环
                continue;
            }
            //指向了cur
            else {
                //第二次来到cur
                //不打印
                //断开连接
                mostRightNode.right = null;
                //cur向右移动
            }
        }
        //System.out.print(cur.value+" ");
        if (cur.value < preNodeValue){
            return false;
        }
        preNodeValue = cur.value;
        //cur没有左孩子，cur向右移动
        cur = cur.right;
    }
    return true;
}

三、位运算

技巧公式

(n >> i) & 1: 取出整数 n在二进制下的第 i 位

n & (~n + 1): 用来求数字的二进制表示的最右边的 1

x ^ y: x + y无进位相加

x & y: x + y 应该进位的数字

题

返回较大值

给定两个有符号32位整数a和b，返回a和b中较大的（不用比较）

/**
 * @Author: 郜宇博
 */
public class getMaxNoIf {
    public static void main(String[] args) {
        int a = -2147483647;
        int b = 2147480000;
        System.out.println(getMax(a,b));
    }

    /**
     * 可能会越界
        a >0 , b < 0时，可能越界 此时sc:1,所以符号不同是，返回a是否大于0就可以

        符号不相同时，a的符号值代表是否应该返回a，
        符号相同时，a-b的符号值代表是否应该返回a

        也就是returnA: difSab * sa + sameSaB * sc(sc>0代表a大)
        returnB: ~ returnA
     */
    public static int getMax(int a, int b){
        //a的符号
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign (a-b);
        //查看a和b是否相同符号,相同为0 不同为1
        int difSab = sa ^ sb;
        int sameSab = invert(difSab);
        int returnA = difSab * sa + sameSab * sc;
        int returnB = invert(returnA);
        return returnA * a + returnB * b;
    }
    //取反
    public static int invert(int a){
        return a ^ 1;
    }
    //得到a的符号，非负返回1，负数返回0
    public static int sign(int a){
        //得到二进制最左边的符号位
        int sign = a >> 31;
        //& 1
        int res =  invert(sign & 1);
        return res;
    }
}

判断是否2，4的幂

判断一个32位正数是不是2的幂、4的幂

/**
 * @Author: 郜宇博
 */
public class TwoPower {
    public static void main(String[] args) {
        System.out.println(isFourPower(18));
    }

    /**
     * 方法一：
         可以先获取到a二进制最右边的数，然后和原来a比较，相同就是2的幂
       方法二：
         因为如果只有一个1，那么减掉1后，就会把二进制打散如 1000 - 1 = 0111
         所以将减一后的数 & 原来的数，如果为0 就是2的幂

       本方法方法二
     */
    public static boolean isTwoPower(int a){
        return (a & ( a-1)) == 0;
    }

    /**
     * 起码是2的幂才能是4的幂，所以应该先判断是否是2的幂
     * 因为4的幂的二进制，1肯定在偶数位上，所以就可以 & 0101010101...
     * 如果等于0就不是
     */
    public static boolean isFourPower(int a){
        int isFour = a & (0x55555555);
        return isTwoPower(a) && (isFour != 0);
    }


}

加减乘除

给定两个有符号32位整数a和b，不能使用算术运算符，分别实现a和b的加、减、乘、除运 算

/**
 * @Author: 郜宇博
 没有除
 */
public class AddMinusMultiDivdeByBit {
    public static void main(String[] args) {
        System.out.println(add(1,3));
        System.out.println(minus(1,3));
        System.out.println(multi(20,3));

    }
    //获取无进位相加和进位的数， 循环，直到进位的数为0
    public static int add(int a,int b){
        //两数异或后的结果，也就是无进位相加
        int sum  = a;
        while (b != 0){
            sum = a ^ b;
            //b是进位结果
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }
    // a - b == a + (-b)
    // -b == (~b)+1
    public static int minus(int a, int b){
        return add(a ,negNum(b));
    }

    private static int negNum(int b) {
        return add( ~b,1 );
    }
    //如果b末尾为0，则不加到res上，
    public static int multi(int a, int b){
        int res = 0;
        while (b != 0){
            //看b的最后一位是不是0
            if ((b & 1) != 0){
                //更新结果
                res = add(res ,a);
            }
            //a 左移一位
            a <<= 1;
            //b无符号右移一位
            b >>>= 1;
        }
        return res;
    }
}