算法和数据结构

122.

已知:AList = [1, 2, 3]
BSet = {1, 2, 3}
(1)从AList和BSet中查找4，最坏时间复杂度哪个大？
(2)从AList和BSet中插入4，最坏时间复杂度哪个大？

答: (1)
对于查找，列表和集合的最坏时间复杂度都是O(n)，所以一样的。 (2)列表操作插入的最坏时间复杂度为o(n), 集合为o(1)，所以Alist大。 set是哈希表所以操作的复杂度基本上都是o(1)。

123.用Python实现一个二分查找的函数

答:

def binary_search(arr, target):
    n = len(arr)
    left = 0
    right = n - 1
    while left <= right :
    mid = (left + right) // 2
    if arr[mid] < target:
        left = mid + 1
    elif arr[mid] > target:
        right = mid - 1
    else :
        print(f"index:{mid},value:{arr[mid]}")
        return True
    return False

if __name__ == '__main__':
    l = [1, 3, 4, 5, 6, 7, 8]
    binary_search(l, 8)

124.Python单例模式的实现方法

答: 实现单例模式的方法有多种，之前再说元类的时候用call方法实现了一个单例模式，另外Python的模块就是一个天然的单例模式，这里我们使用new关键字来实现一个单例模式。

"""
通过 new 函数实现简单的单例模式。
"""
class Book:
    def __new__(cls, title):
        if not hasattr(cls, "_ins"):
            cls._ins = super().__new__(cls)
            print('in __new__')
        return cls._ins

    def __init__(self, title):
        print('in __init__')
        super().__init__()
        self.title = title

if __name__ == '__main__':
    b = Book('The Spider Book')
    b2 = Book('The Flask Book')
    print(id(b))
    print(id(b2))
    print(b.title)
    print(b2.title)

125. 使用Python实现一个斐波那契数列

答: 斐波那契数列:数列从第3项开始，每一项都等于前两项之和。

def fibonacci(num):
    a, b = 0, 1
    l = [a, b]
    for i in range(num):
        a, b = b, a + b
        l.append(b)
    return l

if __name__ == '__main__':
    print(fibonacci(10))

126. 找出列表中的重复数字

答:

"""
从头扫到尾，只要当前元素值与下标不同，就做一次判断,numbers[i]与 numbers[numbers[i]]，
相等就认为找到了重复元素，返回 true,否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素。
"""
# -*- coding:utf-8 -*-
class Solution:
    def duplicate(self, numbers):
        if numbers is None or len(numbers) <= 1:
            return False
        use_set = set()
        duplication = {}
        for index, value in enumerate(numbers):
            if value not in use_set:
                use_set.add(value)
            else:
                duplication[index] = value
        return duplication

if __name__ == '__main__':
    s = Solution()
    d = s.duplicate([1, 2, -3, 4, 4, 95, 95, 5, 2, 2, -3, 7, 7, 5])
    print(d)

127. 找出列表中的单个数字

答:

def find_single(l :list):
    result = 0
    for v in l:
        result ^= v
        if result == 0:
            print("没有落单元素")
        else :
            print("落单元素", result)

if __name__ == '__main__':
    l = [1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6]
    find_single(l)

128.写一个冒泡排序

答:

    def bubble_sort(arr):
        n = len(arr)
        for i in range(n - 1):
            for j in range(n - i - 1):.
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

    if __name__ == '__main__':
        l = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]
        bubble_sort(l)
        print(l)

129.写一个快速排序

答:

    def quick_sort(arr, first, last):
        if first >= last:
        return
        mid_value = arr[first]
        low = first
        high = last
        while low < high:
            while low < high and arr[high] >= mid_value:
                high -= 1  # 游标左移
                arr[low] = arr[high]

        while low < high and arr[low] < mid_value:
            low += 1
            arr[high] = arr[low]
            arr[low] = mid_value

    quick_sort(arr, first, low - 1)
    quick_sort(arr, low + 1, last)

    if __name__ == '__main__':
        l = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]
        quick_sort(l, 0, len(l) - 1)
        print(l)

130.写一个拓扑排序

答:

"""
对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。
"""
import pysnooper
from typing import Mapping

@pysnooper.snoop()
def topological_sort(graph:Mapping):
# in_degrees = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0}
    in_degrees = dict((u, 0) for u in graph)
    for u in graph:
        for v in graph[u]:  # 根据键找出值也就是下级节点
            in_degrees[v] += 1  # 对获取到的下级节点的入度加 1
    # 循环结束之后的结果: {'a': 0, 'b': 1, 'c': 1, 'd': 2, 'e': 1, 'f': 4}
    Q = [u for u in graph if in_degrees[u] == 0]  # 入度为 0 的节点
    in_degrees_zero = []
    while Q:
        u = Q.pop()  # 默认从最后一个移除
        in_degrees_zero.append(u)  # 存储入度为 0 的节点
        for v in graph[u]:
            in_degrees[v] -= 1  # 删除入度为 0 的节点，以及移除其指向
            if in_degrees[v] == 0:
            Q.append(v)
    return in_degrees_zero

