xz175411 / python-interview-guide Goto Github PK

def average_num():
    series=[]
    def average(num):
        # series自由变量,未在本地作用域绑定
        series.append(num)
        return sum(series)/len(series)
    return average
aver=average_num()

def average_num():
    count=0
    total=0
    def average(num):
        nonlocal total,count
        total+=num
        count+=1
        return total/count
    return average
aver=average_num()
print(aver(10))

b=9
def test(a):
    print(a)
    global b
    print(b)
    b=6
test(3)

# 手动实现一个带参数的装饰器
def use_arg(argument):
    def decorate(fun):
        def wrapper(*args,**kwargs):
            print('%s is running'%fun.__name__)
            print('传入的参数 %s'%argument)
            return fun()  
        return wrapper
    return decorate
@use_arg('hahhaa')
def demo():
    pass
demo()

import threading
lock=threading.Lock()
n=[0]
def demo():
    #with lock:
    n[0]=n[0]+1
threads=[]
for i in range(5000):
    t=threading.Thread(target=demo)
    threads.append(t)
for t in threads:
    t.start()
print(n)

import copy
a = [1, 2, 3, 4, ['a', 'b']] #原始对象
b = a                       #赋值，传对象的引用
c = copy.copy(a)            #对象拷贝，浅拷贝
d = copy.deepcopy(a)        #对象拷贝，深拷贝
a.append(5)                 #修改对象a
a[4].append('c')            #修改对象a中的['a', 'b']数组对象

class Dog(Animal):
    def run(self):
        print('Dog is running...')

class Cat(Animal):
    def run(self):
        print('Cat is running...')

class Foo(object):
    def bar(self):
        print('Foo.bar')
def bar(self):
    print('Modified bar')
Foo().bar()
Foo.bar = bar
Foo().bar()

 list(map(lambda x: x * x, [1, 2, 3, 4, 5, 6, 7, 8, 9]))
# [1, 4, 9, 16, 25, 36, 49, 64, 81]

def is_odd(n):
    return n % 2 == 1
list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))
# 结果: [1, 5, 9, 15]

def consumer():
    r = 'hello'
    while True:
        n1=yield r  #这里的等式右边相当于一个整体，接受回传值
        if not n1:
            return
        print('[CONSUMER] Consuming %s...' % n1)
        r='%d00 OK' % n1
c = consumer()
c.__next__()
n=0
while n<3:
    n=n+1
    r1=c.send(n)
    print('[PRODUCER] Consumer return: %s' % r1)
c.close()

from functools import wraps
def corountine(func):
    @wraps(func)                      
    # functools.wraps 则可以将原函数对象的指定属性复制给包装函数对象, 默认有 __module__、__name__、__doc__,或者通过参数选择
    def primer(*args, **kwargs):       # 把被装饰的生成器函数替换成这里的 primer 函数；调用 primer 函数时，返回预激后的生成器
        gen = func(*args, **kwargs)    # 调用被装饰的函数，获取生成器对象。
        next(gen)                      # 预激生成器
        return gen                     # 返回生成器
    return primer
    
@corountine               # 预激装饰器
def coro_average():
    total = 0.0
    count = 0
    average = None
    while 1:
        term = yield average
        total += term
        count += 1
        average = total/count
coro3 = coro_average()
print (coro3.send(5))
print (coro3.send(7))
print (coro3.send(10))
coro3.close()

class Person:
    def __init__(self,name,age):
        self.name=name
        self.age=age

# 初始化一个实例时调用__init__方法
tim=Person('Tim',18)
# 将Bob,16分布封装到bob的name和age属性中
bob=Person('Bob',16)

class A:
    def __init__(self):
        print('A')
class B(A):
    def __init__(self):
        print('B')
        super().__init__()
class C(A):
    def __init__(self):
        print('C')
        super().__init__()
class D(B, C):
    def __init__(self):
        print('D')
        super().__init__()

class Province:
    # 静态字段
    country = 'China' 
    def __init__(self,name):
        # 普通字段
        self.name = name
obj1 =Province('BeiJing')
print(obj1.name)
print(Province.country)

