程序员小灰_社区达人页

2022年04月

• 04.29 13:15:22
  发表了文章 2022-04-29 13:15:22

  漫画：什么是 “哈夫曼树” ？

  哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明，这到底是一颗什么样的树呢？ 刚才我们学习了树的带权路径长度（WPL），而哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。 举个例子，给定权重分别为1，3，4，6，8的叶子结点，我们应当构建怎样的二叉树，才能保证其带权路径长度最小？ 原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。

  
• 04.29 13:06:57
  发表了文章 2022-04-29 13:06:57

  漫画：什么是KMP算法？

  KMP算法和BF算法的“开局”是一样的，同样是把主串和模式串的首位对齐，从左到右对逐个字符进行比较。
• 04.29 12:58:02
  发表了文章 2022-04-29 12:58:02

  漫画：如何优化 “字符串匹配算法”？

  BF算法是如何工作的？ 正如同它的全称BruteForce一样，BF算法使用简单粗暴的方式，对主串和模式串进行逐个字符的比较。

  
• 04.29 12:50:37
  发表了文章 2022-04-29 12:50:37

  漫画：什么是字符串匹配算法？

  比较哈希值是什么意思呢？ 用过哈希表的朋友们都知道，每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是hashcode： hashcode = hash（string） 显然，相对于逐个字符比较两个字符串，仅比较两个字符串的hashcode要容易得多。

  
• 04.26 22:07:56
  发表了文章 2022-04-26 22:07:56

  漫画：什么是 HTTPS 协议？

  HTTP协议全称Hyper Text Transfer Protocol，翻译过来就是超文本传输协议，位于TCP/IP四层模型当中的应用层。 HTTP协议通过请求/响应的方式，在客户端和服务端之间进行通信。

  
• 04.26 21:59:30
  发表了文章 2022-04-26 21:59:30

  漫画：“排序算法” 大总结

  冒泡排序： 漫画：什么是冒泡排序？ 选择排序： 漫画：什么是选择排序？ 插入排序： 漫画：什么是插入排序？ 此外还有冒泡排序的变种，鸡尾酒排序： 漫画：什么是鸡尾酒排序？

  
• 04.26 21:26:18
  发表了文章 2022-04-26 21:26:18

  漫画：三种 “奇葩” 的排序算法

  介绍三种“异想天开”的排序算法。

  
• 04.26 21:20:28
  发表了文章 2022-04-26 21:20:28

  漫画：什么是基数排序？

  数组每一个下标位置的值，代表了数列中对应整数出现的次数。 有了这个“统计结果”，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次： 0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10 显然，这个输出的数列已经是有序的了。 这就是计数排序的朴素版本。

  
• 04.26 21:14:36
  发表了文章 2022-04-26 21:14:36

  漫画：去掉一个数，如何让剩余的数乘积最大？

  举个例子，给定如下数组：要删除哪个元素，才能使得剩余元素的乘积最大呢？

  
• 04.26 21:08:44
  发表了文章 2022-04-26 21:08:44

  漫画：什么是归并排序？

  举个例子，有A、B、C、D、E、F、G、H一共8个武术家参考参加比武大会。 第一轮，两两一组，有4名选手胜出（四分之一决赛） 第二轮，两两一组，有两名选手胜出（半决赛） 第三轮，仅剩的两人一组，冠军胜出（总决赛）

  
• 04.26 21:03:07
  发表了文章 2022-04-26 21:03:07

  漫画：什么是希尔排序？

  像这样逐步分组进行粗调，再进行直接插入排序的思想，就是希尔排序，根据该算法的发明者，计算机科学家Donald Shell的名字所命名。 上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，增量的选择可以有很多种，我们在示例中所用的逐步折半的增量方法，是Donald Shell在发明希尔排序时提出的一种朴素方法，被称为希尔增量。

  
• 04.26 20:55:07
  发表了文章 2022-04-26 20:55:07

  漫画：什么是旅行商问题？

  和小灰所遇到的问题类似，旅行商问题所描述的是这样一个场景： 有一个商品推销员，要去若干个城市推销商品。该推销员从一个城市出发，需要经过所有城市后，回到出发地。每个城市之间都有道路连通，且距离各不相同，推销员应该如何选择路线，使得总行程最短呢？

  
