创建型：单例模式
概念 保证一个类仅有一个实例，并提供一个该实例的全局访问点 场景 应用程序的日志应用 读取配置文件 数据库连接池 多线程线程池 必须有一个类的实例，并且必须可以从一个著名的访问点访问它 当唯一的实例可以由子类扩展，并且客户端应该能够使用扩展的实例而无需修改其代码 实现 普通实现 ...
2020_05_11_02
多态 编译时多态 通过函数重载实现 运行时多态 多态性可以概括为“一个接口，多个方法”，程序运行时才决定调用哪个具象化函数 多态通过虚函数实现，虚函数允许子类重新定义成员函数，而子类重写定义父类函数的做法叫做覆盖，override vector底层 vector底层实现是封装了顺...
2020_05_11_01
虚函数 虚函数 虚函数机制用以支持一个有效率的“执行期”绑定。 虚函数指针 C++对象模型： 每个class产生出一堆指向虚函数的指针，放在表格当中。这个表格被称为svirtual table。 没一个类对象被安插一个指针，指向相关的virtual table，这个指针通常被称为...
【Nowcoder-May】
华为在线机试训练 求最小公倍数 Question 正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。 输入描述： 输入两个正整数A和B。 输出描述： 输出A和B的最小公倍数。 实例 输入 5,7 输出 35 Ans
查找_二分查找
简述 也叫折半查找，性能优异。 但是所查找的数列必须是有序序列。 复杂度 时间复杂度 log2(N) 实现 非递归实现 递归实现 插值查找 二分查找每次都会计算出一个mid，然后拿这个mid的值去做比较 $$ mid = \frac{(low+high)}{2} $$ $$ mi...
排序_桶排序
简述 桶排序需要创建若干个桶来协助排序。 所谓桶，每个桶bucket代表一个区间范围，里面可以承载一个或多个元素。 复杂度 名称 最好 平均 最差 空间 稳定性 桶排序 n+k n nlog(n) n 是 实现 算法导论 桶排序思想，假设对数组A[p...r]排序，首先将这些元素...
排序_计数排序
简述 计数排序适用于对一定范围内的元素进行排序。 它的思路就是创建一个范围性的计数数组，用下标去对应元素的值，有几个元素，相应下面命中几次。然后根据元素命中次数对下标值进行一次输出，得到的序列就是有序的序列。 它是不需要进行元素比较。 注意： 当数列最大和最小值差距过大时，不适合...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述 堆排序算法步骤： 把无序数组构建成二叉堆。需要从小到大排序，就...
排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 为什么快速排序比较快？ 因为它使用了分治法...