class Foo:
    def __init__(self,name):
        self.name =name
    # 定义普通实例方法,至少一个self参数
    def ord_func(self):
        print(self.name)
    # 定义类方法，至少一个cls参数
    @classmethod
    def class_func(cls):
        print('类方法')
    # 定义静态方法，无默认参数
    @staticmethod
    def static_fun(): 
        print('静态方法')
f = Foo('ord_func')
f.ord_func()
Foo.class_func()
Foo.static_fun()

class Goods:
    # 查看属性值 
    @property       
    def price(self):   
        print('@property')
    # 修改、设置属性
    @price.setter                                         
    def price(self, value):       
        print('@price.setter')
    # 删除属性
    @price.deleter   
    def price(self):      
       print('@price.deleter')                             
obj = Goods()
# 自动执行 @property 修饰的 price 方法，并获取方法的返回值 
obj.price
# 自动执行 @price.setter 修饰的 price 方法，并将2000赋值给方法的参数              
obj.price = 2000 
# 自动执行 @price.deleter 修饰的 price 方法  
del obj.price     

class Foo:
    def __init__(self):
        pass
    def __call__(self,*args,**kwargs):
        print('__call__')
# 执行 __init__
obj6 = Foo() 
# 执行 __call__
obj6()

class Province:
    country = 'China'
    def __init__(self, name, count):
        self.name = name
        self.count = count
    def func(self, *args, **kwargs):
        print('func')
# 获取类的成员，即：静态字段、方法、
# 输出：{'__module__': '__main__', 'country': 'China', '__init__': <function Province.__init__ at 0x00000264B20F1E18>, 
# 'func': <function Province.func at 0x00000264B4638D08>, '__dict__': <attribute '__dict__' of 'Province' objects>, 
# '__weakref__': <attribute '__weakref__' of 'Province' objects>, '__doc__': None}
print(Province.__dict__)
# 输出：{'name': 'HeBei', 'count': 1000}
obj1 = Province('HeBei',1000)
print(obj1.__dict__)
obj2 = Province('HeNan', 3)
# 输出：{'name': 'HeNan', 'count': 3}
print(obj2.__dict__)

class Foo:
    def __init__(self):
        pass
    def __str__(self):
        return '__str__'
obj=Foo()
print(obj)

# 通过元编程实现类自定义属性大写
class Base(type):
    def __new__(cls,name,bases,attrs):
        upper_attrs={}
        for k,v in attrs.items():
            if not k.startswith("__"):
                upper_attrs[k.upper()]=v
            else:
                upper_attrs[k]=v
        return type.__new__(cls,name,bases,upper_attrs)
class Foo(metaclass=Base):
    foo=True
    def hello(self):
        print("world")
def hello():
    print("world")
print(dir(Foo))

class Singleton(type):
    _instances = {}
    def __call__(cls, *args, **kwargs):
        if cls not in cls._instances:
            cls._instances[cls] = super(Singleton, cls).__call__(*args, **kwargs)
        return cls._instances[cls]

class Foo(metaclass=Singleton):
    pass
foo1=Foo()
foo2=Foo()
print(id(foo1)==id(foo2))

def singleton(cls):
    _instance = {}
    def wrapper():
        if cls not in _instance:
            _instance[cls] = cls()
        return _instance[cls]
    return wrapper
    
@singleton
class Cls(object):
    def __init__(self):
        pass
cls1 = Cls()
cls2 = Cls()
print(id(cls1) == id(cls2))

def bubble_sort(alist):
    for i in range(len(alist)-1):
        for j in range(len(alist)-1-i):
            if alist[j]>alist[j+1]:
                alist[j],alist[j+1]=alist[j+1],alist[j]
alist=[54,26,93,17,77,31,44,55,20]
bubble_sort(alist)
print(alist)

def select_sort(alist):
    for i in range(len(alist)-1):
        min_index=i
        for j in range(i+1,len(alist)):
            if alist[j]<alist[min_index]:
                min_index=j
        if i!=min_index:
            alist[i],alist[min_index]=alist[min_index],alist[i]
alist=[54,26,93,17,77,31,44,55,20]
select_sort(alist)
print(alist)

def insert_sort(alist):
    for i in range(1,len(alist)):
        for j in range(i,0,-1):
            if alist[j]<alist[j-1]:
                alist[j],alist[j-1]=alist[j-1],alist[j]
            else:
                break
