【无标题】

力扣 155

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。
  示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1. 方法1：辅助栈
   用一个辅助栈，辅助栈的最上面总是存储插入的数据的最小值，如果新插入的数据比辅助栈顶元素 小或者相等，就插入辅助栈中去。
   在非辅助栈pop元素的时候，如果辅助栈的栈顶元素和非辅助栈pop出去的元素相等，辅助栈栈顶的元素出栈。

注意：辅助栈插入元素的时候，插入的元素的满足条件是 小于等于 当前辅助栈的栈顶的元素。等于的元素也要插入，因为辅助栈的pop的条件是和非辅助栈的pop元素相等，如果 插入的规则是小于，会出现辅助栈pop之后最小元素数和非辅助栈的最小元素数量不相等的情况。

class MinStack:

    def __init__(self):
        self.lack = []
        self.helper = []



    def push(self, val: int) -> None:
        if not self.lack:
            self.lack.append(val)
            self.helper.append(val)
        else:
            self.lack.append(val)
            if not self.helper or self.helper[-1] >= val:
                self.helper.append(val)
    
    def pop(self) -> None:
        val = self.lack.pop()
        if val == self.helper[-1]:
            self.helper.pop()




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


    def getMin(self) -> int:
        if self.helper:

            return self.helper[-1]
        else:
            return 0

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2. 不用辅助栈，直接在栈
   可以用一个栈，这个栈同时保存的是每个数字 x 进栈的时候的值 与 插入该值后的栈内最小值。
   即每次新元素 x 入栈的时候保存一个元组：（当前值 x，栈内最小值）。

   这个元组是一个整体，同时进栈和出栈。即栈顶同时有值和栈内最小值，top()函数是获取栈顶的当前值，即栈顶元组的第一个值； getMin() 函数是获取栈内最小值，即栈顶元组的第二个值；pop() 函数时删除栈顶的元组。

   每次新元素入栈时，要求新的栈内最小值：比较当前新插入元素 x 和 当前栈内最小值（即栈顶元组的第二个值）的大小。

   • 新元素入栈：当栈为空，保存元组 (x, x)；
   • 当栈不空，保存元组 (x, min(此前栈内最小值， x))) 出栈：删除栈顶的元组。

class MinStack:

    def __init__(self):
        self.lack = []


    def push(self, val: int) -> None:
        if not self.lack:
            self.lack.append((val,val))

        else:
            if val <= self.lack[-1][1]:
                self.lack.append((val,val))
            else:
                self.lack.append((val,self.lack[-1][1]))
    

    def pop(self) -> None:
        self.lack.pop()


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


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



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

线程安全的单例模式

import threading

"""
线程安全的单利模式

紧跟with后面的语句被求值后，返回对象的 __enter__() 方法被调用，这个方法的返回值将被赋值给as后面的变量。
当with后面的代码块全部被执行完之后，将调用前面返回对象的 __exit__()方法
"""
def synchronized(func):
    func.__lock__ = threading.Lock()

    def lock_func(*args, **kwargs):
        with func.__lock__:
            return func(*args, **kwargs)

    return lock_func

class Singleton(object):
    instance = None

    @synchronized
    def __new__(cls):
        # 关键在于这，每一次实例化的时候，我们都只会返回这同一个instance对象
        if not cls.instance:
            cls.instance = super(Singleton, cls).__new__(cls)
        return cls.instance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

分库分表的思路

两个超大集合的差集

1. 内存充足的情况下

如果你内存足够大，那可以先将一个列表读入集合s1中，遍历第二个列表，准备一个空集合s2，对于每一个元素，判断是否在s1，不在则加入s2，在则从s1中删除该元素。遍历结束后，s1中的元素和s2中的元素分别是两个列表独立存在的元素，也就是两个列表之差异。

2. 内存不足的情况下

如果不想占用太多内存，假设数据存在文件中每次只能同时去除一小部分放到内存，那就得牺牲一点时间复杂度。
首先归并升序排序两个列表，可以只需要很小内存即可完成。
然后双指针读取文件，有序情况下很容易判断出两个列表的差异。
假设两个列表长度分别为m、n，方法一时间复杂度是 O(m + n)，但是占用了大量内存。

方法二时间复杂度主要是排序的复杂度，O(m log m) + O(n log n), 占用内存可以非常小。

生成器和迭代器的不同 用生成器生成斐波那契数列