插入排序 

InsertionSort(A, length)
    for j=2 to A.length
        i = j - 1
        key = A[j]
        while i > 0 && key < A[i]
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
归并排序 

Merge(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L1[1...n1 + 1] be a new array
    let L2[1...n2 + 1] be a new array
    for i = 1 to n1
        L1[i] = A[p + i - 1]
    for i = 1 to n2
        L2[i] = A[q + i]
    L[n1 + 1] = INT_MAX
    L[n2 + 1] = INT_MAX
    i = 1
    j = 1
    for k=q to r
        if L1[i] <= L2[j]
            A[k] = L1[i]
            i = i + 1
        else
            A[k] = L2[j]
            j = j + 1
MergeSort(A, p, r)
    if p < r
        q = (r - p) / 2
        MergeSort(A, p, q)
        MergeSort(A, q + 1, r)
        Merge(A, p, q, r)
冒泡排序 

BubbleSort(A)
    for i = 1 to A.length - 1
        for j = A.lenght downto i + 1
            if A[j] < A[j - 1]
                exchange A[j] with A[j - 1]
堆排序 

left(i)
    return 2 * i
right(i)
    return 2 * i + 1
HEAPIFY(A, i)
    l = left(i)
    r = right(i)
    if l <= A.heap-size && A[i] <= A[l]
        large = l
    else
        large = i
    if r <= A.heap-size && A[large] <= A[r]
        large = r
    if large != i
        exchange A[i] with A[large]
        HEAPIFY(A, large)
BuildHeap(A)
    A.heapsize = A.length
    for i = A.length / 2 downto 1
        HeapINF(i)
HeapSort(A)
    BuildHeap(A)
    for A.length downto 2
        exchange A[heapsize] with A[1]
        A.heap-size = A.heap-size - 1
        HEAPIFY(A, 1)
快速排序 

Partition (A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r - 1
        if A[j] <= x
            i = i + 1
            exchange A[j] wight A[i]
    exchange A[i + 1] with A[r]
    return i + 1
QuickSort(A, p, r)
    if p < r
        q = Partition(A, p, r)
        QuickSort(A, p, q - 1)
        QuickSort(A, q + 1, r)
计数排序 

CountingSort(A, B, k)
    let C[0 ... k] be a new array
    for i = 0 to k        
        C[i] = 0
    for i = 1 to A.length
        C[A[i]] = C[A[i]] + 1
    for i = 1 to k                                
        C[i] = C[i] + C[i - 1]
    for i = A.length downto 1
        B[C[A[i]]] = A[i]
        C[A[i]] = C[A[i]] - 1
桶排序 

BucketSort(A)
    n = A.length
    let B[0 ... n - 1] be a new Array
    for i = 0 to n - 1
        let B[i] be a empty list
    for i = 1 to n
        insert A[i] to B[n * A[i]]
    for i = 0 to n - 1
        use InsertionSort to sort B[i]
    concatenate the lists B[0], B[1], ... B[n - 1] together in order
优先级队列的数据结构底层，特性，应用

优先级队列（Priority Queue）是一种特殊的队列，其数据项拥有优先级，可以根据优先级来确定出队顺序。在底层实现上，优先级队列可以通过多种数据结构来实现，常见的包括堆（Heap）和有序数组。

在堆（通常是二叉堆或者斐波那契堆）实现下，优先级队列的特性包括：插入：在O(log n)时间内将新元素插入到合适的位置。删除最高优先级元素：在O(log n)时间内移除并返回具有最高优先级的元素。获取最高优先级元素：在O(1)时间内获取具有最高优先级的元素。

有序数组实现 在有序数组实现下，优先级队列的特性包括：插入：需要在O(n)时间内找到合适的位置插入新元素，并保持数组有序。删除最高优先级元素：在O(1)时间内移除并返回具有最高优先级的元素。 获取最高优先级元素：在O(1)时间内获取具有最高优先级的元素。

如何判断一棵树是搜索树？

节点数值大小判断：对于每个节点，其左子树中的所有节点的值都应该小于当前节点的值，而右子树中的所有节点的值都应该大于当前节点的值。这是二叉搜索树的一个重要性质。

中序遍历判断：对树进行中序遍历，如果得到的节点值序列是递增的，则该树是搜索树。因为中序遍历对于二叉搜索树来说会得到一个递增的节点值序列。

递归判断：可以使用递归的方法来判断树的每个节点是否满足搜索树的条件。对于每个节点，需要判断其值是否在一定范围内，并且递归地判断其左子树和右子树是否也满足搜索树的条件。

数组和链表的区别？使用场景有什么区别？

存储方式：数组：在内存中以连续的方式存储元素。链表：通过指针将节点链接在一起，每个节点可以存储元素值以及指向下一个节点的指针。

插入和删除操作：数组：插入和删除操作可能需要移动大量元素，特别是在中间或开头位置进行操作时。链表：插入和删除元素效率较高，只需要改变相邻节点的指针即可。

随机访问：数组：支持根据索引快速访问元素，时间复杂度为 O(1)。链表：不支持直接根据索引访问元素，需要从头节点开始沿着指针遍历到目标位置，时间复杂度为 O(n)。

空间复杂度：数组：由于需要在内存中保持连续的空间，可能存在一定的空间浪费。链表：不需要连续的内存空间，可以更加灵活地利用内存。

使用场景的区别：当需要频繁进行随机访问或者对数组元素进行增删操作时，数组通常更适合。例如，需要实现栈、队列等数据结构时，可以选择数组。当需要频繁进行插入和删除操作、元素个数不固定、或者对内存空间使用要求较高时，链表通常更适合。例如，实现链表、队列等数据结构时，可以选择链表。

Hash为什么查找很快？

因为Hash不需要去检索数据，而是通过哈希函数直接计算，判断是否存在，存在则直接返回。

1 红黑树

红黑树与AVL的比较：

AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；

红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；

所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

红黑树详解: https://xieguanglei.github.io/blog/post/red-black-tree.html

教你透彻了解红黑树: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

哈希冲突的解决办法

哈希冲突是指不同的输入数据经过哈希函数计算后得到相同的哈希值，这种情况在使用哈希表等数据结构时会导致冲突。以下是一些常见的哈希冲突解决办法：

  1. 链地址法（Separate Chaining）： 将哈希表的每个槽（bucket）设为一个链表或者其他数据结构，当发生哈希冲突时，将新元素追加到对应槽位上的链表中。这种方法需要额外的存储空间来存储链表节点，但是当有很多哈希冲突时，它可以提供较好的性能。
  2. 开放寻址法（Open Addressing）： 当发生哈希冲突时，通过一定的探测序列向后顺延，寻找下一个可用的插入位置。常见的探测序列包括线性探测、二次探测和双重散列等。开放寻址法避免了存储链表节点的开销，但是当装载因子较高时性能可能下降严重。
  3. 再哈希（Rehashing）： 当哈希表中元素数量达到一定阈值时，触发再哈希操作，即重新构建一个更大的哈希表，并将所有元素重新插入到新的哈希表中。这样可以通过增大哈希表容量来减少哈希冲突的概率。
  4. 建立公共溢出区： 将散列表分为基本表和溢出表两部分，当发生冲突时，将冲突的记录存入溢出表。这种方法可以避免链地址法中频繁动态分配内存的开销。
  5. 使用链表加速查找： 在发生哈希冲突时，可以采用链表形式来加速查找冲突元素，例如 Java 中的 HashMap 就使用了链表形式来解决冲突。

选择合适的哈希冲突解决办法取决于实际场景和需求，通常需要根据数据分布、性能要求和空间复杂度等方面进行综合考量。

二叉树的前中后序遍历的非递归与递归实现（已知前中序遍历，求后续遍历）

1
2
3
4
5

PreorderTreeWalk(x)
    print(x)
    PreorderTreeWalk(x.left)
    PreorderTreeWalk(x.right)
PreorderTreeWalk-Loop(x)

树的基本概念（入树的高度）

一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。

几乎所有平衡树的操作都基于树旋转操作，通过旋转操作可以使得树趋于平衡。

二分查找及其实现

图的邻接表和邻接矩阵的表示

DFS

BFS

最短路径

实现哈希表 // 通过哈希来划分解题

优先级队列 //通过队列来序列化操作解题

字符串处理

动态规划

旋转数组查找

逆置链表

逆置后面k个节点

判断链表是否有环

链表快排

链表归并

排序矩阵查找一个数

快排、堆排：无序数组查找第k大的元素

判断是否是平衡二叉树

二叉树层次遍历

环形打印矩阵

求字符串的最长回文长度

编程题

1 台阶问题/斐波那契

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1

fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

第二种记忆方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def memo(func):
    cache = {}
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap


@memo
def fib(i):
    if i < 2:
        return 1
    return fib(i-1) + fib(i-2)

第三种方法

1
2
3
4
5

def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return b

2 变态台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1

fib = lambda n: n if n < 2 else 2 * fib(n - 1)

3 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。

1

f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)

4 杨氏矩阵查找

在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

使用Step-wise线性搜索。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def get_value(l, r, c):
    return l[r][c]

def find(l, x):
    m = len(l) - 1
    n = len(l[0]) - 1
    r = 0
    c = n
    while c >= 0 and r <= m:
        value = get_value(l, r, c)
        if value == x:
            return True
        elif value > x:
            c = c - 1
        elif value < x:
            r = r + 1
    return False

6 链表成对调换

1->2->3->4转换成2->1->4->3.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        if head != None and head.next != None:
            next = head.next
            head.next = self.swapPairs(next.next)
            next.next = head
            return next
        return head

8 合并两个有序列表

知乎远程面试要求编程

尾递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def _recursion_merge_sort2(l1, l2, tmp):
    if len(l1) == 0 or len(l2) == 0:
        tmp.extend(l1)
        tmp.extend(l2)
        return tmp
    else:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
        return _recursion_merge_sort2(l1, l2, tmp)

def recursion_merge_sort2(l1, l2):
    return _recursion_merge_sort2(l1, l2, [])

循环算法

思路：

定义一个新的空列表

比较两个列表的首个元素

小的就插入到新列表里

把已经插入新列表的元素从旧列表删除

直到两个旧列表有一个为空

再把旧列表加到新列表后面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def loop_merge_sort(l1, l2):
    tmp = []
    while len(l1) > 0 and len(l2) > 0:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
    tmp.extend(l1)
    tmp.extend(l2)
    return tmp

pop弹出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

a = [1,2,3,7]
b = [3,4,5]

def merge_sortedlist(a,b):
    c = []
    while a and b:
        if a[0] >= b[0]:
            c.append(b.pop(0))
        else:
            c.append(a.pop(0))
    while a:
        c.append(a.pop(0))
    while b:
        c.append(b.pop(0))
    return c
print merge_sortedlist(a,b)

9 交叉链表求交点

其实思想可以按照从尾开始比较两个链表，如果相交，则从尾开始必然一致，只要从尾开始比较，直至不一致的地方即为交叉点，如图所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# 使用a,b两个list来模拟链表，可以看出交叉点是 7这个节点
a = [1,2,3,7,9,1,5]
b = [4,5,7,9,1,5]

for i in range(1,min(len(a),len(b))):
    if i==1 and (a[-1] != b[-1]):
        print "No"
        break
    else:
        if a[-i] != b[-i]:
            print "交叉节点：",a[-i+1]
            break
        else:
            pass

另外一种比较正规的方法，构造链表类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def node(l1, l2):
    length1, lenth2 = 0, 0
    # 求两个链表长度
    while l1.next:
        l1 = l1.next
        length1 += 1
    while l2.next:
        l2 = l2.next
        length2 += 1
    # 长的链表先走
    if length1 > lenth2:
        for _ in range(length1 - length2):
            l1 = l1.next
    else:
        for _ in range(length2 - length1):
            l2 = l2.next
    while l1 and l2:
        if l1.next == l2.next:
            return l1.next
        else:
            l1 = l1.next
            l2 = l2.next

修改了一下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#coding:utf-8
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def node(l1, l2):
    length1, length2 = 0, 0
    # 求两个链表长度
    while l1.next:
        l1 = l1.next#尾节点
        length1 += 1
    while l2.next:
        l2 = l2.next#尾节点
        length2 += 1

    #如果相交
    if l1.next == l2.next:
        # 长的链表先走
        if length1 > length2:
            for _ in range(length1 - length2):
                l1 = l1.next
            return l1#返回交点
        else:
            for _ in range(length2 - length1):
                l2 = l2.next
            return l2#返回交点
    # 如果不相交
    else:
        return

思路: http://humaoli.blog.163.com/blog/static/13346651820141125102125995/

10 二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#coding:utf-8
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (high - low) / 2 + low    # 避免(high + low) / 2溢出
        guess = list[mid]
        if guess > item:
            high = mid - 1
        elif guess < item:
            low = mid + 1
        else:
            return mid
    return None
mylist = [1,3,5,7,9]
print binary_search(mylist, 3)

参考: http://blog.csdn.net/u013205877/article/details/76411718

冒泡

1
2
3
4
5
6

def bubbleSort(nums):
    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums)-i-1):  # ｊ为列表下标
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