alist=[54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)

# 变换步长（增量）的插入排序->(n ~ n^2,不稳定)
def shell_sort(alist):
    gap=len(alist)//2
    while gap>=1:
        for i in range(gap,len(alist)):
            j=i
            while(j-gap)>=0:
                if alist[j]<alist[j-gap]:
                    alist[j],alist[j-gap]=alist[j-gap],alist[j]
                    j-=gap
                else:
                    break
        gap//=2
alist=[54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)

#分而治之，递归分解/递归合并 （nlogn）
def merge_sort(alist):
    if len(alist)<=1:
        return alist
    mid = len(alist)//2
    left_alist = merge_sort(alist[:mid])
    right_alist = merge_sort(alist[mid:])
    return merge(left_alist,right_alist)
def merge(left_list,right_list):
    result=[]
    j=0
    i=0
    while i<len(left_list) and j < len(right_list):
        if left_list[i]<=right_list[j]:
            result.append(left_list[i])
            i+=1
        else:
            result.append(right_list[j])
            j+=1
    result+=left_list[i:]
    result+=right_list[j:]
    return result
alist=[54,26,93,17,77,31,44,55,20]
print(merge_sort(alist))

# 快速排序使用分而治之来获得与归并排序相同的优点，而不使用额外的存储。
# 有可能列表不能被分成两半。当这种情况发生时，性能降低
def quick_sort(alist, start, end):
    if start>= end:
        return
    #基准
    mark = alist[start]
    left = start
    right = end
    while left < right:
        while left<right  and alist[right]>mark:
            right-=1
        alist[left]=alist[right]
        while left<right and alist[left]<mark:
            left+=1
        alist[right]=alist[left]
    alist[right]=mark
    quick_sort(alist,start,left-1)
    quick_sort(alist,left+1,end)
alist=[54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)

# leetcode 19：快慢双指针
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        second = fist = head
        for i in range(n):  # 第一个指针先走 n 步
            fist = fist.next
 
        if fist == None:  # 如果现在第一个指针已经到头了，那么第一个结点就是要删除的结点。
            return second.next
 
        while fist.next:  # 然后同时走，直到第一个指针走到头
            fist = fist.next
            second = second.next
        second.next = second.next.next  # 删除相应的结点
        return head

# leetcode 21
# 解题思路：合并后的链表仍然是有序的，可以同时遍历两个链表，
# 每次选取两个链表中较小值的节点，依次连接起来，就能得到最终的链表
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l1 or l2
        head=cur=ListNode(0)
        while l1 and l2:
            if l1.val<l2.val:
                cur.next=l1
                l1=l1.next
            else:
                cur.next=l2
                l2=l2.next
            cur=cur.next
        cur.next=l1 or l2
        return head.next

# leetcode 142：判断链表是否有环/定位环入口/环长度，快慢双指针
    class Solution(object):
    def detectCycle(self, head):
        if head is None:
            return
        slow=fast=head
        has_cycle=False
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                has_cycle=True
                break
        if has_cycle:
            slow_p=head
            fast_p=fast
            while slow_p !=fast_p:
                fast_p=fast_P.next
                slow_p=slow_p.next
            return slow_p
        return
        # 环长度
        slow=slow.next
        fast=fast.next.next
        length=1
        while slow!=fast:
            slow=slow.next
            fast=fast.next.next
            length+=1
        return length

# leetcode 2
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        flag=0
        root=n=ListNode(0)
        while l1 or l2 or flag:
            v1=v2=0
            if l1:
                v1=l1.val
                l1=l1.next
            if l2:
                v2=l2.val
                l2=l2.next
            flag,val=divmod(v1+v2+flag,10)
            n.next=ListNode(val)
            n=n.next
        return root.next  

# leetcode 237
class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        next_node=node.next
        next_nextnode=next_node.next
        node.val=next_node.val
        node.next=next_nextnode

# 根据栈的特性
class Solution:
    def printListFromTailToHead(self, listNode):
        if listNode is None:
            return []
        sta=list()
        res=list()
        while listNode:
            sta.append(listNode.val)
            listNode=listNode.next
        while sta:
            res.append(sta.pop())
        return res
