Alee

In the world the most exhausting matter is that spending every day falsely

数据结构与算法之美学习笔记

基础篇之二分查找(下)

基础篇之二分查找(下) 如何快速定位IP对应的省份地址? 通过IP地址来查找IP归属地的功能并不复杂,它是通过维护一个很大的IP地址库来实现的。地址库中包括IP地址范围和归属地的对应关系。 当我们要查询202.102.133.13这个IP地址归属地时,我们就在地址库中搜索,发现这个IP地址落在[202.102.133.0, 202.102.133.255]这个地址范围内,那我们...

数据结构与算法之美学习笔记

基础篇之二分查找(上)

基础篇之二分查找(上) 假设我们有1000万个整数数据,每个数据占8个字节,如何设计数据结构和算法,快速判断某个整数是否出现在这1000万个数据中?如果希望这个功能内存空间占用最多不超过100MB,该如何实现呢? 无处不在的二分思想 二分查找是一种非常简单易懂的快速查找算法。例如:猜字游戏,随机0到99之间的数字,猜这个随机数是多少,猜的过程中,每猜一次会告诉你猜大了还是猜小了...

数据结构与算法之美学习笔记

基础篇之排序优化

基础篇之排序优化 你知道如何实现一个通用的、高性能的排序函数? 在平时的开发中,我们经常直接使用平台编程语言所提供的排序函数,比如Java的Arrays.sort()方法,你知道这些排序函数是如何实现的吗?底层都利用了哪种排序算法呢? 如何选择合适的排序算法? 要实现一个通用的、高效率的排序函数,该如何选择排序算法? 由于线性排序的时间复杂度比较低,适用场景比较特殊。所...

数据结构与算法之美学习笔记

基础篇之线性排序

基础篇之线性排序 你知道如何根据年龄快速地给100万用户排序吗? 何为线性排序 排序算法的时间复杂度是线性的算法叫做线性排序(Linear Sort)。 本篇介绍三种时间复杂度是O(n)的线性排序:桶排序、计数排序、基数排序。这三个算法都不是基于比较的排序算法,都不涉及元素之间的比较操作。这三种排序算法很容易理解,时间、空间复杂度分析也很简单,但是对要排序的数据要求很苛刻,所...

数据结构与算法之美学习笔记

基础篇之排序(下)

基础篇之排序(下) 你知道如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素吗? 归并排序的原理 如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。 归并排序使用的就是分治思想。分治,就是分而治之,将一个大问题分解成小的子问题来解决。小的问题解决了,大问题也就解决了。 分治思想和...

数据结构与算法之美学习笔记

基础篇之排序(上)

基础篇之排序(上) 插入排序和冒泡排序的时间复杂度相同,都是O(n²),在实际的软件开发中,为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢? 如何分析一个“排序算法” 分析一个排序算法,可以从以下几个方面入手 排序算法的执行效率 对于排序算法执行效率的分析,从这几个方面来衡量: 最好情况、最坏情况、平...

数据结构与算法之美学习笔记

基础篇之递归

基础篇之递归 现在很多 App 都有这个推荐注册返佣金功能。这个功能中,用户 A 推荐用户 B 来注册,用户 B 又推荐了用户 C 来注册。我们可以说,用户 C 的“最终推荐人”为用户 A,用户 B 的“最终推荐人”也为用户 A,而用户 A 没有“最终推荐人”。基于此,如何查找指定用户的“最终推荐人”? 如何理解递归 递归是一种应用非常广泛的算法或者编程技巧。很多数据结构和算法...

数据结构与算法之美学习笔记

基础篇之队列

基础篇之栈 当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢? 如何理解“队列” 可以把它想象成排队买票,先来的先买,后来的人只能站在末尾,不允许插队。先进者先出,这就是典型的“队列”。 我们知道栈只支持两个基本操作:入栈push()和出栈pop()。队列跟栈非常相似,支...

数据结构与算法之美学习笔记

基础篇之栈

基础篇之栈 你知道如何实现浏览器的前进和后退功能吗? 如何理解“栈” 我们可以把栈看成是一摞叠在一起的盘子。在放盘子的时候都是从下往上一个一个放,取盘子的时候都是从上往下一个一个地依次取,不能从中间任意抽出。后进先出,先进后出,这就是典型的“栈”结构。 栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。 为什么要用这个“操作受限”的“栈”? 特定的数据结构是对...

数据结构与算法之美学习笔记

基础篇之链表

基础篇之链表 你知道如何用链表来实现LRU缓存淘汰策略吗? 链表结构 链表和数组一样,是非常基础且非常常用的数据结构,这两者有什么区别? 底层存储结构 数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个100MB大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于100MB,仍然会申请失败。 ...