算法笔记 第12页

目录 1. 交换排序——冒泡排序 2. 交换排序——快速排序 3. 选择排序——简单选择排序 4. 选择排序——堆排序 什么是堆 堆排序基本思想 步骤图解 代码实现 5. 插入排序——简单插入排序 6. 插入排序——希尔排序 7. 归并排序...

赞(1)菜鸟2021-12-27阅读(3981)

观察题目示例，序列化的字符串实际上是二叉树的 “层序遍历”（BFS）结果，本文也采用层序遍历。 通常使用的前序、中序、后序、层序遍历记录二叉树的信息不完整，即可能对应着多种二叉树结果。 题目要求的 “序列化” 和 “反序列化” 是 可逆 操...

赞(1)菜鸟2021-03-28阅读(2697)

前序遍历： 节点-左子树-右子树（中-左-右） 中序遍历： 左子树-节点-右子树（左-中-右） 后续遍历： 左子树-右子树-节点（左-右-中） 数据结构 // Definition for a binary tree node. struc...

赞(1)菜鸟2021-03-28阅读(2934)

前缀树 特点就是利用空间换时间，通过利用前缀存储的方法达到高效的查找效率。 3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点...

赞(1)菜鸟2021-03-28阅读(3240)

快排思路实现 有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。 class Finder { public: int fin...

赞(1)菜鸟2021-03-28阅读(2661)

蓄水池抽样算法简介 蓄水池抽样算法是随机算法的一种，用来从N个样本中随机选择K个样本，其中N非常大（以至于N个样本不能同时放入内存）或者N是一个未知数。其时间复杂度为O(N)，包含下列步骤 (假设有一维数组 S, 长度未知，需要从中随机选择...

赞(1)菜鸟2021-03-20阅读(5829)

令A[1…n]是一个整数数列，A中的整数a如果出现的次数多于[n/2]，那么称a为多数元素。 有一个比较漂亮的求解法，我们用归纳法导出这个算法，这个算法的实质是基于下面的观察结论。 观察结论：在原序列中去除两个不同的元素后，那么...

赞(1)菜鸟2021-01-16阅读(2541)

类快排算法 leetcode215 由于只要求找出第k大的数，没必要将数组中所有值都排序。 快排中的partition算法，返回key在数组中的位置的cnt（相对于left的偏移量），如果cnt正好等于k，那么问题则得到解决；如果cnt小于...

赞(1)菜鸟2021-01-16阅读(2142)

一致性Hash算法背景 　　一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算...

赞(1)菜鸟2021-01-09阅读(2616)

什么情况下需要布隆过滤器？ 先来看几个比较常见的例子 字处理软件中，需要检查一个英语单词是否拼写正确 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里，一个网址是否被访问过 yahoo, gmail等邮箱垃圾邮件过滤功能 这几...

赞(1)菜鸟2021-01-09阅读(3716)