勇气与行动

Question:Given an array of integers, find two numbers such that they add up to a specific targetnumber.The function twoSum should return indices of the two numbers such that they add up tothe

一个调度竞争共享资源的多个活动的问题，目标是选出一个最大的互相兼容的活动集合。假定有一个n个活动的集合S={a1,a2,...,an}，这些活动使用同一个资源，而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi。其中0=如果两个活动ai和aj满足[si, fi)和[sj, fj)不重叠，则称它们是兼容的。在活动选择问题中，我们希望选出

最优二叉搜索树：给定一个n个不同关键字的已排序的序列K=（因此k1有些要搜索的值可能不在K中，因此，我们还有n+1个“伪关键字”d0,d1,d2,...,dn表示不在K中的值。d0表示所有小于k1的值，dn表示所有大于kn的值，对i=1,2,...,n-1伪关键字di表示所有在ki和k(i+1)之间的值。对每个伪关键字di也都有一个概率qi表示对应的搜索频率。假定一次搜索的

最长公共子序列问题：S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2=GTCGTTCGGAATGCCGTTGCTCTGTAAA相似度的衡量：寻找第三个串S3,它的所有碱基也都出现在S1和S2中，且在三个串中出现的顺序都相同，但在S1和S2中不要求连续出现。可以找到的S3越长，就可以认为S1和S2的相似度越高。S3=GTCGTCGGAAGCCGGCCGAA

适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。最优子结构：在发掘最优子结构性质的过程中，实际上遵循了如下的通用模式：1.证明问题最优解的第一个组成部分是做出一个选择。例如，选择钢条第一次切割位置，选择矩阵链的划分位置。做出这次选择会产生一个或多个待解的子问题。def memorized_matrix_chain(p):

本节的例子是求解矩阵链相乘问题的动态规划算法。给定一个n个矩阵的序列（矩阵链），我们希望计算它们的乘积A1A2...An。由于矩阵乘法满足结合律，因此任何加括号的方法都会得到相同的计算结果，我们称有如下性质的矩阵乘积链为完全括号话的。它是单一矩阵，或者是两个完全括号花的矩阵乘积链的积，且已外加括号。例如，如果矩阵链为，则共有5种完全括号化的矩阵乘积链。对矩阵链加括号的方式会

求解一个如何切割钢条的问题：公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出，公司管理层希望知道最佳的切割方案。假设我们知道公司出售一段长度为i英寸的钢条的价格为pi（i=1,2,...,）钢条切割问题：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,...,n)，求切割钢条方案，是的销售收益rn最大。注意：如果长度为n英寸的钢条的价格的pn足够大

区间树：闭区间是一个实数的有序对[t1, t2]，其中t1我们可以把一个区间[t1, t2]表示成一个对象i。其中属性i.low=t1为低端点，属性i.high=t2为高端点。区间i和i'重叠：i.low区间树是一种动态集合进行维护的红黑树，其中每个元素x都包含一个区间x.int。每个结点x:包含一个区间属性x.int。且x的关键字为区间的低端点

顺序统计：n个元素集合中的第i（i属于{1,2,...,n}）个顺序统计量就是简单地规定该集合中的具有第i小关键字的元素。本文介绍如何修改红黑树，使得可以在O（lgn）时间内确定任何的顺序统计量。顺序统计树T只是简单地在每个结点上存储附加信息的一棵红黑树，在红黑树的结点x中，除了通常属性x.key，x.color，x.p，x.left和x.right之外，还包括另一个属

红黑树的删除class Node: def __init__(self,key,right,left,p,color): self.key=key self.right=right self.left=left self.p=p self.color=colorclass tree: def _

红黑树的插入过程：class Node: def __init__(self,key,right,left,p,color): self.key=key self.right=right self.left=left self.p=p self.color=colorclass tree:

红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK.通过对任何一条从跟到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。一棵红黑树是满足下面红黑性质的二叉搜索树：1.每个结点或是红色的，或是黑色的。2.根结点是黑色的。3.每个叶结点是黑色的。4.如果一个结点是红色的，则它的

删除比较麻烦：1.如果z没有孩子结点，那么只是简单地将它删除，并修改它的父结点。用NIL作为孩子来替换z。2.如果z只有一个孩子，那么将这个孩子提升到树中z的位置上，并修改z的父结点，用z的孩子来替换z。3.如果z有两个孩子，那么找z的后继y（一定在z的右子树中）并让y占据树中z的位置，z的原来右子树部分成为y的新右子树，并且z的左子树成为y的新左子树。如果y位于z的右子树中，但不是z

