Mr_zhang66的博客

有一对 哈希元 a，b我们可以用这个式子造出哈希函数来磁力链接，每一位数值范围是0-f且总共有16位，这就是所谓哈希码，这就是哈希函数的返回值。能表示的数值范围是：哈希函数的性质：哈希函数的输入域可以是非常大的范围，比如，任意一个字符串，但是输出域是固定的范围（一定位数的bit），假设为S（虽然S可能会很大，但是和输入域没法比），并具有如下性质：典型的哈希函数都有无限的输入值域。当给哈希函数传入相同的输入值时，返回值一样。当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样

给定一个方块矩阵，请把该矩阵调整成顺时针旋转90°之后的样子，要求额外空间复杂度为 O(1)思路：拿上图举例，首先选取矩阵四个角上的点 1,3,9,7 ，按顺时针的方向 1 到 3 的位置（ 1->3 ）、 3->9 、 9->7 、 7->1 ，这样对于旋转后的矩阵而言，这四个点已经调整好了。接下来只需调整 2,6,8,4 的位置，调整方法是一样的。只需对矩阵第一行的前n-1个点采用同样的方法进行调整、对矩阵第二行的前n-3个点……，那么调整n阶矩阵就容易了。以上，四个黑

从宏观的层面找共性，其实转圈打印的过程就是不断顺时针打印外围元素的过程，只要给你一个左上角的点（如 (0,0) ）和右下角的点（如 (3,3) ），你就能够打印出 1 2 3 4 8 12 16 15 14 13 9 5 ；同样，给你 (1,1) 和 (2,2) ，你就能打印出 6 7 11 10 。这个根据两点打印正方形上元素的过程可以抽取出来，整个问题也就迎刃而解了。public class Code_06_PrintMatrixSpiralOrder { public static void .

进阶二 02.05.57

窗口规则：1.L,R 不能回退2.L不能超过R思路：前面介绍的窗口最大值更新结构的特性是，先前放入的数如果还存在于结构中，那么该数一定比后放入的数都大。此题窗口移动的过程就是从窗口中减一个数和增一个数的过程。拿 [1,2,3],4 到 1,[2,3,4]这一过程分析：首先 [1,2,3],4 状态下的窗口应该只有一个值 3 （因为先加了1，加2之前弹出了1，加3之前弹出了2）；转变为 1,[2,3,4] 的过程就是向窗口先减一个数 1 再加一个数 4 的过程，因为窗口中不含1 所以直接加一个.

题目：给你一个无序整型数组，返回其中第K小的数。暴力解：排序解决 O(N*logN)BFPRT算法 O(N)在一个数组中，随机取一个数 做划分值，随机选一个数，既能避免最好，也能避免最坏，28.00进阶二 12:27...

给一个原始串，只能在后面加字符，要求做出一个最短的大字符串（必须包含 两个原始串，且原始串开头位置不同）例子：比如，这棵子树和右边的完全一样需注意，下面这标红的不是子树！子树必须包含所有根节点！把下面的数序列化，变成子树的形式这个字符串可以代表整个二叉树的结构！若s2是s1的子串（KMP算法搞定）！那么T2必然是T1的子树！应用2：如何判断一个字符串不是由一个字符串范式重复得到的！即判断：str能否写为 str‘×n转换成KMP前缀数量和后缀数量的一个整数倍的关系？？

KMP算法是由一个问题而引发的：对于一个字符串 str （长度为N）和另一个字符串 match （长度为M），默认N≥M。如果match 是 str 的子串，请返回其在 str 第一次出现时的首字母下标，若 match 不是 str 的子串则返回 -1 。子序列：可以连续，也可以不连续，比如ac1de，abc123子串/子数组：必然连续二者有时候是混用的！getIndexOf 方法：即getIndexOf （str1，str2）返回一个整型若match 是 str 的子串，返回其在 str 第

哈希表是get每一个key的value，而本题没有value，只有key我们准备两张哈希表，以及一个变量 ：size。一个表存放某 key 的标号，另一个表根据根据标号取某个key如下图所示：A是第0个进来的B是第二个进来的我们现在先忽略remove行为 。就这样一直加到25此时size为26现在用户让我随机等概率返回一个数，怎么做？因为我有size，我可以用math.random函数随机出0-25中的等概率的一个，随机出来的是哪个数字，在map2里面把哪个数字的字符串返回一.

布隆过滤器要解决的问题：黑名单问题问题描述：即：URL属于 黑名单则为true，不属于则为false。介绍：URL是统一资源定位符，对可以从互联网上得到的资源的位置和访问方法的一种简洁的表示，是互联网上标准资源的地址。互联网上的每个文件都有一个唯一的URL，它包含的信息包括：文件的位置以及浏览器应该怎么处理它。经典方法：用哈希表，查每一个url，返回对应true or false。但是要占很大的空间，不满足第二个条件。哈希表里面不用存value。只存key。所以是一个hashset（hashset

工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：、无论是添加、查询还是删除数据，都先 将数据的id 通过哈希函数 换成一个哈希值，记为key如果目前机器有N台，则计算 key%N 的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进的方案。题目中描述的缓存从策略的潜在问题是：如果增加或删除机器时（N变化）代价会很高，所有的数据都不得不根据id重新计算一遍哈希值，并将哈希值对新的机器数进行取模，然

遍历算法时间复杂度是O(N),而遍历是低于O(N)的我们可以利用满二叉树的结点个数为 2^h-1 （h为树的层数）来加速这个过程。我们用h总 纪录变量最深到了哪一层然后遍历x右子树的左边界我们看右子树的左边界有没有到达最后一层如果x的右子树的左边界已经到达最后一层那么x的左子树就是满的 ！且左子树高度为h总-1同时，因为左子树是满的，所以，其节点个数为 2^（h总-1）-1算上根节点，其总的节点数为 2^（h总-1）此时，根的右子树为完全二叉树，和母问题一致！可以用到递归了！若.

“堆”就是一个完全二叉树的结构。完全二叉树：必须 满足 从左到右 依次对齐！比如这棵树判断逻辑是否为 二叉树需要逐层遍历：按如下顺序判断：1.如果二叉树上某个结点 有右孩子无左孩子则一定不是完全二叉树；2.如果不是两个孩子都全（即 要么有左没右，要么左右均无）总共有如下五种情况第一个条件淘汰这种情况否则 ，一定不是完全二叉树比如节点5没中情况1，但是中了情况二。即不是左右两个节点都有那么，从5节点开始，之后的每个节点 都必须是叶节点！问题：返回true还是fal

举例：size balance tree简称sb数平衡性很重要，是用来解决效率问题的二叉树 中序遍历的节点，是依次升序的！那么就是搜索二叉树因此我们可以利用二叉树的中序遍历的非递归方式，比较中序遍历时相邻两个结点的大小，只要有一个结点的值小于其后继结点的那就不是搜索二叉树。搜索二叉树不出现重复节点。初级5 时间： 02.19.19...

例子：3的左子树高度为1，右子树高度为0，所以平衡！1的左子树 高度为2，右子树高度为2，所以平衡！3的左子树高度为2，右子树高度为0，所以不是平衡树所以平衡树和是否为满二叉树没啥特殊联系满二叉树必然是平衡的，但是平衡二叉树未必是满的！一面总共一个多小时，红黑树就是高手也得手写一个小时，所以问道的概率不大。但是可能会问道红黑树是啥，怎么用，和平衡二叉树有什么不同，相似点？下面讲一个高度套路化的东西！递归函数很好用,我们可以这样判断x是否符合平衡性即看x是否会遍历三次！先 来到x..

我们在内存里可以串起一棵树，但是我们总得想办法保存下来。比如机器要关了，内存里的东西都要销毁了，我们需要怎么样才能将指针那些东西保存成文件的格式！以便于我们下回重建出这棵树。这就是本节要讲的 序列化和反序列化的问题！序列化：一些数据 ，用什么形式可以记录下来。记录的过程，就叫序列化。反序列化：把一个文件中的内容怎么还原出内存中的数结构 ，即为反序列化。哈希表怎么序列化反序列 化的？巨简单！序列化：把哈希表遍历，key和value每行对应记到另一个文件反序列化：把这个文件中一行行key和.

几种排序总结冒泡排序把最大数沉到最低选择排序0到n之间 找一个最小的数 排到0位置 ，即： 0到n 位置上的数中最小的数，和0位置上的数 交换1到n之间 找一个最小的数 排到1位置 ，即：1到n 位置上的数中 最小的数 和1位置上的数 交换插入排序（重点，很有用）像扑克牌整牌下面举例说明：一串数字5 3 4 0 6先把0 1 位置上的数 排好序，得到：之后排1 -2位置 上的，得到：这时数字 ‘4’来到了1位置，它还要继续和0位置的数“3”进行比较，发现4大于3，所

一个数组怎么排好序呢？先分别在左右 排好序，然后 再整体排好举一个例子：对于5 3 6；2 0 1这六个数先将其各自在组内排好序，得到：那么具体怎么排序呢？首先分别定义两个指针a，b例如，此时b比较小，b填进去后，转到下一位置...

算法好坏评价标准：时间复杂度。只要完成算法规定的任务，那么所耗费的时间越短越好解释下，什么叫“只要高阶项，不要低阶项，也不要高阶的系数”：对于算法时间复杂度表达式为注：这里N是指样本量。这样的式子，其真正的算法时间复杂度接下来分别举了三个例子来具体阐述算法复杂度：第一个例子的时间复杂度：O(M*N)关于二分法的介绍，见下文：算法复杂度为：流程三分为两个步骤，先排序，后比较整体复杂度为：当样本量不确定时，即不知道m，n哪个大时，只能写成这俩之和！当n小，选2，因为此时log n

heapify代码：当数组中某个值发生变化了（变小），怎么将其重新调整为大根堆如：数组 之前为这个样子6突然变为1怎么将其重新调整为大根堆？先按我们之前提到的公式，找到其左右两个孩子：在这两个孩子中，找到其中最大的，和1比较，交换！得到：继续比较：相应code：其中，heapsize的含义：例如，我们一般以整个数组长度为标记 来判断是否越界同理，我们用heapsize 来标记 堆 越界与否下面解释，这句代码的含义即，如果一开始由7变成5，就不用往下沉，跳出整个

接上文：https://blog.csdn.net/Mr_zhang66/article/details/108441286解析其代码对于一个长度为i的数组，0-——i-1已经构成大根堆，要把i位置的数插进去代码注释如下：其中，这一句的意思：arr【（0-1）/2】=arr【-1/2】=arr【0】在计算机里：下面解析时间复杂度：要把n+1弄进n里面时，之前有几层高度，就比较几次n个数组，高度为log2N（当然是在满二叉树的条件下）log7=3log15=4所以：第

接上篇https://blog.csdn.net/Mr_zhang66/article/details/108440938堆分为两种，一种叫大根堆，一种叫小根堆大根堆：完全二叉树中任何一个树的最大值都是其头部例如下图所示：整棵树的最大值就是其头部6，每颗子树的最大值也是头部 5，每颗小树的 最大值是其自身，如3 4 4小根堆：完全二叉树中任何一个树的最小值都是其头部给一个数组，如何建立 大根堆例如：在构造完全二叉树的过程中发现数字3比父节点数字大，ps:怎么找自己的父位置：按照我们之

接上篇 https://blog.csdn.net/Mr_zhang66/article/details/108440644在实际应用中，可以把一个数组理解为完全二叉树。如下所示（这些数字 都是数组下标）一个位置i，其左、右孩子下标 ：（重点）一个位置i的父节点坐标所以给定一个数组，再给定一个计算公式，就可以脑补出一个完全二叉树在数组中，定义了这个规则，产生了逻辑上的完全二叉树...

额外空间复杂度要完成自己设计流程 需要多少额外的空间如果程序运行过程中，不需要额外的数据结构，只是使用了额外的几个变量。那么额外空间复杂度为O(1)；如果要申请一个和原数组大小一样的数组，那额外空间复杂度为O(n)；如果申请一个是原数组大小一半的数组，那额外空间复杂度为O(n)（因为系数是可以忽略的）...

本文主要阐述并解释了这两句话：递归就是自己调用自己。递归函数就是 系统在帮忙压栈，保护现场举一个例子：题目：如何用递归的形式，在整个数组中 找最大值，即在L到R范围内找全局最大值。思路：分别找到左、右面的最大值，然后比较这两个值的大小。主程序：简单介绍：先定义了一个 arr数组，值为4 3 2 1然后调用getmax函数，参数值为 arr数组，0，arr数组长度-1。getmax函数对应代码：可以看到里面还是调用了getmax函数，像这种自己调用自己的行为，就是递归！综上，这两

例子：在1 2 4 5 7 8 9这些数字中，寻找8我们先定义 数字1的位置索引为L=0;定义 数字9的位置索引为R=6;定义mid=(L+6)/2=3我们先确认mid位置的值是否为8若是比8小，则在mid左侧开始，重新定义一个mid1=（L+mid）/2；然后查看mid1位置上的数是否为8若是比8大，则在mid右侧开始，重新定义一个mid2=（mid+R）/2=4发现4位置为7，比8小，继续向右定义mid3=（mid2+R）/2=5找到8！所以，可以看到，二分法，一次砍掉一半的数，大

堆相当于一个完全二叉树先介绍一下二叉树的概念这是二叉树满二叉树：（非叶节点 的孩子都全）这种不是满二叉树满二叉树是完全二叉树的一种完全二叉树：如果不是满二叉树，请从左到右依次排好例子：反例：问题：这种是完全二叉树吗？...