03-栈和队列

2022-07-18

03-栈和队列 队列 双端队列 注意双端队列各个方法的入队和出队顺序 offer() 就相当于offerLast() peek()和poll()则相当于peekFirst()和pollFirst()

02-hash和集合

2022-07-18

02-hash和集合 set集合 set集合去重的规则,根据内部元素的equals和hashcode去重 二. 哈希表 2.1 散列函数 设计原则: 设计简单 分布均匀 直接定址法 直接把元素放入对应的数组的位置 数据分析法 分析数据算出位置 平方取中法 取余法 比较常用 随机数法 2.2 散列冲突的解决方案 开放地址法 线性探测法 二次探测法 再哈希法 链地址法 算出来相同位置的元素使用链表存储

05-动态规划

2022-07-18

05-动态规划 动态规划(Dynamic Programming) 动态递推 一. 基本思想 递归 + 记忆化 -> 递推 状态的定义:$opt[n], dp[n], fib[n]$ 状态转移方程: opt[n] = best_of(opt[n - 1], opt[n - 2], ...) 最优子结构 二. 范例 package other_algorithm; /** * @Author: M˚Haonan * @Date: 2019-05-08 15:39 * @Description: 动态规划范例 * 给定一个网格地图,中间有一些石头,一个人从起点(0,0)走到终点(m - 1,n - 1),求出路径的所有情况 / public class DynamicProgramming { /* * 使用动态规划,即递推的方式 * @param grip * @return */ public int dynamic(int [][] grip){ //总行数 int rows = grip.length; //总列数 int cols = grip[0].lengt....

04-位运算

2022-07-18

04-位运算 位运算 一. 位运算介绍 以二进制对数据进行运算,直接对内存数据进行操作,处理速度很快 常用运算符 异或的特性 1s代表二进制位都为1的数 二. 常用的位运算 更复杂的操作 三. 总结一些技巧 2的n次方 1 >> n 将1左移n位即为2的n次方 x & -x 当一个偶数与它的负值相与时, 结果是能被这个偶数整除的最大的2的幂 x & -x 即x & (~x + 1),偶数取反+1后,最低为位置的1还是1,&后只留下这个1 当一个奇数与它的负值相与时, 结果为1 奇数不会进位,取反+1后最后一位仍为1 所以x&-x可以取到最低位的1

01-二分法查询算法

2022-07-18

01-二分法查询算法 一. 适用场景 单调递增或递减 存在上下界 能够通过索引访问 二. 算法思想 三. 代码实现 3.1 迭代循环 package array_linked; /** * 二分法查找算法 / public class BinarySearch { public static void main(String[] args) { int a [] = new int[]{1,2,3,4,5,6}; int index = binarySearch2(a, 9); System.out.println(index); } /* * 循环查找的算法 * @param arr * @param target * @return */ public static int binarySearch1(int [] arr, int target){ int begin = 0; int end = arr.length - 1; int mid = (begin + end) / 2; while (true){ if (arr[mid] == target){ retu....

02-贪心算法

2022-07-18

02-贪心算法 贪心算法 一. 概念 对问题求解时,总是做出在当前看来是最好的选择 二. 使用场景 问题能够分解成子问题解决,子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构 贪心算法和动态规划的不同之处在于: 贪心算法对每个子问题的解都做出选择,不能回退 动态规划则会保存以前的结果,并根据以前的结果对当前进行选择,并且可以回退 三. 实战

07-排序算法

2022-07-18

07-排序算法 排序算法 一. 复杂度 二. 稳定性 归并排序、冒泡排序、插入排序、基数排序是稳定的 选择排序、快速排序、希尔排序、堆排序是不稳定的

06-并查集

2022-07-18

06-并查集 并查集 一. 基本介绍 并查集(union&find)是一种树形的数据结构,用于处理一些不交集的合并及查询问题 find 确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集 union 将两个子集合并成同一个集合 二. 应用场景 小弟->老大 帮派识别 两种优化方式· 合并时考虑深度(rank) 调用find时,路径压缩

01-数组和链表

2022-07-18

01-数组和链表 数组和链表 一. 数组 1.1 时间复杂度 ​ 访问每个元素的时间复杂度为o(1) ​ 插入元素的时间复杂度为o(n) ​ 删除元素的时间复杂度为o(n) 二. 链表 2.1 时间复杂度 ​ 插入和删除的时间复杂度为o(1) ​ 查询的时间复杂度为o(n) 三. 常见的算法 跳跃表[^1] [^1]: # 跳跃表 跳跃表是一种特殊的单向有序链表,redis中zset在数据量大时就采用了这种数据结构。 添加,删除,查询的时间复杂度都为O(logn) ```java package algorithm.array_linked; import lombok.Data; import java.util.*; /** * @Author: M˚Haonan * @Date: 2022/1/20 10:54 * @Description: 跳表 * 跳跃表是一种特殊的有序链表,利用空间....

跳跃表

2022-07-18

跳跃表 跳跃表是一种特殊的单向有序链表,redis中zset在数据量大时就采用了这种数据结构。 添加,删除,查询的时间复杂度都为O(logn) package algorithm.array_linked; import lombok.Data; import java.util.*; /** * @Author: M˚Haonan * @Date: 2022/1/20 10:54 * @Description: 跳表 * 跳跃表是一种特殊的有序链表,利用空间换时间,通过多层索引加快链表的检索速度 * * 设计上,采用了一种技巧,每一层都有一个空的哨兵节点,next为实际的元素或索引,down为下一层的哨兵节点。 * 这样设计的好处是,当某个节点的level超过当前的totalLevel需要升一层时,前驱节点可以方便的指定为哨兵节点,直接在哨兵节点的next插入即可 * indexHead指向最顶层的哨兵节点 * * 为了简化,本skipList中不支持重复元素,即score都不相同 */ @Data public class SkipList<E> { //指向最高层索....

java设计模式

2022-07-18

java设计模式 #面向对象设计原则# 1. 单一职责原则 一个对象应该只包含单一的职责,并且该职责被完整的封装在一个类中 降低类的复杂度,一个类只负责一项职责 提高类的可读性和可维护性 降低变更的风险 通常情况下,保证类层次的单一职责。但是类中的方法足够少时,也可以保证方法的单一职责 2. 开闭原则 软件实体应当对扩展(提供方)开放,对修改(使用方)关闭 3. 里氏代换原则 所有引用基类的地方必须能·透明的·使用其子类的对象 个人理解:相当于向上造型。尽量使用基类类型来对对象进行定义,而在运行时再确定其子类类型 即尽量不要重写父类已经实现好的方法 4. 依赖倒转原则 1. 高层模块不应该依赖低层模块,它们都应该依赖抽象。 2. 抽象不应该依赖与细节,细节应该依赖于抽象 3. 要求针对接口编程,不要针对实现编程 4. 一个具体类应当只实现接口或抽象类中声明过的方法,而不要给出多余的方法 三种方式: 接口传递 构造方法传递 setter方式传递 5. 接口隔离原则 客户端不应该依赖那些它不需要的接口 每一个接口应该承担一种相对独立的角色,不干不该干的事情,该干....

14-观察者模式

2022-07-18

14-观察者模式 观察者模式 ​ 在现实世界中,许多对象并不是独立存在的,其中一个对象的行为发生改变可能会导致一个或者多个其他对象的行为也发生改变。例如,某种商品的物价上涨时会导致部分商家高兴,而消费者伤心;还有,当我们开车到交叉路口时,遇到红灯会停,遇到绿灯会行。这样的例子还有很多,例如,股票价格与股民、微信公众号与微信用户、气象局的天气预报与听众、小偷与警察等。 ​ 在软件世界也是这样,例如,Excel 中的数据与折线图、饼状图、柱状图之间的关系;MVC 模式中的模型与视图的关系;事件模型中的事件源与事件处理者。所有这些,如果用观察者模式来实现就非常方便。 一. 定义和特点 1. 定义 ​ 指多个对象间存在一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式,它是对象行为型模式。 2. 特点 观察者模式是一种对象行为型模式,其主要优点如下。 降低了目标与观察者之间的耦合关系,两者之间是抽象耦合关系。 目标与观察者之间建立了一套触发机制。 它的主要缺点如下。 目标与观察者之间的依赖关系并没有完全....

07-享元模式

2022-07-18

07-享元模式 享元模式 ​ 在面向对象程序设计过程中,有时会面临要创建大量相同或相似对象实例的问题。创建那么多的对象将会耗费很多的系统资源,它是系统性能提高的一个瓶颈。例如,围棋和五子棋中的黑白棋子,图像中的坐标点或颜色,局域网中的路由器、交换机和集线器,教室里的桌子和凳子等。这些对象有很多相似的地方,如果能把它们相同的部分提取出来共享,则能节省大量的系统资源,这就是享元模式的产生背景。 一. 定义和特点 1. 定义 ​ 运用共享技术来有效地支持大量细粒度对象的复用。它通过共享已经存在的对象来大幅度减少需要创建的对象数量、避免大量相似类的开销,从而提高系统资源的利用率。 2. 特点 ​ 享元模式的主要优点是:相同对象只要保存一份,这降低了系统中对象的数量,从而降低了系统中细粒度对象给内存带来的压力。 其主要缺点是: 为了使对象可以共享,需要将一些不能共享的状态外部化,这将增加程序的复杂性。读取享元模式的外部状态会使得运行时间稍微变长。 二. 结构和实现 享元模式中存在以下两种状态: 内部状态,即不会随着环境的改变而改变的可共享部分; 外部状态,指随环境改变而改变的不可以共享的部分。....

12-责任链模式

2022-07-18

12-责任链模式 责任链模式 ​ 在现实生活中,常常会出现这样的事例:一个请求有多个对象可以处理,但每个对象的处理条件或权限不同。例如,公司员工请假,可批假的领导有部门负责人、副总经理、总经理等,但每个领导能批准的天数不同,员工必须根据自己要请假的天数去找不同的领导签名,也就是说员工必须记住每个领导的姓名、电话和地址等信息,这增加了难度。这样的例子还有很多,如找领导出差报销、生活中的“击鼓传花”游戏等。 ​ 在计算机软硬件中也有相关例子,如总线网中数据报传送,每台计算机根据目标地址是否同自己的地址相同来决定是否接收;还有异常处理中,处理程序根据异常的类型决定自己是否处理该异常;JSP和 Servlet 的 Filter 等,所有这些,如果用责任链模式都能很好解决。 一. 定义和特点 1. 定义 ​ 为了避免请求发送者与多个请求处理者耦合在一起,将所有请求的处理者通过前一对象记住其下一个对象的引用而连成一条链;当有请求发生时,可将请求沿着这条链传递,直到有对象处理它为止. 2. 特点 在责任链模式中,客户只需要将请求发送到责任链上即可,无须关心请求的处理细节和请求的传递过程,所以责任链将....

10-策略模式

2022-07-18

10-策略模式 策略模式 ​ 在现实生活中常常遇到实现某种目标存在多种策略可供选择的情况,例如,出行旅游可以乘坐飞机、乘坐火车、骑自行车或自己开私家车等,超市促销可以釆用打折、送商品、送积分等方法。 ​ 在软件开发中也常常遇到类似的情况,当实现某一个功能存在多种算法或者策略,我们可以根据环境或者条件的不同选择不同的算法或者策略来完成该功能,如数据排序策略有冒泡排序、选择排序、插入排序、二叉树排序等。 ​ 如果使用多重条件转移语句实现(即硬编码),不但使条件语句变得很复杂,而且增加、删除或更换算法要修改原代码,不易维护,违背开闭原则。如果采用策略模式就能很好解决该问题。 一. 定义和特点 1. 定义 ​ 该模式定义了一系列算法,并将每个算法封装起来,使它们可以相互替换,且算法的变化不会影响使用算法的客户。策略模式属于对象行为模式,它通过对算法进行封装,把使用算法的责任和算法的实现分割开来,并委派给不同的对象对这些算法进行管理。 2. 特点 策略模式的主要优点如下。 多重条件语句不易维护,而使用策略模式可以避免使用多重条件语句。 策略模式提供了一系列的可供重用的算法族,恰当使用继承可以把....

16-代理模式

2022-07-18

16-代理模式 代理模式 ​ 在有些情况下,一个客户不能或者不想直接访问另一个对象,这时需要找一个中介帮忙完成某项任务,这个中介就是代理对象。例如,购买火车票不一定要去火车站买,可以通过 12306 网站或者去火车票代售点买。又如找女朋友、找保姆、找工作等都可以通过找中介完成。 ​ 在软件设计中,使用代理模式的例子也很多,例如,要访问的远程对象比较大(如视频或大图像等),其下载要花很多时间。还有因为安全原因需要屏蔽客户端直接访问真实对象,如某单位的内部数据库等。 一. 定义和特点 1. 定义 ​ 由于某些原因需要给某对象提供一个代理以控制对该对象的访问。这时,访问对象不适合或者不能直接引用目标对象,代理对象作为访问对象和目标对象之间的中介。 2. 特点 代理模式的主要优点有: 代理模式在客户端与目标对象之间起到一个中介作用和保护目标对象的作用; 代理对象可以扩展目标对象的功能; 代理模式能将客户端与目标对象分离,在一定程度上降低了系统的耦合度; 其主要缺点是: 在客户端和目标对象之间增加一个代理对象,会造成请求处理速度变慢; 增加了系统的复杂度 二. 结构和实现 1. 结构 代....

11-命令模式

2022-07-18

11-命令模式 命令模式 ​ 在软件开发系统中,常常出现“方法的请求者”与“方法的实现者”之间存在紧密的耦合关系。这不利于软件功能的扩展与维护。例如,想对行为进行“撤销、重做、记录”等处理都很不方便,因此“如何将方法的请求者与方法的实现者解耦?”变得很重要,命令模式能很好地解决这个问题。 ​ 在现实生活中,这样的例子也很多,例如,电视机遥控器(命令发送者)通过按钮(具体命令)来遥控电视机(命令接收者),还有计算机键盘上的“功能键”等。 一. 定义和特点 1. 定义 ​ 将一个请求封装为一个对象,使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通,这样方便将命令对象进行储存、传递、调用、增加与管理。 2. 特点 命令模式的主要优点如下: 降低系统的耦合度。命令模式能将调用操作的对象与实现该操作的对象解耦。 增加或删除命令非常方便。采用命令模式增加与删除命令不会影响其他类,它满足“开闭原则”,对扩展比较灵活。 可以实现宏命令。命令模式可以与组合模式结合,将多个命令装配成一个组合命令,即宏命令。 方便实现 Undo 和 Redo 操作。命令模式可以与后面介绍的备忘录模....

13-状态模式

2022-07-18

13-状态模式 状态模式 ​ 在软件开发过程中,应用程序中的有些对象可能会根据不同的情况做出不同的行为,我们把这种对象称为有状态的对象,而把影响对象行为的一个或多个动态变化的属性称为状态。当有状态的对象与外部事件产生互动时,其内部状态会发生改变,从而使得其行为也随之发生改变。如人的情绪有高兴的时候和伤心的时候,不同的情绪有不同的行为,当然外界也会影响其情绪变化。 ​ 对这种有状态的对象编程,传统的解决方案是:将这些所有可能发生的情况全都考虑到,然后使用 if-else 语句来做状态判断,再进行不同情况的处理。但当对象的状态很多时,程序会变得很复杂。而且增加新的状态要添加新的 if-else 语句,这违背了“开闭原则”,不利于程序的扩展。 ​ 以上问题如果采用“状态模式”就能很好地得到解决。状态模式的解决思想是:当控制一个对象状态转换的条件表达式过于复杂时,把相关“判断逻辑”提取出来,放到一系列的状态类当中,这样可以把原来复杂的逻辑判断简单化。 一. 定义和特点 1. 定义 ​ 对有状态的对象,把复杂的“判断逻辑”提取到不同的状态对象中,允许状态对象在其内部状态发生改变时改变其行为。 2....

02-建造者模式

2022-07-18

02-建造者模式 建造者模式 ​ 在软件开发过程中有时需要创建一个复杂的对象,这个复杂对象通常由多个子部件按一定的步骤组合而成。例如,计算机是由 CPU、主板、内存、硬盘、显卡、机箱、显示器、键盘、鼠标等部件组装而成的,采购员不可能自己去组装计算机,而是将计算机的配置要求告诉计算机销售公司,计算机销售公司安排技术人员去组装计算机,然后再交给要买计算机的采购员。 ​ 生活中这样的例子很多,如游戏中的不同角色,其性别、个性、能力、脸型、体型、服装、发型等特性都有所差异;还有汽车中的方向盘、发动机、车架、轮胎等部件也多种多样;每封电子邮件的发件人、收件人、主题、内容、附件等内容也各不相同。 ​ 以上所有这些产品都是由多个部件构成的,各个部件可以灵活选择,但其创建步骤都大同小异。只有建造者模式可以很好地描述该类产品的创建。 一. 定义和特点 1. 定义 ​ 指将一个复杂对象的构造与它的表示分离,使同样的构建过程可以创建不同的表示,这样的设计模式被称为建造者模式。它是将一个复杂的对象分解为多个简单的对象,然后一步一步构建而成。它将变与不变相分离,即产品的组成部分是不变的,但每一部分是可以灵活选择....