leetcode刷題記錄
本文記錄一下leetcode刷題記錄，記錄一下自己的解法和心得。

LeetCode

Binary Tree Level Order Traversal II

題目:Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

例子:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

題意分析:
給定一個(gè)二叉樹(shù)，返回自底向上遍歷結(jié)點(diǎn)的值

思路分析

相等于特殊的按層遍歷，在基本的按層遍歷樹(shù)可以選擇用棧或者隊(duì)列來(lái)保存每一層的結(jié)點(diǎn)。在這里我們選擇使用棧。并且使用列表來(lái)模擬棧，在使用一個(gè)列表來(lái)保存需要返回的結(jié)果。

首先，初始化需要將根結(jié)點(diǎn)與level為0的元組存入列表中，循環(huán)這個(gè)棧，不為空的話，在棧的尾部彈出一個(gè)元素，第一次也就是彈出的根結(jié)點(diǎn)和level層數(shù)。

得到彈出的結(jié)點(diǎn)，判斷其是否為空，如果不為空，判斷此時(shí)結(jié)果列表的長(zhǎng)度，也就是已經(jīng)遍歷過(guò)的層數(shù)，

如果小于當(dāng)前層數(shù)+1，也就是在結(jié)果列表的第一個(gè)位置插入一個(gè)列表。如果大于當(dāng)前l(fā)evel+1，我們就可以在結(jié)果列表中放入合適的結(jié)點(diǎn)的值。然后只需要在棧中壓入當(dāng)前結(jié)點(diǎn)的左子樹(shù)和當(dāng)前層數(shù)level+1的元組，和右子樹(shù)和當(dāng)前層數(shù)level+1的元組。最后返回結(jié)果列表即可。

方法一

很容易想到我們可以遍歷兩次數(shù)組，在內(nèi)循環(huán)中判斷兩次循環(huán)中的數(shù)相加是否等于target

class Solution:
    def levelOrderBottom(self, root):
        """
        返回節(jié)點(diǎn)值的自底向上的順序遍歷。（從左到右，從葉到根逐級(jí)地）
        :param root: TreeNode
        :return: list[list[int]]
        """
        stack = [(root, 0)]
        res = []
        # 如果棧不為空
        while stack:
            # 將棧中最后一個(gè)元素彈出
            node, level = stack.pop()
            # 如果該結(jié)點(diǎn)存在
            if node:
                # 如果結(jié)果列表的長(zhǎng)度小于層數(shù)+1
                if len(res) < level + 1:
                    res.insert(0, [])
                # 將當(dāng)前結(jié)點(diǎn)的值添加在結(jié)果列表中
                res[-(level + 1)].append(node.val)
                stack.append((node.right, level + 1))
leetcode刷題記錄
本文記錄一下leetcode刷題記錄，記錄一下自己的解法和心得。

<!--more-->

# LeetCode

## Binary Tree Level Order Traversal II
題目:[Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/)

>Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

