本文轉(zhuǎn)載自
作業(yè)部落的chanvee.
Same Tree
這個(gè)題的意思非常簡(jiǎn)單，給定兩顆二叉樹幌羞，判斷這兩顆二叉樹是否相同悠夯。樹相同包括兩點(diǎn)：一是結(jié)構(gòu)相同癌淮，而是值相同。因此我們只需要對(duì)兩棵樹同時(shí)遍歷)(簡(jiǎn)單的遞歸)一遍沦补，遇到不同（結(jié)構(gòu)不同或者值不同）時(shí)則返回False乳蓄；若遍歷一遍之后沒有發(fā)現(xiàn)不同則說明這兩棵樹相同。代碼如下：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param p, a tree node
# @param q, a tree node
# @return a boolean
def isSameTree(self, p, q):
if p == None and q == None:
return(True)
elif p == None or q == None:
return(False)
else:
if p.val != q.val:
return(False)
else:
if self.isSameTree(p.left, q.left):
return(self.isSameTree(p.right, q.right))
else:
return(False)
Symmetric Tree
這個(gè)題是判斷一棵樹是不是對(duì)稱樹夕膀。我們可以根據(jù)上一個(gè)題來解決這個(gè)問題虚倒，先給代碼：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a boolean
def isSymmetric(self, root):
if root == None:
return(True)
else:
return(self.isSameTree(root.left, root.right))
def isSameTree(self, p, q):
if p == None and q == None:
return(True)
elif p == None or q == None:
return(False)
else:
if p.val != q.val:
return(False)
else:
if self.isSameTree(p.left, q.right):
return(self.isSameTree(p.right, q.left))
else:
return(False)
有代碼可知，我們首先把這個(gè)樹分成左右兩顆子樹店诗，然后遍歷這兩顆子樹裹刮，比較時(shí)不再是左邊和左邊的比，因?yàn)閷?duì)稱庞瘸，所以比較左子樹的左節(jié)點(diǎn)和右子樹的右節(jié)點(diǎn)以及左子樹的右節(jié)點(diǎn)和右子樹的左節(jié)點(diǎn)是否相等即可捧弃。
Add Two Numbers
這個(gè)題目是實(shí)現(xiàn)鏈表的加法，剛開始理解錯(cuò)了擦囊，看到題目給的例子以為給的兩個(gè)列表長(zhǎng)度是相等的违霞，其實(shí)不是哈，不一定等長(zhǎng)瞬场。題目本身很簡(jiǎn)單买鸽，值得一提的是python中鏈表的操作，才開始我硬是沒搞清楚贯被，先貼代碼：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
add = 0
l3 = ListNode(0)
cur = l3
while l1 or l2:
node = ListNode(add)
if l1:
node.val += l1.val
l1 = l1.next
if l2:
node.val += l2.val
l2 = l2.next
if node.val >= 10:
add = 1
else:
add = 0
node.val %= 10
cur.next, cur = node, node
if add:
cur.next = ListNode(1)
return(l3.next)
代碼中cur = l3,表示cur和l3都指向了同一個(gè)鏈表眼五，在另一句cur.next, cur = node, node中，當(dāng)?shù)谝淮螆?zhí)行這句話時(shí)彤灶，首先cur.next指向了node看幼，也代表了l3.next也指向了node，然后cur再指向node幌陕，也就是指向了l3的next速那；當(dāng)再一次執(zhí)行時(shí)诗茎，首先cur.next指向node就相當(dāng)于l3.next.next指向node,以此類推济丘，從而cur就相當(dāng)于實(shí)現(xiàn)了C中的指針的作用了来惧。
Remove Duplicates from Sorted List
這個(gè)題目的意思是去除掉鏈表中所有重復(fù)的元素，即每個(gè)元素只保留一次心例，方法就是遍歷這個(gè)鏈表宵凌，每次將當(dāng)前節(jié)點(diǎn)的值跟下一個(gè)的節(jié)點(diǎn)的值相比，如果相同則將當(dāng)前節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)即可止后，需要注意的是如果下下個(gè)節(jié)點(diǎn)沒有的話摆寄，則當(dāng)前節(jié)點(diǎn)指向None。代碼如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
if head == None:
return(None)
else:
cur = ListNode(head.val)
cur.next, head = head, cur
while cur:
if cur.next and cur.val == cur.next.val:
if cur.next.next:
cur.next = cur.next.next
else:
cur.next = None
else:
cur = cur.next
return(head)
Remove Duplicates from Sorted List II
這個(gè)題是上一個(gè)題目的升級(jí)版，只要出現(xiàn)重復(fù)的數(shù)字微饥，這些數(shù)字都要從鏈表中刪掉逗扒，方法是在鏈表前先加一個(gè)節(jié)點(diǎn)以及一個(gè)刪除標(biāo)識(shí)，然后遍歷這個(gè)鏈表欠橘，比較后兩個(gè)節(jié)點(diǎn)是否相同矩肩，如果相同，先刪掉第一個(gè)節(jié)點(diǎn)肃续，并讓刪除標(biāo)識(shí)變?yōu)檎媸蜷荩砻飨乱淮尾僮餍枰训诙€(gè)節(jié)點(diǎn)刪掉（即使下一次比較的時(shí)候兩個(gè)節(jié)點(diǎn)值不同，但是上次只刪掉了一個(gè)重復(fù)節(jié)點(diǎn)始锚，所以還是要把它刪掉）刽酱，如果下兩個(gè)節(jié)點(diǎn)不同且刪除標(biāo)識(shí)不為真則跳過。代碼如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
if head == None or head.next == None:
return(head)
cur = ListNode(head.val)
cur.next, head = head, cur
flag = False
while cur:
if cur.next and cur.next.next and cur.next.val == cur.next.next.val:
cur.next = cur.next.next
flag = True
elif flag and cur.next:
cur.next = cur.next.next
flag = False
else:
cur = cur.next
return(head.next)
Remove Duplicates from Sorted Array
這個(gè)題與上面兩個(gè)題類似瞧捌，只是有鏈表變?yōu)榱酥羔樋美铮枰⒁獾氖请m然題目只要求返回?cái)?shù)組的長(zhǎng)度，但是它還有一個(gè)隱性的要求就是要使得數(shù)組A[0：len]是你想要的得到的不包含重復(fù)元素的數(shù)組姐呐，如他給的例子A=[1殿怜，1，2],remove 完之后要求A=[1,2,2]曙砂，也就是說A[0：2] = [1头谜，2]。我就在這里卡了好久鸠澈。柱告。。代碼如下：
class Solution:
# @param a list of integers
# @return an integer
def removeDuplicates(self, A):
if A == []:
return(0)
count = 1
for i in range(1,len(A)):
if A[i] != A[i-1]:
A[count] = A[i]
count += 1
return(count)
Remove Duplicates from Sorted Array II
這個(gè)題是上個(gè)題目的升級(jí)版笑陈，這是移除數(shù)組中重復(fù)元素大于2個(gè)的元素并返回新數(shù)組的長(zhǎng)度末荐，思想類似，這里就不在贅述新锈，直接貼代碼：
class Solution:
# @param A a list of integers
# @return an integer
def removeDuplicates(self, A):
if len(A) <= 2:
return(len(A))
count = 2
for i in range(2,len(A)):
if A[i] != A[count-1] or A[i] != A[count-2]:
A[count] = A[i]
count += 1
return(count)
Pascal's Triangle
精簡(jiǎn)版
題目的意思是生成n行的Pascal's三角并存入到列表中。思路是第i(i>=3)的第j個(gè)元素等于第i-1行的第j-1個(gè)元素和第j個(gè)元素之和眶熬，初識(shí)化第一二行之后for一下就可以了妹笆，另外由于Pascal's三角是對(duì)稱的，所以我們每次只需算前一半即可娜氏。代碼如下：
class Solution:
# @return a list of lists of integers
def generate(self, numRows):
if numRows == 1:
return([[1]])
elif numRows == 2:
return([[1],[1,1]])
elif numRows == 0:
return([])
else:
result = [[1],[1,1]]
for i in range(3, numRows+1):
tmp = [1]*i
last = result[i-2]
for j in range(1,(i-1)//2 + 1):
tmp[j] = tmp[i-1-j] = last[j-1] +last[j]
result.append(tmp)
return(result)
Pascal's Triangle II
這個(gè)題跟上一個(gè)題目類似拳缠，只是這次不是全部返回，而是只返回固定的某一行贸弥。由于Pascal's三角中的第i行第j個(gè)元素
_LeTeX(簡(jiǎn)書不支持): _ $$L(i,j)=C^{j-1}_i=\frac{i!}{(j-1)!(n-j+1)!}$$
所有我們就可以很簡(jiǎn)單得到任意一行的值了窟坐，只需再添加一個(gè)計(jì)算階乘的函數(shù)，代碼如下：
class Solution:
# @return a list of integers
def getRow(self, rowIndex):
result = [1]*(rowIndex + 1)
for i in range(1,(rowIndex)//2 + 1):
result[i] = result[rowIndex-i] = self.factorial(rowIndex)//(self.factorial(i)*self.factorial(rowIndex-i))
return(result)
def factorial(self, n):
if n == 1:
return(1)
else:
return(n*self.factorial(n-1))
Minimum Depth of Binary Tree
這個(gè)題目是計(jì)算一顆二叉樹的最小深度，分別計(jì)算左右子樹的深度哲鸳，然后取較小臣疑，深度的計(jì)算方法是如果節(jié)點(diǎn)是葉子節(jié)點(diǎn)深度加1，如果節(jié)點(diǎn)有子節(jié)點(diǎn)深度加1徙菠，初識(shí)化左右子樹深度為無窮大讯沈。代碼如下：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return an integer
def minDepth(self, root):
if root == None:
return(0)
if root.left == None and root.right == None:
return(1)
left = right = float("inf") # 表示無窮大
if root.left != None:
left = 1 + self.minDepth(root.left)
if root.right != None:
right = 1 + self.minDepth(root.right)
return(min(left, right))
Maximum Depth of Binary Tree
與上題類似，只不過是找樹的最大深度婿奔，改一下判別條件就可以了缺狠。代碼如下：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return an integer
def maxDepth(self, root):
if root == None:
return(0)
if root.left == None and root.right == None:
return(1)
left = right = -1
if root.left != None:
left = 1 + self.maxDepth(root.left)
if root.right != None:
right = 1 + self.maxDepth(root.right)
return(max(left, right))
Path Sum
這個(gè)題的意思是一顆二叉樹上是否存在一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，其上所有節(jié)點(diǎn)之和等于一個(gè)指定的數(shù)萍摊。方法就是當(dāng)我們從根節(jié)點(diǎn)往下遞歸時(shí)挤茄，看當(dāng)前節(jié)點(diǎn)是否存在sum減去前面節(jié)點(diǎn)之和的路徑存在。代碼如下：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a boolean
def hasPathSum(self, root, sum):
result = False
if root == None:
return(result)
else:
sum -= root.val
if sum == 0 and root.left == None and root.right == None:
result = True
return(result)
else:
if root.left:
result = result or self.hasPathSum(root.left, sum) # 只要存在一條就返回True
if root.right:
result = result or self.hasPathSum(root.right, sum)
return(result)
Length of Last Word
求一行字符串中最后一個(gè)單詞的長(zhǎng)度冰木，這個(gè)題用python做就非常簡(jiǎn)單了穷劈，代碼如下：
class Solution:
# @param s, a string
# @return an integer
def lengthOfLastWord(self, s):
if s == '':
return(0)
result = s.split()
if result == []:
return(0)
return(len(result[-1]))
Add Binary
這個(gè)題目非常簡(jiǎn)單，就是二進(jìn)制的加法片酝。對(duì)于我們這種python的初學(xué)者來說難點(diǎn)是字符串與列表的轉(zhuǎn)化囚衔，題目本身需要注意的一個(gè)地方就是，最后可能由于進(jìn)位需要補(bǔ)一位雕沿，我們可以先把字符串先倒一轉(zhuǎn)再加练湿，這樣就可以在末尾補(bǔ)位。代碼如下：
class Solution:
# @param a, a string
# @param b, a string
# @return a string
def addBinary(self, a, b):
a = a[::-1] # 字符串倒序
b = b[::-1] # 字符串倒序
i = j = 0
c = []
add = 0 # 表示進(jìn)位
while i < len(a) or j < len(b):
if i < len(a) and j < len(b):
tmp = (int(a[i]) + int(b[j]) + add) % 2
c.append(str(tmp))
if (int(a[i]) + int(b[j]) + add) >= 2:
add = 1
else:
add = 0
i += 1
j += 1
if i < len(a) and j>= len(b):
tmp = (int(a[i]) + add)%2
c.append(str(tmp))
if (int(a[i]) + add) >= 2:
add = 1
else:
add = 0
i += 1
if i >= len(a) and j < len(b):
tmp = (int(b[j]) + add)%2
c.append(str(tmp))
if (int(b[j]) + add) >= 2:
add = 1
else:
add = 0
j += 1
if add:
c.append('1')
c = c[::-1]
result = "".join(c)
return(result)
Valid Parentheses
這道題是判斷括號(hào)是否匹配审轮，就是利用棧來進(jìn)行解決肥哎，遇到正括號(hào)加入棧，遇到反括號(hào)彈出椉苍看是否匹配篡诽，只不過剛開始時(shí)可以直接排除一些結(jié)果:
- 如果字符串的長(zhǎng)度為奇數(shù), 必然False.
- 如果最后一個(gè)字符是
([{必然False. - 第一個(gè)字符為
)]}必然False等.
代碼如下：
class Solution:
# @return a boolean
def isValid(self, s):
if len(s)%2 != 0 or s[-1] == '(' or s[-1] =='[' or s[-1] =='{':
return(False)
result = True
a = []
for i in range(len(s)):
if s[i] =='(' or s[i] =='[' or s[i] =='{':
a.append(s[i])
else:
if len(a) == 0:
result = False
break
if s[i] == ')':
if a.pop() != '(':
result = False
break
if s[i] == ']':
if a.pop() != '[':
result = False
break
if s[i] == '}':
if a.pop() != '{':
result = False
break
return(result)
