67- 二進(jìn)制求和
問(wèn)題
給定兩個(gè)二進(jìn)制字符串纲岭，返回他們的和（用二進(jìn)制表示）。
輸入為非空字符串且只包含數(shù)字 1 和 0窃蹋。
示例 1:
輸入: a = "11", b = "1"
輸出: "100"
示例 2:
輸入: a = "1010", b = "1011"
輸出: "10101"
思路
從右向左准潭，注意不等長(zhǎng)情況，注意進(jìn)位情況腔丧。另外要留心下標(biāo)放椰，不要搞混了。
答案
class Solution:
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
add = 0
result = ''
while a and b : # 公共部分
tmp = int(a[-1]) + int(b[-1]) + add
if tmp >= 2:
add = 1
tmp = tmp % 2
else:
add = 0
result = str(tmp) + result
a = a[:-1]
b = b[:-1]
remain = ''
ret = a if a else b
while ret:
tmp = int(ret[-1]) + add
if tmp >= 2:
add = 1
tmp = tmp % 2
else:
add = 0
result = str(tmp) + result
ret = ret[:-1]
if add:
result = str(add) + result
return result
69- x的平方根
問(wèn)題
實(shí)現(xiàn) int sqrt(int x) 函數(shù)愉粤。
計(jì)算并返回 x 的平方根砾医，其中 x 是非負(fù)整數(shù)。
由于返回類型是整數(shù)衣厘，結(jié)果只保留整數(shù)的部分如蚜，小數(shù)部分將被舍去。
示例
輸入: 8
輸出: 2
說(shuō)明: 8 的平方根是 2.82842..., 由于返回類型是整數(shù)影暴，小數(shù)部分將被舍去错邦。
思路
主要兩種方法：牛頓迭代法，二分查找法型宙。
具體可參見這里
代碼
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0 or x == 1:
return x
x0 = x
t = x
x0 = x0 / 2 + t / (2 * x0)
while abs(x0 * x0 - t) > 0.00001:
x0 = x0 / 2 + t / (2 * x0)
return int(x0)
70 - 爬樓梯
問(wèn)題
假設(shè)你正在爬樓梯兴猩。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階早歇。你有多少種不同的方法可以爬到樓頂呢倾芝？
注意：給定 n 是一個(gè)正整數(shù)。
思路
斐波那契數(shù)列箭跳，與之前劍指offer中的題目重合晨另，參見這里。
代碼
記得要從小往大來(lái)計(jì)算谱姓，而不要從大往小來(lái)遞歸借尿，不然會(huì)有很多重復(fù)計(jì)算，超時(shí)
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return n
f1 = 1
f2 = 2
for i in range(3, n+1):
f1, f2 = f2, f1 + f2
return f2
83- 刪除排序鏈表中的重復(fù)元素
問(wèn)題
給定一個(gè)排序鏈表屉来，刪除所有重復(fù)的元素路翻，使得每個(gè)元素只出現(xiàn)一次。
思路
略
## 代碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
pre = head
cur = head.next
while cur:
if cur.val != pre.val:
pre.next = cur
pre = cur
cur = cur.next
pre.next = cur
return head
88- 合并兩個(gè)有序數(shù)組
問(wèn)題
給定兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2茄靠，將 nums2 合并到 nums1 中茂契，使得 num1 成為一個(gè)有序數(shù)組。
說(shuō)明:
- 初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n慨绳。
- 你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來(lái)保存 nums2 中的元素掉冶。
思路
要注意題目的要求：在nums1本地改動(dòng)真竖，不返回新的數(shù)組。再加上已經(jīng)給出了兩個(gè)list的元素個(gè)數(shù)厌小，又是有序數(shù)組恢共，做有序數(shù)組的歸并，注意需要從后往前做璧亚，這樣可以無(wú)需挪動(dòng)讨韭，極大提高效率。
代碼
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
p = m + n - 1
m = m - 1
n = n - 1
while m >= 0 and n >= 0:
if nums1[m] >= nums2[n]:
nums1[p] = nums1[m]
m -= 1
else:
nums1[p] = nums2[n]
n -= 1
p -= 1
while n >= 0:
nums1[p] = nums2[n]
n -= 1
p -= 1
100- 相同的樹
問(wèn)題
給定兩個(gè)二叉樹癣蟋，編寫一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同拐袜。
如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值梢薪，則認(rèn)為它們是相同的蹬铺。
思路
遞歸遍歷吧
代碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p == None and q == None:
return True
elif not p or not q :
return False
if p.val != q.val:
return False
if self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right):
return True
return False
101- 對(duì)稱二叉樹
問(wèn)題
給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的秉撇。
思路
1）遞歸
如果一棵樹的左右兩個(gè)子樹對(duì)稱甜攀，這棵樹就是對(duì)稱的。據(jù)此可以寫一個(gè)遞歸函數(shù)琐馆，判斷兩棵樹是否對(duì)稱（當(dāng)根節(jié)點(diǎn)值相同规阀，且每棵樹的右子樹都與另一棵樹的左子樹對(duì)稱，這兩棵樹對(duì)稱）瘦麸。
2）迭代 【這個(gè)思路也是不錯(cuò)的谁撼，值得學(xué)習(xí)】
除了遞歸的方法外，我們也可以利用隊(duì)列進(jìn)行迭代滋饲。隊(duì)列中每?jī)蓚€(gè)連續(xù)的結(jié)點(diǎn)應(yīng)該是相等的厉碟，而且它們的子樹互為鏡像。最初屠缭，隊(duì)列中包含的是 root 以及 root箍鼓。該算法的工作原理類似于 BFS，但存在一些關(guān)鍵差異呵曹。每次提取兩個(gè)結(jié)點(diǎn)并比較它們的值款咖。然后，將兩個(gè)結(jié)點(diǎn)的左右子結(jié)點(diǎn)按相反的順序插入隊(duì)列中奄喂。當(dāng)隊(duì)列為空時(shí)铐殃，或者我們檢測(cè)到樹不對(duì)稱（即從隊(duì)列中取出兩個(gè)不相等的連續(xù)結(jié)點(diǎn)）時(shí)，該算法結(jié)束跨新。
代碼
- 遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return self.compare_two(root.left, root.right)
def compare_two(self, lr, rr):
if lr == None and rr == None:
return True
if lr == None or rr == None:
return False
return lr.val == rr.val and self.compare_two(lr.right, rr.left) and self.compare_two(lr.left, rr.right)
2） 迭代
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
q = [root, root]
while q:
left, right = q.pop(0), q.pop(0)
if not left and not right:
continue
if left == None or right == None:
return False
if left.val != right.val:
return False
q.append(left.left)
q.append(right.right)
q.append(left.right)
q.append(right.left)
return True
104- 二叉樹的最大深度
問(wèn)題
給定一個(gè)二叉樹贴谎，找出其最大深度誉察。
思路
1）遍歷
2）迭代焚挠。注意在節(jié)點(diǎn)入棧時(shí)，需要將其所處depth也一起放入词疼，這樣彈出時(shí)才可比較是否是最大深度俯树。
代碼
- 遍歷
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
2）迭代
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
stack = []
if root:
stack.append((1, root))
depth = 0
while stack:
current_depth, root = stack.pop()
if root:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return depth
102- 二叉樹的層次遍歷 I （中等難度）
問(wèn)題
給定一個(gè)二叉樹帘腹，返回其按層次遍歷的節(jié)點(diǎn)值。 （即逐層地许饿，從左到右訪問(wèn)所有節(jié)點(diǎn)）阳欲。
例如:
給定二叉樹:
3
/ \
9 20
/ \
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
思路
與之前遇到的層次遍歷不同的地方在于，這個(gè)題的返回結(jié)果要分層陋率。
而一種非常巧妙的做法是球化，在每一層開始的時(shí)候，q的長(zhǎng)度就是該層的節(jié)點(diǎn)數(shù)量瓦糟，(初始q中只有root筒愚，長(zhǎng)度為1，代表第1層只有root一個(gè)節(jié)點(diǎn)）所以無(wú)需記錄每個(gè)節(jié)點(diǎn)位于第幾層菩浙，像下面代碼寫的這樣就可以實(shí)現(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:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
q = [root, ]
result = []
while q:
level = []
size = len(q)
while size > 0:
node = q.pop(0)
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
size -= 1
result.append(level)
return result
107- 二叉樹的層次遍歷 II
跟102一樣陆淀，只是要求結(jié)果反轉(zhuǎn)一下，從底層向上層逐層遍歷先嬉。按照102寫法最后把列表反轉(zhuǎn)一下就行轧苫。
108- 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
問(wèn)題
將一個(gè)按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹疫蔓。
本題中含懊，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò) 1。
示例:
給定有序數(shù)組: [-10,-3,0,5,9],
一個(gè)可能的答案是：[0,-3,9,-10,null,5]衅胀，它可以表示下面這個(gè)高度平衡二叉搜索樹：
0
/ \
-3 9
/ /
-10 5
思路
二叉搜索樹的左子樹節(jié)點(diǎn)值小于根绢要，右子樹節(jié)點(diǎn)值大于根，給定的又是一個(gè)排序數(shù)組拗小，觀察一下發(fā)現(xiàn)可以將數(shù)組從中間一分為二重罪，分別作為左右子樹，再繼續(xù)二分下去哀九，如此遞歸來(lái)做剿配。
代碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
return self.build_tree(nums, 0, len(nums) - 1)
def build_tree(self, nums, l, r):
if l > r:
return None
if l == r:
return TreeNode(nums[l])
mid = (l + r) // 2
root = TreeNode(nums[mid])
root.left = self.build_tree(nums, l, mid - 1)
root.right = self.build_tree(nums, mid + 1, r)
return root
