算法基础实例—Python3

算法基础实例—Python3

• 指针操作
• 递归
• 算法时间，空间复杂度分析
• 数据结构
• 基础算法实例
  

收集的常见题目

• python 单例模式的实现方法
• 写一个快速排序
• 写一个拓扑排序
• python 实现一个二进制计算
• 有一组“+”和“-”符号，要求将“+”排到左边，“-”排到右边，写出具体的实现方法。
• 单链表反转
• 交叉链表求交点
• 用队列实现栈
• 找出数据流的中位数
• 二叉搜索树中第 K 小的元素
• 如何交换字典 {“A”：1,“B”：2}的键和值？
• Python 里面如何实现 tuple 和 list 的转换？
• 我们知道对于列表可以使用切片操作进行部分元素的选择，那么如何对生成器类型的对象实现相同的功能呢？
• 在重复元素array中查找两个非重复元素
• 给定 n 个项目的重量和值，将这些物品放入容量为 W 的背包中背包中的最大总价值。
• 给定一根长度为 n 英寸的杆和一系列价格，其中包含所有尺寸小于 n 的尺寸的价格。确定通过切割杆和销售件可获得的最大值。
• 给定两个字符串 str1 和 str2 以及可以在 str1 上执行的操作。查找所需的最小编辑数（操作）将’str1’转换为’str2’
• 给定 0 和 1 的二维矩阵，找到最大的广场，其中包含全部 1。
• 找到两者中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。
• 找到给定序列的最长子序列的长度，以便对子序列的所有元素进行排序，按顺序递增。
• 将一个集合划分为两个子集，使得子集和的差异最小
• 给定一组非负整数和一个值和，确定是否存在给定集合的子集，其总和等于给定总和。
• HackerRank 问题算法 DP
• 给定距离 dist，计算用 1,2 和 3 步覆盖距离的总方式
• 在字符板中查找所有可能的单词
• 在有向图中检测周期
• 检测无向图中的循环
• Dijkstra的最短路径算法
• 在给定的边缘加权有向图中找出每对顶点之间的最短距离
• 图形实现
• Kruskal的最小生成树算法
• 拓扑排序
• 两个字符串是否是变位词
• 单链表逆置
• 前序中序求后序
• 求两棵树是否相同
• 求最大树深
• 前中后序遍历
• 二叉树节点
• 广度优先搜索遍历
• 深度优先搜索遍历

不连续子串判断

实现⼀个函数，判断helloworld是否是给定字符串的不连续子串

即helloworld的每个字母均在给定字符串中出现，并且需要保持先后顺序但可以允许不相邻

如helllllllo wwwwwwworld 符合条件，如红色的标记所示。

但helolllllworld不符合条件。

_与+字符变换

给定一个只包含小写字母和‘_’的字符串，输出如下变换后的结果：

字符串被连续的'_'分成了若干子串，如果一段连续的'_'两侧是相同的子串，则将这段'_'的每个字符变为'+'

观察3D空间中的线段是否相交

3D空间里，给定两条长度非零的线段S1、S2（S1与S2不共面），以及一个点O（不在S1、S2上）。

判断以O点作为观测点观察，S1和S2是否相交（即S1和S2至少要有一个公共点）。

**List，Set 查找时间

已知：

    AList = [1,2,3]

    BSet = {1,2,3}

1. 从 AList 和 BSet 中 查找 4，最坏时间复杂度那个大？
2. 从 AList 和 BSet 中 插入 4，最坏时间复杂度那个大？

已整理输出的案例

合并字符串

"""合并字符串
给定字符串，删除开始和结尾处的空格，并将中间的多个连续的空格合并成一个。
# 比如 “   I like     football    ” 会变成 "I like football"
"""

class StripStr():
    def __init__(self):
        pass
    
    def get_real_str(self, strs=None):
        strs ="   I like     football    "  # 会变成 "I like football"
        strs_list = strs.split(" ")
        strs_list = [iStr for iStr in strs_list if len(iStr.strip())]
        new_strs = " ".join(strs_list).strip()
        print(new_strs)
        
if __name__ == "__main__":
    ns = StripStr()
    ns.get_real_str()

重复字符串排序