我们经常需要查找一个存储在二叉搜索树中的关键字，除了SEARCH操作之外，二叉搜索树还能支持诸如MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR的查询操作。在任何高度为h的二叉搜索树上，如何在O(h)的时间内执行完每个操作。查找：在一棵二叉搜索树中查找一个具有给定关键字的节点，输入一个指向树根的指针和一个关键字k，如果这个结点存在，返回一个指向关键字k的结点的

一棵二叉搜索树是以一棵二叉树来组织的。这样一棵树可以使用链表数据结构来表示，其中，每个结点就是一个对象，除了key和卫星数据之外，每个结点还包含属性left、right和p,它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在，则相应属性的值为NIL。根结点是树中唯一父指针为NIL的结点。设x是二叉搜索树中的一个结点，如果y是x左子树中的一个结点，那么y.key=x.

在开放寻址法（open addressing）中，所有元素都存放在散列表中。也就是说，每个表项或包含动态集合的一个元素，或包含NIL。当查找某个元素时，要系统地检查所有的表项，直到找到所需的元素，或最终查明该元素不在表中。开放寻址法中，散列表可能会被填满，以至于不能插入任何新的元素，该方法导致的一个结果是装载因子a绝对不会超过1。为了使用开放寻址法插入一个元素，需要连续地检查散列表，或称为探查

在直接寻址方式下，具有关键字k的元素被存放在槽k中。在散列方式下，该元素存放在槽h(k)中：即利用散列函数（hash function）h，由关键字k计算出槽的位置。这里，函数h将关键字的全域U映射到散列表（hash table）T[0...m-1]的槽位上：h:U->{0,1,...,m-1}这里，散列表的大小m一般要比|U|小得多。我们可以说一个具有关键字k的元素被散列到槽h(k)

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都是取自全域U={0，1，...   ，m-1}中的一个关键字，这里m不是一个很大的数。另外，假设没有两个元素具有相同的关键字。为表示动态集合，我们用一个数组，或称为直接寻址表，记为T[0...m-1]。其中的每个位置，或称为槽（slot）.对应全域U中的一个关键字。槽k指向集合中的一个关键

用链式数据结构表示有根树的问题。树的结点用对象表示，每个结点都含有一个关键字key。二叉树：属性p:指针指向父结点left:指向左孩子right:指向右孩子如果x.p=NIL,则x是根结点如果结点x没有左孩子，则x.left=NIL。右孩子的情况类似。属性T.root指向整棵树T的根结点。如果T.root=NIL.则该树为空。分支无限制的有根树：有一个巧妙的

对象的多数组表示：next数组：key数组：prev数组：三个数组项key[x],next[x],prev[x]一起表示链表中的一个对象。变量L：表头元素的下标。对象的分配和释放：假设多数组表示法中的各数组长度为m，且在某一时刻该动态集合含有n我们把自有对象保存在一个单链表中，称为自由表（free list）。自由表只使用next数组，该数组只存储表中的next指针

链表（linked list）是这样一种数据结构，其中的各对象按线性顺序排列。数组的线性顺序是由数组下标决定的。然而与数组不同的是，链表的顺序是由各个对象里的指针决定的。双向链表（doubly linked list）L的每个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev。对象中还可以包含其他的辅助数据。设x为链表的一个元素，x.next指向它在链表中的后继元素

栈（stack）：后进先出（last-in,first-out,LIFO）被删除的是最近插入的元素。队列（queue）：先进先出（first-in,first-out,FIFO）被删除的总是在集合中存在时间最长的那个元素。栈：INSERT（PUSH）：压入DELETE（POP）：弹出S[0...n-1]来实现一个最多可容纳n个元素的栈。该数组有一个属性S.top，指向最新插入的

Randomized-select算法：渐近运行时间O(n)与快速排序一样，我们仍然将输入数组进行递归划分，但与快速排序不同的是，快速排序会递归处理划分的两边，而Randomized-select只处理划分的一边。下面的代码中返回数组A[p...r]中的第i小的元素。假设输入元素都是互异的。def randomized_select(A,p,r,i): if p