11 快排

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#coding:utf-8
def quicksort(list):
    if len(list)<2:
        return list
    else:
        midpivot = list[0]
        lessbeforemidpivot = [i for i in list[1:] if i<=midpivot]
        biggerafterpivot = [i for i in list[1:] if i > midpivot]
        finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot)
        return finallylist

print quicksort([2,4,6,7,1,2,5])

更多排序问题可见：数据结构与算法-排序篇-Python描述

1
2
3
4
5
6
7
8

def qsort(seq):
    if seq==[]:
        return []
    else:
        pivot=seq[0]
        lesser=qsort([x for x in seq[1:] if x<pivot])
        greater=qsort([x for x in seq[1:] if x>=pivot])
        return lesser+[pivot]+greater

12 找零问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#coding:utf-8
#values是硬币的面值values = [ 25, 21, 10, 5, 1]
#valuesCounts   钱币对应的种类数
#money  找出来的总钱数
#coinsUsed   对应于目前钱币总数i所使用的硬币数目

def coinChange(values,valuesCounts,money,coinsUsed):
    #遍历出从1到money所有的钱数可能
    for cents in range(1,money+1):
        minCoins = cents
        #把所有的硬币面值遍历出来和钱数做对比
        for kind in range(0,valuesCounts):
            if (values[kind] <= cents):
                temp = coinsUsed[cents - values[kind]] +1
                if (temp < minCoins):
                    minCoins = temp
        coinsUsed[cents] = minCoins
        print ('面值:{0}的最少硬币使用数为:{1}'.format(cents, coinsUsed[cents]))

