Press "Enter" to skip to content

Posts tagged as “combination”

花花酱 LeetCode 1255. Maximum Score Words Formed by Letters

Given a list of words, list of  single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a''b''c', … ,'z' is given by score[0]score[1], … , score[25] respectively.

Example 1:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.

Constraints:

  • 1 <= words.length <= 14
  • 1 <= words[i].length <= 15
  • 1 <= letters.length <= 100
  • letters[i].length == 1
  • score.length == 26
  • 0 <= score[i] <= 10
  • words[i]letters[i] contains only lower case English letters.

Solution: Combination

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

C++

花花酱 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] contains only lower case English letters.

Solution: Combination + Bit

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

C++

Solution 2: DP

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

C++

花花酱 LeetCode 77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution: DFS

Time complexity: O(C(n, k))
Space complexity: O(k)

C++

Related Problems

花花酱 LeetCode 78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Solution: Combination

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

Implemention 1: DFS

C++

Python3

Implementation 2: Binary

C++

Python3

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 多重背包