3
推荐
1454
阅读
【LeetCode题解】排序
1. 排序排序（sort）是一种常见的算法，把数据根据特定的顺序进行排列。经典的排序算法如下：冒泡排序（bubble sort）插入排序（insertion sort）选择排序（selection sort）快速排序（quick sort）堆排序（heap sort）归并排序（merge sort）冒泡排序依次比较相邻的两个元素，若逆序则交换；如此走访数列重复n次，即不...
0
推荐
1327
阅读
【LeetCode题解】链表Linked List
1. 链表数组是一种顺序表，index与value之间是一种顺序映射，以O(1)的复杂度访问数据元素。但是，若要在表的中间部分插入（或删除）某一个元素时，需要将后续的数据元素进行移动，复杂度大概为O(n)。链表（Linked List）是一种链式表，克服了上述的缺点，插入和删除操作均不会引起元素的移动；数据结构定义如下：public ...
0
推荐
1306
阅读
【LeetCode题解】数组Array
1. 数组直观地看，数组（Array）为一个二元组<index, value>的集合——对于每一个index，都有一个value与之对应。C语言中，以“连续的存储单元”实现数组：int arr[5], *p_arr[5];数组提供以O(1)O(1)的复杂度访问元素，下标从0开始。但是，数组的插入、删除操作却非常耗时，因为这涉及到了元素间的移动。常见的矩阵，...
0
推荐
1466
阅读
【LeetCode题解】二叉树的遍历
我准备开始一个新系列【LeetCode题解】，用来记录刷题，顺便复习一下数据结构与算法。1. 二叉树二叉树（binary tree）是一种极为普遍的数据结构，树的每一个节点最多只有两个节点——左孩子结点与右孩子结点。C实现的二叉树：struct TreeNode {
int val;
struct TreeNode *left; // left child
struct TreeNod...
1
推荐
1577
阅读
整数压缩编码 ZigZag
在分析Avro源码时，发现Avro为了对int、long类型数据压缩，采用Protocol Buffers的ZigZag编码（Thrift也采用了ZigZag来压缩整数）。1. 补码编码为了便于后面的分析，我们先回顾下几个概念：原码：最高位为符号位，剩余位表示绝对值；反码：除符号位外，对原码剩余位依次取反；补码：对于正数，补码为其自身；对于负数，...
0
推荐
1758
阅读
【数据压缩】LZ78算法原理及实现
在提出基于滑动窗口的LZ77算法后，两位大神Jacob Ziv与Abraham Lempel于1978年在发表的论文 [1]中提出了LZ78算法；与LZ77算法不同的是LZ78算法使用动态树状词典维护历史字符串。【数据压缩】LZ77算法原理及实现【数据压缩】LZ78算法原理及实现1. 原理压缩LZ78算法的压缩过程非常简单。在压缩时维护一个动态词典Dictionar...
3
推荐
1745
阅读
【数据压缩】LZ77算法原理及实现
1. 引言【数据压缩】LZ77算法原理及实现【数据压缩】LZ78算法原理及实现LZ77算法是采用字典做数据压缩的算法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年发表的论文《A Universal Algorithm for Sequential Data Compression》中提出。基于统计的数据压缩编码，比如Huffman编码，需要得到先验知识——信源的字...
0
推荐
1489
阅读
【数据压缩】Huffman编码
1. 压缩编码概述数据压缩在日常生活极为常见，平常所用到jpg、mp3均采用数据压缩(采用Huffman编码)以减少占用空间。编码CC是指从字符空间AA到码字表XX的映射。数据压缩编码指编码后信息的长度较于原始信息要短。本文试图探讨Huffman编码是如何保证唯一可译性、如何压缩、以及压缩效率如何？前缀码前缀码的任意一码字均不...
0
推荐
1215
阅读
Top K问题的两种解决思路
Top K问题在数据分析中非常普遍的一个问题（在面试中也经常被问到），比如：从20亿个数字的文本中，找出最大的前100个。解决Top K问题有两种思路，最直观：小顶堆（大顶堆 -> 最小100个数）；较高效：Quick Select算法。LeetCode上有一个问题215. Kth Largest Element in an Array，类似于Top K问题。1. 堆小顶堆（mi...
2
推荐
1274
阅读
最长回文子串
1. 问题描述回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。所谓最长回文子串问题，是指对于一个给定的母串abcdedcb从所有的为回文串的子串a, ded, cdedc, bcdecdb中；找出最长的那一个bcdecdb。但是该如何判断子串是否回文然后找出最长者呢？正...
2
推荐
1529
阅读
连续子数组最大和
1. 问题描述输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x应该返回 x[2..6]的和187.2. 问题解决我们很自然地能想到穷举的办法，穷举所有的子数组的之和，找出最大值。穷举法i, j的for循环表示x[i..j]，k的for循环用来计算x[i..j]之和。maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = ...
3
推荐
1943
阅读
【动态规划】最长公共子序列与最长公共子串
1. 问题描述子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串cnblogsbelong比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence, LCS），顾名思义，是指在所有的子序列中最长的那一个。子串是要求...
3
推荐
1636
阅读
【图论】有向无环图的拓扑排序
1. 引言有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。拓扑排序是对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。亦可理解为对某点v而言，只有当v的所有源点均出现了，v才能...
0
推荐
1397
阅读
【图论】求无向连通图的割点
1. 割点与连通度在无向连通图中，删除一个顶点v及其相连的边后，原图从一个连通分量变成了两个或多个连通分量，则称顶点v为割点，同时也称关节点(Articulation Point)。一个没有关节点的连通图称为重连通图(biconnected graph)。若在连通图上至少删去k 个顶点才能破坏图的连通性，则称此图的连通度为k。关节点和重连通图...
1
推荐
1461
阅读
【图论】深入理解Dijsktra算法
1. 介绍Dijsktra算法是大牛Dijsktra于1956年提出，用来解决有向图单源最短路径问题；但是不能解决负权的有向图，若要解决负权图则需要用到Bellman-Ford算法。Dijsktra算法思想：在DFS遍历图的过程中，每一次取出离源点的最近距离的点，将该点标记为已访问，松弛与该点相邻的结点。有向图记为G=(n,m)，其中，n为顶点数，m...