if __name__ == '__main__':
# 用字典的键值表示图的节点之间的关系，键当前节点。值是后续节点。
    graph_dict = {
            'a': 'bf',  # 表示 a 指向 b 和 f
            'b': 'cdf',
            'c': 'd',
            'd': 'ef',
            'e': 'f',
            'f': ''}

    t = topological_sort(graph_dict)
    print(t)

131.Python实现一个二进制计算

答:

"""
二进制加法
"""
def binary_add(a:str, b: str):
    return bin(int(a, 2) + int(b, 2))[2:]

if __name__ == '__main__':
    num1 = input("输入第一个数，二进制格式:\n")
    num2 = input("输入第二个数，二进制格式:\n")
    print(binary_add(num1, num2))

132.有一组“+”和“-”符号，要求将“+”排到左边，“-”排到右边，写出具体的实现方法。
答:

"""
有一组“+”和“-”符号，要求将“+”排到左边，“-”排到右边，写出具体的实现方法。
如果让+等于 0，-等于 1 不就是排序了么。
"""
from collections import deque
from timeit import Timer

s = "++++++----+++----"

# 方法一
def func1():
    new_s = s.replace("+", "0").replace("-", "1")
    result = "".join(sorted(new_s)).replace("0", "+").replace("1", "-")
    return result

# 方法二
def func2():
    q = deque()
    left = q.appendleft
    right = q.append
    for i in s:
        if i == "+":
            left("+")
        elif i == "-":
            right("-")

# 方法三
def func3():
    data = list(s)
    start_index = 0
    end_index = 0
    count = len(s)
    while start_index + end_index < count:
        if data[start_index] == '-':
            data[start_index], data[count - end_index - 1] = data[count - end_index - 1], data[start_index]
            end_index += 1
        else :
            start_index += 1
    return "".join(data)

if __name__ == '__main__':
    timer1 = Timer("func1()", "from __main__ import func1")
    print("func1", timer1.timeit(1000000))
    timer2 = Timer("func2()", "from __main__ import func2")
    print("func2", timer2.timeit(1000000))
    timer3 = Timer("func3()", "from __main__ import func3")
    print("func3", timer3.timeit(1000000))

# 1000000 测试结果
# func1 1.39003764
# func2 1.593012875
# func3 3.3487415590000005
# func1 的方式最优，其次是 func2

133.单链表反转

答:

"""
单链表反转
"""
class Node:
    def __init__(self, val=None):
        self.val = val
        self.next = None

class SingleLinkList:
    def __init__(self, head=None):
        """链表的头部"""
        self._head = head

    def add(self, val:int):
    """
    给链表添加元素
    :param val: 传过来的数字
    :return:
    """
        # 创建一个节点
        node = Node(val)
        if self._head is None:
            self._head = node
        else :
            cur = self._head
        while cur.next is not None:
            cur = cur.next  # 移动游标
            cur.next = node  # 如果 next 后面没了证明以及到最后一个节点了

def traversal(self):
    if self._head is None:
        return
    else :
        cur = self._head
        while cur is not None:
        print(cur.val)
        cur = cur.next

def size(self):
    """
    获取链表的大小
    :return:
    """
    count = 0
    if self._head is None:
        return count
    else :
        cur = self._head
        while cur is not None:
        count += 1
        cur = cur.next
        return count

def reverse(self):
    """
    单链表反转
    思路:
    让 cur.next 先断开即指向 none，指向设定 pre 游标指向断开的元素，然后
    cur.next 指向断开的元素，再把开始 self._head 再最后一个元素的时候.
    :return:
    """
    if self._head is None or self.size() == 1:
        return
    else :
        pre = None
        cur = self._head
        while cur is not None:
            post = cur.next
            cur.next = pre
            pre = cur
            cur = post
            self._head = pre  # 逆向后的头节点

if __name__ == '__main__':
    single_link = SingleLinkList()
    single_link.add(3)
    single_link.add(5)
    single_link.add(6)
    single_link.add(7)
    single_link.add(8)
    print("对链表进行遍历")
    single_link.traversal()
    print(f"size:{single_link.size()}")
    print("对链表进行逆向操作之后")
    single_link.reverse()
    single_link.traversal()

134. 交叉链表求交点

答:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA, headB):
    """
    :tye head1, head1: ListNode
    :rtye: ListNode
    """
    if headA is not None and headB is not None:
        cur1, cur2 = headA, headB

    while cur1 != cur2:
        cur1 = cur1.next if cur1 is not None else headA
        cur2 = cur2.next if cur2 is not None else headB

    return cur1

cur1、cur2，2个指针的初始位置是链表headA、headB头结点，cur1、cur2两个指针一直往后遍历。 直到cur1指针走到链表的末尾，然后cur1指向headB；
直到cur2指针走到链表的末尾，然后cur2指向headA； 然后再继续遍历； 每次cur1、cur2指向None，则将cur1、cur2分别指向headB、headA。
循环的次数越多，cur1、cur2的距离越接近，直到cur1等于cur2。则是两个链表的相交点。

135.用队列实现栈ww

