[数据结构]栈、队列、递归

发表于
参加Datawhale的编程计划的第2个任务，涉及栈、队列、递归，用python实现。。

栈

练习：Valid Parentheses（有效的括号）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        pars = [None]
        parmap = {')': '(', '}': '{', ']': '['}
        for c in s:
            if c in parmap and parmap[c] == pars[len(pars)-1]:
                pars.pop()
            else:
                pars.append(c)
        return len(pars) == 1

Longest Valid Parentheses（最长有效的括号）（作为可选）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        maxlen = 0
        stack = []
        last = -1
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(i)     # push the INDEX into the stack!!!!
            else:
                if stack == []:
                    last = i
                else:
                    stack.pop()
                    if stack == []:
                        maxlen = max(maxlen, i-last)
                    else:
                        maxlen = max(maxlen, i-stack[len(stack)-1])
        return maxlen

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

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
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        ans = []
        for i in tokens:
            if i != '/' and i != '*' and i != '+' and i != '-':
                ans.append(int(i))
            else:
                tmp1 = ans.pop()
                tmp2 = ans.pop()
                if i == '/':
                    if tmp1*tmp2 < 0:
                        ans.append(-((-tmp2) // tmp1))
                    else:
                        ans.append(tmp2/tmp1)
                if i == '*':
                    ans.append(tmp2*tmp1)
                if i == '+':
                    ans.append(tmp2 + tmp1)
                if i == '-':
                    ans.append(tmp2 - tmp1)
        return ans[0]

队列

练习：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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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.queue = []
        self.size = k
        self.rear = 0

    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 not self.isFull():
            self.queue.insert(0, value)
            self.rear += 1
            return True
        else:
            return False
        

    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 not self.isFull():
            self.queue.append(value)
            self.rear += 1
            return True
        else:
            return False

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

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

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[0]

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.rear -1]

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        return 0 == self.rear

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        return self.rear == self.size


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

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

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
from collections import deque

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # deque为双端队列
        dq = deque()
        max_numbers = []
        # 方法四：使用双向队列，时间复杂度O(n)。
        # 在队列中维持一个k长度窗口内的递减元素下标，为什么呢？因为当元素递增时，前面的元素就不需要了，因为最大值肯定不会是它们了。
        #
        # 顺序扫描每一个元素，当队头的元素超出窗口视野的时候，将对头元素出队；然后检查队尾，如果队尾元素小于或等于当前元素，
        # 则队尾元素出队，重复检查队尾直至队列为空或者队尾元素大于当前元素。然后当前元素入队。
        # 顺序扫描每一个元素
        for i in range(len(nums)):
            # 当队列中有值，并且元素递增时，让之前的元素出对
            # 之所以要判断dq不为空，是因为第二个条件需要取出对应的值进行比较
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            # 将当前的元素入队
            dq.append(i)
            # 如果当前的i已经大于滑动窗口的大小，并且dq中的长度已经大于k，最先入队的下标和当前的下标之间的差值-1，一定是小于等于K。
            if i >= k and dq and dq[0] == i - k:
                # 出头元素
                dq.popleft()
            # 窗口滑动
            if i >= k - 1:
                # 取出最大值
                max_numbers.append(nums[dq[0]])

        return max_numbers

递归

练习：Climbing Stairs（爬楼梯）

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        sum = 0
        for i in xrange(0, n/2 + 1):
            count = n - i
            sum += reduce(operator.mul, range(count - i + 1, count + 1), 1) / reduce(operator.mul, range(1, i +1), 1)
        return sum

相关链接

编程计划的第2个任务
第二次任务 打卡表格