67- 二进制求和
问题
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
思路
从右向左，注意不等长情况，注意进位情况。另外要留心下标，不要搞混了。
答案
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的平方根
问题
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
思路
主要两种方法：牛顿迭代法，二分查找法。
具体可参见这里
代码
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 - 爬楼梯
问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路
斐波那契数列，与之前剑指offer中的题目重合，参见这里。
代码
记得要从小往大来计算，而不要从大往小来递归，不然会有很多重复计算，超时
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- 删除排序链表中的重复元素
问题
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
思路
略
## 代码
# 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- 合并两个有序数组
问题
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
思路
要注意题目的要求：在nums1本地改动，不返回新的数组。再加上已经给出了两个list的元素个数，又是有序数组，做有序数组的归并，注意需要从后往前做，这样可以无需挪动，极大提高效率。
代码
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- 相同的树
问题
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路
递归遍历吧
代码
# 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- 对称二叉树
问题
给定一个二叉树，检查它是否是镜像对称的。
思路
1）递归
如果一棵树的左右两个子树对称，这棵树就是对称的。据此可以写一个递归函数，判断两棵树是否对称（当根节点值相同，且每棵树的右子树都与另一棵树的左子树对称，这两棵树对称）。
2）迭代 【这个思路也是不错的，值得学习】
除了递归的方法外，我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像。最初，队列中包含的是 root 以及 root。该算法的工作原理类似于 BFS，但存在一些关键差异。每次提取两个结点并比较它们的值。然后，将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
代码
- 递归
# 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- 二叉树的最大深度
问题
给定一个二叉树，找出其最大深度。
思路
1）遍历
2）迭代。注意在节点入栈时，需要将其所处depth也一起放入，这样弹出时才可比较是否是最大深度。
代码
- 遍历
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 （中等难度）
问题
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树:
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
思路
与之前遇到的层次遍历不同的地方在于，这个题的返回结果要分层。
而一种非常巧妙的做法是，在每一层开始的时候，q的长度就是该层的节点数量，(初始q中只有root，长度为1，代表第1层只有root一个节点）所以无需记录每个节点位于第几层，像下面代码写的这样就可以实现分层返回了！妙啊！
代码
# 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一样，只是要求结果反转一下，从底层向上层逐层遍历。按照102写法最后把列表反转一下就行。
108- 将有序数组转换为二叉搜索树
问题
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
思路
二叉搜索树的左子树节点值小于根，右子树节点值大于根，给定的又是一个排序数组，观察一下发现可以将数组从中间一分为二，分别作为左右子树，再继续二分下去，如此递归来做。
代码
# 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
