july算法课笔记

# coding=utf-8

# 第一题
‘‘‘
给定某字符串S，该字符串中有若干空格，
删除这些空格，并返回修改后的字符串；要
求时间复杂度O(N)，空间复杂度O(1)。
?如：“I_have_a___dream!”，返回“Ihaveadream”
?注：有可能两个单词间存在若干空格。
‘‘‘
import copy
import pprint
import random
import re
import collections


def is_remove(a_str):
    pattern = re.compile(r"[\u4e00-\u9fa5]")
    find_list = pattern.findall(a_str)
    if find_list:
        return False
    else:
        return True


def remove_blank(a_in_str, is_remove):
    size = len(a_in_str)
    str_list = list(a_in_str)
    i = 0  # 遍历所有的字符
    j = 0  # 遍历所有的有效字符，因此j<=i
    while (i < size):
        if is_remove(str_list[i]):
            i += 1
        else:
            if j < i:
                str_list[j] = str_list[i]
            i += 1
            j += 1
    return "".join(str_list[:j])   


# print remove_blank("asdb   dfd",is_remove)

# 第二题：
‘‘‘
给定一个数组，找出该数组最大的数。
‘‘‘


def find_max(a_int_list):
    if not a_int_list:
        return
    max = a_int_list[0]
    for i in a_int_list:
        if i > max:
            max = i
    return max


# print find_max([1,3,4,5,6,4,5])

# 第三题
‘‘‘
给定一个数组，找出该数组最大和次大的两
个数。
‘‘‘


def find_two_max(a_int_list):
    if not a_int_list:
        return
    if len(a_int_list) < 2:
        return
    max = a_int_list[0]
    max_2 = a_int_list[1]
    for i in a_int_list:
        if i > max:
            max = i
        elif i > max_2:
            max_2 = i
    return max, max_2


# print find_two_max([1,3,4,5,6,4,5])
# 哈夫曼编码
‘‘‘
Huffman编码
?Huffman编码是一种无损压缩编码方案。
?思想：根据源字符出现的(估算)概率对字符
编码，概率高的字符使用较短的编码，概率
低的使用较长的编码，从而使得编码后的字
符串长度期望最小。
?Huffman编码是一种贪心算法：每次总选择
两个最小概率的字符结点合并。
?称字符出现的次数为频数，则概率约等于频数
除以字符总长；因此，概率可以用频数代替。
‘‘‘


# 计算给定字符串中每个字符的个数
def calc_frequency(a_in_str):
    counter = collections.defaultdict(lambda: 0)
    for a_char in a_in_str:
        counter[a_char] += 1
    return counter


# 定义树节点
class HuffmanNode():
    def __init__(self):
        self.value = 0
        self.parent = None
        self.left_child = None
        self.right_child = None


def select_two_mini(hn_list):
    # 选出两个较小的节点
    #
    if not hn_list:
        return
    mini_1 = None
    mini_2 = None
    i = 0
    for node in hn_list:
        if not node.value or node.parent is not None:
            # 如果已经在树的叶子节点,则continue
            i = i + 1
            continue
        else:
            if mini_1 is None:
                mini_1 = i
                i += 1
                continue
            if mini_2 is None:
                mini_2 = i
                i += 1
                continue
            elif node.value < hn_list[mini_1].value:
                mini_1 = i
            elif node.value < hn_list[mini_2].value:
                mini_2 = i
        i += 1
    return mini_1, mini_2


def HuffmanCoding(char_counter_dict):
    if not char_counter_dict:
        return
    # 字符列表
    char_list = char_counter_dict.keys()
    # 值列表
    value_list = char_counter_dict.values()
    leaf = len(char_counter_dict)
    # 共有2n-1 个节点
    node_num = 2 * leaf - 1
    # 先把所有的节点生成
    hn_list = [HuffmanNode() for _ in range(node_num)]
    # 先把leaf节点放在hn_list的前n个位置上
    for i in range(leaf):
        hn_list[i].value = value_list[i]
    # 每次选择最小的两个节点建树，填补后面的hn_list,parent,child字段全部放的是索引号
    for i in range(leaf, node_num):
        node1, node2 = select_two_mini(hn_list)
        hn_list[node1].parent = hn_list[node2].parent = i
        hn_list[i].left_child = node1
        hn_list[i].right_child = node2
        hn_list[i].value = hn_list[node1].value + hn_list[node2].value
    print hn_list
    # 根据建立好的哈夫曼树来计算从叶子到根计算每个叶子节点的哈夫曼编码
    huffman_codding = []
    for i in range(leaf):
        a_codding = ""
        child = i
        pt = hn_list[i].parent
        while (pt):
            if hn_list[pt].left_child == child:
                a_codding += "0"
            else:
                a_codding += "1"
            child = pt
            pt = hn_list[pt].parent
        a_codding = a_codding[::-1]
        huffman_codding.append(a_codding)
    return dict(zip(char_list, huffman_codding))


