目录

 

数组

1. 二维数组转置

2.有序二维数组查找

链表

1.单项列表实现反向打印

2.双向列表

栈

1.利用列表实现栈

2.利用链表实现栈

Link-Based vs. Array-Based Sequences

3.字符串公式计算

4.判断字符串数学公式是否合法

5.文件内容顺序倒置

队列

1.python内部集成队列

2.数组实现队列

3.链表实现队列

---

数组

1. 二维数组转置

grid = [['.', '.', '.', '.', '.', '.'],
['.', 'O', 'O', '.', '.', '.'],
['O', 'O', 'O', 'O', '.', '.'],
['O', 'O', 'O', 'O', 'O', '.'],
['.', 'O', 'O', 'O', 'O', 'O'],
['O', 'O', 'O', 'O', 'O', '.'],
['O', 'O', 'O', 'O', '.', '.'],
['.', 'O', 'O', '.', '.', '.'],
['.', '.', '.', '.', '.', '.']]

#转置四种种方法
grid_T =map(list,zip(*grid))
#grid_T = list(zip(*grid))
#grid_T = list(list(i) for i in zip(*grid))
#grid_T = [[row[i] for row in grid] for i in range(len(grid[0]))]

for line in grid_T:
    dots = ''
    for dot in line:
        dots += dot
    print(dots,end='\n')

2.有序二维数组查找

题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

class Solution:
    def Find_lower_left(self,target,array):
        """        从左下向右上检测        """
        cols = len(array[0])-1
        rows = len(array)-1
        i = rows
        j=0
        while j<=cols and i>=0:
            if target>array[i][j]:
                j +=1
            elif target<array[i][j]:
                i -=1
            else:
                return True
        return False

    def Find_upper_right(self,target,array):
        """        从右上向左下检测       """
        rows = len(array)-1
        cols = len(array[0])-1
        i = 0
        j = cols
        while i<=rows and j >=0:
            if target>array[i][j]:
                i +=1
            elif target< array[i][j]:
                j -=1
            else:
                return True
        return False


if __name__=="__main__":
    solution = Solution()
    target = 11
    array = [[1,3,5],[7,9,11],[13,15,17]]
    print(solution.Find_lower_left(target,array))
    print(solution.Find_upper_right(target,array))

链表

1.单项列表实现反向打印

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

class Solution:
    """
    反向打印链表
    """
    def printListFromTailToHead(self, listNode):
        # write code here
        pre_header = listNode
        result = []
        while pre_header != None:
            #result.append(pre_header.val)
            #  return result[::-1] or result.reverse()
            result.insert(0,pre_header.val)
            pre_header = pre_header.next
        return result

    def printListFromTailToHead_1(self, listNode):
        #   递归的方法
        if listNode is not None:
            return list(self.printListFromTailToHead_1(listNode.next))+ list([listNode.val])
        else:
            return []

if __name__ == "__main__":
    solution = Solution()
    Node_1 = ListNode(1)
    Node_2 = ListNode(2)
    Node_3 = ListNode(3)
    Node_1.next = Node_2
    Node_2.next = Node_3

    print(solution.printListFromTailToHead(Node_1))

2.双向列表

class _DoubleLinkedBase:
    '''A base class providing a doubly linked list representation.'''
    class _Node:
        __slots__ = '_element','_prev','_next'

        def __init__(self,element,prev,next_):
            self._element = element
            self._prev = prev
            self._next = next_
    def __init__(self):
        # 这里header和trailer只是一个前后标识，并没有实际存储作用
        self._header = self._Node(None,None,None)
        self._trailer = self._Node(None,None,None)
        self._header._next = self._trailer
        self._trailer._prev = self._header
        self._size = 0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size == 0
    def _insert_between(self,e,predecessor,successor):
        newest = self._Node(e,predecessor,successor)
        predecessor._next = newest
        successor._prev = newest
        self._size += 1
        return newest
    def _delete_node(self,node):
        predecessor = node._prev
        successor = node._next
        predecessor._next = successor
        successor._prev = predecessor
        self._size -= 1
        element = node._element
        node._prev = node._next = node._element = None
        return element

栈

1.利用列表实现栈

