量化投资学习笔记42——基本数据结构算法总结1

还是补基础，学拉钩教育的《300分钟搞定数据结构与算法》https://kaiwu.lagou.com/course/courseInfo.htm?courseId=3 课程的笔记。
01.常用数据结构
数组、字符串
①示例:翻转字符串
用两个指针分别指向字符串首尾，交换两个字符，指针分别向前后进一位。直到两个指针相遇。

# 翻转字符串
str = "algorithm"
head = 0
tail = len(str) - 1
ls = ["a"]*len(str)
while head <= tail:
    ls[head] = str[tail]
    ls[tail] = str[head]
    head += 1
    tail -= 1
result = ''.join(ls)
print(result)

数组的优点:简单，索引查询效率O(1)。
数组的缺点:值查询，增删的效率O(n)。
②两个字符串s和t，判断t是否是s的异位词。
即字母数量相同，排列不同。

# 2.两个字符串s和t，判断t是否是s的异位词。
def isAnagram(s, t):
    alpha = [chr(i) for i in range(97, 123)]
    alphadic = {char:0 for char in alpha}
    l1 = len(s)
    l2 = len(t)
    if l1 != l2:
        return False
    for i in range(l1):
        alphadic[s[i]] += 1
        alphadic[t[i]] -= 1
    for i in range(97, 123):
        if alphadic[chr(i)] != 0:
            return False
    return True

力扣第242题，提交通过。
链表
优点，灵活使用内存空间，插入删除时间复杂度O(1)
缺点，只能顺序查找，复杂度O(n)。
③链表翻转问题
给定一个链表，每k个节点进行翻转。

def reverseKGroup(head, k):
    h = ListNode(-1)
    h.next = head
    cur = pre = h
   
    n = -1
    while cur != None:
        n += 1
        cur = cur.next
       
    while n >= k:
        cur = pre.next
        for _ in range(k - 1):
            lat = cur.next
            cur.next = lat.next
            lat.next = pre.next
            pre.next = lat
        pre = cur
        n -= k
       
    return h.next

力扣第25题，提交通过。第24题就是k = 2的情况，也提交通过了。
栈:后进先出，只能从栈顶进出。时间复杂度O(1)。
④给定一个只包含()[]{}的字符串，判断其是否有效。

# 5.判断括号符号的有效性
class Stack:
    def __init__(self):
        self.data = []
        self.length = 0
       
    def push(self, val):
        self.data.append(val)
        self.length += 1
       
    def pop(self):
        if self.length == 0:
            return None
        res = self.data.pop()
        self.length -= 1
        return res
       
    def getLength(self):
        return self.length
   
    def get_item(self):
        if self.length == 0:
            return None
        else:
            return self.data[self.length-1]
       
   
def isValid(s):
    length = len(s)
    if length == 0:
        return True
    if length % 2 != 0:
        return False
    stack = Stack()
    left = ["(", "[", "{"]
    right =  [")", "]", "}"]
    for i in range(length):
        c = s[i]
        cp = None
        if c in left:
            stack.push(c)
        elif c in right:
            cp = stack.pop()
            if ((c == ")" and cp != "(") or
                 (c == "]" and cp != "[") or
                 (c == "}" and cp != "{")):
                return False

    if stack.getLength() == 0:
        return True
    else:
        return False

力扣第20题，已提交通过。
⑤气温列表
给定一个每日气温列表，返回一个列表，数值为今天以后多长时间气温会回升。

# 算法一，穷举，超时了
def dailyTemperatures(T):
    n = len(T)
    result = [0]*n
    for i in range(n):
        T0 = T[i]
        d = 1
        bHigh = False
        for j in range(i+1, n):
            if T[j] > T[i]:
                bHigh = True
                break
            d += 1
        if bHigh == False:
            d = 0
        result[i] = d
    return result

能想到的最简单的方法是直接穷举，复杂度是O(n²)。力扣739题，提交显示超出时间限制。
再照教程用栈试试。

# 算法2，用堆栈，降低时间复杂度
def dailyTemperatures2(T):
# print(T)
# n = len(T)
# result = [0]*n
# stack = Stack()
# for i in range(n):
# if stack.getLength() == 0:
# stack.push(i)
# T_top = T[i]
# continue
# top_index = stack.get_item()
# if T[i] > T[top_index]:
# i_top = stack.pop()
# result[i_top] = i - i_top
# stack.push(i)
# else:
# stack.push(i)
# print(i, T[i], top_index, T[top_index])
# return result
    ans = [0]*len(T)
    stack = []
    for i in range(len(T) - 1, -1, -1):
        while stack and T[i] >= T[stack[-1]]:
            stack.pop()
        if stack:
            ans[i] = stack[-1] - i
        stack.append(i)
    return ans

自己写的总是有问题，网上找了个现成的，通过了。
其它栈的题。
力扣224:输入含数字，括号和+-的字符串，计算结果。

# 7.基本计算器
def calculate(s):
    stack = []
    res = 0
    num = 0
    sign = 1
    for c in s:
        if c.isdigit():
            num = num*10 + int(c)
        elif c == "+" or c == "-":
            res = res + num*sign
            if c == "+":
                sign = 1
            else:
                sign = -1
            num = 0
        elif c == "(":
            stack.append(res)
            stack.append(sign)
            sign = 1
            res = 0
        elif c == ")":
            res = res + sign*num
            old_sign = stack.pop()
            old_res = stack.pop()
            res = old_res + old_sign*res
            sign = 1
            num = 0
    res = res + sign*num
    return res