• 04.26 20:51:06
  发表了文章 2022-04-26 20:51:06

  漫画：如何找到两个数组的中位数？（修订版）

  对于偶数长度的数组，可以根据中位数分成长度相等的两部分，左半部分最大元素（6），永远小于等于右半部分的最小元素（7）。 对于奇数长度的数组，同样可以根据中位数分成两部分：

  
• 04.26 20:44:04
  发表了文章 2022-04-26 20:44:04

  漫画：什么是插入排序？

  人们如何进行扑克牌的排序呢？ 举个例子，比如我手中有红桃6,7,9,10这四张牌，已经处于升序排列：这时候，我又抓到了一张红桃8，如何让手中的五张牌重新变成升序呢？用冒泡排序，选择排序，亦或是快速排序？

  
• 04.26 20:37:48
  发表了文章 2022-04-26 20:37:48

  漫画：什么是选择排序？

  我们假定要获得升序数列，冒泡排序的原理是什么呢？ 顾名思义，就是把每一元素和下一个元素进行比较和交换，使得较大的元素像气泡一样向右侧移动：

  
• 04.26 20:31:26
  发表了文章 2022-04-26 20:31:26

  漫画：什么是最小生成树？

  它的最小生成树是什么样子呢？下图绿色加粗的边可以把所有顶点连接起来，又保证了边的权值之和最小，去掉那些多余的边，该图的最小生成树如下。

  
• 04.26 20:25:59
  发表了文章 2022-04-26 20:25:59

  漫画：“旋转数组”中的二分查找

  旋转点是什么呢？我们这里规定，假设旋转有序数组恢复为普通有序数组，位于普通有序数组第一个位置的元素，就是旋转数组的旋转点。 直白地说，旋转点就是旋转数组中最小的元素：

  
• 04.26 20:19:14
  发表了文章 2022-04-26 20:19:14

  漫画：什么是二分查找？（修订版）

  如果我们把场景转换成最初的面试问题：在包含1000个整型元素的有序数组中查找某个特定整数，又该如何去做呢？

  
• 04.26 20:13:06
  发表了文章 2022-04-26 20:13:06

  漫画：有趣的 “切蛋糕“ 问题

  给定蛋糕大小的集合cakes，给定顾客饭量的集合mouths，如何计算出这些蛋糕可以满足的最大顾客数量？

  
• 04.26 20:04:20
  发表了文章 2022-04-26 20:04:20

  漫画：图的 “多源” 最短路径

  下面我们来看一看Floyd算法的详细步骤。

  
• 04.26 19:57:07
  发表了文章 2022-04-26 19:57:07

  漫画：Dijkstra 算法的优化

  如何求得最短路径的详细节点，而不仅仅是距离？

  
• 04.26 19:51:48
  发表了文章 2022-04-26 19:51:48

  漫画：图的 “最短路径” 问题

  究竟什么是迪杰斯特拉算法？它是如何寻找图中顶点的最短路径呢？ 这个算法的本质，是不断刷新起点与其他各个顶点之间的 “距离表”。 让我们来演示一下迪杰斯特拉的详细过程。

  
• 04.26 19:45:22
  发表了文章 2022-04-26 19:45:22

  漫画：深度优先遍历 和 广度优先遍历

  深度优先遍历简称DFS（Depth First Search），广度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种方式。

  
• 04.26 19:38:18
  发表了文章 2022-04-26 19:38:18

  漫画：什么是 “图”？（修订版）

  微信中，许许多多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构当中的图（Graph）。

  
• 04.26 19:32:55
  发表了文章 2022-04-26 19:32:55

  漫画：什么是加密算法？

  如何进行加密呢？古人想出了一种非常朴素的加密方法，被称为凯撒密码。加密的原理就像下图这样。

  
• 04.26 19:27:51
  发表了文章 2022-04-26 19:27:51

  漫画：如何将一个链表“逆序”？

  让我们从链表头部开始，建立三个临时节点的引用，分别为p1，p2，p3。它们分别指向头节点、第二个节点、第三个节点。

  
• 04.26 19:21:12
  发表了文章 2022-04-26 19:21:12

  漫画：寻找无序数组的第k大元素（修订版）

  题目是什么意思呢？比如给定的无序数组如下： 如果 k=6，也就是要寻找第6大的元素，这个元素是哪一个呢？ 显然，数组中第一大的元素是24，第二大的元素是20，第三大的元素是17 ...... 第6大的元素是9。

  
