<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/2/27 15:32
"""


class Queue:
    def __init__(self):
        self.list = []

    def enqueue(self, item):
        self.list.insert(0, item)

    def dequeue(self):
        if self.list:
            return self.list.pop()
        return None

    def isEmpty(self):
        return len(self.list) == 0

    def size(self):
        return len(self.list)


def hotPotato(namelist, num):
    """
    烫手山芋问题
    :param namelist:
    :param num: 传递次数
    :return:
    """
    queue = Queue()
    for name in namelist:
        queue.enqueue(name)

    while queue.size() > 1:
        for i in range(num):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    return queue.dequeue()


if __name__ == "__main__":
    queue = Queue()
    print(queue.isEmpty())
    [queue.enqueue(i) for i in range(10)]
    print(queue.isEmpty())
    print(queue.list)
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.size())
    print(queue.list)

    print(hotPotato(["Bill", "David", "Susan", "Jane", "Kent", "Brad"], 7))<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/3/1 15:58
"""


# 单例模式
class Single(object):
    def __new__(cls):
        if not hasattr(cls, "_instance"):
            cls._instance = super(Single, cls).__new__(cls)
        return cls._instance


obj1 = Single()
obj2 = Single()

obj1.attr1 = 'value1'
print(obj1.attr1, obj2.attr1)

print(obj1 is obj2)


# 共享属性
class Borg(object):
    _state = {}
    def __new__(cls):
        ob = super(Borg, cls).__new__(cls)
        ob.__dict__ = cls._state
        return ob

<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/2/27 16:45
"""


class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.next = None

    def set_data(self, item):
        self.data = item

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_next(self, next):
        self.next = next


class UnorderedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

    def add_order(self, item):
        """
        有序链表添加
        :param item:
        :return:
        """
        current = self.head
        pre = None
        state = False
        while not state:
            if item <= current.get_data() and pre is None:
                state = True
            if item < current.get_data():
                state = True
            else:
                pre = current
                current = current.get_next()
        temp = Node(item)
        temp.set_next(current)
        pre.set_next(temp)

    def get(self, index):
        # 支持负数
        index = index if index >= 0 else len(self) + index
        if index < 0 or len(self) < index:
            return None
        pre = self.head
        while index:
            pre = pre.next
            index -= 1
        return pre

    def set(self, index, data):
        node = self.get(index)
        if node:
            node.set_data(data)
        return node

    def insert(self, index, data):
        """
        1.index 插入节点位置包括正负数
        2.找到index-1-->pre_node的节点
        3.pre_node.next-->node
          node.next-->pre_node.next.next
        4.head
        :param index:
        :param data:
        :return:
        """
        new_node = Node(data)
        if abs(index + 1) > len(self):
            return False
        index = index if index >= 0 else len(self) + index + 1
        if index == 0:
            new_node.set_next(self.head)
            self.head = new_node
        else:
            pre_node = self.get(index-1)
            after_node = self.get(index)
            pre_node.set_next(new_node)
            new_node.set_next(after_node)
        return new_node

    def remove(self, item):
        current = self.head
        pre = None
        state = False
        while not state:
            if item == current.get_data():
                state = True
            else:
                pre = current
                current = current.get_next()
        if pre is None:
            self.head = current.get_next()
        else:
            pre.set_next(current.get_next())

    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.get_data() == item:
                found = True
            else:
                current = current.get_next()

        return found

    def __reversed__(self):
        """
        1.pre-->next 转变为 next-->pre
        2.pre 若是head 则把 pre.nex --> None
        3.tail-->self.head
        :return:
        """
        def reverse(pre_node, node):
            if pre_node is self.head:
                pre_node.set_next(None)
            if node:
                next_node = node.get_next()
                node.set_next(pre_node)
                return reverse(node, next_node)
            else:
                self.head = pre_node
        return reverse(self.head, self.head.get_next())

    def __len__(self):
        pre = self.head
        length = 0
        while pre:
            length += 1
            pre = pre.next
        return length

    def __str__(self):
        pre = self.head
        list_all = []
        while pre:
            list_all.append(pre.get_data())
            pre = pre.next
        return str(list_all)


if __name__ == "__main__":
    single_link_list = UnorderedList()
    single_link_list.add(78)
    single_link_list.add(88)
    single_link_list.add(68)
    single_link_list.add(58)
    single_link_list.add(38)
    print(len(single_link_list))
    print(single_link_list.search(78))
    single_link_list.remove(88)
    print(single_link_list)
    print("set index = 1 -- data = 99")
    single_link_list.set(1, 99)
    print("get value index = 1")
    print(single_link_list.get(1).get_data())
    print(single_link_list)
    single_link_list.insert(1, 55)
    print("insert index = 1 -- data = 55")
    print(single_link_list)
    single_link_list.__reversed__()
    print(single_link_list)
<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/2/27 16:20
"""


