算法基提升础学习2 算法基提升础学习2

一、树形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 = https://www.it610.com/article/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 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 = https://www.it610.com/article/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 = https://www.it610.com/article/cur.value; //cur没有左孩子，cur向右移动 cur = cur.right; } return true; }

三、位运算技巧公式 (n >> i) & 1: 取出整数 n在二进制下的第 i 位
n & (~n + 1): 用来求数字的二进制表示的最右边的 1
【算法基提升础学习2】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; } }