class ArrayStack:
    '''LIFO Stack implementation using a Python list as underlying storage.'''
    def __init__(self):
        self.data = []
    def __len__(self):
        return len(self.data)
    def is_empty(self):
        return len(self.data) == 0
    def push(self, e):
        self.data.append(e)
    def top(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        return self.data[-1]
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        return self.data.pop()

2.利用链表实现栈

class LinkedStack:
    class _Node:
        __slots__ = '_element','_next'      # __slots__变量限制该class能添加的属性
        def __init__(self,element,next):
            self._element = element
            self._next = next
    def __init__(self):
        self._head = None                   # 链表的第一个node
        self._size = 0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size == 0
    def push(self, e):
        self._head = self._Node(e,self._head)
        self._size += 1
    def top(self):
        if self.is_empty():
            raise IndexError('Stack is empty')
        return self._head._element
    def pop(self):
        if self.is_empty():
            raise IndexError('Stack is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        return answer

Link-Based vs. Array-Based Sequences

数组：

• 数组提供基于整数索引的元素的O(1)时间访问。相反，定位第k个元素在链表中需要O(k)时间从开始遍历列表，或者可能是O(n-k)时间，如果从双端向后遍历链表。
• 基于数组的表示通常使用比链接结构更少的内存,但有时会出现存储空间大于存储元素情况，造成内存浪费。
• 插入和删除操作非常昂贵(后继内存会相应移动)

链表优势：

• 基于链表的结构支持O(1)时间插入和删除在任意位置。而基于数组的列表类，在索引k处插入或弹出使用O(n-k+1)时间，因为所有后续元素会被循环移位
• 利用分散内存存储元素，没有浪费内存，插入和删除操作方便

 

3.字符串公式计算

def Evaluate(expr):
    ops = LinkedStack()
    vals = LinkedStack()
    for i in expr:
        if i == '(':
            pass
        elif i == '+':
            ops.push(i)
        elif i == '-':
            ops.push(i)
        elif i == '*':
            ops.push(i)
        elif i == '/':
            ops.push(i)
        elif i == '//':
            ops.push(i)
        elif i == ')': # 如果字符为）,弹出运算符合操作数，计算结果并压入栈
            op = ops.pop()
            v = vals.pop()
            if op == '+':
                v = vals.pop() + v
            if op == '-':
                v = vals.pop() - v
            if op == '*':
                v = vals.pop() * v
            if op == '/':
                v = vals.pop() / v
            if op == '//':
                v = vals.pop()//v
            vals.push(v)
        else:
            vals.push(int(i))
    return vals.pop()

if __name__ == '__main__':
   print( Evaluate('(1+(2*2))'))

4.判断字符串数学公式是否合法

def match_math(expr):
    '''Return True if all delimiters are properly match; False otherwise.'''
    lefty = '({['
    righty = ')}]'
    S = LinkedStack()
    for c in expr:
        if c in lefty:
            S.push(c)
        elif c in righty:
            if S.is_empty():
                return False
            if righty.index(c) != lefty.index(S.pop()):
                return False
    return S.is_empty()

if __name__ == '__main__':
   print( match_math('(1+(2*2))'))

5.文件内容顺序倒置

def reverse_file(file_name):
    '''Overwrite given file with its contents line-by-line reversed.'''
    S = LinkedStack()
    original = open(file_name)
    for line in original:
        S.push(line.rstrip('\n'))
    original.close()

    output = open(file_name,'w')
    while not S.is_empty():
        output.write(S.pop() + '\n')
    output.close()


if __name__ == '__main__':
    reverse_file('tst.txt')

队列

1.python内部集成队列

import queue                     #单向
from collections import deque    #双向

2.数组实现队列

class ArrayQueue:
    DEFAULT_CAPACITY = 10                                   #固定大小，循环使用
    def __init__(self):
        self._data = [None]*ArrayQueue.DEFAULT_CAPACITY     #是一个具有固定容量的列表实例的引用。
        self._size = 0                                      #表示存储在队列中的元素的当前数量
        self._front = 0                                     #队列第一个元素在数据中的索引

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        '''Return (but do not remove) the element at the front of the queue'''
        if self.is_empty():
            raise IndexError('Queue is empty')
        return self._data[self._front]

    def dequeue(self):
        '''Remove and return the first element of the queue'''
        if self.is_empty():
            raise IndexError('Queue is empty')
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front +1)%len(self._data)
        self._size -= 1
        return answer

    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front + self._size)%len(self._data)      #在_data范围内循环使用
        self._data[avail] = e
        self._size += 1

    def _resize(self,cap):
        old = self._data
        self._data = [None] * cap
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1+walk) % len(old)
        self._front = 0