思路: http://blog.csdn.net/wdxin1322/article/details/9501163

方法: http://www.cnblogs.com/ChenxofHit/archive/2011/03/18/1988431.html

13 广度遍历和深度遍历二叉树

给定一个数组，构建二叉树，并且按层次打印这个二叉树

14 二叉树节点

1
2
3
4
5
6
7

class Node(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))

15 层次遍历

1
2
3
4
5

def lookup(root):
    row = [root]
    while row:
        print(row)
        row = [kid for item in row for kid in (item.left, item.right) if kid]

1
2
3
4
5
6
7
8
9

def lookup(root):
    stack = [root]
    while stack:
        current = stack.pop(0)
        print(current.data)
        if current.left:
            stack.append(current.left)
        if current.right:
            stack.append(current.right)

16 深度遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def deep(root):
    if not root:
        return
    print root.data
    deep(root.left)
    deep(root.right)

if __name__ == '__main__':
    lookup(tree)
    deep(tree)

17 前中后序遍历

深度遍历改变顺序就OK了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#coding:utf-8
#二叉树的遍历
#简单的二叉树节点类
class Node(object):
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right

#中序遍历:遍历左子树,访问当前节点,遍历右子树

def mid_travelsal(root):
    if root.left is not None:
        mid_travelsal(root.left)
    #访问当前节点
    print(root.value)
    if root.right is not None:
        mid_travelsal(root.right)

