- 博客(118)
- 收藏
- 关注
RSS订阅原创 崇台九层，起于累土：数组内存及数组面试常问算法全面解析
本章将以 Java 语言为列，深入浅出介绍数组。此部分主要介绍所有编程语言中基本都会涉及到的数据结构：数组。数组相信大家都会使用，但是当面试过程中闻到涉及到内存分析、数据结构对应的算法时，总会有让你猝不及防的地方，比如数组的内存模型分析？本章主要以 Java 语言为列，以阿里巴巴的面试题为主，围绕以下话题深入浅出进行讲解。1. 数组结构首先，什么是数组？数组好比一个“储物空间”，可以有顺序的...
2020-09-22 12:07:57
343
原创 长风破浪会有时：单向链表、双向链表和循环链表图文解析
链表的种类有很多。我们常常会用到的链表有：单向链表、双向链表和循环链表。链表不同于数组的地方在于：它的物理存储结构是非连续的，也就是说链表在内存中不是连续的，并且无序。它是通过数据节点的互相指向实现，当前节点除了存储数据，还会存储下一个节点的地址。我们不必在创建时指定链表的长度，因为链表可以无限的插入节点延伸，且插入和删除数据时，其时间复杂度都是 O(1)。1. 单向链表1.1 单向链表结构...
2020-09-22 12:07:56
914
原创 真金不怕火练：如何用双向链表实现LRU淘汰机制算法
无论是应届生的春招、秋招还是社招，难以避免的一关都是要面对面试官来几个手撕算法，如果你参加过几次面试，就知道链表出现的频率是极其高的。上一篇文章主要给大家讲解了链表的一些类型，包括：单向链表、双向链表以及循环链表，同时还给出了不同链表的代码实现，做一些简单的增删改查。那么本章将提高一点难度，为你介绍常见的链表算法，包括一些 BAT 等大厂的笔试面试题，同时最后彩蛋里将详细的介绍可以称之为链表笔...
2020-09-22 12:07:54
233
原创 明修栈道，暗度陈仓：栈与队列的定义
栈和队列有相似点也有不同点，相似点在于他们都是线性数据结构，不同点是一个先进后出，一个是先进先出，本质上就是逆序操作与顺序操作。这两种数据结构在企业的面试中经常出现，不仅有考察相关代码的实现，也会考察这两种数据结构具体的应用。这部分内容将会带大家梳理、掌握栈与队列这两个数据结构。1. 栈1.1 定义要明白栈的概念，就需要从“栈”这个字开始解读，《说文》中解释到：栈，棚也。所以本质上，栈就是用...
2020-09-22 12:07:52
322
原创 草船借箭，火烧赤壁：栈与队列的存储结构与实现
1 栈的多种存储结构以及实现栈有两种实现方式一种是顺序存储结构、还有一种是链式存储结构。这两种存储结构对应两种存储的数据结构：数组和链表。数组和链表的相关内容可以参考本文其他章节的内容。1.1 栈的顺序存储结构前面我们说了栈是数据结构中线性表的特殊存在，所以栈的顺序存储方式也就是线性表的顺序存储的方式，也就是我们接下来要讲的顺序栈，因此顺序栈的实现形式也就是线性表顺序存储的实现形式-数组。因...
2020-09-22 12:07:51
258
原创 万事俱备，只欠东风：栈与队列的应用
1 栈的应用栈在很多面试的问题中都会被问到，其实按照我的理解栈的应用就是递归的应用。所以接下来将会介绍一些有关栈的应用，当你看到这些应用，会有一种感觉：这特么不就是递归吗？OK，话不多说，开始栈的应用1.1 递归栈在程序设计中具有非常广泛的应用，其中递归的应用是求职者必须知道的。在此之前我们先了解一下递归，然后再解释如何应用栈实现递归。递归的概念想必大家都看过《盗梦空间》，主人公在梦里...
2020-09-22 12:07:49
232
原创 尺有所短，寸有所长：算法性能衡量的好坏
排序问题一直是计算机还有面试中常见到的知识点，排序算法的好坏能影响到系统的性能，本文将循序渐进、图文并茂的方式讲解常见的排序算法，然后分析各算法的时间复杂度、空间复杂度等情况，之后结合实际应用讲解面试中常问的点。章节主要细分如下：尺有所短，寸有所长——算法性能衡量的好坏柿子先挑软的捏——基础排序算法直挂云帆济沧海——排序算法进阶纸上得来终觉浅，绝知此事要躬行——排序算法性能比较与实际应用...
2020-09-22 12:07:48
109
原创 柿子先挑软的捏：基础排序算法
笔者在写到这一部分的时候，就在思考怎么去讲解才最大化读者的需要。从面试的经验来看，对于排序算法只需要掌握比较重要的几种，但是对于知识面的拓展上来说又不得不了对所有的排序算法有所了解。排序应用于开发中，我们的业务无时无刻不跟排序有关，往往处理数据的时候第一步就是排序，下面将对排序进行详细的介绍。1. 选择排序概念：对于给定的一组记录，经过第一轮之后得到最小的元素，然后将该记录与第一个记录的位置进...
2020-09-22 12:07:46
229
原创 进阶硬菜——排序算法进阶
下面这一章所讲解到算法将是最精彩和有趣的，涉及到的算法思路将会在你以后的代码中经常使用；讲解到的算法有归并排序、快速排序、堆排、桶排序。1. 归并排序归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治策略（divide-and-conquer）：分治法将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案“修补...
2020-09-22 12:07:44
100
原创 纸上得来终觉浅，绝知此事要躬行——排序算法性能比较与实际应用
1. 算法重温下面我们将带大家重新熟悉下排序算法。插入排序插入排序是一种较为简单的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。形象的可以理解为打扑克抓牌的过程，通常我们右手抓牌，没抓一张牌，就放到左手，抓下一张牌后，会把这张牌依次与左手上的牌比较，并把它插入到一个合适的位置（按牌面大小）。选择排序选择排序的排序思想就和它的...
2020-09-22 12:07:43
65
原创 千树万树梨花开：二叉树的实现以及存储结构
前面我们讲的所有的数据结构都是线性表结构，栈、队列等等。现在我们来讲一种非线性表结构——树。树这种数据结构比线性表的数据结构要复杂得多，内容也比较多，其应用也十分的广泛。在正式的内容开始之前，我想先问大家一个问题：我们为什么需要二叉树？带着这个问题，我们就来学习今天的内容吧！1. 为什么需要树这种数据结构客观世界中许多事务存在层次关系，比如说社会组织结构以及信息管理等，这种分层次的组织被证...
2020-09-22 12:07:41
101
原创 往来行旅才纷纭：二叉树的四大遍历方法
树遍历是对树中的每个节点只访问一次的过程。我们一提到树这一数据结构，很多人首先想到的就是树的遍历。这是因为，不管是在老师讲述树这一数据结构时，还是在面试时，亦或是在实际应用中，二叉树的遍历都是反复会出现的。我们常说二叉树这种数据结构是优雅的，抛开实用方面不谈，多种多样二叉树的遍历方法完美的展现了这一点。不同的遍历方法把树的节点展开成列表的方式，而每种遍历方法都能从树中更加直观的提取出来一些信息。...
2020-09-22 12:07:40
92
原创 众里寻他千百度：二叉查找树的优势
前面我们在讲述树之前，为大家介绍了二分查找这一个重要的算法。我们知道，二分查找适合对固定不变的数据进行查找，那如果要去查询的数据是不断变化的呢？我们知道，链表这种数据结构可以灵活的插入和删除数据，所以动态数据的存储适合采用链表这种数据结构；有序数组可以使用二分查找算法来高效地实现数据查找；那么将链表插入、删除的灵活性以及有序数组查找的高效性结合起来就产生了二叉查找树这种数据结构，二叉查找树以及伴...
2020-09-22 12:07:38
365
原创 轻重在平衡：平衡查找树的强大威力
1. 有了查找二叉树，为什么还需要平衡二叉树上一节我们讲述了查找二叉树，对于二叉查找树来说，其查找效率十分依赖于树中节点的拓扑结构，也就是节点间的布局关系。举一个例子，下图描绘了一个节点插入顺序为 1、2、3、4、5 的查找二叉树。这些节点是按照递升顺序被插入的，如果这样，那么这颗查找二叉树的拓扑结构其实就是将节点排布在一条线上，而不是以扇形结构散开，再查找某个值的时候，运行时间就会退减到线性时...
2020-09-22 12:07:37
82
原创 太极定二仪，清浊始以形：红黑树的实现和性质
我们在前面的章节中讲述了平衡二叉查找树，也就是叶节点高度差的绝对值不超过 1，并且左右两个子树都是一颗平衡树。最早被发明的是平衡二叉查找树是 AVL 树，后面红黑树才被发明。AVL 树在每次的插入和删除时都要进行调整，会比较耗时。所以 AVL 树就不适合应用于频繁插入、删除的数据集。至于红黑树，在这方面相较于 AVL 树会有一些优势，其在插入、删除、查找等各种操作的性能都比较稳定。对于工程应用，...
2020-09-22 12:07:35
260
原创 芳树千株发：B+、B- 树的实现和性质
在数据库系统的使用过程当中，数据的查询是使用最频繁的一种数据操作。基本的查询算法当然是顺序查找（linear search），遍历表然后逐行匹配行值是否等于待查找的关键字，其时间复杂度为 O(n)。但时间复杂度为 O(n) 的算法规模小的表，负载轻的数据库，也能有好的性能。 但是数据增大的时候，时间复杂度为 O(n) 的算法显然是糟糕的，性能就很快下降了。那么，应用在数据库中的查找是什么呢？我们...
2020-09-22 12:07:33
148
原创 万家杨柳青烟里：B+、B- 树的应用场景
1. 每一种数据结构都有它的使命正如链表可以构成缓存容器实现数据的暂时存放，B+、B- 树更多的被用来作为数据库搜索引擎的索引提高读取效率，例如：MySQL 的 InnonDB 用 B+ 树结构做索引；MySQL 的 MyISAM 引擎以及 MongoDB 用 B- 树作为索引。1.1 为什么在数据库中使用索引？假设您需要在文件中存储数字列表，然后在该列表中搜索给定的数字。最简单的解决方案是...
2020-09-22 12:07:32
105
原创 一览众山小：专栏总结和我们过往经验分享
这篇文章是我们本专栏的最后一篇文章，其内容包含了对整个专栏的一个总结以及对数据结构和算法的一些思考。数据结构和算法是计算机世界的一颗璀璨明珠，是一代又一代计算机行业的从业者智慧的结晶。学习数据结构不能仅仅将其作为笔试、面试以及考试的工具，而是要把数据结构和算法应用到实际的学习和工作中去，解决实际的开发问题。但是，很多人都觉得在实际的工作总中几乎不用费心地去考虑程序中和数据结构相关的问题，或者说...
2020-09-22 12:07:30
120
原创 leetcode 43 Multiply Strings
题目描述Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.举例Input: num1 = “123”, num2 = “456”Output: “56088”备注T...
2019-11-19 21:51:21
111
原创 leetcode18 4Sum
题目描述Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum o...
2019-11-15 22:51:52
95
原创 Ubuntu修改用户名导致密码无效问题
很多使用ubuntu的小伙伴可能会想要修改自己的用户名。在修改用户名过程中，如果你没有切换到root权限，而只是执行sudo vim /etc/paaawd，那么在修改了/etc/passwd这个文件中的用户名部分、用户组部分和主目录部分之后，如果你退出了，那么修改了用户名之后与密码无法匹配，退出系统更是再也登录不上，也无法切换到root权限。针对这一问题，有人说要重装系统，其实不需要，现给出解...
2019-08-26 19:48:02
3910
原创 LeetCode 24. Swap Nodes in Pairs（成对交换单链表的结点）
题目描述Given a linked list, swap every two adjacent nodes and return its head.You may not modify the values in the list’s nodes, only nodes itself may be changed.示例输入： 1->2->3->4输出： 2->1...
2019-07-16 22:35:48
121
原创 清晰易懂地介绍KMP算法
清晰易懂地介绍KMP算法一个简单的假设例子：正文： …模式字符串： B A A A A其中，正文长度为N，模式字符串长度为M，一般来说N>>M。我们先来做一个假设，假设正文中仅有A和B两个字符组成。那么如果第五个字符匹配失败，可知正文对应部分肯定为B A A A B。那么此时，我们没有必要去回退文本指针i，因为正文对应部分的第2-4个字符均为A,都和模式字符串的第一个字符...
2019-05-09 22:09:30
260
转载 SVD原理及推导
转载于：http://blog.csdn.net/zhongkejingwang/article/details/43053513在网上看到有很多文章介绍SVD的，讲的也都不错，但是感觉还是有需要补充的，特别是关于矩阵和映射之间的对应关系。前段时间看了国外的一篇文章，叫A Singularly Valuable Decomposition The SVD of a Matrix，觉得分析的特别好...
2019-03-05 21:15:11
435
原创 临界区和互斥量
对于windows，临界区（critical sections ）比 互斥量（mutexes） 更加轻量级（lighter-weight）。互斥量可以在进程之间共享，但总是会导致对内核的系统调用，这会带来一些开销。当一个进程进入临界区，没有其他进程可被允许在临界区执行，即没有两个进程可同时在临界区内执行。其优点是在多进程抢占的情况下只能切换到内核模式。通过对多线程的串行化来访问公共资源或一段代...
2018-11-06 22:25:51
426
原创 Mirror Tree
Given a Binary Tree, convert it into its mirror.分析：程序分为3个大的部分。什么情况下可以结束交换左右节点递归 private TreeNode mirrorRecursively(TreeNode root1) { if(root1 == null || (root1.left==null && root1.ri...
2018-11-05 09:41:58
356
原创 Median of Two Sorted Arrays
这是leetcode上的一道题目。求这两个以排序数组的中位数。分析：第一步：先根据2个数组加起来的总长度是奇数还是偶数来判断最终的中位数是一个数还是2个数相加取平均值。第二步：设置2个指针，分别指向这两个数组的起始位置。然后不断进行比较这两个指针指向的值以更新这两个指针（下面程序已经有说明）。需要注意的是当指针指到数组末尾时该如何操作。注：另外返回的时double型的结果。返回的结果要 ...
2018-10-25 16:27:59
111
原创 Code 排列小球（Ways to arrange Balls such that adjacent balls are of different types）
举例：input: 2 1 1output: 6使用递归的方法来求解：public class Main { // Returns count of arrangements // where last placed ball is // 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r' stati...
2018-10-24 12:13:56
518
1
原创 synchronized锁住了谁
先来看一段代码public class MultiThread { private static int num = 0; /** static */ public synchronized void printNum(String tag){ try { if(tag.equals("a")){ num = 200; System.out.pri...
2018-10-24 10:18:30
279
原创 数据库锁
无论何时，只要有多个查询需要在同一时刻修改数据，都会产生并发控制问题。下面讨论MySQL在2个层面上的并发控制：服务器层和存储引擎层。在处理并发读或写的时候，可以通过实现一个由两种类型的锁组成的锁系统来解决问题：共享锁和排他锁（读锁和写锁）。一种提高共享资源并发性的方式是让锁定的对象更有选择性，尽量只锁定需要修改的部分，而不是所有的资源。下面介绍MySQL的两种最重要的锁策略：表锁：开销...
2018-10-23 23:01:07
97
原创 操作系统的基本概念
操作系统通过引入进程和线程，使得程序可以并发运行。几种进程或线程同步互斥的控制方法：临界区：通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。互斥共享的资源称为临界资源（每次仅仅允许一个进程访问的资源）。每个进程中访问临界资源的那段代码成为临界区。互斥量（Mutex） ：互斥量跟临界区很相似，只有拥有互斥对象的线程才具有访问资源的权限。不同的是——使用互斥不仅仅能够...
2018-10-23 20:47:03
1545
原创 分布式一致性
分布式系统不可能同时满足一致性，可用性和分区容忍性，最多只能同时满足其中的二项。其中，网络分区指的是分布式系统中的节点被划分为多个区域，每个区域内部可以通信，但是区域之间无法通信。在分区容忍性条件下，分布式系统在遇到任何网络分区故障时，仍然需要对外提供一致性和可用性服务，除非整个网络环境发生了故障。另外，可用性和一致性往往是冲突的。为了保证一致性，需要让所有的节点下线成为不可用状态，等待同...
2018-10-23 16:26:35
333
原创 TCP协议的Time_Wait
首先，TIME_WAIT并不是多余的。在TCP协议被创造，经历了大量的实际场景实践之后，TIME_WAIT出现了，因为TCP主动关闭连接的一方需要TIMEWAIT状态，它是我们的朋友。为什么需要TIme_WaitTCP协议要保证在所有可能的情况下使得所有的数据都能够被正确送达。当你关闭一个socket时，主动关闭一端的socket将进入TIME_WAIT状态，而被动关闭一方则转入CLOSED状...
2018-10-20 11:24:10
372
原创 强一致性算法
分布式系统对fault tolorence的一般解决方案是state machine replication主从同步复制Master接受写请求Master复制日志到SlaveMaster等待，直到所有从库返回问题：一个节点失败，Master阻塞，导致整个集群不可用，保证了一致性，可用性大大降低。多数派每次写入保证写入大于N/2个节点 每次读保证从大于N/2个节点读问题：在并发环...
2018-10-15 15:28:06
1498
原创 索引背后的原理
MySQL的官方定义：索引是帮助MySQL高效获取数据的数据结构。查询时数据库最主要的功能，我们都希望查询数据的速度可以尽可能地快。在数据之外，数据库系统还维护着满足特定查找算法地数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引...
2018-10-11 22:21:07
200
原创 Hash索引
Hash索引的检索效率很高，可以一次定位。其查询效率远远高于B+树索引。但是，Hash索引还有很多弊端。Hash索引仅仅支持"=",“IN"和”<=>"查询，不支持范围查询。经过响应的Hash算法处理之后的Hash值的大小关系，不能保证和Hash运算前完全一致。Hash索引不能利用部分索引键查询。对于组合索引，Hash索引在计算Hash值的时候是组合索引键何合并之后再一起计算...
2018-10-11 15:58:55
218
原创 垃圾回收机制
垃圾回收机制将垃圾回收机制，我想先从JVM的运行时数据区开始讲起。JVM的运行时数据区程序计数器可以看作是当前程序所执行的字节码的行号指示器。java虚拟机的多线程是通过线程轮流切换并分配处理器执行时间的方式来实现的。在任何一个确定的时刻，一个处理器（对于多核处理器来说是一个内核）都只会执行一条线程中的命令。因此，为了线程切换之后能够恢复到正确的执行位置，每个线程需要一个独立的程序计数器。...
2018-10-09 22:21:43
112
原创 问答
1.什么是RPCremote produce call——远程过程调用，其是一种通过网络向远程计算机请求服务，不需要了解底层网络技术的协议。本地过程调用机制在RPC调用中是不可行的，因为编译器无法通过编译的方法实现远程过程调用机制。RPC的远程调用是构建在语言级别的，必须使用Socket通信完成。我们将现有的本地方法调用和Socket网络通信技术相结合来模拟实现透明的远程过程调用。实现...
2018-09-19 22:36:53
200
原创 TCP的重点机制
TCP对应用程序一次把多长的报文传递给TCP的缓存是不关心的。TCP根据接收方的窗口大小和当前网络的拥塞程度决定一个报文端应该包含多少个字节。可靠传输的工作原理TCP以下的网络提供的是不可靠的传输。理想的传输条件是：1.传输信道不产生差错2.不管发送方发送的速度，接收方总是来得及处理收到的数据。为了尽可能达到理想条件，设计了以下机制。停止等待（不实际使用）：1.超时重传...
2018-09-17 17:17:15
263
原创 socket编程演进
1. 单线程的服务器，每次只能处理一个requestimport java.io.IOException;import java.net.ServerSocket;import java.net.Socket;import java.util.Scanner;public class Server { public static void main(String[]...
2018-09-14 09:28:33
133
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人