Leetcode题解 - Easy - 3

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,但存在一些关键差异。每次提取两个结点并比较它们的值。然后,将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。

代码

  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)

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也一起放入,这样弹出时才可比较是否是最大深度。

代码

  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

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
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容