测试开发基础 | 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)

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)

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))

# -*- 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)

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)

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)

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)

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)

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))