Press "Enter" to skip to content

Posts published in November 2018

花花酱 LeetCode 939. Minimum Area Rectangle

Problem

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

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

Example 2:

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

Note:

  1. 1 <= points.length <= 500
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. All points are distinct.

Solution 1: HashTable + Brute Force

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

Space complexity: O(n)

C++

C++ / 1D hashtable

花花酱 LeetCode 938. Range Sum of BST

Problem

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:

  1. The number of nodes in the tree is at most 10000.
  2. The final answer is guaranteed to be less than 2^31.

Solution: In-order traversal

Time complexity: O(n)

Space complexity: O(n)

C++

花花酱 LeetCode 937. Reorder Log Files

Problem

https://leetcode.com/problems/reorder-log-files/description/

You have an array of logs.  Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier.  Then, either:

  • Each word after the identifier will consist only of lowercase letters, or;
  • Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs.  It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log.  The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties.  The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

  1. 0 <= logs.length <= 100
  2. 3 <= logs[i].length <= 100
  3. logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution: Partition + Sort

  1. partition the array such that all digit logs are after all letter logs
  2. sort the letter logs part based on the log content

Time complexity: O(n + aloga)

Space complexity: O(n)

C++

Knapsack Problem 背包问题

Videos

上期节目中我们对动态规划做了一个总结,这期节目我们来聊聊背包问题。

背包问题是一个NP-complete的组合优化问题,Search的方法需要O(2^N)时间才能获得最优解。而使用动态规划,我们可以在伪多项式(pseudo-polynomial time)时间内获得最优解。

0-1 Knapsack Problem 0-1背包问题

Problem

Given N items, w[i] is the weight of the i-th item and v[i] is value of the i-th item. Given a knapsack with capacity W. Maximize the total value. Each item can be use 0 or 1 time.

0-1背包问题的通常定义是:一共有N件物品,第i件物品的重量为w[i],价值为v[i]。在总重量不超过背包承载上限W的情况下,能够获得的最大价值是多少?每件物品可以使用0次或者1次

例子:

重量 w = [1, 1, 2, 2]

价值 v = [1, 3, 4, 5]

背包承重 W = 4

最大价值为9,可以选第1,2,4件物品,也可以选第3,4件物品;总重量为4,总价值为9。

动态规划的状态转移方程为:

Solutions

Search

DP2

DP1/tmp

DP1/push

DP1/pull

 

Unbounded Knapsack Problem 完全背包

完全背包多重背包是常见的变形。和01背包的区别在于,完全背包每件物品可以使用无限多次,而多重背包每件物品最多可以使用n[i]次。两个问题都可以转换成01背包问题进行求解。

但是Naive的转换会大大增加时间复杂度:

完全背包:“复制”第i件物品到一共有 W/w[i] 件

多重背包:“复制”第i件物品到一共有 n[i] 件

然后直接调用01背包进行求解。

时间复杂度:

完全背包 O(Σ(W/w[i])*W)

多重背包 O(Σn[i]*W)

不难看出时间复杂度 = O(物品数量*背包承重)

背包承重是给定的,要降低运行时候,只有减少物品数量。但怎样才能减少总的物品数量呢?

这就涉及到二进制思想:任何一个正整数都可以用 (1, 2, 4, …, 2^K)的组合来表示。例如14 = 2 + 4 + 8。
原本需要放入14件相同的物品,现在只需要放入3件(重量和价值是原物品的2倍,4倍,8倍)。大幅降低了总的物品数量从而降低运行时间。

完全背包:对于第i件物品,我们只需要创建k = log(W/w[i])件虚拟物品即可。

每件虚拟物品的重量和价值为:1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^k*(w[i], v[i])。

多重背包:对于第i件物品,我们只需要创建k + 1件虚拟物品即可,其中k = log(n[i])。

每件虚拟物品的重量和价值为:1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^(k-1)*(w[i], v[i]), 以及 (n[i] – 2^k – 1) * (w[i], v[i])。

例如:n[i] = 14, k = 3, 虚拟物品的倍数为 1, 2, 4 和 7,这4个数组合可以组成1 ~ 14中的任何一个数,并且不会>14,即不超过n[i]。

二进制转换后直接调用01背包即可

时间复杂度:

完全背包 O(Σlog(W/w[i])*W)

多重背包 O(Σlog(n[i])*W)

空间复杂度 O(W)

其实完全背包和多重背包都可以在 O(NW)时间内完成,前者在视频中有讲到,后者属于超纲内容,以后有机会再和大家深入分享。

Bounded Knapsack Problem 多重背包

 

花花酱 LeetCode 648. Replace Words

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

  1. The input will only have lower-case letters.
  2. 1 <= dict words number <= 1000
  3. 1 <= sentence words number <= 1000
  4. 1 <= root length <= 100
  5. 1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)