• 04.25 22:45:54
  发表了文章 2022-04-25 22:45:54

  漫画：如何用Zookeeper实现分布式锁？

  1.持久节点 （PERSISTENT） 默认的节点类型。创建节点的客户端与zookeeper断开连接后，该节点依旧存在 。 2.持久节点顺序节点（PERSISTENT_SEQUENTIAL） 所谓顺序节点，就是在创建节点时，Zookeeper根据创建的时间顺序给该节点名称进行编号：

  
• 04.25 22:37:26
  发表了文章 2022-04-25 22:37:26

  漫画：什么是分布式锁？

  分布式锁的实现有哪些？ 1.Memcached分布式锁 利用Memcached的add命令。此命令是原子性操作，只有在key不存在的情况下，才能add成功，也就意味着线程得到了锁。 2.Redis分布式锁 和Memcached的方式类似，利用Redis的setnx命令。此命令同样是原子性操作，只有在key不存在的情况下，才能set成功。（setnx命令并不完善，后续会介绍替代方案）

  
• 04.25 22:27:16
  发表了文章 2022-04-25 22:27:16

  漫画：什么是ZooKeeper？

  Zookeeper的数据模型，Zookeeper的数据模型是什么样子呢？它很像数据结构当中的树，也很像文件系统的目录。 树是由节点所组成，Zookeeper的数据存储也同样是基于节点，这种节点叫做Znode。 但是，不同于树的节点，Znode的引用方式是路径引用，类似于文件路径。

  
• 04.25 22:16:34
  发表了文章 2022-04-25 22:16:34

  漫画：什么是蓝绿部署？

  什么是蓝绿部署？ 蓝绿部署，英文名Blue Green Deployment，是一种可以保证系统在不间断提供服务的情况下上线的部署方式。 如何保证系统不间断提供服务呢？ 蓝绿部署的模型中包含两个集群，就好比海豚的左脑和右脑。

  
• 04.25 22:07:39
  发表了文章 2022-04-25 22:07:39

  漫画：什么是分布式事务？

  什么是分布式事务？分布式事务用于在分布式系统中保证不同节点之间的数据一致性。分布式事务的实现有很多种，最具有代表性的是由Oracle Tuxedo系统提出的XA分布式事务协议。

  
• 04.25 21:55:56
  发表了文章 2022-04-25 21:55:56

  漫画：什么是服务熔断？

  熔断这一概念来源于电子工程中的断路器（Circuit Breaker）。在互联网系统中，当下游服务因访问压力过大而响应变慢或失败，上游服务为了保护系统整体的可用性，可以暂时切断对下游服务的调用。

  
• 04.25 21:47:32
  发表了文章 2022-04-25 21:47:32

  漫画：什么是数据仓库？

  数据库和数据仓库之间的关系。如果说，那个世界的每一个生命个体都是一条数据记录，那么普通的魔戒的地位就好比是数据库，而至尊魔戒的地位就好比是数据仓库。

  
• 04.25 21:31:48
  发表了文章 2022-04-25 21:31:48

  漫画：什么是微服务？

  缺点一：项目过于臃肿，当大大小小的功能模块都集中在同一项目的时候，整个项目必然会变得臃肿，让开发者难以维护。 缺点二：资源无法隔离，就像刚刚小灰的经历一样，整个单体系统的各个功能模块都依赖于同样的数据库、内存等资源，一旦某个功能模块对资源使用不当，整个系统都会被拖垮。

  
• 04.25 21:23:07
  发表了文章 2022-04-25 21:23:07

  漫画：什么是协程？

  什么是进程和线程有一定基础的小伙伴们肯定都知道进程和线程。 进程是什么呢？直白地讲，进程就是应用程序的启动实例。比如我们运行一个游戏，打开一个软件，就是开启了一个进程。 进程拥有代码和打开的文件资源、数据资源、独立的内存空间。

  
• 04.25 21:13:10
  发表了文章 2022-04-25 21:13:10

  漫画：什么是CAS机制？（进阶篇）

  这一期我们来深入介绍之前遗留的两个问题：1. Java当中CAS的底层实现2. CAS的ABA问题和解决方法.

  
• 04.25 16:51:51
  发表了文章 2022-04-25 16:51:51

  漫画：什么是 CAS 机制？

  加了同步锁之后，count自增的操作变成了原子性操作，所以最终的输出一定是count=200，代码实现了线程安全。

  
