Press "Enter" to skip to content

Posts published in October 2017

花花酱 LeetCode 719. Find K-th Smallest Pair Distance

题目大意:给你一个数组,返回所有数对中,绝对值差第k小的值。

Problem:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Note:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

Idea

Bucket sort

Binary search / dp

Solution

C++ / binary search

 

C++ / bucket sort w/ vector O(n^2)

Related Problems:

花花酱 LeetCode 621. Task Scheduler

题目大意:给你一些用字母表示的任务,执行每个任务需要单位时间的CPU。对于相同的任务,CPU需要n个单位时间的冷却时间,期间可以执行其他不相同的任务。问最少多少时间可以完成所有任务。

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Note:

  1. The number of tasks is in the range [1, 10000].
  2. The integer n is in the range [0, 100].

Idea:

Counting

Time complexity: O(n)

Space complexity: O(1)

 

 

花花酱 LeetCode 699. Falling Squares

题目大意:方块落下后会堆叠在重叠的方块之上,问每一块方块落下之后最高的方块的高度是多少?

Problem:

On an infinite number line (x-axis), we drop given squares in the order they are given.

The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[i][0] and sidelength positions[i][1].

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

 

Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have dropped, after dropping squares represented by positions[0], positions[1], ..., positions[i].

Example 1:

Example 2:

Note:

 

  • 1 <= positions.length <= 1000.
  • 1 <= positions[i][0] <= 10^8.
  • 1 <= positions[i][1] <= 10^6.



Idea:

Range query with map

 

Solution:

C++ map

 

C++ vector without merge

C++ / vector with merge (slower)

 

Related Problems:

花花酱 LeetCode 715. Range Module

Problem:

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

 

  • addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
  • queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
  • removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example 1:

Note:

  • A half open interval [left, right) denotes all real numbers left <= x < right.
  • 0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
  • The total number of calls to addRange in a single test case is at most 1000.
  • The total number of calls to queryRange in a single test case is at most 5000.
  • The total number of calls to removeRange in a single test case is at most 1000.



Idea:

map / ordered ranges

  

 

Solution:

C++ / vector

C++ / map

Related Problems:

花花酱 LeetCode 347. Top K Frequent Elements

Problem:

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

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.



Idea:

 

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

Java

Python

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

C++/array

Java

Python

Related Problems