撒地方大神

1.对列表进行过滤
li = [{"id":3}, {"id":1}, {"id":5}]
filter_list = filter(lambda item: item.get("id")> 3, li)
for item in filter_list:
    print(item.get("id"))
	
	
2.写一个类似于字段用法的类
class RepeatDic(object):
    def __init__(self):
        self.__li = []

    def __getitem__(self, item):
        filter_items = filter(lambda x: x[0] == item, self.__li)
        return [i[1] for i in filter_items]

    def __setitem__(self, key, value):
        self.__li.append((key, value))

    def __delitem__(self, key):
        self.__li = [item for item in self.__li if item[0] != key]


obj = RepeatDic()

obj["haha"] = "heihei"
print(obj["haha"])
obj["haha"] = "hehe"
print(obj["haha"])
del obj["haha"]
print(obj["haha"])

3.二分法查找
li = range(0, 30,  2)
def mid_find(li, left, right, val):
    if right >= left:
        mid = (left + right) // 2
        if li[mid] > val:
            right = mid - 1
            return mid_find(li, left, right, val)
        elif li[mid] < val:
            left = mid + 1
            return mid_find(li, left, right, val)
        else:
            return mid
    else:
        return None

要点：左右边界移动，碰头时终止循环
def mid_find2(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] > val:
            right = mid - 1
        elif li[mid] < val:
            left = mid + 1
        else:
            return mid

ret = mid_find2(li, 120)
print(ret)



4.一个大小为100G的文件etl_log.txt, 要读取文件中的内容, 写出具体过程代码？
要点：指定字节数读，弄成一个生成器
def readFile(file_path):
    with open(file_path, "r", encoding="utf-8") as f:
        while 1:
            block = f.read(1024)
            if block:
                yield block
            else:
                return

it = readFile("run.py")
for item in it:
    print(item)

5.写一个上下文管理类
class NewFile(object):
    def __init__(self, path):
        self.path = path
        self.__file_handler  = None

    def __exit__(self, exc_type, exc_val, exc_tb):
        if self.__file_handler:
            print("close")
            self.__file_handler.close()

    def __enter__(self):
        self.__file_handler = open(self.path, 'r', encoding="utf-8")
        print("open")
        return self.__file_handler

with NewFile("run.py") as f:
    print(f.read())
	
6.冒泡排序
要点：内层循环时时比较，时时交换
def bubble_sort(li):
    for i in range(len(li)-1):  #第i趟
        exchange = False
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        if not exchange:  #这里属于优化，也就是如果这次循环中没有发生一次交换，那么此时已经是有序的
            return
 
 
li = list(range(10000))
random.shuffle(li)
 
bubble_sort(li)

7.后序遍历，我称之为深度优先遍历
要点：深度优先 一般都可以用栈来实现，需要确定pop的条件，以及做好pop后的标识
# 非递归方式
def find(root_node):
    li = []
    stack = []
    stack.append([root_node,[root_node.lchild, root_node.rchild]])
    while len(stack) > 0:
        currNodeItem = stack[-1]
        if currNodeItem[1][0] is None and currNodeItem[1][1] is None:
            #当前是叶子节点，输出到列表
            li.append(currNodeItem[0].data)
            # 标志父亲节点这个儿子已经输出
            if len(stack) > 1: #考虑如果root节点就是叶子节点
                parentNodeItem = stack[-2]
                childs = parentNodeItem[1]
                for index,child in enumerate(childs):
                    if currNodeItem[0] == child:
                        childs[index] = None
                        break
            # 把栈里的数据移除掉
            stack.pop()
        elif currNodeItem[1][0] is not None: #有左儿子，添加左儿子
            lchild = currNodeItem[1][0]
            stack.append([lchild, [lchild.lchild, lchild.rchild]])
        else: # 没有左儿子情况下，有右儿子，添加右儿子
            rchild = currNodeItem[1][1]
            stack.append([rchild, [rchild.lchild, rchild.rchild]])

    return ','.join(li)

print(find(root)) #B,D,C,A,F,G,E  对应后序遍历

# 递归遍历
def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end=',')

8.广度优先，层级遍历
要点：使用 队列，一般出队，一边把儿子入队
def find(root):
    from collections import deque
    que = deque()
    que.append(root)
    while len(que) > 0:
        currentNode = que.popleft()
        print(currentNode.data, end=',')
        if currentNode.lchild:
            que.append(currentNode.lchild)
        if currentNode.rchild:
            que.append(currentNode.rchild)

find(root)

