algorithm-reading
leetcode/lintcode题解/算法学习笔记
1. Part I - Basics
2. Data Structure
- 2.1. Linked List
- 2.2. Binary Tree
- 2.3. Binary Search Tree
- 2.4. Huffman Compression
- 2.5. Priority Queue
3. Basics Sorting
- 3.1. Bubble Sort
- 3.2. Selection Sort
- 3.3. Insertion Sort
- 3.4. Merge Sort
- 3.5. Quick Sort
- 3.6. Heap Sort
- 3.7. Bucket Sort
- 3.8. Counting Sort
- 3.9. Radix Sort
4. Basics Misc
- 4.1. Bit Manipulation
5. Part II - Coding
6. String - 字符串
- 6.1. strStr
- 6.2. Two Strings Are Anagrams
- 6.3. Compare Strings
- 6.4. Anagrams
- 6.5. Longest Common Substring
- 6.6. Rotate String
- 6.7. Reverse Words in a String
7. Integer Array - 整型数组
- 7.1. Remove Element
- 7.2. Zero Sum Subarray
- 7.3. Subarray Sum K
- 7.4. Subarray Sum Closest
- 7.5. Product of Array Exclude Itself
- 7.6. Partition Array
- 7.7. First Missing Positive
- 7.8. 2 Sum
- 7.9. 3 Sum
- 7.10. 3 Sum Closest
- 7.11. Remove Duplicates from Sorted Array
- 7.12. Remove Duplicates from Sorted Array II
- 7.13. Merge Sorted Array
- 7.14. Merge Sorted Array II
- 7.15. Median
8. Binary Search - 二分搜索
- 8.1. Binary Search
- 8.2. Search Insert Position
- 8.3. Search for a Range
- 8.4. First Bad Version
- 8.5. Search a 2D Matrix
- 8.6. Find Peak Element
- 8.7. Search in Rotated Sorted Array
- 8.8. Find Minimum in Rotated Sorted Array
- 8.9. Search a 2D Matrix II
- 8.10. Median of two Sorted Arrays
- 8.11. Sqrt x
- 8.12. Wood Cut
9. Math and Bit Manipulation - 数学技巧与位运算
- 9.1. Single Number
- 9.2. Single Number II
- 9.3. Single Number III
- 9.4. O1 Check Power of 2
- 9.5. Convert Integer A to Integer B
- 9.6. Factorial Trailing Zeroes
- 9.7. Unique Binary Search Trees
- 9.8. Update Bits
- 9.9. Fast Power
10. Linked List - 链表
- 10.1. Remove Duplicates from Sorted List
- 10.2. Remove Duplicates from Sorted List II
- 10.3. Remove Duplicates from Unsorted List
- 10.4. Partition List
- 10.5. Two Lists Sum
- 10.6. Two Lists Sum Advanced
- 10.7. Remove Nth Node From End of List
- 10.8. Linked List Cycle
- 10.9. Linked List Cycle II
- 10.10. Reverse Linked List
- 10.11. Reverse Linked List II
- 10.12. Merge Two Sorted Lists
- 10.13. Merge k Sorted Lists
- 10.14. Reorder List
- 10.15. Copy List with Random Pointer
- 10.16. Sort List
- 10.17. Insertion Sort List
- 10.18. Check if a singly linked list is palindrome
11. Reverse - 翻转法
- 11.1. Recover Rotated Sorted Array
12. Binary Tree - 二叉树
- 12.1. Binary Tree Preorder Traversal
- 12.2. Binary Tree Inorder Traversal
- 12.3. Binary Tree Postorder Traversal
- 12.4. Binary Tree Level Order Traversal
- 12.5. Maximum Depth of Binary Tree
- 12.6. Balanced Binary Tree
- 12.7. Binary Tree Maximum Path Sum
- 12.8. Lowest Common Ancestor
13. Binary Search Tree - 二叉搜索树
- 13.1. Insert Node in a Binary Search Tree
- 13.2. Validate Binary Search Tree
- 13.3. Search Range in Binary Search Tree
- 13.4. Convert Sorted Array to Binary Search Tree
- 13.5. Convert Sorted List to Binary Search Tree
- 13.6. Binary Search Tree Iterator
14. Exhaustive Search - 穷竭搜索
- 14.1. Subsets
- 14.2. Unique Subsets
- 14.3. Permutation
- 14.4. Unique Permutations
- 14.5. Unique Binary Search Trees II
15. Dynamic Programming - 动态规划
- 15.1. Triangle
- 15.2. Knapsack - 背包问题
  - 15.2.1. Backpack
- 15.3. Matrix
  - 15.3.1. Minimum Path Sum
  - 15.3.2. Unique Paths
- 15.4. Sequence
  - 15.4.1. Climbing Stairs
  - 15.4.2. Jump Game
- 15.5. Word Break
- 15.6. Longest Increasing Subsequence
- 15.7. Palindrome Partitioning II
- 15.8. Longest Common Subsequence
- 15.9. Edit Distance
16. Appendix I Interview and Resume
- 16.1. Interview
- 16.2. Resume

algorithm-reading

Huffman Compression - 霍夫曼压缩

主要思想：放弃文本文件的普通保存方式：不再使用7位或8位二进制数表示每一个字符，而是用较少的比特表示出现频率最高的字符，用较多的比特表示出现频率低的字符。

使用变长编码来表示字符串，势必会导致编解码时码字的唯一性问题，因此需要一种编解码方式唯一的前缀码，而表示前缀码的一种简单方式就是使用单词查找树，其中最优前缀码即为Huffman首创。

以符号F, O, R, G, E, T为例，其出现的频次如以下表格所示。

Symbol	F	O	R	G	E	T
Frequence	2	3	4	4	5	7
Code	000	001	100	101	01	10

则对各符号进行霍夫曼编码的动态演示如下图所示。基本步骤是将出现频率由小到大排列，组成子树后频率相加作为整体再和其他未加入二叉树中的节点频率比较。加权路径长为节点的频率乘以树的深度。

Huffman

有关霍夫曼编码的具体步骤可参考 Huffman 编码压缩算法 | 酷壳 - CoolShell.cn 和霍夫曼编码 - 维基百科，自由的百科全书，清晰易懂。