• 04.25 16:39:51
  发表了文章 2022-04-25 16:39:51

  漫画：如何实现大整数相乘？（整合版）

  大整数相乘又是如何实现的呢？ 起初，小灰认为只要按照大整数相加的思路稍微做一下变形，就可以轻松实现大整数相乘。但是随着深入的学习，小灰才发现事情并没有那么简单......

  
• 04.25 16:22:16
  发表了文章 2022-04-25 16:22:16

  漫画：如何实现大整数相加？（修订版）

  本周一发布的漫画，存在一些细节上的问题，在这里做出如下修改：1.修改了代码中进位判断条件的bug，优化了部分代码的可读性。2.增加了JDK工具类BigInteger和BigDecimal的说明。3.补充了一个优化方法，即把大整数拆分成数组时，按十进制每9位拆分，而非每1位拆分。把整数倒序存储，整数的个位存于数组0下标位置，最高位存于数组长度-1下标位置。之所以倒序存储，更加符合我们从左到右访问数组的习惯。

  
• 04.25 16:03:09
  发表了文章 2022-04-25 16:03:09

  漫画：删去k个数字后的最小值

  举例：给定整数1593212，删去3个数字，新整数的最小情况是1212给定整数30200，删去1个数字，新整数的最小情况是200，给定整数10，删去2个数字，新整数的最小情况是0，需要注意的是，给定的整数大小可以超过long类型的范围，所以需要用字符串来表示。

  
• 04.25 15:47:58
  发表了文章 2022-04-25 15:47:58

  漫画：什么是LRU算法？

  用户信息当然是存在数据库里。但是由于我们对用户系统的性能要求比较高，显然不能每一次请求都去查询数据库。 所以，小灰在内存中创建了一个哈希表作为缓存，每次查找一个用户的时候先在哈希表中查询，以此提高访问性能。

  
• 04.25 15:09:17
  发表了文章 2022-04-25 15:09:17

  漫画：如何用栈实现队列？

  既然我们拥有两个栈，那么我们可以让其中一个栈作为队列的入口，负责插入新元素；另一个栈作为队列的出口，负责移除老元素。队列的主要操作无非有两个：入队和出队。在模拟入队操作时，每一个新元素都被压入到栈A当中。

  
• 04.25 14:55:35
  发表了文章 2022-04-25 14:55:35

  漫画：什么是桶排序？

  让我们先来回顾一下计数排序： 计数排序需要根据原始数列的取值范围，创建一个统计数组，用来统计原始数列中每一个可能的整数值所出现的次数。

  
• 04.25 14:46:40
  发表了文章 2022-04-25 14:46:40

  漫画：什么是计数排序？

  如何给无序的随机整数排序呢？ 非常简单，让我们遍历这个无序的随机数列，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。 比如第一个整数是9，那么数组下标为9的元素加1

  
• 04.25 14:32:35
  发表了文章 2022-04-25 14:32:35

  漫画：什么是优先队列？

  队列的特点是什么？聪明的小伙伴们都知道，是先进先出（FIFO）。那么，优先队列又是什么样子呢？ 优先队列不再遵循先入先出的原则，而是分为两种情况： 最大优先队列，无论入队顺序，当前最大的元素优先出队。 最小优先队列，无论入队顺序，当前最小的元素优先出队。

  
• 04.25 14:23:27
  发表了文章 2022-04-25 14:23:27

  漫画：什么是堆排序？

  在上一篇漫画中，小灰介绍了 二叉堆 这样一种强大的数据结构： 漫画：什么是二叉堆？（修正版） 那么，这个二叉堆怎样来使用呢？我们这一期将会详细讲述。

  
• 04.25 14:13:09
  发表了文章 2022-04-25 14:13:09

  漫画：什么是二叉堆？（修正版）

  什么是二叉堆？二叉堆本质上是一种完全二叉树，它分为两个类型：1.最大堆2.最小堆 什么是最大堆呢？最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

  
• 04.24 23:21:10
  发表了文章 2022-04-24 23:21:10

  漫画：什么是时间复杂度？

  时间复杂度的意义，究竟什么是时间复杂度呢？让我们来想象一个场景：某一天，小灰和大黄同时加入了一个公司......一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒，内存占用5MB。小灰的代码运行一次要花100秒，内存占用500MB。

  
• 04.24 23:09:11
  发表了文章 2022-04-24 23:09:11

  漫画：什么是快速排序？（完整版）

  同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。