算法笔记——左神进阶(4)平衡搜索二叉树、累加和为定值最长子数组

本文主要是介绍算法笔记——左神进阶(4)平衡搜索二叉树、累加和为定值最长子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

搜索二叉树

搜索二叉树:对于搜索二叉树的任何一个节点,左子树的值都比节点小,右子树的值都比他大。
TreeMap中,跟HashMap中一样可以提供key-value,同时会将key按照大小顺序排列。中间采用的就是搜索二叉树的知识。

具备平衡性的搜索二叉树:

AVL树——平衡性最严格

任何一个节点的左子树和右子树高度差不大于1,复杂度还是O(logN)。导致调整非常频繁。

红黑树——平衡性要求不严格

每个节点染上色,头和叶节点必然黑,相邻两个节点不能出现连续的红节点,任何一条链,黑色节点个数相差不超过1.所以任何一条链的最长链和最短链的高度差不超过1倍。


搜索二叉树添加平衡性

对于搜索二叉树中的平衡性,都是针对二叉树进行左旋或右旋的调整,不同的搜索二叉树只是针对于左旋和右旋的动作组合。将整个搜索二叉树进行高度的调整,使其实现平衡性。

AVL发现不平衡的机制:

当二叉树进行删除和添加的时候,可能导致二叉树不平衡。
添加或删除时:对于整个二叉树而言存在添加数的时候除了添加节点信息以外,还需要添加左子树和右子树的最大高度信息,当插入一个值的时候,如果树的某一子树高度发生改变,则此时会对父节点存储的最大高度的信息进行更新,会 一直更新到跟节点,然后依次判断高度是否一致或最多相差1,如果不满足,则此时发生左旋或右旋的操作,使其实现平衡。

调整组合类型:LL,RR,LR,RL

LL(左边的左边较长):此时简单进行一个向右就可以
RR(右边的右边较长):此时简单进行一个左旋就可以
RL(右边的左边较长):首先将右边的左边节点变成父节点,然后进行右旋
LR(左边的右边较长):首先将左边的右边节点变成父节点,然后再进行左旋

注意这一部分主要是理解和使用,暂时不用扣代码
AVL树调整平衡性代码

AVL树继承了原本的node类型,但是增加了一个height。

public void rebalance(AVLNode node){   //插入一个新的节点,判断不平衡while(node != null){Node parent = node.parent; int leftHeight = (node.left == null)? -1:((AVLNode) node.left).height;  //把左子树的高度拿过来int rightHeight = (node.right == null) ? -1 : ((AVLNode)node.right).height;int nodeBalance = rightHeight -leftHeight; //高度差if(nodeBalance == 2){ //右树超了if(node.right.right != null){node = (AVLNode)avlRotateLeft(node);break;}else{node = (AVLNode)doubleRotateRightLeft(node);break;}//此时为左树超了}else if(nodeBalance == -2){此判断是LL型if(node.left.left != null){//此时只进行一个右旋的操作node = (AVLNode)avlRotateRight(node);break;}else{node = (AVLNode)doubleRotateLeftRight(node);break;}}else{updateHeight(node);}node = (AVLNode)parent; //往父节点窜}
}
//确立这棵树的高度,从node开始就从本节点开始依次向上调整看是否平衡,
private static final void updateHeight(AVLNode node){int leftHeight = (node.left == null) ? -1:((AVLNode) node.left).height;int rightHeight = (node.right == null) ? -1:((AVLNode) node.right).height;//看左树和右树的高度更高的+1,就是这棵树的高度node.height = 1+ Math.max(leftHeight,rightHeight);
}

题目1:

在这里插入图片描述
【思路】

  1. 将每一个矩阵进行拆分,第一个【1,3,3】拆分为(1,3,上)和(3,3,下);第二个拆分成(2,4,上)和(4,4,下);第三个拆分成(5,1,上)和(6,1,下)
  2. 将位置按照从小到大进行排序,轮廓的变化意味着最大高度发生变化了;较低的高度被较高的高度进行覆盖,覆盖住之后此时出现轮廓。
  3. 建立一张treeMap,将大楼信息拆分成两个,一方面是位置,高度,增加,另一个是位置,高度,减少。此时在map中保存key为某一个高度的高度线,value为某一个高度有几条。
  4. 在遍历整个矩阵过程中,在treeMap中新建节点,此时可以知道最大高度是否发生变化,从而确定当前位置是否产生轮廓。只要上就增加,下就减少,所以,当过了一个矩阵的时候,此时次数信息为0,此时将对应节点删除。

【代码】
关键是最大高度的变化