"""从类似如下的文本文件中读取出所有的姓名，并打印出重复的姓名和重复的次数，并按重复次数排序：
# 1,张三,28
# 2,李四,35
# 3,张三,28
# 4,王五,35
# 5,张三,28
# 6,李四,35
# 7,赵六,28
# 8,田七,35
"""
class GetRepeatStr():
    def __init__(self):
        self.strs = """1,张三,28
                        2,李四,35
                        3,张三,28
                        4,王五,35
                        5,张三,28
                        6,李四,35
                        7,赵六,28
                        8,田七,35"""

    
    def count_repeat_num(self, strs=None):
        strs_lines = self.strs.split('\n')
        strs_lines = [iStr.split(",")[1] for iStr in strs_lines]
        strs_count = []
        real_strs = set(strs_lines)
        for iStr in real_strs:
            count = 0
            for temp_str in strs_lines:
                if iStr in temp_str:
                    count += 1
            strs_count.append({"name":iStr,"count":count})
#         print(strs_count)
        return strs_count
    
    def sort_strs_count(self, strs_count=None):
        strs_count = sorted(strs_count, key=lambda strs:strs["count"] )
#         print(strs_count)
        return strs_count
        
    def print_sorted_repeat_strs(self, strs=None):
        strs_count = self.count_repeat_num()
        sorted_strs = self.sort_strs_count(strs_count)
        print(sorted_strs)

if __name__ == "__main__":
    strs = GetRepeatStr()
    strs.print_sorted_repeat_strs()

集合覆盖

"""集合覆盖
"""

def over_space():
    
    s1 = input()
    s1 = [num for num in s1.split(' ') if right_number(num)]
    if None in s1:
        return None
    s1_x1, s1_y1, s1_x2, s1_y2 = s1
    s2 = input()
    s2 = [right_number(num) for num in s2.split(' ') ]
    if None in s2:
        return None
    s2_x1, s2_y1, s2_x2, s2_y2 = s2
    col = min(int(s1_x2),int(s2_x2)) - max(int(s1_x1),int(s2_x1))
    row = min(int(s1_y2),int(s2_y2)) - max(int(s1_y1),int(s2_y1))
    overSpace = col * row
    print(overSpace)

import copy
from collections import defaultdict
def helloworld(taskStr="helloworld"):
    s = input()
    s = list(s) 
    if len(taskStr) > len(s):
        return False
    s1 = ''.join([char for char in s if char in taskStr])
    tempIndex = 0
    for char in taskStr:
        if char in s1:
            sIndex = s1.index(char)
            if tempIndex <= sIndex:
                tempIndex = sIndex
            else:
                print("false")
                return False
    print("true")
    return True

判断回文字符串

"""判断回文字符串"""

def huiwen(s,i,step,rst):
    if i > len(s) - 1:
        return rst
    if s[i] != s[i+step] and s[i+step] == "" and i+step < len(s) - 1:
        step += 1
        return huiwen(s,i,step,rst)
    elif s[i] == s[i+step] and i+step < len(s) - 1:
        rst = s[i] + '+'*step + s[i+step]
        i += step
        step = 1
        return huiwen(s,i,step,rst)
    elif s[i] != s[i+step] and s[i+step] != "" and i+step < len(s) - 1:
        i += step
        step = 1
        return huiwen(s,i,step,rst)
    else:
        rst = s[i] + '_'*step + s[i+step]
        return rst

def asser_huiwen(s):
    s = s.strip('_')
    length = len(s)
    s = s.split("_")
    # s.remove("")
    rst = ""
    huiwen(s,i=0,step=1,rst=rst)
    print(rst)


if __name__ == "__main__":
    # helloworld()
    print(asser_huiwen("__aa_ab__ab"))

初始化链表

"""初始化链表

"""
class Node:
    def __init__(self,value):
        self.value = value
        self.next = None

class LinkList(object):
    def __init__(self):
        self.head = Node("head")
        
    def append_list(self,head,value):
        newNode = Node(value)
        head.next = newNode
        
    def display_list(self, head=None):
        tempHead = head or self.head
        count = -1
        while tempHead.next != None:
            count += 1
            print(tempHead.value,end=" ")
            tempHead = tempHead.next
        print("\nThe count of single Link list is : {}".format(count))

    def delete_item(self,value):
        tempHead = self.head
        deleteNode = tempHead.next
        if tempHead.value == value:
            tempHead = tempHead.next
            return 
        elif deleteNode.value == value:
            tempHead.next = deleteNode.next
            return 
        else:
            while deleteNode.value != value:
                tempHead = tempHead.next
                deleteNode = tempHead.next
            tempHead.next = deleteNode.next
        

    def init_list_by_arry(self,arry=[]):
        head = self.head
        if arry:
            for item in arry:
                self.append_list(head,item)
                head = head.next
        else:
            raise IOError("Arry is null ! ")
    
    def reverse_list_by_swap(self):
        if self.head is None or self.head.next is None:
            return self.head
        head = self.head
        pre = None
        cur = head
        while cur:
            head = cur
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return head
    
    def reverse_list_recursion(self,head=None, newhead=None):
        head = head or self.head
        if head is None:
            return  
        if head.next is None:
            rhead = head 
        else:
            rhead = self.reverse_list_recursion(head=head.next,newhead=rhead)
            head.next.next = head
            head.next = None
        return rhead
        