# 递归
class Solution:
    def printListFromTailToHead(self, listNode):
        if listNode is None:
            return []
        return self.printListFromTailToHead(listNode.next)+[listNode.val]

# leetcode 206
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre=None
        # 不断取出和向后移动头节点,并将头节点连接到新头节点后面
        while head:
            next_node=head.next
            head.next=pre
            pre=head
            head=next_node
        return pre

# leetcode 146:
# 字典（哈希）+双端链表
class Node(object): 
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None
        
class LRUCache(object):
 
    def __init__(self, capacity):
        self.dic = {}
        self.capacity = capacity
        self.dummy_head = Node(0, 0)
        self.dummy_tail = Node(0, 0)
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head
 
    def get(self, key):
        if key not in self.dic:
            return -1
        node = self.dic[key]
        self.remove(node)
        self.append(node)
        return node.val
 
    def put(self, key, value):
        if key in self.dic:
            self.remove(self.dic[key])
        node = Node(key, value)
        self.append(node)
        self.dic[key] = node
 
        if len(self.dic) > self.capacity:
            head = self.dummy_head.next
            self.remove(head)
            del self.dic[head.key]
 
    def append(self, node):
        tail = self.dummy_tail.prev
        tail.next = node
        node.prev = tail
        self.dummy_tail.prev = node
        node.next = self.dummy_tail
 
    def remove(self, node):
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

# leetcode 20
class Solution:
    def isValid(self, s: str) -> bool:
        chars={'(':')','[':']','{':'}'}
        stack=[]
        for i in s:
            if i in chars:
                stack.append(i)
            else:
                if not stack or chars[stack.pop()]!=i:
                    return False
        return not stack

# leetcode 232: 一个栈作为缓存区
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1=[]
        self.stack2=[]
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack1.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self.stack2)==0:
            while(self.stack1):
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.stack2)==0:
            while(self.stack1):
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.stack1 and not self.stack2

# leetcode 946:借用一个辅助的栈tmp，遍历压栈顺序
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        tmp=[]
        while pushed:
            tmp.append(pushed.pop(0))
            while tmp and tmp[-1]==popped[0]:
                popped.pop(0)
                tmp.pop()
        return not tmp

# leetcode 155：实际上就是实现最小栈（重点是连续弹出最小值时的问题）
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]
        self.minstack=[]

    def push(self, x: int) -> None:
        self.stack.append(x)
        if self.minstack:
            self.minstack.append(x)
        else:
            if x<self.minstack[-1]:
                self.minstack.append(x)
            else:
                self.minstack.append(self.minstack[-1])

    def pop(self) -> None:
        self.stack.pop()
        self.minstack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]

# leetcode 946
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        tmp=[]
        while pushed:
            tmp.append(pushed.pop(0))
            while tmp and tmp[-1]==popped[0]:
                popped.pop(0)
                tmp.pop()
        return not tmp

from pythonds.basic.queue import Queue
def hotPotato(namelist,num):
    simple_queue = Queue()
    for name in namelist:
        simple_queue.enqueue(name)
    while simple_queue.size()>1:
        for i in range(num):
            simple_queue.enqueue(simple_queue.dequeue())
        simple_queue.dequeue()
    return simple_queue.dequeue()

print(hotPotato(["Bill","David","Susan","Jane","Kent","Brad"],2))

# leetcode 23
from Queue import PriorityQueue
class Solution(object):
    def mergeKLists(self, lists):
        head = point = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))
        while not q.empty():
            val, node = q.get()
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

# 递归解法
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ret=[]
        if root:
            ret=ret+[root.val]
            ret=ret+self.preorderTraversal(root.left)
            ret=ret+self.preorderTraversal(root.right)
        return ret
# 迭代算法思路：使用栈的**，从根节点开始以此使用ret添加根节点值，stack添加右节点，
# curr=左节点，如果左节点为None，则获取其上一个右节点（一直输出根节点，添加其右节点，
# 遍历左节点，右节点的输出顺序为从下往上）
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ret=[]
        if root==None:
            return ret
        stack=[]
        curr=root
        while curr or stack:
            if curr:
                ret.append(curr.val)
                stack.append(curr.right)
                curr=curr.left
            else:
                curr=stack.pop()
        return ret