#前序遍历:访问当前节点,遍历左子树,遍历右子树

def pre_travelsal(root):
    print (root.value)
    if root.left is not None:
        pre_travelsal(root.left)
    if root.right is not None:
        pre_travelsal(root.right)

#后续遍历:遍历左子树,遍历右子树,访问当前节点

def post_trvelsal(root):
    if root.left is not None:
        post_trvelsal(root.left)
    if root.right is not None:
        post_trvelsal(root.right)
    print (root.value)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def pre_order(root):
    if not root:
        return
    print(root.data)
    pre_order(root.left)
    pre_order(root.right)
		
def mid_order(root):
    if not root:
        return
    mid_order(root.left)
		    print(root.data)
    mid_order(root.right)
		
def las_order(root):
    if not root:
        return
    las_order(root.left)
    las_order(root.right)
          print(root.data)

18 求最大树深

1
2
3
4

def maxDepth(root):
        if not root:
            return 0
        return max(maxDepth(root.left), maxDepth(root.right)) + 1

19 求两棵树是否相同

1
2
3
4
5
6
7

def isSameTree(p, q):
    if p == None and q == None:
        return True
    elif p and q :
        return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
    else :
        return False

20 前序中序求后序

推荐: http://blog.csdn.net/hinyunsin/article/details/6315502

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def rebuild(pre, center):
    if not pre:
        return
    cur = Node(pre[0])
    index = center.index(pre[0])
    cur.left = rebuild(pre[1:index + 1], center[:index])
    cur.right = rebuild(pre[index + 1:], center[index + 1:])
    return cur

