class Node:
    def __init__(self, val, next):
        self.val = val
        self.next = next


a = Node("8", None)
b = Node("5", a)
c = Node("3", b)
d = Node("1", c)

aa = Node("7", None)
bb = Node("6", aa)
cc = Node("4", bb)
dd = Node("2", cc)


def combine_node(a: Node, b: Node) -> Node:
    if a is None or b is None:
        return a or b
    result = t = Node(-1, None)
    while a is not None and b is not None:
        if a.val >= b.val:
            t.next = b
            b = b.next
        else:
            t.next = a
            a = a.next
        t = t.next
    if a is not None:
        t.next = a
    if b is not None:
        t.next = b
    return result.next


def print_node(node: Node):
    while node:
        print(f"{node.val} =>", end=" ")
        node = node.next
    print()


print_node(d)
print_node(dd)
temp = combine_node(d, dd)
print_node(temp)

# 1 => 3 => 5 => 8 => 
# 2 => 4 => 6 => 7 => 
# 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 

def brackets_check(s: str) -> bool:
    temp = []
    brackets_list = ["[", "]", "{", "}", "(", ")"]
    brackets_dict = {")": "(",
                     "]": "[",
                     "}": "{"}
    for i in s:
        if i in brackets_list:
            if i in brackets_dict.keys():
                if temp.pop() != brackets_dict.get(i):
                    return False
            else:
                temp.append(i)
    if len(temp) == 0:
        return True
    else:
        return False


ss = "s(sdf)ssdf{[]}"
print(brackets_check(ss))

    def largestNumber(l: List[int]) -> str:
        for i in range(len(l) - 1):
            for j in range(len(l) - 1, i, -1):
                if self.bigger_than(l[j], l[j - 1]):
                    l[j], l[j - 1] = l[j - 1], l[j]
        print(l)
        return str(int("".join(map(str,l))))

    def bigger_than(n1: int, n2: int):
        return str(n1) + str(n2) > str(n2) + str(n1)

# print(max_combined_num([7864, 334, 447, 7732, 8498, 6, 33, 331, 1, 330, 2]))
# print(max_combined_num([3,30,34,5,9]))
print(max_combined_num([121, 12]))



# build-in function
def largestNumber1(self, nums):
    import functools
    if not any(nums):
        return "0"
    return "".join(sorted(map(str, nums), key=functools.cmp_to_key=lambda n1, n2: -1 if n1+n2>n2+n1 else (1 if n1+n2<n2+n1 else 0)))
    
# bubble sort
def largestNumber2(self, nums):
    for i in xrange(len(nums), 0, -1):
        for j in xrange(i-1):
            if not self.compare(nums[j], nums[j+1]):
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return str(int("".join(map(str, nums))))
    
def compare(self, n1, n2):
    return str(n1) + str(n2) > str(n2) + str(n1)
    
# selection sort
def largestNumber3(self, nums):
    for i in xrange(len(nums), 0, -1):
        tmp = 0
        for j in xrange(i):
            if not self.compare(nums[j], nums[tmp]):
                tmp = j
        nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
    return str(int("".join(map(str, nums))))
    
# insertion sort
def largestNumber4(self, nums):
    for i in xrange(len(nums)):
        pos, cur = i, nums[i]
        while pos > 0 and not self.compare(nums[pos-1], cur):
            nums[pos] = nums[pos-1]  # move one-step forward
            pos -= 1
        nums[pos] = cur
    return str(int("".join(map(str, nums))))

# merge sort        
def largestNumber5(self, nums):
    nums = self.mergeSort(nums, 0, len(nums)-1)
    return str(int("".join(map(str, nums))))
    
def mergeSort(self, nums, l, r):
    if l > r:
        return 
    if l == r:
        return [nums[l]]
    mid = l + (r-l)//2
    left = self.mergeSort(nums, l, mid)
    right = self.mergeSort(nums, mid+1, r)
    return self.merge(left, right)
    
def merge(self, l1, l2):
    res, i, j = [], 0, 0
    while i < len(l1) and j < len(l2):
        if not self.compare(l1[i], l2[j]):
            res.append(l2[j])
            j += 1
        else:
            res.append(l1[i])
            i += 1
    res.extend(l1[i:] or l2[j:])
    return res
    
# quick sort, in-place
def largestNumber(self, nums):
    self.quickSort(nums, 0, len(nums)-1)
    return str(int("".join(map(str, nums)))) 

def quickSort(self, nums, l, r):
    if l >= r:
        return 
    pos = self.partition(nums, l, r)
    self.quickSort(nums, l, pos-1)
    self.quickSort(nums, pos+1, r)
    
def partition(self, nums, l, r):
    low = l
    while l < r:
        if self.compare(nums[l], nums[r]):
            nums[l], nums[low] = nums[low], nums[l]
            low += 1
        l += 1
    nums[low], nums[r] = nums[r], nums[low]
    return low