例子:
```text
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

題意分析:
給定一個(gè)二叉樹(shù)，返回自底向上遍歷結(jié)點(diǎn)的值

思路分析

相等于特殊的按層遍歷，在基本的按層遍歷樹(shù)可以選擇用?；蛘哧?duì)列來(lái)保存每一層的結(jié)點(diǎn)。在這里我們選擇使用棧。并且使用列表來(lái)模擬棧，在使用一個(gè)列表來(lái)保存需要返回的結(jié)果。

首先，初始化需要將根結(jié)點(diǎn)與level為0的元組存入列表中，循環(huán)這個(gè)棧，不為空的話，在棧的尾部彈出一個(gè)元素，第一次也就是彈出的根結(jié)點(diǎn)和level層數(shù)。

得到彈出的結(jié)點(diǎn)，判斷其是否為空，如果不為空，判斷此時(shí)結(jié)果列表的長(zhǎng)度，也就是已經(jīng)遍歷過(guò)的層數(shù)，

如果小于當(dāng)前層數(shù)+1，也就是在結(jié)果列表的第一個(gè)位置插入一個(gè)列表。如果大于當(dāng)前l(fā)evel+1，我們就可以在結(jié)果列表中放入合適的結(jié)點(diǎn)的值。然后只需要在棧中壓入當(dāng)前結(jié)點(diǎn)的左子樹(shù)和當(dāng)前層數(shù)level+1的元組，和右子樹(shù)和當(dāng)前層數(shù)level+1的元組。最后返回結(jié)果列表即可。

方法一

很容易想到我們可以遍歷兩次數(shù)組，在內(nèi)循環(huán)中判斷兩次循環(huán)中的數(shù)相加是否等于target

class Solution:
    def levelOrderBottom(self, root):
        """
        返回節(jié)點(diǎn)值的自底向上的順序遍歷。（從左到右，從葉到根逐級(jí)地）
        :param root: TreeNode
        :return: list[list[int]]
        """
        stack = [(root, 0)]
        res = []
        # 如果棧不為空
        while stack:
            # 將棧中最后一個(gè)元素彈出
            node, level = stack.pop()
            # 如果該結(jié)點(diǎn)存在
            if node:
                # 如果結(jié)果列表的長(zhǎng)度小于層數(shù)+1
                if len(res) < level + 1:
                    res.insert(0, [])
                # 將當(dāng)前結(jié)點(diǎn)的值添加在結(jié)果列表中
                res[-(level + 1)].append(node.val)
                stack.append((node.right, level + 1))
                stack.append((node.left, level + 1))
        return res

使用隊(duì)列的話，方式其實(shí)也是大同小異，這里就不在闡述。

Convert Sorted Array to Binary Search Tree

題目:Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

題意分析:
給定一個(gè)數(shù)組，元素按升序排序，將其轉(zhuǎn)換為高度平衡的BST。

思路分析

想要轉(zhuǎn)換成平衡二叉樹(shù)，首先我們需要知道什么叫做平衡二叉樹(shù)，知道了bst是深才能開(kāi)始思考與討論。

平衡二叉樹(shù)（Self-balancing binary search tree）又被稱為AVL樹(shù)（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)

平衡二叉樹(shù)主要的特點(diǎn)就是“棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)”,知道了這個(gè)，題目又要求我們把一個(gè)已經(jīng)排序的數(shù)組(列表)作為整個(gè)二叉樹(shù)的值。

所以我們可以找出數(shù)組中的中值，把他作為根，把小于中值的作為左子樹(shù)，大于中值的作為右子樹(shù)，在利用遞歸的思想，從左子樹(shù)中找到左子樹(shù)的根，在右子樹(shù)中找到右子樹(shù)的根，就可以得到我們所需要的平衡二叉樹(shù)。

所以我們可以有以下解法

方法一

很容易想到我們可以遍歷兩次數(shù)組，在內(nèi)循環(huán)中判斷兩次循環(huán)中的數(shù)相加是否等于target

class Solution:
    def sortedArrayToBST(self, num):
        """
        將已排序的數(shù)組轉(zhuǎn)換為高度平衡二叉樹(shù)
        :param num: list[int]
        :return: TreeNode
        """
        # 如果列表為空
        if not num:
            return None
        # 列表中間的值為列表長(zhǎng)度整數(shù)2
        mid = len(num) // 2
        # 生成一個(gè)以中值為結(jié)點(diǎn)的值的作為根結(jié)點(diǎn)
        root = TreeNode(num[mid])
        # 遞歸求出
        # 左子樹(shù)為小于中間值一部分
        root.left = self.sortedArrayToBST(num[:mid])
        # 右子樹(shù)為大于中間值的一部分
        root.right = self.sortedArrayToBST(num[mid + 1:])
        return root

Balanced Binary Tree

題目:Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

題意分析:
給定一個(gè)二叉樹(shù)，判斷其是否是平衡二叉樹(shù)

思路分析

在上一題的分析中，我們已經(jīng)知道了什么叫做平衡二叉樹(shù)。題目給出的方法返回值的bool類型，不利于我們?nèi)パh(huán)遞歸的判斷它。我們可以單獨(dú)寫(xiě)一個(gè)check函數(shù)，其返回值是int類型。當(dāng)函數(shù)返回-1時(shí)，該二叉樹(shù)為非平衡二叉樹(shù)，當(dāng)函數(shù)返回值不為-1時(shí)，該二叉樹(shù)為平衡二叉樹(shù)。

所以我們可以有以下解法

方法一

class Solution:
    def isBalanced(self, root):
        """
        判斷一個(gè)樹(shù)是否為平衡二叉樹(shù)
        當(dāng)check函數(shù)的發(fā)揮值不等于-1時(shí)返回true，等于-1是返回false
        :param root: TreeNode
        :return: bool
        """
        return self.check(root) != -1

    def check(self, root):
        """
        檢查結(jié)點(diǎn)
        :param root: TreeNode
        :return: int
        """
        # 結(jié)點(diǎn)為空時(shí)
        if root is None:
            return 0
        # 遞歸得出左子樹(shù)的返回值
        left = self.check(root.left)
        # 遞歸得出右子樹(shù)的返回值
        right = self.check(root.right)
        # 如果左子樹(shù)不為平衡樹(shù)或者右子樹(shù)不為平衡二叉樹(shù)，
        # 左右子樹(shù)想減的值大于1(-1-(-1))左右子樹(shù)不為平衡樹(shù)的情況
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        # left right分別等于0或1的情況
        return 1 + max(left, right)

Minimum Depth of Binary Tree

題目:Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

題意分析:
求出二叉樹(shù)的最小深度

思路分析

如果該樹(shù)為空，需要單獨(dú)討論，返回深度為0.遞歸調(diào)用自己，傳入根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)，如果其中有空節(jié)點(diǎn)，那么此時(shí)的left或者right就有值為0，既然求的是最小的深度，那么就可以返回該子樹(shù)的深度。如果兩個(gè)值均不為0了，那么就返回左子樹(shù)和右子樹(shù)深度的最小值，最后加上子樹(shù)到根節(jié)點(diǎn)的1，即為最小深度。

所以我們可以有以下解法

方法一

class Solution:
    def minDepth(self, root):
        # 如果是空樹(shù)
        if not root:
            return 0
        # 遞歸求出子節(jié)點(diǎn)的深度
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        # 如果節(jié)點(diǎn)為空
        if left == 0 or right == 0:
            return left + right + 1
        # 不為空情況下計(jì)算左右子樹(shù)的最小深度
        return min(left, right) + 1

Path Sum

題目:Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

例子：

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

題意分析:
題意還是很清楚的，給定一顆二叉樹(shù)，在給定一個(gè)和，判斷從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)之間的路徑和是否有等于給定的sum。

思路分析

對(duì)于空樹(shù)，也就是只有根節(jié)點(diǎn)并且根節(jié)點(diǎn)為空，或者樹(shù)中只有根節(jié)點(diǎn)，這兩種情況都需要單獨(dú)討論。

對(duì)于空樹(shù)，我們可以直接返回False不等于即可。

對(duì)于只有根節(jié)點(diǎn)的樹(shù)，我們需要判斷一下，該節(jié)點(diǎn)的值是否等于sum，等于就返回True

對(duì)特殊情況討論完畢，我們就可以遞歸判斷左子樹(shù)和右子樹(shù)的情況了，傳入的sum需要用原來(lái)的sum-根節(jié)點(diǎn)的值。題目只要去判斷是否有，所有我們用或去連接即可

所以我們可以有以下解法

方法一

class Solution:
    def hasPathSum(self, root, sum):
        """
        判斷從根到葉子節(jié)點(diǎn)的值之和是否有等于sum的
        :param root: TreeNode
        :param sum: int
        :return: bool
        """
        # 如果是空樹(shù)
        if not root:
            return False
        # 如果只有根節(jié)點(diǎn)，并且根節(jié)點(diǎn)的值等于sum
        if root.val == sum and not root.left and not root.right:
            return True
        # 遞歸判斷對(duì)左右節(jié)點(diǎn)的情況，每次需要將sum減去節(jié)點(diǎn)的值
        return self.hasPathSum(root.left, sum - root.val) \
               or self.hasPathSum(root.right, sum - root.val)

Pascal's Triangle

題目:Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

例子：

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

題意分析:
給定一個(gè)行數(shù)，生成一個(gè)帕斯卡三角形。

思路分析

如果不看例子，我們估計(jì)不知道什么叫帕斯卡三角形，題目也給出了我們一個(gè)例子。我們需要從每一行中找出規(guī)律，才能得到結(jié)果。

很容易可以看出，每一行第i位上的數(shù)字，等于上一行的i位數(shù)加上i+1上的數(shù)。

同時(shí)我們可以看到，每一行第一個(gè)數(shù)都是1

我們?cè)谇蟪雒恳恍械牧斜碇螅湃氲奖４嫠行械牧斜碇屑纯伞?/p>

所以我們可以有以下解法

方法一

import copy


class Solution:
    def generate(self, numRows):
        # 最外側(cè)的列表
        allrows = []
        # 每一行的列表
        row = []
        # 循環(huán)迭代每一行
        for i in range(numRows):
            # 像每行的第一個(gè)元素插入1
            row.insert(0, 1)
            # 對(duì)該行進(jìn)行迭代(1開(kāi)始因?yàn)橐呀?jīng)插入了1，該行的長(zhǎng)度-1因?yàn)楸Ａ袅松弦恍械膮?shù))
            for j in range(1, len(row) - 1):
                # 其中的參數(shù)等于索引為j和j+1位置的和
                row[j] = row[j] + row[j + 1]
            # 進(jìn)行深拷貝，如果不進(jìn)行深拷貝，Python會(huì)一直操作的是一個(gè)row最后只會(huì)append一個(gè)相同的row
            allrows.append(copy.deepcopy(row))
        return allrows

這段代碼中涉及都了一個(gè)深拷貝的問(wèn)題，因?yàn)槲颐恳恍械牧斜韗ow，一直是一個(gè)，當(dāng)每次循環(huán)操作的是同一個(gè)row，如果不使用深拷貝，最后append到列表中的都是最后一行的值，所以這里使用深拷貝，將每一行的值拷貝出來(lái)append到列表中。

Pascal's Triangle II

題目:Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

例子：

For example, given k = 3,
Return [1,3,3,1].

題意分析:
給定一個(gè)行數(shù)，生成帕斯卡三角形該行的數(shù)。

思路分析

這一題其實(shí)只是上一題的一部分，生成第n行的列表即可。

首先，每一行的第一個(gè)數(shù)都是1，我們就可以創(chuàng)建一個(gè)第一個(gè)元素為1的列表。然后就可以循環(huán)行數(shù)，這里可以使用列表推導(dǎo)式。

可以在該行的列表前面加上[0]，再在該行的列表后面加上[0]，然后使用zip()函數(shù)，將生成的兩個(gè)新列表合并起來(lái)，用x和y分別取第一列的兩個(gè)值，并求出x+y的和作為列表的第一個(gè)元素，將第二列也分別作為x和y進(jìn)行同樣的操作。最后得到的就是帕斯卡三角形該行的數(shù)。

所以我們可以有以下解法

方法一

class Solution:
    def getRow(self, rowIndex):
        """
        計(jì)算帕斯卡三角形的制定行數(shù)的元素
        :param rowIndex: int
        :return: list
        """
        row = [1]
        for i in range(rowIndex):
            # 使用列表推導(dǎo)式迭代x+y的值
            # 其中x和y分別等于[0] + row和row + [0]的第一列和第二列
            row = [x + y for x, y in zip([0] + row, row + [0])]
        return row

Valid Palindrome

題目:Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

例子：

"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:

• Have you consider that the string might be empty? This is a good question to ask during an interview.
• For the purpose of this problem, we define empty string as valid palindrome.

題意分析:
判斷一個(gè)字符串是否是回文，只考慮字母和數(shù)字，不考慮其他字符。

思路分析

又是一個(gè)求回文的題目，有點(diǎn)不同的就是，在字符串中添加了一些我們需要忽略的字符，最容易想到的方法就是將這些字符去掉，我們?nèi)ヅ袛嘈碌淖址欠袷腔匚?，但是這樣無(wú)疑增加了時(shí)間和空間復(fù)雜度。

為了解決那個(gè)問(wèn)題，我們得在一次循環(huán)中解決，并且不能創(chuàng)建新的字符串，所以，我們只能忽略它。

我們可以先定義兩個(gè)下標(biāo)，一個(gè)表示表示開(kāi)始下標(biāo)，一個(gè)表示結(jié)束下標(biāo)，因?yàn)榍蠡匚?，只需要循環(huán)一半，并且開(kāi)始下標(biāo)小于結(jié)束下標(biāo)，

因?yàn)槲覀儾恢姥h(huán)的次數(shù)，所以我們使用while循環(huán)，在這個(gè)循環(huán)內(nèi)部我們需要找到符合屬于字母和數(shù)字的字符最開(kāi)始的下標(biāo)是多少，如果第一個(gè)字符不屬于字母或數(shù)字，那么將開(kāi)始下標(biāo)+1，依次類推，直到找到第一個(gè)屬于字母或數(shù)字的字符下標(biāo)，結(jié)束下標(biāo)也一樣，只不過(guò)當(dāng)不符合要求時(shí)是將下標(biāo)-1.

得到有效的開(kāi)始下標(biāo)和結(jié)束下標(biāo)，我們就可以進(jìn)行比較了，因?yàn)檫@里還忽略大小寫(xiě)，去比較兩個(gè)字符是否相等就可以了，如果不相等，直接返回False

所以我們可以有以下解法

方法一

class Solution:
    def isPalindrome(self, s):
        """
        判斷字符串是否是回文(只考慮字母和數(shù)字)
        :param s: str
        :return: bool
        """
        # 分別得到第一個(gè)和最后一個(gè)字符的索引
        i, r = 0, len(s) - 1
        # 判斷回文只需要判斷一半
        while i < r:
            # 當(dāng)左邊字符索引小魚(yú)右邊字符串并且
            # 左字符串屬于字母和數(shù)字時(shí)
            while i < r and not s[i].isalnum():
                i += 1
            # 當(dāng)左邊字符索引小魚(yú)右邊字符串并且
            # 右字符串屬于字母和數(shù)字時(shí)
            while i < r and not s[r].isalnum():
                r -= 1
            # 為了判斷相等，均轉(zhuǎn)換為小寫(xiě)去判斷是否相等
            if s[i].lower() != s[r].lower():
                return False
            # 左字符向后移動(dòng)一個(gè)
            i += 1
            # 右字符向前移動(dòng)
            r -= 1
        return True

Single Number

題目:Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

• Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

題意分析:
給定一個(gè)列表，其中除了一個(gè)元素，其他元素都有兩個(gè)，找出這個(gè)只有一個(gè)的元素(不使用額外的空間)

思路分析

想找出唯一的元素，最開(kāi)始很容易想到的是循環(huán)每一個(gè)元素，然后判斷該元素是否在剩下的列中中還存在，這種方式可以解決其他元素不只出現(xiàn)兩次的情況，

但是這題比較特殊，除本身外，其他元素出現(xiàn)的次數(shù)是一致的，并且元素還都是int類型。所以就可以用一種比較投機(jī)取巧的辦法。

我們可以先將該列表去重，這樣所有元素就只出現(xiàn)了一次，然后我們將其求和并乘以2，這樣我們就得到了兩倍的和，然后我們?cè)谇笠粋€(gè)元列表的和，這兩者的差就是只出現(xiàn)了一次的元素

所以我們可以有以下解法

方法一

class Solution:
    def singleNumber(self, nums):
        """
        找到數(shù)組只只出現(xiàn)了一次的元素(其他元素都出現(xiàn)了兩次)
        :param nums: list[int]
        :return: int
        """
        # 使用set()去重把每個(gè)元素都得到一個(gè)
        # 求出所有單個(gè)元素的和,求出兩倍的值
        # 再減去未去重時(shí)所有元素的和
        return 2 * sum(set(nums)) - sum(nums)

Linked List Cycle

題目:Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Note:

• Can you solve it without using extra space?

題意分析:
判斷單鏈表中是否有環(huán)。不使用額外空間

思路分析

判斷列表是否有環(huán)，一個(gè)鏈表如果有環(huán)，那么至少是三個(gè)節(jié)點(diǎn)組成，第三個(gè)指向第一個(gè)。所以我們這里可以使用快慢指針的概念，慢指針一次移動(dòng)一個(gè)節(jié)點(diǎn)，快指針一次移動(dòng)兩個(gè)節(jié)點(diǎn)，在快指針存在并且快指針的下一個(gè)節(jié)點(diǎn)不為空的時(shí)候循環(huán)，判斷快指針的節(jié)點(diǎn)是否等于慢指針的節(jié)點(diǎn)。

當(dāng)單鏈表為空，或者只有頭節(jié)點(diǎn)時(shí)需要單獨(dú)處理。

所以我們可以有以下解法

方法一

class Solution:
    def hasCycle(self, head):
        """
        判斷單鏈表中是否有環(huán)(不使用額外的空間)
        :param head: ListNode
        :return: bool
        """
        # 如果鏈表的頭節(jié)點(diǎn)或者頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空
        if not head or not head.next:
            return False
        # 使用快慢指針
        # 慢指針一次向前移動(dòng)一個(gè)節(jié)點(diǎn)
        slow = head
        # 快指針一次向前移動(dòng)兩個(gè)節(jié)點(diǎn)
        fast = head.next
        # 如果快指針存在并且快指針的下一個(gè)節(jié)點(diǎn)也存在
        while fast and fast.next:
            # 使慢指針向后移動(dòng)一個(gè)節(jié)點(diǎn)
            slow = slow.next
            # 使快指針向后移動(dòng)兩個(gè)節(jié)點(diǎn)
            fast = fast.next.next
            # 如果快指針等于慢指針，即有環(huán)
            if slow == fast:
                return True
        return False

Min Stack

題目:Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

例子:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

題意分析:
設(shè)計(jì)一個(gè)棧，支持一些基本操作

思路分析

使用列表去模擬棧即可。

所以我們可以有以下解法

方法一

class MinStack:
    def __init__(self):
        self.q = []

    def push(self, x):
        """
        向棧種推入一個(gè)元素
        :param x: int
        :return: void
        """
        curMin = self.getMin()
        if curMin is None or x < curMin:
            curMin = x
        self.q.append((x, curMin))

    def pop(self):
        """
        彈出一個(gè)元素
        :return: void
        """
        self.q.pop()

    def top(self):
        """
        得到棧頂元素
        :return: int
        """
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][0]

    def getMin(self):
        """
        得到最小棧中最小的元素
        :return: int
        """
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][1]

注：

• 以上代碼見(jiàn)github:https://github.com/EarthChen/LeetCode_Record
• 上述環(huán)境在ubuntu16.04 lts和python3.5中測(cè)試成功
• 上述文字皆為個(gè)人看法，如有錯(cuò)誤或建議請(qǐng)及時(shí)聯(lián)系我