在一个有n个元素的集合中，需要做多少次比较才能确定其最小元素呢？我们可以很容易地给出n-1次比较这个上界。def minimum(A): min = A[0] for i in range(1,len(A)): if min > A[i]: min = A[i] return min运行结果：>>> A=[12,3,5,

桶排序:假设输入数据服从均匀分布，平均情况下它的时间代价为O(n)。桶排序假设输入是由一个随机过程产生，该过程将元素均匀、独立地分布在[0, 1)区间上。桶排序将[0， 1)区间划分为n个相同大小的子区间，或称为桶（下面的程序中为列表B）。然后，将n个输入数分别放到各个桶中。因为输入数据是均匀独立地分布在[0,  1)区间上，所以一般不会出现很多数落在同一个桶的情况。为了得

基数排序：首先按照最低有效位进行排序，最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。import math def sort(a, radix=10): """a为整数列表， radix为基数""" K = int(math.ceil(mat

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。计数排序的基本思想是：对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了，例如，如果有17个元素小于x，则x就应该在第18个输出位置上，当有几个元素相同时，这一方案要略做修改。因为不能把它们放在同一个输出位置上。假设输入是一个数组A[0...n-1]

与始终采用A[r]作为主元的方法不同，随机抽样是从子数组A[p...r]中随机选择一个元素作为主元。首先将A[r]与A[p...r]中随机选出的一个元素进行交换，通过对序列p,,,,r的随机抽样，我们可以保证主元元素x=A[r]是等概率地从子数组r-p+1个元素中选取的。因为主元元素是随机选取的，我们期望在平均情况下，对输入数组的划分是比较均衡的。def randomized_quic

快速排序：采用分治思想：1.分解：数组A[p....r]被划分成两个（可能为空）子数组A[p...q-1]和A[q+1....r]，使得A[p...q-1]中的每个元素都小于等于A[q]。而A[q]也小于等于A[q+1....r]中的每个元素。其中，计算下标q也是划分过程的一部分。2.解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1....r]进行排序。3.合并

我们首先关注如何基于最大堆实现最大优先队列：优先队列（priority queue）是一种用来维护一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字（key）。一个最大优先队列支持以下操作：INSERT(S，x)：把元素x插入集合S中，这一操作等价于S=S U {x}MAXIMUM(S)：返回S中具有最大关键字的元素。EXTRACT-MAX(S)：去掉

堆排序算法： def heapsort(self,A):开始的时候，利用build_max_heap将输入数组A建成最大堆。因为数组中的最大元素总在根结点A[0]中。通过把它与A[len(A)-1]交换。可以让元素A[0]放到正确的位置。这个时候，我们从堆中去掉A中的最后一个结点。即heap_size-1。其实heap_size起作用的地点主要在函数max_heapify(self,hea

我们可以用自底向上的方法利用过程max-heapify把一个大小为n=A.length的数组A[0..n-1]转换为最大堆。子数组A(下取整n/2.....n-1)中的元素都是叶结点。每个叶结点都可以看成只包含一个元素的堆。过程build_max_heap(A)对树中的其他结点都调用一次max-heapify：代码：import mathclass heapsort: def _

函数max_heapify可以检测以下标i为根结点的子树是否是最大堆。首先假定根结点为left(i)和right(i)的二叉树都是最大堆，但这时A[i]有可能小于其他孩子。这样就违背了最大堆的性质。max_heapify通过让A[i]的值在最大堆中“逐级下降”，从而使得以下标i为根结点的子树重新遵循最大堆的性质。import mathclass heapsort: def _

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的每一个元素。除了最底层外，该树是完全充满的，而且是从左到右填充。树的根结点：A[0]。给定一个下标i，很容易得到它的父结点、左孩子和右孩子的下标。import mathclass heapsort: def __init__(self,a_A): self.list=a_A

在面试一个应聘者之后，我们能够给每人一个分数score。在面试过j个人之后，我们知道这j个人中的最高分，但是不知道后面的n-j个会不会有最高的。我们决定采取如下策略：选择一个正整数k如果最高得分的应聘者在前k个应聘者。我们将雇佣第n个应聘者。class Assitant: def __init__(self,a_name="anonymous",value=0):

随机排列数组：一个通常的方法是为数组的每个元素A[i]赋一个随机的优先级P[i]，然后依据优先级对数组A中的元素进行排序Permute-by-sorting:import randomdef random_array(n): P = random.sample(range(n*10), n) return P def permute_by_sorti

雇佣问题：从n个候选者中选择出最好的候选者。assList是所有候选者列表。类Assistant中的name是候选者的名字。value是候选者价值得分（当然是越高的越优秀啦~~~）hire_assitant返回最优秀者。def hire_assistant(assList): n = len(assList) best = 0 index = 0

矩阵乘法：def square_matrix_multiply(A,B): C = [] n = len(A) C = [[0 for col in range(n)] for row in range(n)] for i in range(0,n): for j in range(0,n): for k in r

寻找最大子数组问题：给定数组A：寻找A中的和最大的非连续子数组。我们称这样的连续子数组为最大子数组（maximum subarray）使用分治策略的求解方法：假定我们要寻找子数组A[low...high]的最大子数组。使用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是，找到子数组的中央位置，比如mid，然后考虑求解两个子数组A[low...mid]和A[mid+1.

归并排序：def merge(A,p,q,r): n1 = q-p+1 n2 = r-q L = [] R = [] for i in range(n1): L.append(A[p+i]) for j in range(n2): R.append(A[q+1+j]) L.appe