leetcode-python-binary search

1、Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

解析：这题归类在binary search类别，那么顾名思义是想让我们用二分搜索的方法解决的，

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in xrange(len(numbers)): # xrange是数字生成器，生成0到len(numbers)-1的数
            l, r = i+1, len(numbers)-1 # 设置两个指针
            tmp = target - numbers[i] # tem是总和减去当前值的差
            while l <= r: # 
                mid = l + (r-l)//2 # //表示除法，返回整数 mid是中间指针
                if numbers[mid] == tmp: # 如果在两个指针的中间找到一个数等于tem，则成功
                    return [i+1, mid+1]
                elif numbers[mid] < tmp: # 否则，根据中间值和tem值大小，移动指针
                    l = mid+1
                else:
                    r = mid-1

2、Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

解析：这题其实和上面的题有很相像的地方，只不过原始数据是以存储为二叉树的结构，大致有两种解法：1、递归中序遍历这棵树，能得到一个从小到大排序的数组，然后再用第一步的方法进行求解；2、遍历这棵树，将其存在一个hash表中，方便之后直接可以从相应的位置直接查找；相比之下，由于都引入了外界存储，hash表的查找时间比数组的查找时间短，因此，这里推荐引入hash表这个存储结构

第二种解法：

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        if (not root):
            return False
        s = set() # 定义一个hash集，将遍历的值存在hash表中
        queue = [root]
        while (queue):
            node = queue.pop(0)
            s.add(node.val)
            if(node.left): # 遍历这棵树的左子树
                queue.append(node.left)
            if(node.right): # 遍历右子树
                queue.append(node.right)
        for num in s: # 遍历这个hash表
            if k - num in s and 2 * (k - num) != k: # 若差值k在hash表并且不是自己本身
                return True

        return False

3、Intersection of Two Arrays（两数组的交集）

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = []; dictionary = {}
        for num in nums1: # 将nums1数组中的数存到字典中，python的字典相当于hash表
            if not dictionary.has_key(num):
                 dictionary[num] = 1
        for num in nums2: # 遍历数组nums2的数
            if dictionary.has_key(num): # 
                res.append(num)
        return list(set(res));

4、Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

解析：这题和上一题的不一样之处在于，有多少个相同的数就输出多少个数

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dict1 = dict()
        for i in nums1: # 统计一下出现的频次
            if i not in dict1:
                dict1[i] = 1
            else:
                dict1[i] += 1
        ret = []
        for i in nums2:
            if i in dict1 and dict1[i]>0: 
                ret.append(i)
                dict1[i] -= 1

        return ret

5、First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

解析：题目这么长，主要意思就是查找到第一个质量有问题的版本，其实就是用二分查找法

6、 Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

题目大意：给定一棵树，按照层序遍历输出

7、107. Binary Tree Level Order Traversal II

题目原文

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example: 
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

• 1
• 2
• 3
• 4
• 5

return its bottom-up level order traversal as:

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

• 1
• 2
• 3
• 4
• 5

给定一个二叉树，返回其从下到上的层序遍历（从左到右，从下到上）。

这一题和第6题一样，只需要将每次层次遍历的结果插入到结果列表的最前面即可

8、Path Sum

求二叉树结点和为指定数值的路径

9、Invert Binary Tree

Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

二叉树翻转

10、Path Sum III

输出二叉树中子路径和为指定数值的路径