def deep(root):
    if not root:
        return
    deep(root.left)
    deep(root.right)
    print root.data

21 单链表逆置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))

def rev(link):
    pre = link
    cur = link.next
    pre.next = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre

root = rev(link)
while root:
    print root.data
    root = root.next

思路: http://blog.csdn.net/feliciafay/article/details/6841115

方法: http://www.xuebuyuan.com/2066385.html?mobile=1

22 两个字符串是否是变位词

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

class Anagram:
    """
    @:param s1: The first string
    @:param s2: The second string
    @:return true or false
    """
    def Solution1(s1,s2):
        alist = list(s2)

        pos1 = 0
        stillOK = True

        while pos1 < len(s1) and stillOK:
            pos2 = 0
            found = False
            while pos2 < len(alist) and not found:
                if s1[pos1] == alist[pos2]:
                    found = True
                else:
                    pos2 = pos2 + 1

            if found:
                alist[pos2] = None
            else:
                stillOK = False

            pos1 = pos1 + 1

        return stillOK

    print(Solution1('abcd','dcba'))

    def Solution2(s1,s2):
        alist1 = list(s1)
        alist2 = list(s2)

        alist1.sort()
        alist2.sort()


        pos = 0
        matches = True

        while pos < len(s1) and matches:
            if alist1[pos] == alist2[pos]:
                pos = pos + 1
            else:
                matches = False

        return matches

    print(Solution2('abcde','edcbg'))

    def Solution3(s1,s2):
        c1 = [0]*26
        c2 = [0]*26

        for i in range(len(s1)):
            pos = ord(s1[i])-ord('a')
            c1[pos] = c1[pos] + 1

        for i in range(len(s2)):
            pos = ord(s2[i])-ord('a')
            c2[pos] = c2[pos] + 1

        j = 0
        stillOK = True
        while j<26 and stillOK:
            if c1[j] == c2[j]:
                j = j + 1
            else:
                stillOK = False

        return stillOK

    print(Solution3('apple','pleap'))

23 动态规划问题

