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]
]
題意分析:
給定一個二叉樹乌奇，返回自底向上遍歷結(jié)點的值
思路分析
相等于特殊的按層遍歷响蕴，在基本的按層遍歷樹可以選擇用棧或者隊列來保存每一層的結(jié)點蹲坷。在這里我們選擇使用棧。并且使用列表來模擬棧邑飒，在使用一個列表來保存需要返回的結(jié)果循签。
首先，初始化需要將根結(jié)點與level為0的元組存入列表中幸乒，循環(huán)這個棧懦底，不為空的話唇牧，在棧的尾部彈出一個元素罕扎，第一次也就是彈出的根結(jié)點和level層數(shù)。
得到彈出的結(jié)點丐重，判斷其是否為空腔召，如果不為空，判斷此時結(jié)果列表的長度扮惦，也就是已經(jīng)遍歷過的層數(shù)臀蛛，
如果小于當前層數(shù)+1，也就是在結(jié)果列表的第一個位置插入一個列表崖蜜。如果大于當前l(fā)evel+1浊仆，我們就可以在結(jié)果列表中放入合適的結(jié)點的值。然后只需要在棧中壓入當前結(jié)點的左子樹和當前層數(shù)level+1的元組豫领，和右子樹和當前層數(shù)level+1的元組抡柿。最后返回結(jié)果列表即可。
方法一
很容易想到我們可以遍歷兩次數(shù)組等恐，在內(nèi)循環(huán)中判斷兩次循環(huán)中的數(shù)相加是否等于target
class Solution:
def levelOrderBottom(self, root):
"""
返回節(jié)點值的自底向上的順序遍歷洲劣。（從左到右备蚓，從葉到根逐級地）
:param root: TreeNode
:return: list[list[int]]
"""
stack = [(root, 0)]
res = []
# 如果棧不為空
while stack:
# 將棧中最后一個元素彈出
node, level = stack.pop()
# 如果該結(jié)點存在
if node:
# 如果結(jié)果列表的長度小于層數(shù)+1
if len(res) < level + 1:
res.insert(0, [])
# 將當前結(jié)點的值添加在結(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]
]
題意分析:
給定一個二叉樹郊尝，返回自底向上遍歷結(jié)點的值
思路分析
相等于特殊的按層遍歷，在基本的按層遍歷樹可以選擇用椪骄或者隊列來保存每一層的結(jié)點流昏。在這里我們選擇使用棧。并且使用列表來模擬棧样傍，在使用一個列表來保存需要返回的結(jié)果横缔。
首先，初始化需要將根結(jié)點與level為0的元組存入列表中衫哥，循環(huán)這個棧茎刚，不為空的話，在棧的尾部彈出一個元素撤逢，第一次也就是彈出的根結(jié)點和level層數(shù)膛锭。
得到彈出的結(jié)點，判斷其是否為空蚊荣，如果不為空初狰，判斷此時結(jié)果列表的長度，也就是已經(jīng)遍歷過的層數(shù)互例，
如果小于當前層數(shù)+1奢入，也就是在結(jié)果列表的第一個位置插入一個列表。如果大于當前l(fā)evel+1媳叨，我們就可以在結(jié)果列表中放入合適的結(jié)點的值腥光。然后只需要在棧中壓入當前結(jié)點的左子樹和當前層數(shù)level+1的元組，和右子樹和當前層數(shù)level+1的元組糊秆。最后返回結(jié)果列表即可武福。
方法一
很容易想到我們可以遍歷兩次數(shù)組，在內(nèi)循環(huán)中判斷兩次循環(huán)中的數(shù)相加是否等于target
class Solution:
def levelOrderBottom(self, root):
"""
返回節(jié)點值的自底向上的順序遍歷痘番。（從左到右捉片，從葉到根逐級地）
:param root: TreeNode
:return: list[list[int]]
"""
stack = [(root, 0)]
res = []
# 如果棧不為空
while stack:
# 將棧中最后一個元素彈出
node, level = stack.pop()
# 如果該結(jié)點存在
if node:
# 如果結(jié)果列表的長度小于層數(shù)+1
if len(res) < level + 1:
res.insert(0, [])
# 將當前結(jié)點的值添加在結(jié)果列表中
res[-(level + 1)].append(node.val)
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return res
使用隊列的話，方式其實也是大同小異汞舱，這里就不在闡述伍纫。
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.
題意分析:
給定一個數(shù)組，元素按升序排序昂芜，將其轉(zhuǎn)換為高度平衡的BST莹规。
思路分析
想要轉(zhuǎn)換成平衡二叉樹，首先我們需要知道什么叫做平衡二叉樹说铃，知道了bst是深才能開始思考與討論访惜。
平衡二叉樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法）嘹履，且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹
平衡二叉樹主要的特點就是“棵空樹或它的左右兩個子樹的高度差的絕對值不超過1债热，并且左右兩個子樹都是一棵平衡二叉樹”,知道了這個砾嫉，題目又要求我們把一個已經(jīng)排序的數(shù)組(列表)作為整個二叉樹的值。
所以我們可以找出數(shù)組中的中值窒篱，把他作為根焕刮，把小于中值的作為左子樹，大于中值的作為右子樹墙杯，在利用遞歸的思想配并，從左子樹中找到左子樹的根，在右子樹中找到右子樹的根高镐，就可以得到我們所需要的平衡二叉樹溉旋。
所以我們可以有以下解法
方法一
很容易想到我們可以遍歷兩次數(shù)組，在內(nèi)循環(huán)中判斷兩次循環(huán)中的數(shù)相加是否等于target
class Solution:
def sortedArrayToBST(self, num):
"""
將已排序的數(shù)組轉(zhuǎn)換為高度平衡二叉樹
:param num: list[int]
:return: TreeNode
"""
# 如果列表為空
if not num:
return None
# 列表中間的值為列表長度整數(shù)2
mid = len(num) // 2
# 生成一個以中值為結(jié)點的值的作為根結(jié)點
root = TreeNode(num[mid])
# 遞歸求出
# 左子樹為小于中間值一部分
root.left = self.sortedArrayToBST(num[:mid])
# 右子樹為大于中間值的一部分
root.right = self.sortedArrayToBST(num[mid + 1:])
return root
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.
題意分析:
給定一個二叉樹嫉髓，判斷其是否是平衡二叉樹
思路分析
在上一題的分析中观腊，我們已經(jīng)知道了什么叫做平衡二叉樹。題目給出的方法返回值的bool類型算行，不利于我們?nèi)パh(huán)遞歸的判斷它梧油。我們可以單獨寫一個check函數(shù)，其返回值是int類型州邢。當函數(shù)返回-1時儡陨，該二叉樹為非平衡二叉樹，當函數(shù)返回值不為-1時量淌，該二叉樹為平衡二叉樹骗村。
所以我們可以有以下解法
方法一
class Solution:
def isBalanced(self, root):
"""
判斷一個樹是否為平衡二叉樹
當check函數(shù)的發(fā)揮值不等于-1時返回true，等于-1是返回false
:param root: TreeNode
:return: bool
"""
return self.check(root) != -1
def check(self, root):
"""
檢查結(jié)點
:param root: TreeNode
:return: int
"""
# 結(jié)點為空時
if root is None:
return 0
# 遞歸得出左子樹的返回值
left = self.check(root.left)
# 遞歸得出右子樹的返回值
right = self.check(root.right)
# 如果左子樹不為平衡樹或者右子樹不為平衡二叉樹类少，
# 左右子樹想減的值大于1(-1-(-1))左右子樹不為平衡樹的情況
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.
題意分析:
求出二叉樹的最小深度
思路分析
如果該樹為空叙身，需要單獨討論渔扎，返回深度為0.遞歸調(diào)用自己硫狞，傳入根節(jié)點的左子樹和右子樹，如果其中有空節(jié)點晃痴，那么此時的left或者right就有值為0残吩，既然求的是最小的深度，那么就可以返回該子樹的深度倘核。如果兩個值均不為0了泣侮，那么就返回左子樹和右子樹深度的最小值，最后加上子樹到根節(jié)點的1紧唱，即為最小深度活尊。
所以我們可以有以下解法
方法一
class Solution:
def minDepth(self, root):
# 如果是空樹
if not root:
return 0
# 遞歸求出子節(jié)點的深度
left = self.minDepth(root.left)
right = self.minDepth(root.right)
# 如果節(jié)點為空
if left == 0 or right == 0:
return left + right + 1
# 不為空情況下計算左右子樹的最小深度
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.
題意分析:
題意還是很清楚的隶校，給定一顆二叉樹，在給定一個和蛹锰，判斷從根節(jié)點到葉子節(jié)點之間的路徑和是否有等于給定的sum深胳。
思路分析
對于空樹，也就是只有根節(jié)點并且根節(jié)點為空铜犬，或者樹中只有根節(jié)點舞终，這兩種情況都需要單獨討論。
對于空樹癣猾，我們可以直接返回False不等于即可敛劝。
對于只有根節(jié)點的樹，我們需要判斷一下纷宇，該節(jié)點的值是否等于sum夸盟，等于就返回True
對特殊情況討論完畢，我們就可以遞歸判斷左子樹和右子樹的情況了像捶，傳入的sum需要用原來的sum-根節(jié)點的值满俗。題目只要去判斷是否有，所有我們用或去連接即可
所以我們可以有以下解法
方法一
class Solution:
def hasPathSum(self, root, sum):
"""
判斷從根到葉子節(jié)點的值之和是否有等于sum的
:param root: TreeNode
:param sum: int
:return: bool
"""
# 如果是空樹
if not root:
return False
# 如果只有根節(jié)點作岖，并且根節(jié)點的值等于sum
if root.val == sum and not root.left and not root.right:
return True
# 遞歸判斷對左右節(jié)點的情況唆垃，每次需要將sum減去節(jié)點的值
return self.hasPathSum(root.left, sum - root.val) \
or self.hasPathSum(root.right, sum - root.val)
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]
]
題意分析:
給定一個行數(shù)，生成一個帕斯卡三角形痘儡。
思路分析
如果不看例子辕万，我們估計不知道什么叫帕斯卡三角形，題目也給出了我們一個例子沉删。我們需要從每一行中找出規(guī)律渐尿，才能得到結(jié)果。
很容易可以看出矾瑰，每一行第i位上的數(shù)字砖茸，等于上一行的i位數(shù)加上i+1上的數(shù)。
同時我們可以看到殴穴，每一行第一個數(shù)都是1
我們在求出每一行的列表之后凉夯，放入到保存所有行的列表中即可。
所以我們可以有以下解法
方法一
import copy
class Solution:
def generate(self, numRows):
# 最外側(cè)的列表
allrows = []
# 每一行的列表
row = []
# 循環(huán)迭代每一行
for i in range(numRows):
# 像每行的第一個元素插入1
row.insert(0, 1)
# 對該行進行迭代(1開始因為已經(jīng)插入了1采幌，該行的長度-1因為保留了上一行的參數(shù))
for j in range(1, len(row) - 1):
# 其中的參數(shù)等于索引為j和j+1位置的和
row[j] = row[j] + row[j + 1]
# 進行深拷貝劲够，如果不進行深拷貝，Python會一直操作的是一個row最后只會append一個相同的row
allrows.append(copy.deepcopy(row))
return allrows
這段代碼中涉及都了一個深拷貝的問題休傍，因為我每一行的列表row征绎，一直是一個，當每次循環(huán)操作的是同一個row磨取，如果不使用深拷貝人柿，最后append到列表中的都是最后一行的值柴墩，所以這里使用深拷貝，將每一行的值拷貝出來append到列表中凫岖。
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].
題意分析:
給定一個行數(shù)拐邪，生成帕斯卡三角形該行的數(shù)。
思路分析
這一題其實只是上一題的一部分隘截，生成第n行的列表即可扎阶。
首先，每一行的第一個數(shù)都是1婶芭，我們就可以創(chuàng)建一個第一個元素為1的列表东臀。然后就可以循環(huán)行數(shù)，這里可以使用列表推導式犀农。
可以在該行的列表前面加上[0]惰赋，再在該行的列表后面加上[0]，然后使用zip()函數(shù)呵哨，將生成的兩個新列表合并起來赁濒，用x和y分別取第一列的兩個值，并求出x+y的和作為列表的第一個元素孟害，將第二列也分別作為x和y進行同樣的操作拒炎。最后得到的就是帕斯卡三角形該行的數(shù)。
所以我們可以有以下解法
方法一
class Solution:
def getRow(self, rowIndex):
"""
計算帕斯卡三角形的制定行數(shù)的元素
:param rowIndex: int
:return: list
"""
row = [1]
for i in range(rowIndex):
# 使用列表推導式迭代x+y的值
# 其中x和y分別等于[0] + row和row + [0]的第一列和第二列
row = [x + y for x, y in zip([0] + row, row + [0])]
return row
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.
題意分析:
判斷一個字符串是否是回文挨务，只考慮字母和數(shù)字击你，不考慮其他字符。
思路分析
又是一個求回文的題目谎柄，有點不同的就是丁侄，在字符串中添加了一些我們需要忽略的字符，最容易想到的方法就是將這些字符去掉朝巫，我們?nèi)ヅ袛嘈碌淖址欠袷腔匚暮枰。沁@樣無疑增加了時間和空間復雜度。
為了解決那個問題劈猿，我們得在一次循環(huán)中解決拙吉，并且不能創(chuàng)建新的字符串，所以糙臼，我們只能忽略它庐镐。
我們可以先定義兩個下標恩商，一個表示表示開始下標变逃，一個表示結(jié)束下標，因為求回文怠堪，只需要循環(huán)一半揽乱，并且開始下標小于結(jié)束下標名眉，
因為我們不知道循環(huán)的次數(shù)，所以我們使用while循環(huán)凰棉，在這個循環(huán)內(nèi)部我們需要找到符合屬于字母和數(shù)字的字符最開始的下標是多少损拢，如果第一個字符不屬于字母或數(shù)字，那么將開始下標+1撒犀，依次類推福压，直到找到第一個屬于字母或數(shù)字的字符下標，結(jié)束下標也一樣或舞，只不過當不符合要求時是將下標-1.
得到有效的開始下標和結(jié)束下標荆姆，我們就可以進行比較了，因為這里還忽略大小寫映凳，去比較兩個字符是否相等就可以了胆筒，如果不相等，直接返回False
所以我們可以有以下解法
方法一
class Solution:
def isPalindrome(self, s):
"""
判斷字符串是否是回文(只考慮字母和數(shù)字)
:param s: str
:return: bool
"""
# 分別得到第一個和最后一個字符的索引
i, r = 0, len(s) - 1
# 判斷回文只需要判斷一半
while i < r:
# 當左邊字符索引小魚右邊字符串并且
# 左字符串屬于字母和數(shù)字時
while i < r and not s[i].isalnum():
i += 1
# 當左邊字符索引小魚右邊字符串并且
# 右字符串屬于字母和數(shù)字時
while i < r and not s[r].isalnum():
r -= 1
# 為了判斷相等诈豌，均轉(zhuǎn)換為小寫去判斷是否相等
if s[i].lower() != s[r].lower():
return False
# 左字符向后移動一個
i += 1
# 右字符向前移動
r -= 1
return True
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?
題意分析:
給定一個列表仆救，其中除了一個元素，其他元素都有兩個矫渔，找出這個只有一個的元素(不使用額外的空間)
思路分析
想找出唯一的元素彤蔽，最開始很容易想到的是循環(huán)每一個元素，然后判斷該元素是否在剩下的列中中還存在庙洼，這種方式可以解決其他元素不只出現(xiàn)兩次的情況铆惑，
但是這題比較特殊，除本身外送膳，其他元素出現(xiàn)的次數(shù)是一致的员魏，并且元素還都是int類型。所以就可以用一種比較投機取巧的辦法叠聋。
我們可以先將該列表去重撕阎，這樣所有元素就只出現(xiàn)了一次，然后我們將其求和并乘以2碌补，這樣我們就得到了兩倍的和虏束，然后我們在求一個元列表的和，這兩者的差就是只出現(xiàn)了一次的元素
所以我們可以有以下解法
方法一
class Solution:
def singleNumber(self, nums):
"""
找到數(shù)組只只出現(xiàn)了一次的元素(其他元素都出現(xiàn)了兩次)
:param nums: list[int]
:return: int
"""
# 使用set()去重把每個元素都得到一個
# 求出所有單個元素的和,求出兩倍的值
# 再減去未去重時所有元素的和
return 2 * sum(set(nums)) - sum(nums)
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)镇匀，一個鏈表如果有環(huán)，那么至少是三個節(jié)點組成袜啃，第三個指向第一個汗侵。所以我們這里可以使用快慢指針的概念，慢指針一次移動一個節(jié)點，快指針一次移動兩個節(jié)點晰韵，在快指針存在并且快指針的下一個節(jié)點不為空的時候循環(huán)发乔，判斷快指針的節(jié)點是否等于慢指針的節(jié)點。
當單鏈表為空雪猪，或者只有頭節(jié)點時需要單獨處理栏尚。
所以我們可以有以下解法
方法一
class Solution:
def hasCycle(self, head):
"""
判斷單鏈表中是否有環(huán)(不使用額外的空間)
:param head: ListNode
:return: bool
"""
# 如果鏈表的頭節(jié)點或者頭節(jié)點的下一個節(jié)點為空
if not head or not head.next:
return False
# 使用快慢指針
# 慢指針一次向前移動一個節(jié)點
slow = head
# 快指針一次向前移動兩個節(jié)點
fast = head.next
# 如果快指針存在并且快指針的下一個節(jié)點也存在
while fast and fast.next:
# 使慢指針向后移動一個節(jié)點
slow = slow.next
# 使快指針向后移動兩個節(jié)點
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.
題意分析:
設計一個棧只恨，支持一些基本操作
思路分析
使用列表去模擬棧即可译仗。
所以我們可以有以下解法
方法一
class MinStack:
def __init__(self):
self.q = []
def push(self, x):
"""
向棧種推入一個元素
: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):
"""
彈出一個元素
: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]
注：
- 以上代碼見github:https://github.com/EarthChen/LeetCode_Record
- 上述環(huán)境在ubuntu16.04 lts和python3.5中測試成功
- 上述文字皆為個人看法，如有錯誤或建議請及時聯(lián)系我