# 递归解法同上
# 迭代解法
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if root==None:
            return res
        stack=[]  #添加根节点
        curr=root
        while curr or stack:
            if curr:
                stack.append(curr)
                curr=curr.left
            else:
                curr=stack.pop()
                res.append(curr.val)
                curr=curr.right
        return res

# 递归解法同上
# 迭代算法思路：后序遍历方式为：左右中，将其进行反转 中右左，
# 那么我们可以实现一个中右左，其原理与前序遍历一样
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ret=[]
        if root==None:
            return ret
        stack=[]
        curr=root
        while curr or stack:
            if curr:
                ret.append(curr.val)
                stack.append(curr.left)
                curr=curr.right
            else:
                curr=stack.pop()
        return ret[::-1]

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if root.left==None or root.right==None:
            return self.minDepth(root.left)+self.minDepth(root.right)+1
        else:
            return min(map(self.minDepth,(root.left,root.right)))+1

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        average=[]
        if root:
            level=[root]
            while level:
                average.append(sum(i.val for i in level)/len(level))
                level=[kid for node in level for kid in (node.left,node.right) if kid]
        return average

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter=0
        def dfs(root):
            if root==None:
                return 0
            left=dfs(root.left)
            right=dfs(root.right)
            self.diameter=max(self.diameter,left+right)
            return max(left,right)+1
        dfs(root)
        return self.diameter

'''
思路：递归，如果当前节点就是p或q，说明当前节点就是最近的祖先；如果当前节点不是p或p，
就试着从左右子树里找pq；如果pq分别在一左一右被找到，那么当前节点还是最近的
祖先返回root就好了；否则，返回它们都在的那一边。
'''
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root==None:   
            return 
        if root==p or root==q:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root
        if left:
            return left
        if right:
            return right
        else:
            return 

# leetcode 14
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        temp_str=""
        zip_obj = zip(*strs)
        for obj in zip_obj:
            if(len(set(obj)))>1:
                break
            temp_str+=obj[0]
        return temp_str 

# leetcode 5
class Solution:
    def longestPalindrome(self, s: str) -> str:
        start=0
        maxstr=0
        for i in range(len(s)):
            if i-maxstr>=1 and s[i-maxstr-1:i+1]==s[i-maxstr-1:i+1][::-1]:
                start = i-maxstr-1
                maxstr+=2
                continue
            if  i-maxstr>=0 and s[i-maxstr:i+1]==s[i-maxstr:i+1][::-1]:
                start = i-maxstr
                maxstr+=1
        return s[start:start+maxstr]

# leetcode 3 ：滑动窗口法
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_str=0
        for i in range(len(s)):
            if len(s[i-max_str:i+1])==len(set(s[i-max_str:i+1])):
                max_str+=1
        return max_str

class HashMap:
    def __init__(self):
        self.size = 11
        self.slots = [None]*self.size
        self.data = [None]*self.size

    def put(self, key, data):
        hash_value = self.hash(key, len(self.slots))
        if self.slots[hash_value] == None:
            self.slots[hash_value] = key
            self.data[hash_value] = data
        else:
            # 键一样时替换
            if self.slots[hash_value] == key:
                self.data[hash_value] = data
            else:
                # 重新散列，+1线性探测
                next_slot = self.rehash(hash_value, len(self.slots))
                while self.slots[next_slot] != None and self.slots[next_slot] != key:
                    next_slot = self.rehash(next_slot, len(self.slots))
                if self.slots[next_slot] != None:
                    self.slots[next_slot] = key
                    self.data[next_slot] = data
                else:
                    self.data[next_slot] = data

    def get(self, key):
        start_slot = self.hash(key, len(self.slots))
        found = False
        data = None
        stop = False
        position = start_slot
        while self.slots[position] != None and not stop and not found:
            if self.slots[position] == key:
                data = self.data[position]
                found = True
            else:
                position = self.rehash(position,len(self.slots))
                if position==start_slot:
                    stop = True
        return data 

    def hash(self, key, size):
        return key % size

    def rehash(self, oldhash, size):
        return (oldhash+1) % size

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, data):
        return self.put(key, data)
hashmap=HashMap()
hashmap[0]='cat'
hashmap[1]='dog'
hashmap[2]='bird'
print(hashmap.slots)
print(hashmap.data  )