# a_dict = {"A": 15, "B": 7, "C": 6, "D": 6, "E": 5}
# print HuffmanCoding(a_dict)
‘‘‘
思考题：字符串循环左移
?给定一个字符串S[0…N-1]，要求把S的前k
个字符移动到S的尾部，如把字符串“abcdef”
前面的2个字符‘a’、‘b’移动到字符串的尾
部，得到新字符串“cdefab”：即字符串循环
左移k。
?循环左移n+k位和k位的效果相同。
?多说一句：循环左移k位等价于循环右移n-k位。
?算法要求：
?时间复杂度为O(n)，空间复杂度为O(1)。
解法：
首先将字符串a分为两段,要移动的前i位为b，剩余部分为c，
则字符串可表示为bc，
左移i位的结果其实就是cb，
则算法的目的就是将bc转换为cb。
首先将b逆序为b‘，再将c逆序为c‘，
最后将(b‘c‘)‘整体逆序即得到cb。
‘‘‘


def reverse_str(a_str_list, start, end):
    if not a_str_list:
        return
    while (end > start):
        tem = a_str_list[start]
        a_str_list[start] = a_str_list[end]
        a_str_list[end] = tem
        start += 1
        end -= 1


def circulation(a_in_str, k_len):
    a_list = list(a_in_str)
    reverse_str(a_list, 0, k_len - 1)
    reverse_str(a_list, k_len, len(a_in_str) - 1)
    reverse_str(a_list, 0, len(a_in_str) - 1)
    return "".join(a_list)


# print circulation("abcde",2)

##############################################第二课链表、队列、堆栈#####################################################

‘‘‘
Eratosthenes筛法求素数
?给定正整数N，求小于等于N的全部素数。
?Eratosthenes筛法
?将2到N写成一排；
?记排头元素为x，则x是素数；除x以外，将x的
倍数全部划去；
?重复以上操作，直到没有元素被划去，则剩余
的即小于等于N的全部素数。
?为表述方面，将排头元素称为“筛数”。

‘‘‘


# 算法改进: 当筛a时，a*a 以内的数已经完成了筛选,不包括a*a
# 注意这种标记法

def Eratosthenes(end_num):
    all_num_flags = [True for i in xrange(1, end_num + 2)]
    all_num_flags[0] = False  # 为了编写代码方便，0位置设为不可用
    # 首先默认全部数是素数
    p = 2  # 第一个筛子
    end_range = p * p
    while end_range <= end_num:
        # 任何一个筛子p 的第一个合数是 p*p
        cp = end_range
        while cp <= end_num:
            all_num_flags[cp] = False
            cp += p
        # 筛选下一个筛子
        p += 1
        while not all_num_flags[p]:
            p += 1
        end_range = p * p
    i = 0
    prime_num_list = []
    for flag in all_num_flags:
        if flag:
            prime_num_list.append(i)
        i += 1
    return prime_num_list


‘‘‘
链表相加
?给定两个链表，分别表示两个非负整数。它
们的数字逆序存储在链表中，且每个结点只
存储一个数字，计算两个数的和，并且返回
和的链表头指针。
?如：输入：2→4→3、5→6→4，输出：7→0→8
‘‘‘


class AddNode():
    def __init__(self):
        self.value = None
        self.next = None


def add_node_list(nl1, nl2):
    if not nl2:
        return nl1
    if not nl1:
        return nl2
    head = AddNode()
    cur = head
    carry = 0  # 进位
    while (nl1 and nl2):
        value = nl1.value + nl2.value + carry
        carry = value // 10
        value = value % 10
        new_node = AddNode()
        new_node.value = value
        cur.next = new_node
        cur = cur.next
        nl1 = nl1.next
        nl2 = nl2.next

    # 将长的链表的未向附在后边
    if nl1:
        long_nl = nl1
    else:
        long_nl = nl2
    while (long_nl):
        value = long_nl.value + carry
        new_node = AddNode()
        new_node.value = value
        long_nl = long_nl.next
        cur.next = new_node
        cur = cur.next
    return head.next


def print_node_list(nl):
    head = nl
    while (head):
        print head.value,
        head = head.next
    print "\n"


def test_add_node_list():
    nl1 = AddNode()
    cur = nl1
    for i in range(3):
        new_node = AddNode()
        new_node.value = random.randint(1, 9)
        cur.next = new_node
        cur = cur.next
    nl2 = AddNode()
    cur = nl2
    for i in range(4):
        new_node = AddNode()
        new_node.value = random.randint(1, 9)
        cur.next = new_node
        cur = cur.next
    print_node_list(nl1.next)
    print_node_list(nl2.next)
    head = add_node_list(nl1.next, nl2.next)
    print_node_list(head)


