Press "Enter" to skip to content

Posts tagged as “hard”

花花酱 LeetCode 956. Tallest Billboard

Problem

You are installing a billboard and want it to have the largest height.  The billboard will have two steel supports, one on each side.  Each steel support must be an equal height.

You have a collection of rods which can be welded together.  For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.

Return the largest possible height of your billboard installation.  If you cannot support the billboard, return 0.

Example 1:

Input: [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.

Example 2:

Input: [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.

Example 3:

Input: [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.

Note:

  1. 0 <= rods.length <= 20
  2. 1 <= rods[i] <= 1000
  3. The sum of rods is at most 5000.

Solution: DP

如果直接暴力搜索的话时间复杂度是O(3^N),铁定超时。对于每一根我们可以选择1、放到左边,2、放到右边,3、不使用。最后再看一下左边和右边是否相同。

题目的数据规模中的这句话非常重要:

The sum of rods is at most 5000.

这句话就是告诉你算法的时间复杂度和sum of rods有关系,通常需要使用DP。

由于每根柱子只能使用一次(让我们想到了 回复 01背包),但是我们怎么去描述放到左边还是放到右边呢?

Naive的方法是用 dp[i] 表示使用前i个柱子能够构成的柱子高度的集合。

e.g. dp[i] = {(h1, h2)},  h1 <= h2

和暴力搜索比起来DP已经对状态进行了压缩,因为我并不需要关心h1, h2是通过哪些(在我之前的)柱子构成了,我只关心它们的当前高度。

然后我可以选择

1、不用第i根柱子

2、放到低的那一堆

3、放到高的那一堆

状态转移的伪代码:

for h1, h2 in dp[i – 1]:

dp[i] += (h1, h2)        # not used

dp[i] += (h1, h2 + h)  # put on higher

if h1 + h < h2:

dp[i] += (h1 + h, h2)  # put on lower

else:

dp[i] += (h2, h1 + h)  # put on lower

假设 rods=[1,1,2]

dp[0] = {(0,0)}

dp[1] = {(0,0), (0,1)}

dp[2] = {(0,0), (0,1), (0,2), (1,1)}

dp[3] = {(0,0), (0,1), (0,2), (0,3), (0,4), (1,1), (1,2), (1,3), (2,2)}

但是dp[i]这个集合的大小可能达到sum^2,所以还是会超时…

时间复杂度 O(n*sum^2)

空间复杂度 O(n*sum^2) 可降维至 O(sum^2)

革命尚未成功,同志仍需努力!

all pairs的cost太大,我们还需要继续压缩状态!

重点来了

通过观察发现,若有2个pairs:

(h1, h2), (h3, h4),

h1 <= h2, h3 <= h4, h1 < h3, h2 – h1 = h4 – h3 即 高度差 相同

如果 min(h1, h2) < min(h3, h4) 那么(h1, h2) 不可能产生最优解,直接舍弃。

因为如果后面的柱子可以构成 h4 – h3/h2 – h1 填补高度差,使得两根柱子一样高,那么答案就是 h2 和 h4。但h2 < h4,所以最优解只能来自后者。

举个例子:我有 (1, 3) 和 (2, 4) 两个pairs,它们的高度差都是2,假设我还有一个长度为2的柱子,那么我可以构成(1+2, 3) 以及 (2+2, 4),虽然这两个都是解。但是后者的高度要大于前者,所以前者无法构成最优解,也就没必要存下来。

所以,我们可以把状态压缩到高度差对于相同的高度差,我只存h1最大的

我们用 dp[i][j] 来表示使用前i个柱子,高度差为j的情况下最大的公共高度h1是多少。

状态转移(如下图)

dp[i][j] = max(dp[i][j], dp[i – 1][j])

dp[i][j+h] = max(dp[i][j + h], dp[i – 1][j])

dp[i][|j-h|] = max(dp[i][|j-h|], dp[i – 1][j] + min(j, h))

时间复杂度 O(nsum)

空间复杂度 O(nsum) 可降维至 O(sum)

dp[i] := max common height of two piles of height difference i.

e.g. y1 = 5, y2 = 9 => dp[9 – 5] = min(5, 9) => dp[4] = 5.

answer: dp[0]

Time complexity: O(n*Sum)

Space complexity: O(Sum)

C++ hashmap

C++ / array

C++/2D array

花花酱 LeetCode 936. Stamping The Sequence

Problem

You want to form a target string of lowercase letters.

At the beginning, your sequence is target.length '?' marks.  You also have a stamp of lowercase letters.

On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp.  You can make up to 10 * target.length turns.

For example, if the initial sequence is “?????”, and your stamp is "abc",  then you may make “abc??”, “?abc?”, “??abc” in the first turn.  (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)

If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn.  If the sequence is not possible to stamp, return an empty array.

For example, if the sequence is “ababc”, and the stamp is "abc", then we could return the answer [0, 2], corresponding to the moves “?????” -> “abc??” -> “ababc”.

Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within 10 * target.length moves.  Any answers specifying more than this number of moves will not be accepted.

Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]
([1,0,2] would also be accepted as an answer, as well as some other answers.)

Example 2:

Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]

Note:

  1. 1 <= stamp.length <= target.length <= 1000
  2. stamp and target only contain lowercase letters.

Solution: Greedy + Reverse Simulation

Reverse the stamping process. Each time find a full or partial match. Replace the matched char to ‘?’.

Don’t forget the reverse the answer as well.

T = “ababc”, S = “abc”

T = “ab???”, index = 2

T = “?????”, index = 0

ans = [0, 2]

Time complexity: O((T – S)*S)

Space complexity: O(T)

C++

花花酱 LeetCode 952. Largest Component Size by Common Factor

Problem

Given a non-empty array of unique positive integers A, consider the following graph:

  • There are A.length nodes, labelled A[0] to A[A.length - 1];
  • There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

  1. 1 <= A.length <= 20000
  2. 1 <= A[i] <= 100000

Solution: Union Find

For each number, union itself with all its factors.

E.g. 6, union(6,2), union(6,3)

Time complexity: \( O(\Sigma{sqrt(A[i])})  \)

Space complexity: \( O(max(A)) \)

C++

Python3

花花酱 LeetCode 943. Find the Shortest Superstring

Problem

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

  1. 1 <= A.length <= 12
  2. 1 <= A[i].length <= 20

Solution 1: Search + Pruning

Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].