# 尾递归
def _recursion_merge_sort2(l1, l2, tmp):
    if len(l1) == 0 or len(l2) == 0:
        tmp.extend(l1)
        tmp.extend(l2)
        return tmp
    else:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
        return _recursion_merge_sort2(l1, l2, tmp)

def recursion_merge_sort2(l1, l2):
    return _recursion_merge_sort2(l1, l2, [])


# 循环算法

# def loop_merge_sort(l1, l2): 
#     tmp = [] 
#     while len(l1) > 0 and len(l2) > 0: 
#         if l1[0] < l2[0]: 
#             tmp.append(l1[0]) 
#             del l1[0] 
#         else: tmp.append(l2[0]) 
#             del l2[0] 
#             tmp.extend(l1) 
#             tmp.extend(l2) 
#     return tmp

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def node(l1, l2):
    length1, lenth2 = 0, 0
    # 求两个链表长度
    while l1.next:
        l1 = l1.next
        length1 += 1
    while l2.next:
        l2 = l2.next
        length2 += 1
    # 长的链表先走
    if length1 > lenth2:
        for _ in range(length1 - length2):
            l1 = l1.next
    else:
        for _ in range(length2 - length1):
            l2 = l2.next
    while l1 and l2:
        if l1.next == l2.next:
            return l1.next
        else:
            l1 = l1.next
            l2 = l2.next

# cryptography < 1.3.4
    cryptography_version = "1.2.3"
    try:
        cryptography_version = list(map(int, cryptography_version.split('.')))
    except ValueError:
        return

    if cryptography_version < [1, 3, 4]:
        pass

#1 直接创建
dict = {'name':'earth', 'port':'80'}
#2 工厂方法
items=[('name','earth'),('port','80')]
dict2=dict(items)
dict1=dict((['name','earth'],['port','80']))
#3 fromkeys()方法
dict1={}.fromkeys(('x','y'),-1)
dict={'x':-1,'y':-1}
dict2={}.fromkeys(('x','y'))
dict2={'x':None, 'y':None}

#用集合

list(set(l))

#用字典

l1 = ['b','c','d','b','c','a','a']
l2 = {}.fromkeys(l1).keys()
print l2

#用字典并保持顺序

l1 = ['b','c','d','b','c','a','a']
l2 = list(set(l1))
l2.sort(key=l1.index)
print l2

#列表推导式

l1 = ['b','c','d','b','c','a','a']
l2 = []
[l2.append(i) for i in l1 if not i in l2]

def foo(x):
    print "executing foo(%s)"%(x)

class A(object):
    def foo(self,x):
        print "executing foo(%s,%s)"%(self,x)

    @classmethod
    def class_foo(cls,x):
        print "executing class_foo(%s,%s)"%(cls,x)

    @staticmethod
    def static_foo(x):
        print "executing static_foo(%s)"%x

a=A()

# 这里先理解下函数参数里面的self和cls.这个self和cls是对类或者实例的绑定,对于一般的函数来说我们可以这么调用foo(x),这个函数就是最常用的,它的工作跟任何东西(类,实例)无关.对于实例方法,我们知道在类里每次定义方法的时候都需要绑定这个实例,就是foo(self, x),为什么要这么做呢?因为实例方法的调用离不开实例,我们需要把实例自己传给函数,调用的时候是这样的a.foo(x)(其实是foo(a, x)).类方法一样,只不过它传递的是类而不是实例,A.class_foo(x).注意这里的self和cls可以替换别的参数,但是python的约定是这俩,还是不要改的好.

# 对于静态方法其实和普通的方法一样,不需要对谁进行绑定,唯一的区别是调用的时候需要使用a.static_foo(x)或者A.static_foo(x)来调用.

# 1/使用__new__方法
class Singleton(object):
    def __new__(cls, *args, **kw):
        if not hasattr(cls, '_instance'):
            orig = super(Singleton, cls)
            cls._instance = orig.__new__(cls, *args, **kw)
        return cls._instance

class MyClass(Singleton):
    a = 1

#2 共享属性
#创建实例时把所有实例的__dict__指向同一个字典,这样它们具有相同的属性和方法.
class Borg(object):
    _state = {}
    def __new__(cls, *args, **kw):
        ob = super(Borg, cls).__new__(cls, *args, **kw)
        ob.__dict__ = cls._state
        return ob

class MyClass2(Borg):
    a = 1

#3 装饰器版本    
def singleton(cls, *args, **kw):
    instances = {}
    def getinstance():
        if cls not in instances:
            instances[cls] = cls(*args, **kw)
        return instances[cls]
    return getinstance

@singleton
class MyClass:
  ...