LeetCode 81. Search in Rotated Sorted Array II

Description

Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,0,1,2,2,5,6]` might become `[2,5,6,0,0,1,2]`).

You are given a target value to search. If found in the array return `true`, otherwise return `false`.

Example 1:

``````Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
``````

Example 2:

``````Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
``````

Follow up:

• This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

LeetCode 74. Search a 2D Matrix

Description

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

``````Input:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

target = 3
Output: true

target = 13
Output: false
``````

LeetCode 69. Sqrt(x)

Description

Sqrt(x)

Implement `int sqrt(int x)`.

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

``````Input: 4
Output: 2
``````

Example 2:

``````Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
``````

LeetCode 50. Pow(x, n)

Description

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

``````Input: 2.00000, 10
Output: 1024.00000
``````

Example 2:

``````Input: 2.10000, 3
Output: 9.26100
``````

Example 3:

``````Input: 2.00000, -2
Output: 0.25000
Explanation: 2^{-2} = {1/2}^2 = 1/4 = 0.25
``````

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

`x``n`次方。

LeetCode 33. Search in Rotated Sorted Array

Search in Rotated Sorted Array

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`).

You are given a target value to search. If found in the array return its index, otherwise return `-1`.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of `O(log n)`.

LeetCode 29. Divide Two Integers

Divide Two Integers

Description

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

LeetCode 4. Median of Two Sorted Arrays

Median of Two Sorted Arrays

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

``````nums1 = [1, 3]
nums2 = [2]
``````

The median is 2.0 Example 2:

``````nums1 = [1, 2]
nums2 = [3, 4]
``````

The median is (2 + 3)/2 = 2.5

Programer

ChengDu·China