力扣227，增加乘除法的计算器。

# 高级计算器
def highCulate(s):
    # 初始化sign为 “+”，是因为开头是数字
    num ,stack ,sign = 0 , [] , '+'
    for i in range(len(s)):
        ch = s[i]
        if ch.isdigit():
            num = num * 10 + int(ch) #根据当前数字之前的符号，来决定如何处理当前数值
        # 并将处理后的数值压入栈中
        if ch in "+-*/" or i == len(s)-1:
            if sign == "+" :
                stack.append(num)
            elif sign == "-" :
                stack.append(-num)
            elif sign == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop()/num))
            num = 0
            sign = ch
    return sum(stack)

力扣84题，柱状图最大矩形面积

# 9.柱状图最大矩形
def maxJu(heights):
    heights.append(0)
    stack = []
    maxArea = 0
    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            top = stack.pop()
            wide = 0
            if stack:
                wide = i - stack[-1] -1
            else:
                wide = i
            maxArea = max(maxArea, heights[top] * wide)
        stack.append(i)
    return maxArea
```    
队列:先进先出。
应用:需要顺序处理，数据量在变化。
双端队列:在队列头尾都可以O(1)复杂度查看和增删。
力扣239题，给定一个数组和窗口大小k，返回每个窗口中的最大值。
先用最直接的算法
```python
# 滑动窗口最大值
def maxSlidingWindow(nums, k):
    i = 0
    n = len(nums)
    res = [0]*(n-k+1)
    while i <= n - k:
        temp = nums[i:i+k]
        res[i] = max(temp)
        i += 1
    return res

再用双端队列

# 用双端队列求解
def maxSlidingWindow2(nums, k):
    deque = collections.deque()
    res = []
    for i, num in enumerate(nums):
        while deque and deque[0] <= i - k: 
            deque.popleft()
        while deque and num > nums[deque[-1]]:
            deque.pop()
        deque.append(i)
        if i >= k-1:
            res.append(nums[deque[0]])
    return res

提交，运行时间比第一个快了很多。
树的特点是有递归形式。
树的遍历有前序，中序和后序三种，以访问根结点的顺序区分。
参考
https://zhuanlan.zhihu.com/p/55577744
照着撸一遍吧。

# coding:utf-8
# 树的各种遍历方式


# 节点类
class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None
       
    def __str__(self):
        return str(self.item)
       
       
# 二叉树类
class Tree:
    def __init__(self):
        self.root = Node("root")
       
    # 增加节点
    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
        else:
            q = [self.root]
           
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)
                   
    # 先序遍历
    def preorder(self, root):
        if root is None:
            return []
        result = [root.item]
        left_item = self.preorder(root.left)
        right_item = self.preorder(root.right)
        return result + left_item + right_item
       
    # 中序遍历
    def inorder(self, root):
        if root is None:
            return []
        result = [root.item]
        left_item = self.inorder(root.left)
        right_item = self.inorder(root.right)
        return left_item + result + right_item
       
    # 后序遍历
    def postorder(self, root):
        if root is None:
            return []
        result = [root.item]
        left_item = self.postorder(root.left)
        right_item = self.postorder(root.right)
        return left_item + right_item + result
       
    # 层次遍历
    def traverse(self):
        if self.root is None:
            return None
        q = [self.root]
        res = [self.root.item]
        while q != []:
            pop_node = q.pop(0)
            if pop_node.left is not None:
                q.append(pop_node.left)
                res.append(pop_node.left.item)
               
            if pop_node.right is not None:
                q.append(pop_node.right)
                res.append(pop_node.right.item)
        return res
           

if __name__ == "__main__":
    t = Tree()
    for i in range(10):
        t.add(i)
    print("前序遍历:", t.preorder(t.root))
    print("中序遍历:", t.inorder(t.root))
    print("后序遍历:", t.postorder(t.root))
    print("层次遍历:", t.traverse())

结果
前序遍历: [‘root’, 0, 2, 6, 7, 3, 8, 9, 1, 4, 5]
中序遍历: [6, 2, 7, 0, 8, 3, 9, ‘root’, 4, 1, 5]
后序遍历: [6, 7, 2, 8, 9, 3, 0, 4, 5, 1, ‘root’]
层次遍历: [‘root’, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

树的应用
力扣230题，给定二叉搜索树，找到第k个最小的元素。
对二叉搜索树进行中序遍历，即为对数据进行排序，其第k个值即为所求。

# 力扣230题，第k大的元素
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
   
def kthSmallest(root, k):
    def inorder(root):
        return inorder(root.left) + [root.val] + inorder(root.right) if r else []
    return inorder(root)[k-1]

提交通过。

本篇的代码： https://github.com/zwdnet/MyQuant/tree/master/42
以前学过的，但是一动手才发现很多时候都写不出来，要参考别人写的。实际干活还是用最简单的线性结构，算法第一个念头就是穷举。不知道我是该去刷题呢还是做中学，碰到了再说？先把这个系列学完吧。

我发文章的三个地方，欢迎大家在朋友圈等地方分享，欢迎点“在看”。
我的个人博客地址：https://zwdnet.github.io
我的知乎文章地址： https://www.zhihu.com/people/zhao-you-min/posts
我的微信个人订阅号：赵瑜敏的口腔医学学习园地