Time complexity: O(n!)

Space complexity: O(n)

C++

Java

Solution 2: DP

g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].

We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.

We can solve it with DP that uses exponential time.

dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.

e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).

Time complexity: O(n^2 * 2^n)

Space complexity: O(n * 2^n)

C++

花花酱 LeetCode 940. Distinct Subsequences II

Problem

Given a string S, count the number of distinct, non-empty subsequences of S .

Since the result may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".

Example 3:

Input: "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Note:

  1. S contains only lowercase letters.
  2. 1 <= S.length <= 2000

Solution: DP

counts[i][j] := # of distinct sub sequences of s[1->i] and ends with letter j. (‘a'<= j <= ‘z’)

Initialization:

counts[*][*] = 0

Transition:

counts[i][j] = sum(counts[i-1]) + 1 if s[i] == j  else counts[i-1][j]

ans = sum(counts[n])

e.g. S = “abc”

counts[1] = {‘a’ : 1}
counts[2] = {‘a’ : 1, ‘b’ : 1 + 1 = 2}
counts[3] = {‘a’ : 1, ‘b’ : 2, ‘c’: 1 + 2 + 1 = 4}
ans = sum(counts[3]) = 1 + 2 + 4 = 7

Time complexity: O(N*26)

Space complexity: O(N*26) -> O(26)

C++

Python3