可参考：动态规划(DP)的整理-Python描述

  • 假设你的键盘只有以下键:A，Ctrl + A，Ctrl + C，Ctrl + V。

    这里 Ctrl+A，Ctrl+C，Ctrl+V 分别代表「全选」，「复制」，「粘贴」，组合键算一次按键。

    如果你只能按键盘 N 次，请写一个程序可以产生最多数量的 A. 也就是说输入是 N（你按键盘的次数），输出是 M（产生的A的个数）。

    加分项：打印出中间你按下的那些键。

    问题细节：

    • Ctrl+A 算一次按键。
    • Ctrl+A，Ctrl+C，Ctrl+V 并不能让现有的字符数量加倍，需要再按一次 Ctrl+V 才行，所以说 3 次按键可以让现有字符翻倍的说法是错误的，应该是 4 次。

    初步想法：

    • 看了这道题第一反应，这是个 DP 问题，然后想了一会儿给出第一个状态转移方程（这个是错的）。
    1

    F[i] = max{F[i-1], F[i-4]*2}

    然后发现一个问题，存在一种情况，就是剪贴板中存在一定数量的字符，这时候是可以继续粘贴的。然后写出第二个状态转移方程（很可惜这个仍然是错的）。

    1

    F[i] = max{F[i-1], F[i-4]*2, F[i-1]+a}

    这里的 a 表示剪贴板中已经存在的字符。

    这里存在一个问题，输出几个结果就可以看到，当 i=20 的时候结果可以输出 128 个字符。这个结果是错的，正确答案应该是 150 个。

    跟踪结果可以看到，这时候的按键顺序为：AAAA Ctrl+acvvvv Ctrl+acvvvv Ctrl+acvv（A 代表按下 A，Ctrl+acv 代表「全选」「复制」「粘贴」，下同）

    可是正确结果应该是 AAAAAA Ctrl+acvvvvv Ctrl+vvvvv

    问题出在哪儿了呢？很容易可以得到，正确结果中在 i=10 的时候输出的结果是 12 而不是最优解 16. 所以这里有个问题，每一步的最优并不一定导致全局的最优。

    维基百科教育我们，动态规划问题需要具有的一个性质是「最优子结构」，可是这道题不满足，所以这压根儿就不是一道 DP 题。

    深搜（DFS）:

    • 到这里暂时思路断了，那就写个「万金油」搜索吧，很容易可以得到下面的代码：
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    # -*- coding: UTF-8 -*-
# author: TheLover_Z

### version 1: DFS


def search(m, clipboard_num, n, keys):
    global max_m
    global key_pressed
    if (n == 0 and m > max_m):
        max_m = m
        key_pressed = keys
        return
    if (n >= 1 and clipboard_num < 1):  # press a
        keys += '[a]'
        search(m + 1, clipboard_num, n - 1, keys)
    if (n >= 1 and clipboard_num > 1):  # press control-v
        keys += '[c-v]'
        search(m + clipboard_num, clipboard_num, n - 1, keys)
    if (n >= 4):  # press control-acvv
        keys += '[c-acvv]'
        search(m * 2, m, n - 4, keys)


def main():
    n = 45
    global max_m
    max_m = 0
    global key_pressed
    key_pressed = ''
    search(0, 0, n, key_pressed)
    print ">> pressed %s times can get maximum %s chars " % (n, max_m)
    print ">> solution: %s" % (key_pressed)

if __name__ == '__main__':
    main()

    经测试，当 n=45 用时 2.068443 秒。

    https://gist.github.com/liamzh/5449825

  • 两个整数数组各有100亿条数据，并已经排序，保存在磁盘上，内存10M。

    问：

    （1）如何取得交集？时间和空间效率分别是多少？Python 集合set()操作方法

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    import os
os.system('sort -u -n s1.num > s1.ns')
os.system('sort -u -n s2.num > s2.ns')
i1 = open('s1.ns', 'r')
i2 = open('s2.ns', 'r')
try:
    d1 = i1.next()
    d2 = i2.next()
    while True:
        if (d1 < d2):
            d1 = i1.next()
        elif (d2 < d1):
            d2 = i2.next()
        else:
            print d1,
            d1 = i1.next()
            d2 = i2.next()
except StopIteration:
    pass

    （2）如果其中一个数组只有100条数据，如何优化算法取得交集？时间和空间效率分别是多少？

    对一个数据中的100个数字在另一个数组中进行二分查找。时间复杂度是O(logn), 空间复杂度是O(1)

    （3）用自己熟悉的语言实现第2个问题，要求可以正确运行；假设已经提供函数read_elt(arrary_name, index)可以用来读取某个数组的第index个元素，元素个数分别用m=100和n=10^10表示。

字典树