Leetcode题Binary Search： 222/230/240/275/278/300,Python多种解法(十五)

前文

  继上篇math后，我们加快刷的速度，本期分享Binary Search的题，对于重复的题就直接跳过了！

222. Count Complete Tree Nodes

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    """
    题意是求完全二叉树的节点数，参考博文：https://www.cnblogs.com/yrbbest/p/4993469.html
    完全二叉树即是除了最后一行节点不满，其他都是满的，而且最后一行是从左至右依次满的；满二叉树则是子节点要么满要么不满，
    该解法就是利用二者特性来做的，先定义一个求树高度的函数(求高度往左子树找)，然后分别求得左子树和右子树的高度，如果二者相等，则左子树是
    满二叉树，右子树是完全二叉树；如果不等，则右子树是满二叉树，左子树是完全二叉树
    Runtime: 64 ms, faster than 98.26% of Python online submissions for Count Complete Tree Nodes.
    Memory Usage: 27.7 MB, less than 57.43% of Python online submissions for Count Complete Tree Nodes.
    """
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        count = 0
        while root:
            l ,r = map(self.getHeight ,(root.left ,root.right))
            if l== r:
                count += 2 ** l
                root = root.right
            else:
                count += 2 ** r
                root = root.left
        return count

    def getHeight(self, root):
        height = 0
        while root:
            height += 1
            root = root.left
        return height

230. Kth Smallest Element in a BST

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    """
    题意是求BST中第k小的树节点
    BST即binary search tree，树节点满足左子树小于该节点小于右子树，所以中序遍历后就可以得到有序列表
    中序遍历即：左子树→根节点→右子树，所以根据中序遍历写得递归代码如下
    Runtime: 52 ms, faster than 42.88% of Python online submissions for Kth Smallest Element in a BST.
    Memory Usage: 19.8 MB, less than 5.44% of Python online submissions for Kth Smallest Element in a BST.
    """
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.k = k
        self.res = None
        self.helper(root)
        return self.res

    def helper(self ,Node):
        if not Node:
            return
        self.helper(Node.left)
        self.k -= 1
        if self.k == 0:
            self.res = Node.val
            return self.res
        self.helper(Node.right)


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution2(object):
    """
    用非递归的方法来实现，利用到栈的数据结构
    先遍历到左子树树底，依次将左子树的所有节点压入栈，最后栈顶存放的就是最小的数，然后依次从栈推出，
    当k位于左子树的时候直接返回值即可，如果不在左子树，那就继续将右子树压入栈
    Runtime: 44 ms, faster than 77.44% of Python online submissions for Kth Smallest Element in a BST.
    Memory Usage: 19.6 MB, less than 63.94% of Python online submissions for Kth Smallest Element in a BST.
    """
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

240. Search a 2D Matrix II

class Solution(object):
    """
    题意是求从上到下、从左到右升序排序的矩阵里是否存在某个值
    该题也被分到了树的分类里，该解法利用到python的any，针对每一行，any匹配是否存在即可
    看到any的源码描述： Return True if bool(x) is True for any x in the iterable.
    也即是遍历每个数，用bool(x)查看是否存在
    Runtime: 156 ms, faster than 22.01% of Python online submissions for Search a 2D Matrix II.
    Memory Usage: 15.8 MB, less than 13.81% of Python online submissions for Search a 2D Matrix II.
    """
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        return any(target in row for row in matrix)


class Solution2(object):
    """
    该解法从最后一行开始遍历，如果最后一行第一个数小于该值，则往右推移一列，如果对应的数大于该值，则往上推移一列；
    这两个都是依赖于题目给的从上到下、从左到右的升序排序，所以当同一行的数小于该值，则他上一行的数也必然小于该值，
    所以可以继续往下遍历
    Runtime: 44 ms, faster than 92.26% of Python online submissions for Search a 2D Matrix II.
    Memory Usage: 15.8 MB, less than 24.21% of Python online submissions for Search a 2D Matrix II.
    """
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        y = m - 1
        x = 0
        while y >= 0 and x < n:
            if matrix[y][x] == target:
                return True
            elif matrix[y][x] < target:
                x += 1
            else:
                y -= 1
        return False

275. H-Index II

274解法位于：https://blog.csdn.net/weixin_42681866/article/details/90711421

class Solution(object):
    """
    参照274的解法，取最优的二分法即可
    Runtime: 132 ms, faster than 45.22% of Python online submissions for H-Index II.
    Memory Usage: 16.5 MB, less than 57.46% of Python online submissions for H-Index II.
    """
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        N = len(citations)
        l, r = 0, N - 1
        H = 0
        while l <= r:
            mid = l + (r - l) / 2
            H = max(H, min(citations[mid], N - mid))
            if citations[mid] < N - mid:
                l = mid + 1
            else:
                r = mid - 1
        return H

278. First Bad Version

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
def isBadVersion(version):
    pass

import bisect
class Solution(object):
    """
    用python 的库bisect来实现，指定0-n这样的list区间，然后对每个数进行isBadVersion(i)判断
    这里用到了__getitem__(self, i)的魔法方法，使得区间的每个数可以用索引访问，当为false时返回结果
    Runtime: 12 ms, faster than 93.14% of Python online submissions for First Bad Version.
    Memory Usage: 11.8 MB, less than 44.40% of Python online submissions for First Bad Version.
    """
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        class Wrap:
            def __getitem__(self, i):
                return isBadVersion(i)
        return bisect.bisect(Wrap(), False, 0, n)




class Solution2(object):
    """
    标准的二分法来解决，相当于是上面的解释版
    Runtime: 12 ms, faster than 93.14% of Python online submissions for First Bad Version.
    Memory Usage: 11.6 MB, less than 96.89% of Python online submissions for First Bad Version.
    """
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        start = 1
        end = n
        while start <= end:
            mid = (start + end) // 2
            if isBadVersion(mid):
                if not isBadVersion(mid -1):
                    return mid
                else:
                    end = mid
            else:
                if isBadVersion(mid + 1):
                    return mid + 1
                else:
                    start = mid + 1

300. Longest Increasing Subsequence

class Solution(object):
    """
    题意是求数组的最大递增子序列，参考博文：https://blog.csdn.net/fuxuemingzhu/article/details/79820919
    通过动态规划的思想来完成，假设要求F(n)的最大子序列，可以先求得F(n-1)的，以此类推，我们知道F(1)=1即第一个数的
    最大子序列必定是1，那接下来就比较第2个数和第一个数，如果小于第1，则第2个数最大子序列也为1；如大于，则为2。同样的第三个数
    就要比较第1和第2，如果大于，则对应的数上+1.若一直小于，则跳过！
    Runtime: 976 ms, faster than 40.42% of Python online submissions for Longest Increasing Subsequence.
    Memory Usage: 12.1 MB, less than 13.58% of Python online submissions for Longest Increasing Subsequence.
    """
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums :return 0
        dp = [0] * len(nums)
        dp[0] = 1
        for i in range(1 ,len(nums)):
            tmax = 1
            for j in range(0 ,i):
                if nums[i] > nums[j]:
                    tmax = max(tmax ,dp[j] +1)
            dp[i] = tmax
        return max(dp)

总结

  此次分享到此，感谢观看~