class Deque:
    def __init__(self):
        self.list = []

    def isEmpty(self):
        return self.list == []

    def size(self):
        return len(self.list)

    def add_front(self, item):
        self.list.append(item)

    def add_rear(self, item):
        self.list.insert(0, item)

    def remove_front(self):
        return self.list.pop()

    def remove_rear(self):
        return self.list.pop(0)


def palindrome(string):
    """
    判断是否回文
    :param string: 待判断字符串
    :return:
    """
    deque = Deque()
    state = True
    for i in string:
        deque.add_front(i)

    while deque.size() > 1 and state:
        top = deque.remove_front()
        end = deque.remove_rear()
        if top != end:
            state = False
    return state

if __name__ == "__main__":
    print(palindrome("123456654321"))
<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/2/27 14:16
"""


class Stack:
    def __init__(self):
        self.list = []

    def isEmpty(self):
        return len(self.list) == 0

    def push(self, item):
        self.list.append(item)

    def pop(self):
        if self.list:
            return self.list.pop()
        return None

    def peek(self):
        if self.list:
            return self.list[-1]
        return None

    def size(self):
        return len(self.list)


def par_check(string):
    """
    符号匹配 如：{{([][])}()}}
    :param string:
    :return:
    """
    s = Stack()
    state = True
    index = 0
    swtich = {
        "{": "}",
        "(": ")",
        "[": "]"
    }

    while index < len(string) and state:
        if string[index] in "{([":
            s.push(string[index])
        else:
            if s.isEmpty():
                state = False
            else:
                if swtich[s.pop()] != string[index]:
                    state = False

        index = index + 1

    if state and s.isEmpty():
        return True
    else:
        return False




if __name__ == "__main__":
    stack = Stack()
    print(stack.isEmpty())
    [stack.push(i) for i in range(10)]
    print(stack.list)
    print(stack.isEmpty())
    print(stack.peek())
    print(stack.pop())
    print(stack.peek())
    print(stack.size())


    print(par_check("{{([][])}()}}"))


<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/2/27 9:50
"""


class SortedDict(dict):
    def __init__(self):
        self.list = []
        super(SortedDict, self).__init__()

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

        super(SortedDict, self).__setitem__(key, value)

    def __getitem__(self, key):
        if key not in self.list:
            raise KeyError('dict has not key: %s' % key)
        return self.get(key)

    def __delitem__(self, key):
        if key not in self.list:
            raise KeyError('dict has not key: %s' % key)
        self.list.remove(key)
        self.pop(key)

    def popitem(self, tail=True):
        """

        :param tail: True 最后一个元素 False 第一个元素
        :return:
        """
        if not self.list:
            raise KeyError('dict is empty')
        if tail:
            del self.list[-1]
            return self.get(self.list[-1])
        else:
            del self.list[0]
            return self.get(self.list[0])

    def __iter__(self):
        return iter(self.list)

    def __str__(self):

        temp_list = []
        for key in self.list:
            value = self.get(key)

            temp_list.append("'%s':%s" % (key, value,))

        temp_str = '{' + ','.join(temp_list) + '}'
        return temp_str


if __name__ == "__main__":
    obj = SortedDict()
    obj["test"] = "test"
    obj["test1"] = "test1"
    obj["test2"] = "test2"
    obj["test3"] = "test3"
    for key in obj:
        print(key)
    print("test")
    del obj["test2"]
    print(obj)
    obj.popitem()
    print(obj)
<file_sep>#!/usr/bin/env python
# encoding: utf-8
"""
@author: leason
@time: 2018/3/2 16:41
"""


# 斐波那契
# 只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
def memo(func):
    cache = {}

    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrap


@memo
def fib(i):
    if i < 2:
        return 1
    return fib(i - 1) + fib(i - 2)
