leetcode 778. Swim in Rising Water

leetcode
九章

题目描述

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 264. Ugly Number II

leetcode
九章

题目描述

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation:1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

  1. 1 is typically treated as an ugly number.
  2. n does not exceed 1690.

Tags: Math, Dynamic Programming, Heap

Difficulty: Medium

答案



leetcode 295. Find Median from Data Stream

leetcode
九章

题目描述

Median is the middle value in an ordered integer list. If the size of the list
is even, there is no middle value. So the median is the mean of the two middle
value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

  1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
  2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

Tags: Heap, Design

Difficulty: Hard

答案



leetcode 239. Sliding Window Maximum

难度:Hard

leetcode
九章

题目描述

Given an array nums , there is a sliding window of size k which is moving
from the very left of the array to the very right. You can only see the k
numbers in the window. Each time the sliding window moves right by one
position. Return the max sliding window.

Example:

Input: _nums_ = [1,3,-1,-3,5,3,6,7], and _k_ = 3
Output:[3,3,5,5,6,7] 
Explanation:
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       **3**
 1 [3  -1  -3] 5  3  6  7       **3**
 1  3 [-1  -3  5] 3  6  7      **5**
 1  3  -1 [-3  5  3] 6  7       **5**
 1  3  -1  -3 [5  3  6] 7       **6**
 1  3  -1  -3  5 [3  6  7]      **7**

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty
array.

Follow up:
Could you solve it in linear time?

Tags: Heap, Sliding Window

Difficulty: Hard

答案

leetcode 378. Kth Smallest Element in a Sorted Matrix

难度:Middle

leetcode
九章

题目描述

Given a n x n matrix where each of the rows and columns are sorted in
ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth
distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

Tags: Binary Search, Heap

Difficulty: Medium

答案

leetcode 347. Top K Frequent Elements

难度:Middle

leetcode
九章

题目描述

Given a non-empty array of integers, return the k most frequent
elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O( n log n ), where n is the array’s size.

Tags: Hash Table, Heap

Difficulty: Medium

答案

leetcode 215. Kth Largest Element in an Array

题目描述

Find the k th largest element in an unsorted array. Note that it is the
kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

Example 2:

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Tags: Divide and Conquer, Heap

Difficulty: Medium

答案


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