题目序号 475、374、350、349、278、167、35、658、454¶

475. Heaters¶

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

Numbers of houses and heaters you are given are non-negative and will not exceed 25000.

Positions of houses and heaters you are given are non-negative and will not exceed 10^9.

As long as a house is in the heaters’ warm radius range, it can be warmed.

All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

374. Guess Number Higher or Lower¶

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower: 1 : My number is higher 0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

350. 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.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

349. 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.

278. 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.

167. 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

35. Search Insert Position¶

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

# O(n) time
def searchInsert1(self, nums, target):
    i = 0
    while i < len(nums):
        while i < len(nums) and nums[i] < target:
            i += 1
        return i

# O(lgn) time
def searchInsert(self, nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        if l == r:
            if target <= nums[l]:
                return l
            else:
                return l+1
        mid = (l+r) >> 1
        if nums[mid] > target:
            r = mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            return mid


A shorter version and a recursive version just for reference:

# O(lgn) time
def searchInsert3(self, nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        mid = (l+r) >> 1
        if nums[mid] >= target:
            r = mid - 1
        elif nums[mid] < target:
            l = mid + 1
    return l

# O(lgn) time, recursively
def searchInsert(self, nums, target):
    return self.helper(nums, 0, len(nums)-1, target)

def helper(self, nums, l, r, target):
    if l == r:
        if nums[l] >= target:
            return l
        else:
            return l+1
    mid = l + (r-l)//2
    if nums[mid] > target:
        return self.helper(nums, l, mid, target)
    elif nums[mid] < target:
        return self.helper(nums, mid+1, r, target)
    else:
        return mid

658. Find K Closest Elements¶

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

The value k is positive and will always be smaller than the length of the sorted array.

Length of the given array is positive and will not exceed 104

Absolute value of elements in the array and x will not exceed 104

UPDATE (2017/9/19): The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

454. 4Sum II¶

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:

The two tuples are:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0