def task():
    begin = yield
    end = yield  
    yield
    for x in range(begin,end):
        yield x



if __name__ == "__main__":
    ll = LinkList()
    ll.init_list_by_arry([1,2,3,4,5,6,7,8,9])
    ll.display_list()
    # ll.delete_item(5)
    rl = ll.reverse_list_by_swap()
    ll.display_list(rl)
    # rl = ll.reverse_list_recursion()
    # ll.display_list(rl)
    t = task()
    t.send(None)
    t.send(3)

反转化链表

***反转化链表

***
class Node:
    def __init__(self,value):
        self.val = value
        self.next = None

class LinkList(object):
    def __init__(self):
        self.head = Node("head")
        
    def append_list(self,value):
        point = self.head
        newNode = Node(value)
        point.next = newNode
        point = point.next
        
    def display_list(self):
        tempHead = self.head
        while tempHead.next != None:
            print(tempHead.value)
            tempHead = tempHead.next
            
    def init_list_by_arry(self,arry=[]):
        if arry:
            for item in arry:
                self.append_list(item)
        else:
            raise IOError("Arry is null ! ")
    
class RecurseList:
    def non_recurse(head):
        if head is None or head.next is None:
            return head
        pre = None
        cur = head
        
if __name__ == "__main__":
    ll = LinkList()
    ll.init_list_by_arry([1,2,3,4,5,6,7,8,9])
    ll.display_list()

二叉树遍历

"""二叉树遍历
# 参考连接：https://zhuanlan.zhihu.com/p/33977566
"""

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

    def has_value(self, value):
        if self.data == value:
            return True
        else:
            return False
        
class BitTree:
    def __init__(self):
        self.root = None
        self.bitList = []

    def add_bit_item(self, item):
        if not isinstance(item, BitNode):
            item = BitBode(item)
        if self.root is None:
            self.root = item
            self.bitList.append(item)
        else:
            rootNode = self.bitList[0]
            while True:
                if item.data < rootNode.data:
                    # 往左移
                    if rootNode.left == None:
                        rootNode.left = item
                        self.bitList.append(item)
                        break
                    else:
                        rootNode = rootNode.left
                elif item.data > rootNode.data:
                    # 往右移
                    if rootNode.right == None:
                        rootNode.right = item
                        self.bitList.append(item)
                        break
                    else:
                        rootNode = rootNode.right

    def front_traverse(self,root):
        if root == None:
            return None
        print(root.data)
        self.front_traverse(root.left)
        self.front_traverse(root.right)

def display_bitTree(bitTree):
    if not isinstance(bitTree, BitTree):
        raise ValueError("类型错误")
    for bit in bitTree.bitList:
        print(bit.data)

def middle_traverse(root):
    if root == None:
        return None
    middle_traverse(root.left)
    print(root.data)
    middle_traverse(root.right)

def last_traverse(root):
    if root == None:
        return None
    last_traverse(root.left)
    last_traverse(root.right)
    print(root.data)

def floor_traverse(root):
    # 按层次遍历
    from collections import deque
    q = deque()
    if root == None:
        return None
    q.append(root)
    while q:
        node = q.pop()
        print(node.data)
        if node.left != None:
            q.append(node.left)
        if node.right != None:
            q.append(node.right)
    

if __name__ == "__main__":
    node1 = BitNode(15)
    node2 = BitNode(9)
    node3 = BitNode(16)
    node4 = BitNode(8)
    node5 = BitNode(10)
    node6 = BitNode(17)
    node7 = BitNode(20)
    bitTree = BitTree()
    for i in [node1,node2,node3,node4,node5,node6,node7,]:
        bitTree.add_bit_item(i)
    
    display_bitTree(bitTree)
    # 15 9 16 8 10 17 20
    print("先序遍历：")
    bitTree.front_traverse(bitTree.root)
    print("中序遍历：")
    middle_traverse(bitTree.root)
    print("后序遍历：")
    last_traverse(bitTree.root)
    print("按层次遍历：")
    floor_traverse(bitTree.root)

类继承

"""类继承
"""
from __future__ import division

class People:

    def __init__(self,name,age):
        self.name = name
        self.age = age
        
    def getName(self):
        return self.name
    
    def getAge(self):
        return self.age

class Student(People):
    
    def __init__(self,name,age,id):
        People.__init__(self, name, age)
        self.id = id
        
    def getId(self):
        return self.id

