突然就想鸽掉算导了。虽然知识点+题目可能也就完成了50%到60%的样子，不过其实作者也在Quora上说过，8小时工作制下完整读完这本书要一年……想来能在暑假两个多月写这么多东西已经是很不错的了。写算导的初衷，无非就是想给自己找点事情做而已。马上要开学了，难以再心无旁骛，于是就先这样吧。
HDFS是Hadoop的文件系统，MapReduce是Hadoop并行计算框架。
HDFS是Hadoop的分布式文件系统，全名为Hadoop Distributed File System。它有以下三个基本概念：
块是默认大小为64MB的逻辑单元。HDFS里面的文件被分成相同大小的数据块来进行存储和管理。当然，文件的备份和查找也是基于数据块进行处理的。
NameNode是管理节点（直译名字节点）。它存放着文件与数据块（Block）的映射表，也存放着数据块与数据节点（DataNode）的映射表。这俩被统称为文件元数据。
DataNode是工作节点（也就是数据节点），用来存放数据块。比如下图中，每个工作节点就存放了三个数据块。
动态规划方法是一种对具有交叠子问题的问题进行求解的技术。如果不同的子问题拥有公共的子子问题，那么分治算法的递归里有可能会反复地求解一个公共的子子问题。不得不承认，DP(dynamic program)大概是本书唯一能够抗衡分治法的存在了。尽管这本书没有提到Warshall和Ford，没有背包问题也没有小机器人，剩下的文字依然皓如繁星。愿天堂没有DP。
先修知识：
钢条切割问题指的是，将一条长钢条切割成几条短钢条出售，求解售价最大化问题。其中不同长度的钢条的价格不同，甚至也会出现根本不切割而利益最大的情形。也可以概括为，利用手上限额的资源，合理分配以达到利益最大化的问题。
最长公共子序列问题指的是，求解两个序列的最长的相同子序列。子序列所含元素在序列中的位置下标应该是严格递增的。例如，Z={B,C,D,B}是X={A,B,C,B,D,A,B}的子序列，此时位置下标为{1,2,4,6}。
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: “A man, a plan, a canal: Panama” Output: true
Example 2:
Input: “race a car” Output: false
easy one. 字符串练手。
先修知识：
一棵树不存在回路。其中除了根结点以外所有的结点都有父结点（或者说父结点为NIL），除了叶子以外所有的结点都有子结点（或者说子结点为NIL）。二叉树描述的是包含叶子和根在内的所有结点，都最多只有两个子结点（或者子树）的树结构。二叉树体系内最重要的一种叫做二叉搜索树（又叫二叉查找树），再往下分，二叉搜索树又包括平衡二叉查找树（AVL树）和红黑树等等。
扩张数据结构一般要走下列四个步骤：
举个例子，选取一个完全二叉树。我要维护的是结点的关键字逐层往上递减这个性质，因此修改内部代码之后，再设计一个新操作EXTRACT-MIN，就能把这个完全二叉树扩张成为一个最小堆了。
忙完实习后，终于有时间更新了……这一讲会讨论一些基本的数据结构和散列表。比起算法而言，数据结构应该更通用也更实用些，毕竟小项目可以只招一些API战士，而增删改查 (CRUD boy) 是绝对离不开数据结构的。书上的诸如「指针和对象的实现」就跳过了，我只用 java 和 python 。
keywords: 基本数据结构 散列技术（函数）