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- 相同的樹

問題

給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。

如果兩個樹在結構上相同，并且節(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 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）遞歸
如果一棵樹的左右兩個子樹對稱，這棵樹就是對稱的。據此可以寫一個遞歸函數，判斷兩棵樹是否對稱（當根節(jié)點值相同，且每棵樹的右子樹都與另一棵樹的左子樹對稱，這兩棵樹對稱）。

2）迭代【這個思路也是不錯的，值得學習】
除了遞歸的方法外，我們也可以利用隊列進行迭代。隊列中每兩個連續(xù)的結點應該是相等的，而且它們的子樹互為鏡像。最初，隊列中包含的是 root 以及 root。該算法的工作原理類似于 BFS，但存在一些關鍵差異。每次提取兩個結點并比較它們的值。然后，將兩個結點的左右子結點按相反的順序插入隊列中。當隊列為空時，或者我們檢測到樹不對稱（即從隊列中取出兩個不相等的連續(xù)結點）時，該算法結束。

代碼

遞歸

# 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）迭代。注意在節(jié)點入棧時，需要將其所處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 （中等難度）

問題

給定一個二叉樹，返回其按層次遍歷的節(jié)點值。（即逐層地，從左到右訪問所有節(jié)點）。
例如:
給定二叉樹:

返回其層次遍歷結果：

[
  [3],
  [9,20],
  [15,7]
]

思路

與之前遇到的層次遍歷不同的地方在于，這個題的返回結果要分層。

而一種非常巧妙的做法是，在每一層開始的時候，q的長度就是該層的節(jié)點數量，(初始q中只有root，長度為1，代表第1層只有root一個節(jié)點）所以無需記錄每個節(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 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- 將有序數組轉換為二叉搜索樹

問題

將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1。

示例:

給定有序數組: [-10,-3,0,5,9],
一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：

      0
     / \
   -3   9
   /   /
 -10  5

思路

二叉搜索樹的左子樹節(jié)點值小于根，右子樹節(jié)點值大于根，給定的又是一個排序數組，觀察一下發(fā)現可以將數組從中間一分為二，分別作為左右子樹，再繼續(xù)二分下去，如此遞歸來做。

代碼


# 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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Leetcode題解 - Easy - 3