class Xdict(dict):
    
    def __init__(self,new_dict):
        dict.__init__(self)
        self.new_dict = dict(new_dict)
        
    def getKeys(self,value):
        if value in self.new_dict.values():
            key_list = []
            for ikey in self.new_dict.keys():
                if value in self.new_dict[ikey]:
                    key_list.append(ikey)
            return key_list
        else:
            return None

        
class Vector:
    
    def __init__(self,x,y,z):
        self.vt = (x,y,z)
    
    def __add__(self,other):
        return self.format(map(sum,zip(self.vt,other.vt)))
        
    def sub(self,si):
        return si[0] - si[1]
    
    def __sub__(self,other):     
        return self.format(map(self.sub,zip(self.vt,other.vt)))
        
    def mul(self,si):
        return si[0] * si[1]
    
    def div(self,si):
        return si[0] / si[1]
    
    def __mul__(self,other):
        return self.format(map(self.mul,zip(self.vt,[other]*len(self.vt))))

    
    def __truediv__(self,other):
        return self.format(map(self.div,zip(self.vt,[other]*len(self.vt))))
    
    def format(self,mps):
        for i in range(len(mps)):
            mps[i] = float("{:.1f}".format(mps[i]))
        return str(tuple(mps))
    
    def __str__(self): 
        for i in range(len(self.vt)):
            self.vt[i] = float("{:.1f}".format(self.vt[i]))     
        return str(tuple(self.vt))
        

        
if __name__ == '__main__':
    alist = input().split()
    blist = input().split()
    n = float(input())
    
    a = Vector(float(alist[0]),float(alist[1]),float(alist[2]))    
    b = Vector(float(blist[0]),float(blist[1]),float(blist[2]))    
    
    print "{} {} {} {}".format(a+b,a-b,a*n,a/n)

类方法重载

"""类方法重载"""

from __future__ import division
       
class Vector:
    
    def __init__(self,x,y,z):
        self.vt = (x,y,z)
    
    def __add__(self,other):
        self.vt = map(sum,zip(self.vt,other.vt))
        return self.__str__()
        
    def sub(self,si):
        return si[0] - si[1]
    
    def __sub__(self,other):     
        self.vt = map(self.sub,zip(self.vt,other.vt))
        return self.__str__()
        
    def mul(self,si):
        return si[0] * si[1]
    
    def div(self,si):
        return si[0] / si[1]
    
    def __mul__(self,other):
        self.vt = map(self.mul,zip(self.vt,[other]*len(list(self.vt))))
        return self.__str__()
    
    def __truediv__(self,other):
        self.vt = map(self.div,zip(self.vt,[other]*len(list(self.vt))))
        return self.__str__()
    
    def __str__(self):
        self.vt = list(self.vt)
        for i in range(len(self.vt)):
            self.vt[i] = float("{:.1f}".format(self.vt[i]))     
        return str(tuple(self.vt))
        

        
if __name__ == '__main__':
    alist = input().split()
    blist = input().split()
    n = float(input())
    a = Vector(float((alist[0])),float(alist[1]),float(alist[2]))
    b = Vector(float(blist[0]),float(blist[1]),float(blist[2]))    
    
    print ("{} {} {} {}".format(a+b,a-b,a*n,a/n))

完全数（Perfect number）

"""完全数（Perfect number）
又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
如果一个数恰好等于它的因子之和，则称该数为“完全数”。
第一个完全数是6，第二个完全数是28，第三个完全数是496，后面的完全数还有8128、33550336等等。
求某个范围内的完全数，先获取该范围内的所有数的约数（整除数），在验证约数之和是否等于自身。
调用divisors(num) 获取每个数的约数
调用checkDivisors(divs,num) 验证约数之和是否等于自身
"""

def countWanmeishu(nums):
    counts = []
    for ni in range(nums):
        divs = divisors(ni)       
        if divs and checkDivisors(divs[0],divs[1]):
            print "完美数： {}, 因子：{} \n".format(divs[1],divs[0])
            counts.append((divs))
    return counts   

合并重叠的空间集合

"""合并重叠的空间集合
"""
import copy

class Solution:
    def merge(self, intervals):
        if intervals == []:
            return intervals
        intervals.sort()
        begin = intervals[0][0]
        end = intervals[0][1]
        rst = list()
        for i in range(1, len(intervals)):
            if intervals[i][0] > end:
                rst.append([begin, end])
                begin = intervals[i][0]
                end = intervals[i][1]
            else:
                if intervals[i][1] > end:
                    end = intervals[i][1]
        rst.append([begin, end])
        return rst
                    
                    
    def cover_spcace(self,dirA,dirB):
        print(dirA, dirB)
        if max(dirA[0], dirB[0]) <= min(dirA[1],dirB[1]):
            return True
        else:
            return False
        
    def merge_set(self, dirA,dirB):
        newDir = (min(dirA[0],dirB[0]),max(dirA[1],dirB[1]))
        return newDir
        
