# leetcode 778. Swim in Rising Water

## 题目描述

On an N x N `grid`, each square `grid[i][j]` represents the elevation at that
point `(i,j)`.

Now rain starts to fall. At time `t`, the depth of the water everywhere is
`t`. You can swim from a square to another 4-directionally adjacent square if
and only if the elevation of both squares individually are at most `t`. You
can swim infinite distance in zero time. Of course, you must stay within the
boundaries of the grid during your swim.

You start at the top left square `(0, 0)`. What is the least time until you
can reach the bottom right square `(N-1, N-1)`?

Example 1:

``````Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.``````

Example 2:

``````Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
**0  1  2  3  4**
24 23 22 21  **5**
**12 13 14 15 16**
**11** 17 18 19 20
**10  9  8  7  6**

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.``````

Note:

1. `2 <= N <= 50`.
2. grid[i][j] is a permutation of [0, …, N*N - 1].

Tags: Binary Search, Heap, Depth-first Search, Union Find

Difficulty: Hard



# leetcode 153. Find Minimum in Rotated Sorted Array

## 题目描述

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]`).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

``````Input: [3,4,5,1,2]
Output: 1``````

Example 2:

``````Input: [4,5,6,7,0,1,2]
Output: 0``````

Tags: Array, Binary Search

Difficulty: Medium



# leetcode 154. Find Minimum in Rotated Sorted Array II

## 题目描述

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]`).

Find the minimum element.

The array may contain duplicates.

Example 1:

``````Input: [1,3,5]
Output: 1``````

Example 2:

``````Input: [2,2,2,0,1]
Output: 0``````

Note:

Tags: Array, Binary Search

Difficulty: Hard



# leetcode 718. Maximum Length of Repeated Subarray

## 题目描述

Given two integer arrays `A` and `B`, return the maximum length of an subarray
that appears in both arrays.

Example 1:

``````Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].``````

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

Tags: Array, Hash Table, Binary Search, Dynamic Programming

Difficulty: Medium



# leetcode 209. Minimum Size Subarray Sum

## 题目描述

Given an array of n positive integers and a positive integer s , find
the minimal length of a contiguous subarray of which the sum ≥ s. If
there isn’t one, return 0 instead.

*Example: *

``````Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.``````

If you have figured out the O ( n ) solution, try coding another solution
of which the time complexity is O ( n log n ).

Tags: Array, Two Pointers, Binary Search

Difficulty: Medium



# leetcode 278. First Bad Version

## 题目描述

You are a product manager and currently leading a team to develop a new
check. Since each version is developed based on the previous version, all the

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.

Example:

``````Given n = 5, and version = 4 is the first bad version.

Then 4 is the first bad version. ``````

Tags: Binary Search

Difficulty: Easy



# leetcode 50. Pow(x, n)

## 题目描述

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

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/22 = 1/4 = 0.25``````

Note:

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

Tags: Math, Binary Search

Difficulty: Medium

# leetcode 278. First Bad Version

## 题目描述

You are a product manager and currently leading a team to develop a new
check. Since each version is developed based on the previous version, all the

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.

Example:

``````Given n = 5, and version = 4 is the first bad version.

Then 4 is the first bad version. ``````

Tags: Binary Search

Difficulty: Easy

# leetcode 69. 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.``````

Tags: Math, Binary Search

Difficulty: Easy

# leetcode 240. Search a 2D Matrix II

## 题目描述

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 in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

``````[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]``````

Given target = `5`, return `true`.

Given target = `20`, return `false`.

Tags: Binary Search, Divide and Conquer

Difficulty: Medium

:D 一言句子获取中...