编程基础-2-栈、队列、递归

发表于 | 分类于 | 评论数： | 阅读次数：

栈

先进后出；push；pop

两种存储表示方式：顺序栈，链式栈

用数组实现一个顺序栈

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
# coding:utf-8

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

    def isempty(self):
        if (len(self.stack) == 0):
            return True
        return False

    def push(self, e):
        return self.stack.append(e)

    def pop(self):
        if not self.isempty():
            self.stack.pop()

    def print_info(self):
        print(self.stack)


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.print_info()  # [1, 2, 3]
stack.pop()
stack.print_info()  # [1, 2]
stack.push(4)
stack.print_info()  # [1, 2, 4]

用链表实现一个链式栈

使用head表示栈顶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
 
class Stack:
    def __init__(self):
        self.head = None
 
    def push(self, data):
        if self.head is None:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
 
    def pop(self):
        if self.head is None:
            return None
        else:
            popped = self.head.data
            self.head = self.head.next
            return popped

编程模拟实现一个浏览器的前进、后退功能

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
43
44
45
46
47
# coding:utf-8

class Browser:
    def __init__(self):
        self.stack = []
        self.index = -1

    def isempty(self):
        if (len(self.stack) == 0):
            return True
        return False

    def access(self, e):
        self.stack.append(e)
        self.index += 1
        return e

    def forward(self):
        self.index = min(self.index-1, len(self.stack)-1)
        return self.stack[self.index]

    def back(self):
        if not self.isempty():
            self.index = max(self.index - 1, 0)
            return self.stack[self.index]


bw = Browser()
print(bw.access(1))
print(bw.access(2))
print(bw.access(3))
print(bw.forward())
print(bw.access(4))
print(bw.back())
print(bw.back())

"""
1
2
3
before 2
after 1
2
4
2
1
"""

对应的 LeetCode 练习题

Valid Parentheses（有效的括号）

英文版：https://leetcode.com/problems/valid-parentheses/

中文版：https://leetcode-cn.com/problems/valid-parentheses/

代码见：leetcode-20-有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        re_dict = {"(": ")", "{": "}", "[": "]"}
        stack = []
        for t in s:
            if t not in re_dict:
                if len(stack) == 0:
                    return False
                elif stack[-1] != t:
                    return False
                else:
                    stack.pop()
            else:
                stack.append(re_dict[t])
        if (len(stack)):
            return False
        return True

Longest Valid Parentheses（最长有效的括号）

英文版：https://leetcode.com/problems/longest-valid-parentheses/

中文版：https://leetcode-cn.com/problems/longest-valid-parentheses/

参考：https://leetcode.com/problems/longest-valid-parentheses/solution/

改方法使用栈，先在栈底放入-1，然后放各个括号索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                else:
                    ans = max(ans, i - stack[-1])
        return ans

测试用例

1
2
3
4
5
s = Solution()
print(s.longestValidParentheses("(()"))  # 2
print(s.longestValidParentheses(")()())"))  # 4
print(s.longestValidParentheses("(()())"))  # 6
print(s.longestValidParentheses("()(()"))  # 2

Evaluate Reverse Polish Notatio（逆波兰表达式求值）

英文版：https://leetcode.com/problems/evaluate-reverse-polish-notation/

中文版：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

题中指明逆波兰式总是有效的，因此无需判定有效，直接使用栈解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for s in tokens:
            if s == "+":
                b = stack.pop()
                a = stack.pop()
                stack.append(a + b)
            elif s == "-":
                b = stack.pop()
                a = stack.pop()
                stack.append(a - b)
            elif s == "*":
                b = stack.pop()
                a = stack.pop()
                stack.append(a * b)
            elif s == "/":
                b = stack.pop()
                a = stack.pop()
                stack.append(int(a / b))  # 负数除法：6//-132 = -1，而非0。因此采用先除，后取整方法
            else:
                stack.append(int(s))  # 将字符转为int存入栈
            # print(stack)
        return stack[0]

python除法可参考：python – 整数除以负数

更简洁的写法(耗时更长)：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        symbol = ["+", "-", "*", "/"]
        for s in tokens:
            if s in symbol:
                b = stack.pop()
                a = stack.pop()
                stack.append(str(int(eval(a + s + b))))
            else:
                stack.append(s)  # 栈中存字符
            # print(stack)
        return int(stack[0])  # 最后结果转为int

部分测试用例：