3.链表实现队列

class LinkedQueue:
    class _Node:
        __slots__ = '_element','_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise IndexError('Queue is empty')
        return self._head._element

    def dequeue(self):
        if self.is_empty():
            raise IndexError('Queue is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None
        return answer

    def enqueue(self, e):
        newest = self._Node(e,None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

树

令T为非空二叉树，n为节点数，为外部节点(叶节点)，为内部节点，h为高度：

对于一棵满二叉树，外部节点或者说是叶子节点数是n，则内部节点数是n-1。

前序遍历

输入：树结构T，遍历以p为根的子树

Algorithm preorder(T, p):
    perform the “visit” action for position p
    for each child c in T.children(p) do
        preorder(T, c)        #递归遍历以C为根的子树

中序遍历

输入：遍历以p为根的子树

Algorithm inorder(p):
    if p has a left child lc then
        inorder(lc)             #递归遍历P的左子树
    perform the “visit” action for position p
    if p has a right child rc then
        inorder(rc)             #递归遍历P的右子树

 

后序遍历

​

输入：树结构T，遍历以p为根的子树

Algorithm postorder(T, p):
    for each child c in T.children(p) do
        postorder(T, c)             #递归遍历以C为根的子树
    perform the “visit” action for position p

 

广度优先遍历

广度优先遍历是用于游戏中常用的方法

​

输入：树结构T

Algorithm breadthfirst(T):
    Initialize queue Q to contain T.root( )
    while Q not empty do
        p = Q.dequeue( )                     #P是队列中最古老的条目
        perform the “visit” action for position p
        for each child c in T.children(p) do
            Q.enqueue(c)                     #将P的孩子添加到队列的末尾以供稍后访问

 

1.根据前向和中序遍历得到树结构

class TreeNode:
    def __init__(self,x):
        self.val = x
        self.right = None
        self.left = None

class Solution:
    def reConstructBinaryTree(self, pre, tin):
        """
        :param pre: 前向遍历
        :param tin: 中序遍历
        :return: 树结构
        """
        if not pre or not tin:
            return None
        root = TreeNode(pre.pop(0))
        index = tin.index(root.val)
        # 递归
        root.left = self.reConstructBinaryTree(pre,tin[:index])
        root.right = self.reConstructBinaryTree(pre,tin[index+1:])
        return root

if __name__=="__main__":
    solution = Solution()
    pre = [1,2,4,7,3,5,6,8]
    tin = [4,7,2,1,5,3,8,6]
    tree = solution.reConstructBinaryTree(pre,tin)
    print(tree)

散列表（Hash Table）

利用算术操作将键转换为数组的索引，来访问数组中的键值对。在时间和空间上作出权衡

1. 利用散列函数将被查找的键转化为数组的一个索引，但会出现地址碰撞问题
2. 处理碰撞冲突：拉链法和线性探测法

散列函数

每种类型的键，都需要一个与之对应的散列函数

Python中计算Hash Code的标准机制是内置函数hash(x). 根据输入对象x返回一个整数值，用作哈希代码。但只有不可变的数据类型在Python中被认为是可哈希的。

除留余数法

• 整数

选择大小为素数M的数组，对任意正整数k，计算k除以M的余数

• 字符串

将字符串看作一个大整数：这种计算可以将字符串看作一个R进制值，并除以M取余数。

hash = 0
for i in range(len(s)):
    hash = (R*hash + s[i]) % M

• 组合键

例如：键Date，其中有day（两个数字），month（两个数），year（四个数）

hash = (((day*R +month)%M)*R+year)%M

基于拉链法的散列表

将数组中每个元素指向一个链表，链表中每个结点都存储了散列值作为键值对。

1. 首先根据散列值找到对应的链表
2. 然后沿着链表顺序查找相应的键