# test_add_node_list()

"""
链表的部分翻转
?给定一个链表，翻转该链表从m到n的位置。
要求直接翻转而非申请新空间。
?如：给定^-1→2→3→4→5，m=2，n=4，返回
^-1→4→3→2→5。
?假定给出的参数满足：1≤m≤n≤链表长度。
"""


class int_node():
    def __init__(self):
        self.value = None
        self.next = None


def part_reverse(nl, start, end):
    if end <= start:
        return
    p_head = nl  # 头插的头部节点
    for i in range(start - 1):
        p_head = nl.next
    p_end = p_head.next  # 最终的尾部
    p_cur = p_end.next  # 当前要头插的节点
    for _ in range(end - start):
        # 头插法
        # 1 先释放p_cur.next : 结果的尾部指向当前要改变的尾部
        p_end.next = p_cur.next
        # 2 再填补上p_cur.next ：当前的尾部指向头的下一个节点
        p_cur.next = p_head.next
        # 3 再填补上p_head.next ：头的下一个节点指向当前
        p_head.next = p_cur
        # 4 完成当前移动之后，让p_cur 指向下一个需要移动的节点
        p_cur = p_end.next


def test_part_reverse():
    head = int_node()
    p_cur = head
    head.value = -1
    for i in range(10):
        new_node = int_node()
        new_node.value = random.randint(1, 9)
        p_cur.next = new_node
        p_cur = new_node
    print_node_list(head)
    part_reverse(head, 1, 10)
    print "翻转后"
    print_node_list(head)


# test_part_reverse()

‘‘‘
最长公共子序列，即Longest Common
Subsequence，LCS。
?一个序列S任意删除若干个字符得到新序列T，则T
叫做S的子序列；
?两个序列X和Y的公共子序列中，长度最长的那
个，定义为X和Y的最长公共子序列。
? 字符串13455与245576的最长公共子序列为455
? 字符串acdfg与adfc的最长公共子序列为adf
?注意区别最长公共子串(Longest Common Substring)
? 最长公共字串要求连续

解法：属于动态规划问题
需要前面所有规划路径上的解才能解决问题
一般情况下都是先求长度，再求具体值
初始条件:

LCS(X,0) = 0
状态转移方程：
LCS(Xm,Yn)=LCS(Xm-1,Yn-1) 当xm = ym 时
LCS(Xm,Yn)=MAX(LCS(Xm-1,Yn),LCS(Xm,Yn-1)) 当xm ！= ym 时
得到迭代过程中的全部解之后，回溯棋盘可得最终解空间

状态转移方程变为数据结构：
Xm序列和Yn序列分别横置和竖置，变为一个（m+1）*（n+1）的数组棋盘
（i，j）格子代表Xm[:i],Yn[:j]的最大公共子序列的长度
当（i，j）对应字符不相等时，取左、上中较大的数
当（i，j）对应字符相等时，取对角的数+1

从末尾元素回溯棋盘，记录走斜线的格子，就是解空间

‘‘‘


def lcs(Xm, Yn):
    m = len(Xm)
    n = len(Yn)
    chess = []
    first_row = []
    for j in range(n + 1):
        first_row.append(0)
    for i in range(m + 1):
        chess.append(copy.deepcopy(first_row))
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if Xm[i - 1] == Yn[j - 1]:
                chess[i][j] = chess[i - 1][j - 1] + 1
            else:
                chess[i][j] = max([chess[i - 1][j], chess[i][j - 1]])
    # pprint.pprint (chess)
    return chess


def recall_lcs(Xm, Yn, chess):
    print chess
    m = len(Xm)
    n = len(Yn)
    result = []
    while (m != 0 and n != 0):
        if Xm[m - 1] == Yn[n - 1]:
            result.append(Yn[n - 1])
            m -= 1
            n -= 1
        else:
            if chess[m][n - 1] >= chess[m - 1][n]:
                n -= 1
            else:
                m -= 1
    result.reverse()
    print "".join(result)


# Xm="abcdefg"
# Yn="bcafegd"
# chess = lcs(Xm,Yn)
# recall_lcs(Xm,Yn,chess)
def recall_lcs_dfs(Xm, Yn, m, n, chess, result):
    ‘‘‘
    深度优先算法,发现可能有重复解，两条路径有交叉点的情况
    递归的核心是把上下文放入参数当中，这样在遇到n岔路时可以把上下文传入，
    递归执行n-1个路口，然后返回，继续执行最后一个路口，递归结束
    :param Xm:
    :param Yn:
    :param m:
    :param n:
    :param chess:
    :param result:
    :return:
    ‘‘‘
    rl = list(result)

    while (m != 0 and n != 0):
        if Xm[m - 1] == Yn[n - 1]:
            rl.append(Yn[n - 1])
            m -= 1
            n -= 1
        else:
            if chess[m][n - 1] > chess[m - 1][n]:
                n -= 1
            elif chess[m][n - 1] == chess[m - 1][n]:
                # 当前节点有两条路可选，选一条路进行递归，把上下文打包传入
                recall_lcs_dfs(Xm, Yn, m - 1, n, chess, "".join(rl))
                # 回到岔路口走下一条路
                n -= 1
            else:
                m -= 1
    rl.reverse()
    print "".join(rl)