1
2
3
4
s = Solution()
print(s.evalRPN(["2", "1", "+", "3", "*"]))  # 9,((2 + 1) * 3) = 9
print(s.evalRPN(["4", "13", "5", "/", "+"]))  # 6,  (4 + (13 / 5)) = 6
print(s.evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # 22

队列

用数组实现一个顺序队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# coding:utf-8
class Queue:
    def __init__(self):
        self.items = []

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

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

    def dequeue(self):
        return self.items.pop()

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

用链表实现一个链式队列

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
# coding:utf-8
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = self.rear = None

    def isEmpty(self):
        return self.front == None

    def EnQueue(self, item):
        temp = Node(item)

        if self.rear == None:
            self.front = self.rear = temp
            return
        self.rear.next = temp
        self.rear = temp

    def DeQueue(self):

        if self.isEmpty():
            return
        temp = self.front
        self.front = temp.next

        if (self.front == None):
            self.rear = None
        return str(temp.data)

实现一个循环队列

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
class Queue:
    def __init__(self):
        front = None
        rear = None


def enQueue(q, value):
    temp = Node()
    temp.data = value
    if (q.front == None):
        q.front = temp
    else:
        q.rear.link = temp

    q.rear = temp
    q.rear.link = q.front


def deQueue(q):
    if (q.front == None):
        print("Queue is empty")
        return -1

    value = None
    if (q.front == q.rear):
        value = q.front.data
        q.front = None
        q.rear = None
    else:
        temp = q.front
        value = temp.data
        q.front = q.front.link
        q.rear.link = q.front

    return value

对应的 LeetCode 练习题

Circular Deque（设计一个双端队列）

英文版：https://leetcode.com/problems/design-circular-deque/

中文版：https://leetcode-cn.com/problems/design-circular-deque/

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class MyCircularDeque(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.k = k
        self.queue = []

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if self.isFull():
            return False
        self.queue.insert(0, value)
        return True

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if self.isFull():
            return False
        self.queue.append(value)
        return True

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if self.isEmpty():
            return False
        self.queue.pop(0)
        return True

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if self.isEmpty():
            return False
        self.queue.pop()
        return True

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if len(self.queue) > 0:
            return self.queue[0]  # 注意不是pop(0)
        return -1  # 根据测试用例预期返回-1， 不写return None

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if len(self.queue) > 0:
            return self.queue[-1]  # 注意不是pop()
        return -1  # 根据测试用例预期返回-1， 不写return None

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        if len(self.queue) == 0:
            return True
        return False

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        if len(self.queue) == self.k:
            return True
        return False

部分测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
circularDeque = MyCircularDeque(3)  # 设置容量大小为3
print(circularDeque.insertLast(1))  # 返回 true
print(circularDeque.insertLast(2))  # 返回 true
print(circularDeque.insertFront(3))  # 返回 true
print(circularDeque.insertFront(4))  # 已经满了，返回 false
print(circularDeque.getRear())  # 返回 2
print(circularDeque.isFull())  # 返回 true
print(circularDeque.deleteLast())  # 返回 true
print(circularDeque.insertFront(4))  # 返回 true
print(circularDeque.getFront())  # 返回 4

print("=" * 30)
obj = MyCircularDeque(4)  # null
print(obj.insertFront(9))  # true
print(obj.deleteLast())  # true
print(obj.getRear())  # -1

"""
["MyCircularDeque","insertFront","deleteLast","getRear","getFront","getFront","deleteFront","insertFront","insertLast","insertFront","getFront","insertFront"]
[[4],[9],[],[],[],[],[],[6],[5],[9],[],[6]]

[null,true,true,-1,-1,-1,false,true,true,true,9,true]
"""

Sliding Window Maximum（滑动窗口最大值）

英文版：https://leetcode.com/problems/sliding-window-maximum/

中文版：https://leetcode-cn.com/problems/sliding-window-maximum/

递归

实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)

1
2
3
4
5
6
7
8
9
10
# coding:utf-8

def fbs(n):
    if n <= 0:
        return -1
    if n == 1 or n == 2:
        return 1
    return fbs(n - 1) + fbs(n - 2)

print(fbs(5))  #5

实现求阶乘 n!

1
2
3
4
5
6
7
8
9
10
# coding:utf-8

def factorial(n):
    if n <= 0:
        return -1
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5)) #120

实现一组数据集合的全排列

参考：https://blog.csdn.net/qq_42015869/article/details/79996227

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def perm(data, begin, end):
    if begin == end:  # 递归结束条件，当交换到最后一个元素的时候不需要交换，1的全排列还是1。
        print(data)  # 打印一次排列完成后的数组。
    else:
        j = begin
        for i in range(begin, end):  # 从begin到end全排列。
            data[i], data[j] = data[j], data[i]
            perm(data, begin + 1, end)
            data[i], data[j] = data[j], data[i]  # 递归完成后，交换回原来的位置。


arr = [1, 2, 3]
perm(arr, 0, len(arr))

""""
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
"""

对应的 LeetCode 练习题

70. 爬楼梯

方法一：斐波拉切（用时28 ms，击败了99.36%的用户）

观察发现是斐波拉切数，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        else:
            ans = [1, 1]
            for i in range(2, n + 1):
                ans.append(ans[i - 2] + ans[i - 1])
            return ans[-1]

方法二：使用递归（超时）

这道题自顶向下的思考：如果要爬到n台阶，有两种可能性:

  1. 在n-1的台阶处爬一层台阶
  2. 在n-2的台阶处爬两层台阶

继续向下延伸思考，到达每一次层一共有几种方法这个问题就变成了2个子问题：

  1. 到达n-1层台阶有几种方法
  2. 到达n-2层台阶有几种方法

之后对返回子问题之和即可。

因为递归的时候出现了很多次重复的运算。如爬n-2层的计算出现了2次，这种重复计算随着input的增大，会出现的越来越多，时间复杂度也会将以指数的级别上升。

1
2
3
4
5
6
7
8
9
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 1
        if n == 2: return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
方法三：动态规划

优化方法二，将之前的计算好了的结果存起来，之后如果遇到重复计算直接调用结果，效率将会从之前的指数时间复杂度，变成O(N)的时间复杂度。

1
2
3
4
5
6
7
8
class Solution(object):
    def climbStairs(self, n):
        if n == 1: return 1
        res = [0 for i in range(n)]
        res[0], res[1] = 1, 2
        for i in range(2, n):
            res[i] = res[i-1] + res[i-2]
        return res[-1]

参考：https://leetcode.com/problems/climbing-stairs/discuss/163347/Python-3000DP-or-tm