Dongxing's Wiki
  • LeetCode
  • LeetCode
anthony
2019-01-22
目录

Leetcode题解（3）- Easy

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 69- x的平方根

# 问题

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

# 思路

主要两种方法：牛顿迭代法，二分查找法。

具体可参见这里 (opens new window)

# 代码

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 70 - 爬楼梯

# 问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

# 思路

斐波那契数列，与之前剑指offer中的题目重合，参见这里 (opens new window)。

# 代码

记得要从小往大来计算，而不要从大往小来递归，不然会有很多重复计算，超时

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
1
2
3
4
5
6
7
8
9
10
11
12
13

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 101- 对称二叉树

# 问题

给定一个二叉树，检查它是否是镜像对称的。

# 思路

1）递归 如果一棵树的左右两个子树对称，这棵树就是对称的。据此可以写一个递归函数，判断两棵树是否对称（当根节点值相同，且每棵树的右子树都与另一棵树的左子树对称，这两棵树对称）。

2）迭代 【这个思路也是不错的，值得学习】 除了递归的方法外，我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像。最初，队列中包含的是 root 以及 root。该算法的工作原理类似于 BFS，但存在一些关键差异。每次提取两个结点并比较它们的值。然后，将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

# 代码

  1. 递归
# 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 104- 二叉树的最大深度

# 问题

给定一个二叉树，找出其最大深度。

# 思路

1）遍历 2）迭代。注意在节点入栈时，需要将其所处depth也一起放入，这样弹出时才可比较是否是最大深度。

# 代码

  1. 遍历
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
1
2
3
4
5
6
7
8
9
10
11
12

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 102- 二叉树的层次遍历 I （中等难度）

# 问题

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树:

    3
   / \
  9  20
    /  \
   15   7
1
2
3
4
5

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
1
2
3
4
5

# 思路

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

而一种非常巧妙的做法是，在每一层开始的时候，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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 107- 二叉树的层次遍历 II

跟102一样，只是要求结果反转一下，从底层向上层逐层遍历。按照102写法最后把列表反转一下就行。

# 108- 将有序数组转换为二叉搜索树

# 问题

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
1
2
3
4
5
6
7
8

# 思路

二叉搜索树的左子树节点值小于根，右子树节点值大于根，给定的又是一个排序数组，观察一下发现可以将数组从中间一分为二，分别作为左右子树，再继续二分下去，如此递归来做。

# 代码


# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
上次更新: 2020/09/19, 22:09:00
Leetcode题解（2）- Easy
Leetcode题解（4）- Easy

← Leetcode题解（4）- Easy→

Theme by Vdoing | Copyright © 2017-2023 anthony 京ICP备17072417-3