def test_recall_lcs_dfs():
    Xm = "efghab"
    Yn = "egfahb"
    chess = lcs(Xm, Yn)
    print chess
    result = ""
    recall_lcs_dfs(Xm, Yn, 6, 6, chess, result)


#
‘‘‘
原数组为A {5，6，7，1，2，8}
?排序后：A’{1，2，5，6，7，8}
?因为，原数组A的子序列顺序保持不变，而且排序
后A’本身就是递增的，这样，就保证了两序列的最
长公共子序列的递增特性。如此，若想求数组A的
最长递增子序列，其实就是求数组A与它的排序数
组A’的最长公共子序列。
? 此外，本题也可以直接使用动态规划/贪心法来求解

贪心法就是一阶马尔科夫模型
动态规划就是高阶马尔科夫模型
都具有无后效性：只需要看前面的结果，而前面的结果是不改变的。
总结：历史是不可改变的，未来是不可预期的，现在是能从历史推演出来的！
最长递增子序列: 动态规划解法：贪心法


‘‘‘


# 动态规划法
def lis_dp(a_int_list):
    # 构造二维数组
    results = []
    # for i in range(len(a_int_list)):
    #     results.append([])

    j = 0
    max = 0
    # 考察每个元素，每个元素的初始长度为其本身，
    for i in a_int_list:
        results.append([i])

        # 循环查询前面的j个结果，如果能更新，就更新二维数组
        for h in range(j):
            if i > results[h][-1] and len(results[h]) + 1 > len(results[j]):
                temp2 = copy.deepcopy(results[h])
                temp2.append(i)
                if len(temp2) > len(results[j]):
                    results[j] = temp2
        if len(results[j]) > len(results[max]):
            max = j
        j += 1
    print results
    print max
    return results[max]


# a_int_list = [3, 5, 8, 7, 4, 9, 12, 6]
# print lis_dp(a_int_list)


# 贪心法
def greedy_lis(a_int_list):
    temp = []
    fl = []
    for _ in a_int_list:
        fl.append(False)
    fl[0] = True
    for num in a_int_list:
        if not temp:
            temp.append(num)
            continue
        if num > temp[-1]:
            temp.append(num)
        else:
            # 替换掉temp中比num稍微大一点点的元素
            # for i in range(len(temp)):
            #     if temp[i]>num:
            #         temp[i]=num
            # 改为折半查找：
            low = 0
            high = len(temp) - 1
            while (low < high):
                mid = (low + high) / 2
                if num < temp[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            if temp[low] > num:
                temp[low] = num
            else:
                temp[low + 1] = num
    print temp
    print len(temp)


# a_int_list = [3, 5, 8, 7, 4, 9, 12, 6]
# greedy_lis(a_int_list)

‘‘‘
给定字符串S[0…N-1]，设计算法，枚举S的
全排列

一般这种题就是考递归的思想的，
解法：

‘‘‘


def swap(a_int_list, a, b):
    if a == b:
        return
    else:
        temp = a_int_list[a]
        a_int_list[a] = a_int_list[b]
        a_int_list[b] = temp
def is_duplicate(a_int_list,i_start,i):
    while(i_start<i):
        if a_int_list[i_start] == a_int_list[i]:
            return True
        i_start+=1
    else:
        return False

#
def Permutation(a_int_list,size,i_start):
    # 这个递归上下文又开始点i_start 和 size 唯一确定，
    # 每次i_start 都向下移动，而size不变
    # 出口条件为i_start 移动到了最后一个元素，也就是任何单个元素的全排列只有他自己
    #i_start 从0开始计数
    if i_start == size-1:
        print a_int_list
        return
    swaped =  set([])
    for i in range(i_start,size): # a[i]是当前要交换的元素
        # if is_duplicate(a_int_list,i_start,i):
        #     # a[i]是否与[i_start,i)重复，如果当前要交换的元素，在之前已经交换过了，就不交换了
        #     continue
        # 考空间换时间
        if a_int_list[i] in swaped:
            continue
        swaped.add(a_int_list[i] )
        swap(a_int_list,i,i_start)
        Permutation(a_int_list,size,i_start+1)
        swap(a_int_list,i_start,i)

Permutation([1,2,3,2],4,0)

# KMP算法