if __name__ == "__main__":
    listA = [[1,3],[2,6],[8,10],[15,18]]
    listA =[[1,4],[4,5]]
    listA = [[1,4],[0,2],[3,5]]

    rst = [[1,6],[8,10],[15,18]]
    S = Solution()
    print(S.merge(listA))

实现列表中重复元素最后一次出现的索引位置

""" 实现列表中重复元素最后一次出现的索引位置

>>> get_last_exist_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 5)
5
>>> get_last_exist_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 8)
12
>>> get_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 5)
5
>>> get_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 8)
12
 """

listA = [3,4,5,6,6,5,4,3,2,1,7,8,8,3]
target = 5
def get_last_exist_dir(listA, target):
    # 倒置 list，查找其第一次出现的位置
    return len(listA)- 1 - listA[::-1].index(target) 
    # for index, num in listA[::-1]:
    #     if num == target:
    #         return index

def get_dir(listA, target):
    # 二分法 和 快速排序想法尝试，并不能有效解决所有情况！
    rst = None
    length = len(listA)
    left = 0
    right = length - 1
    # listA = listA[::-1]
    while left < right:
        mid = left + (right-left) // 2
        # if target in listA[mid:]:
        if target >= listA[mid]:
            rst = mid
            left = mid + 1
        else:
            right = mid - 1
    return rst

if __name__ == "__main__":
    import doctest
    doctest.testmod()

9*9乘法表

""" 9 * 9 乘法表
    用逗号分隔每个打印项，如果print的最后没有逗号，每一次循环都会换行。 
"""
def chengfabiao(n):
    if n <= 0:
        return 0
    for cs in range(1,n):
        print '\n'
        for cbs in range(1,cs + 1):
            print "%d x %d=%2d "%(cs,cbs,cs * cbs) , 

递增三元组子序列

• 题目描述

  给出一个无序的整数序列，返回是否存在递增的三元组子序列。

  如果存在 i, j, k 使得 arr[i]<arr[j]<arr[k] and 0<i<j<k<n-1，即返回true；如果不存在则返回false。
  请给出一个O(N)时间复杂度以及O(1)额外空间的算法。

  Example 1： [1, 2, 3, 4, 5]

  返回true。

  Example 2: [5, 4, 3, 2, 1]

  返回false。

• 分析解答

  不难想到枚举的方法，先枚举第一个数，再枚举找到第二个数（比第一个大），再枚举第三个数（比第二个数大），得到答案。但这样穷举过于低效，与要求的O(N)相距甚远。还有一种穷举方法是先预处理得到一个数组p，p[i]表示是否存在这样的j, j>i and arr[j]>arr[i]。这种方法符合时间复杂度的要求，但是额外空间是O(N)。因此我们需要换种思路，一边穷举一边记录已知的有用信息。当我们穷举到第i个数时，假设我们尚未找到答案，那么有以下几种情况：

  我们只找到一个数（前i-1个数没有递增的两个数），此时我们记录前i-1个数的最小值。我们已找到递增的二元组子序列，此时我们需要记录的是这样的最小二元组（以第二个数为第一关键字）

  有时我们需要记录第三个数。比如已有递增子序列（3，5），之后又出现一个数1，我们必须记录1，因为如果之后出现2，（1，2）当递增序列会覆盖（3，5）。

""" 递增三元组子序列
# Testcases:

>>> incressingThriplet_O1([1,2,3,4,5,6])
True
>>> incressingThriplet_O1([6,5,5,6,6,6])
False
>>> incressingThriplet_O1([8,9,3,5,8])
True
>>> incressingThriplet_O1([1,2,1,1,1,1])
False
"""

# O(n)时间复杂度 O(1)空间复杂度
def incressingThriplet_O1(numList):
    if len(numList) <= 2: return False;
    # 记录中间值，固定的空间(first, second)
    # first, second 默认取 list 中最大元素，如果是最小的或随机的，第二个递增元素就不能够确定 
    first, second = max(numList), max(numList)
    for iNum in numList:
        if iNum <= first:
            first = iNum
        if iNum > first and iNum <= second: 
            second = iNum
        if iNum > second:
            # print(first, second, iNum)
            return True
    return False

if __name__ == "__main__":
    import doctest
    doctest.testmod()