答: 下面代码分别使用1个队列和2个队列实现了栈。

from queue import Queue
# 使用 2 个队列实现
class MyStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        # q1 作为进栈出栈，q2 作为中转站
        self.q1 = Queue()
        self.q2 = Queue()

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.q1.put(x)

    def pop(self):

        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """

        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())  # 将 q1 中除尾元素外的所有元素转到 q2 中
            if self.q1.qsize() == 1:
                res = self.q1.get()  # 弹出 q1 的最后一个元素
                self.q1, self.q2 = self.q2, self.q1  # 交换 q1,q2
        return res

    def top(self):

        """
        Get the top element.
        :rtype: int
        """
        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())  # 将 q1 中除尾元素外的所有元素转到 q2 中
            if self.q1.qsize() == 1:
                res = self.q1.get()  # 弹出 q1 的最后一个元素
                self.q2.put(res)  # 与 pop 唯一不同的是需要将 q1 最后一个元素保存到 q2 中
                self.q1, self.q2 = self.q2, self.q1  # 交换 q1,q2
        return res

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return not bool(self.q1.qsize() + self.q2.qsize())  # 为空返回 True，不为空返回 False
    # 使用 1 个队列实现
    class MyStack2(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.sq1 = Queue()

        def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
            self.sq1.put(x)

        def pop(self):
            """
            Removes the element on top of the stack and returns that element.
            :rtype: int
            """
            count = self.sq1.qsize()
            if count == 0:
                return False
            while count > 1:
                x = self.sq1.get()
                self.sq1.put(x)
                count -= 1
            return self.sq1.get()

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        count = self.sq1.qsize()
        if count == 0:
            return False
        while count:
            x = self.sq1.get()
            self.sq1.put(x)
            count -= 1
        return x

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return self.sq1.empty()

    if __name__ == '__main__':
        obj = MyStack2()
        obj.push(1)
        obj.push(3)
        obj.push(4)
        print(obj.pop())
        print(obj.pop())
        print(obj.pop())
        print(obj.empty())

136. 找出数据流的中位数

答: 对于一个升序排序的数组，中位数为左半部分的最大值，右半部分的最小值，而左右两部分可以是无需的，只要保证左半部分的数均小于右半部分即可。因此，左右两半部分分别可用最大堆、最小堆实现。
如果有奇数个数，则中位数放在左半部分；如果有偶数个数，则取左半部分的最大值、右边部分的最小值之平均值。
分两种情况讨论: 当目前有偶数个数字时，数字先插入最小堆，然后选择最小堆的最小值插入最大堆(第一个数字插入左半部分的最小堆）。
当目前有奇数个数字时，数字先插入最大堆，然后选择最大堆的最大值插入最小堆。 最大堆:根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。 最小堆:根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

# -*- coding:utf-8 -*-
from heapq import *

class Solution:
    def __init__(self):
        self.maxheap = []
        self.minheap = []

    def Insert(self, num):
        if (len(self.maxheap) + len(self.minheap)) & 0x1:  # 总数为奇数插入最大堆
            if len(self.minheap) > 0:
                if num > self.minheap[0]:  # 大于最小堆里的元素
                    heappush(self.minheap, num)  # 新数据插入最小堆
                    heappush(self.maxheap, -self.minheap[0])  # 最小堆中的最小插入最大堆
                    heappop(self.minheap)
                else :
                    heappush(self.maxheap, -num)
            else :
                heappush(self.maxheap, -num)
        else :  # 总数为偶数 插入最小堆
            if len(self.maxheap) > 0:  # 小于最大堆里的元素
                if num < -self.maxheap[0]:
                    heappush(self.maxheap, -num)  # 新数据插入最大堆
                    heappush(self.minheap, -self.maxheap[0])  # 最大堆中的最大元素插入最小堆
                    heappop(self.maxheap)
                else :
                    heappush(self.minheap, num)
            else :
                heappush(self.minheap, num)

    def GetMedian(self, n=None):
        if (len(self.maxheap) + len(self.minheap)) & 0x1:
            mid = self.minheap[0]
        else :
            mid = (self.minheap[0] - self.maxheap[0]) / 2.0
        return mid

if __name__ == '__main__':
    s = Solution()
    s.Insert(1)
    s.Insert(2)
    s.Insert(3)
    s.Insert(4)
    print(s.GetMedian())

137. 二叉搜索树中第K小的元素

答: 二叉搜索树(BinarySearchTree)，又名二叉排序树(BinarySortTree)。 二叉搜索树是具有有以下性质的二叉树:
若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
左、右子树也分别为二叉搜索树。二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。所以对其遍历一个节点就进行计数，计数达到k的时候就结束。

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

class Solution:
    count = 0
    nodeVal = 0

    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.dfs(root, k)
        return self.nodeVal

    def dfs(self, node, k):

        if node != None:
            self.dfs(node.left, k)
            self.count = self.count + 1
        if self.count == k:
            self.nodeVal = node.val
            # 将该节点的左右子树置为 None,来结束递归，减少时间复杂度
            node.left = None
            node.right = None
            self.dfs(node.right, k)