9.选择排序
# 选择排序，你就记成 选择性最小下标来排序
# 每次循环取最开始那个值的索引 作为最小值索引
def select_sort(li):
    for i in range(len(li)-1): #第几趟
        min_loc = i
        change_flag = False
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                change_flag = True
                min_loc = j
        if not change_flag:
            return
        li[i], li[min_loc] = li[min_loc], li[i]

li = [2,5,4,58,1,175,1,4]
select_sort(li)
print(li)


10.插入排序
#记录手里牌的下标和抓到牌的值,利用冒泡的方式去把抓到牌往左冒
#刚开始手里有一张牌，
def insert_sort(li):
    for i in range(1, len(li)): #摸到牌的下标
        tmp = li[i]
        j = i - 1 #手牌下标
        while j >= 0 and tmp < li[j]:
            li[j+1] = li[j]
            j-=1
        li[j+1] = tmp

11.快速排序
#快排是分而治之的思想
# 要点：递归终止条件就是上下边界碰头， 分区时维护两个指标指针，一个追整个数据，一个追踪小于的标志的值的个数
# 标志值可以去最后的一位数， 两指针出现不相等时，要把大的值交换到 靠右边，  在最后要把标志值交换一下
def quickSort(li, p, r):
    if p>=r:return
    q = partition(li,p,r)
    quickSort(li,p,q-1)
    quickSort(li,q+1,r)

def partition(li, p, r):
    '''

    :param li: 数据列表
    :param p: 数据区间的上标
    :param r: 数据区间的下标
    :return:
    '''
    pivot = li[r] #定义分区点为最后位置的元素
    i = p # 定义 i 指针, 用于追踪小于标志值
    j = p
    while j <= r: # 循环遍历 j 指针
        if li[j] < pivot:
            if j != i: # 如果出现i j不相等，说明比标志值的大的值出现，开始实时把这个值交换到右边
                swap(li, i, j)
            i+=1
        j+=1
    swap(li, i, r) #当p和r碰头时，循环终止，把标志值交换到  小于标志值的分界处
    return i

def swap(li, i, j):
    li[i], li[j] = li[j],li[i]

li = [42,4,4651,47,785,2,7,2,485]
quickSort(li,0, len(li)-1)
print(li)


12.Python 一个数如果恰好等于它的因子之和，这个数就称为"完数"。例如6=1＋2＋3.编程找出1000以内的所有完数
for i in range(2, 1001):
    m = []
    for j in range(1,i):
        if i % j == 0:
            m.append(j)
    if sum(m) == i:
        print(i)

13.单例模式
class singleton(object):
    __instance = None

    def __new__(cls, *args, **kwargs):
        if cls.__instance is None:
            cls.__instance = object.__new__(cls, *args, **kwargs)
        return cls.__instance

a = singleton()
b  = singleton()
print(id(a), id(b))

14.99乘法表
for row in range(1,10):
    for col in range(1, row+1):
        print("%s * %s = %s"%(col, row, col*row), end="  ")
    print()

15.看代码 写结果
https://zhuanlan.zhihu.com/p/23582996?refer=passer

16.类继承查找循环
要点：python2的经典类和新式类(继承了object) 都是按照深度优先查找类，只不过在查过中，有个细节不一样就是
遇到 重复类的保留情况，经典类是去掉后面的保留第一个，而新式类则是去掉前面的保留最后一个
python3的C3 MRO算法有点复杂，这个我没怎么去了解
一般5到6个类的继承关系我直接去看，一旦比这复杂，我会直接调用__mro__属性来查看
class A(object):
    def __init__(self):
        print("enter A")
        super(A, self).__init__()
        print("leave A")

class B(object):
    def __init__(self):
        print("enter B")
        super(B, self).__init__()
        print("leave B")

class C(A):
    def __init__(self):
        print("enter C")
        super(C, self).__init__()
        print("leave C")

class D(A):
    def __init__(self):
        print("enter D")
        super(D, self).__init__()
        print("leave D")

class E(B,C):
    def __init__(self):
        print("enter E")
        super(E, self).__init__()
        print("leave E")

class F(E,D):
    def __init__(self):
        print("enter F")
        super(F, self).__init__()
        print("leave F")

# print(F.__mro__)

16.二叉树的最大深度
from collections import deque
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return 0

        queue = deque()
        queue.append(root)
        depth = 0

        while queue:
            size = len(queue)
            for i in range(size):
                curr = queue.popleft()
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            depth += 1
        return depth

obj = Solution()
ret = obj.preorderTraversal(e)
print(ret)