//Node格式与内容
public static class Node{public boolean be;public int p;public int h;public Node(boolean boRe,int position,int height){be = bORe;     //是上还是下p = position;  //在哪个位置h = height;   //高度}
}//定义比较器
public static class NodeComparator implements Comparator<Node> {@Overridepublic int compare(Node o1,Node o2){if(o1.p != o2.p){  //按位置排序return o1.p-o2.p;}if(o1.be != o2.be){return o1.be ? -1:1;}return 0;}
}public static List<List<Integer>> buildingOutline(int[][] buildings){Node[] nodes = new Node[buildings.length *2];for(int i =0;i<buildings.length;i++){//在放置的时候,将向上的信息和向下的信息收集nodes[i *2] = new Node(true,buildings[i][0],building[i][2]);nodes[i*2+1] = new Node(false,buildings[i][1],buildings[i][2]);}//按照严格的位置排序Arrays.sort(nodes,new NodeComparator());  //htMap进行标记最大高度信息,pmMap记录每一个位置冲到的最大高度//key为高度信息,value是出现次数TreeMap<Integer,Integer> htMap = new TreeMap<>();  //key是位置,遍历pmMap时,会严格按照key升序TreeMap<Integer,Integer> pmMap = new TreeMap<>();for(int i = 0;i<nodes.length;i++){//进行向上还是向下的判断if(nodes[i].be){  //代表向上//如果高度第一次出现,则将当前节点放入if(!htMap.containsKey(nodes[i].h)){htMap.put(nodes[i].h,1);}else{//如果之前出现过,则此时将出现次数+1htMap.put(nodes[i].h,htMap.get(nodes[i].h)+1);}}else{//此时是向下的情况if(htMap.containsKey(nodes[i].h)){//如果现在的高度是1,再减去1,所以需要将现在的节点移除if(htMap.get(nodes[i].h) == 1){htMap.remove(nodes[i].h);}else{//高度大于1,则此时将高度减一htMap.put(nodes[i].h,htMap.get(nodes[i].h)-1);}}}if(htMap.isEmpty()){pmMap.put(nodes[i].p,0);}else{pmMap.put(nodes[i].p,htMap.lastKey());}}List<List<Integer>> res = new ArrayList<>();int start = 0;int height = 0;//因为为treeMap,所以拿出当前位置时是升序排列的for(Entry<Integer,Integer> entry : pmMap.entrySet()){int curPosition = entry.getKey();int curMaxHeight = entry.getValue();//如果之前的高度跟新拿出的高度不同,则意味着此时要生成轮廓线if(height != curMaxHeight){//如果之前的高度为0,则意味着此时开启新的轮廓线,此时跳过if,直接设置起始位置和height//高度不同,也不为0,则也会设置起始位置和heightif(height != 0){//形成整个轮廓线List<Integer> newRecord = new ArrayList<Integer>();newRecord.add(start);newRecord.add(curPosition);newRecord.add(height);res.add(newRecord);}start = curPosition;height = curMaxheight;}}return res;
}

题目2:

给定一个数组arr,数组中有0,正值和负值,给定一个aim值,求累加和为给定值的最长子数组。
一旦出现连续的子数组,子串之类的题,一旦求出必须以每个位置数截止的最长子数组,最长的子数组必定在其中

【思路】
使用sum表示从0位置开始累加到当前位置的所有数目的和,在以当前位置结尾时,此时计算从0开始累加到哪个位置最早出现sum-aim,这代表从该位置到当前位置的和位aim。此时的数组为以当前位置结尾的最长子数组,然后当前位置++,再次计算。

【代码】注意!!! -1位置的累加和为0,一定要加上。 否则会漏掉从第一个数开始的子数组。

public static int maxLength(int[] arr,int aim){if(arr == null || arr.length == 0){return 0;}HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();map.put(0,-1);int len = 0;int sum = 0;for(int i = 0;i< arr.length; i++){sum += arr[i];if(map.containsKey(sum-aim)){len = Math.max(i-map.get(sum-aim),len);}if(!map.containsKey(sum)){map.put(sum,i);}}return len;
}

题目3:

一个整数数组中,求数组中奇数和偶数数目相等的最长子数组

【思路】跟题目2类似,只需要将奇数变成1,偶数变成-1,使得aim等于0,由题目2解法就得到了相应的结果。

类似题目:一个数组只有0、1、2,求1和2数量相等的最长子数组,把2替换成-1,求aim等于0的最长子数组即可。

这篇关于算法笔记——左神进阶(4)平衡搜索二叉树、累加和为定值最长子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/384041

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.