# leetcode 1
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)
        # 组合为一个索引序列，同时列出数据和数据下标
        demo_dict = dict((num,i)for i,num in enumerate(nums))
        for i,num in enumerate(nums):
            #get()方法和[key]方法的主要区别在于[key]在遇到不存在的key时会抛出KeyError错
            j=demo_dict.get(target-num)
            if j and i!=j:
                return [i,j]

# leetcode 15
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        # 排序后遍历
        for t in range(len(nums)- 2):
            # 跳过相同的情况
            if t > 0 and nums[t] == nums[t - 1]:
                    continue
            # i向后判断，j向前判断
            i, j = t + 1, len(nums) - 1
            while i < j:
                _sum = nums[t] + nums[i] + nums[j]
                if _sum == 0:
                    res.append([nums[t], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    # 跳过相同的情况
                    while i < j and nums[i] == nums[i - 1]:
                        i += 1
                    while i < j and nums[j] == nums[j + 1]:
                        j -= 1
                elif _sum < 0:
                    i += 1
                else:
                    j -= 1
        return res

# leetcode 187
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        res=dict()
        for i in range(len(s)-9):
            res[s[i:i+10]]=res.get(s[i:i+10],0)+1
        return [k for k,v in res.items() if v>=2]

# leetcode 350
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res=[]
        num_dict={}
        for num in nums1:
            if num not in num_dict:
                num_dict[num]=1
            else:
                num_dict[num]+=1
        for num in nums2:
            if num in num_dict and num_dict[num]>0:
                num_dict[num]-=1
                res.append(num)
        return res

# leetcode 17
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        d = {'2':"abc",
             '3':"def",
             '4':"ghi",
             '5':"jkl",
             '6':"mno",
             '7':"pqrs",
             '8':"tuv",
             '9':"wxyz"
            }
        res = []
        self.dfs(d, digits, "", res)
        return res
    
    def dfs(self, d, digits, tmp , res):
        if not digits:
            res.append(tmp)
        else:
            for num in d[digits[0]]:
                self.dfs(d, digits[1:], tmp + num, res)

# leetcode 215
'''
任意选定数组内一个数mark，将比其大和比其小的值分别放在左右两个数组里，接着判断两边数字
的数量，如果左边的数量大于k个，说明第k大的数字存在于mark及mark左边的区域，对左半区执行
partition函数；如果左边的数量小于k个，说明第k大的数字在mark和mark右边的区域之内，对右
半区执行partition函数。直到左半区刚好有k-1个数，那么第k大的数就已经找到了。
'''
class Solution(object):
    def findKthLargest(self, nums, k):
        mark = random.choice(nums)
        num1,num2=list(),list()
        for num in nums:
            if num>mark:
                num1.append(num)
            if num<mark:
                num2.append(num)
        if k<=len(num1):
            return self.findKthLargest(num1,k)
        if k>len(nums)-len(num2):
            return self.findKthLargest(num2,k-(len(nums)-len(num2)))
        return mark

# leetcode 322
class Solution(object):
    def coinChange(self, coins, amount):
    # 建一个长度是 amount + 1的dp数组，构成面额从0到 amount需要使用的最少硬币数量。
        dp = [0] + [-1] * amount
        for x in range(amount):
            if dp[x] < 0:
                continue
            for c in coins:
                if x + c > amount:
                    continue
                if dp[x + c] < 0 or dp[x + c] > dp[x] + 1:
                    dp[x + c] = dp[x] + 1
        return dp[amount]

import threading
import time
class GetHtml(threading.Thread):
    def __init__(self,name):
        super().__init__(name=name)
    def run(self):
        print('get html start')
        time.sleep(2)
        print('get html end')
class GetUrl(threading.Thread):
    def __init__(self,name):
        super().__init__(name=name)
    def run(self):
        print('get url start')
        time.sleep(4)
        print('get url end')
if __name__ == "__main__":
    thread1=GetHtml(name='html')
    thread2=GetUrl(name='url')
    start_time=time.time()
    thread1.start()
    thread2.start()
    thread1.join()
    thread2.join()
    end_time=time.time()
    total_time=end_time-start_time
    print('total running tim:{}'.format(total_time))