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]
]

思路

与之前遇到的层次遍历不同的地方在于，这个题的返回结果要分层。

而一种非常巧妙的做法是，在每一层开始的时候，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

Leetcode题解 - Easy - 3