Press "Enter" to skip to content

Posts tagged as “subset”

花花酱 LeetCode 646. Maximum Length of Pair Chain

这题我选DP,因为不需要证明,直接干就行了。

方法1: DP

首先还是需要对pairs的right进行排序。一方面是为了方便chaining,另一方面是可以去重。

然后定义 dp[i] := 以pairs[i]作为结尾,最长的序列的长度。

状态转移:dp[i] = max(dp[j] + 1) where pairs[i].left > pairs[j].right and 0 < j < i.

解释:对于pairs[i],找一个最优的pairs[j],满足pairs[i].left > pairs[j].right,这样我就可以把pairs[i]追加到以pairs[j]结尾的最长序列后面了,长度+1。

边检条件:dp[0:n] = 1,每个pair以自己作为序列的最后元素,长度为1。

时间复杂度:O(n2)
空间复杂度:O(n)

方法2: 贪心

和DP一样,对数据进行排序。

每当我看到 cur.left > prev.right,那么就直接把cur接在prev后面。我们需要证明这么做是最优的,而不是跳过它选后面的元素。

Case 0: cur已经是最后一个元素了,跳过就不是最优解了。

假设cur后面有next, 因为已经排序过了,我们可以得知 next.right >= cur.right。

Case 1: next.right == cur.right。这时候选cur和选next对后面的决策来说是一样的,但由于Case 0的存在,我必须选cur。

Case 2: next.right > cur.right。不管left的情况怎么样,由于right更小,这时候选择cur一定是优于next。

综上所述,看到有元素可以连接起来就贪心的选它就对了。

时间复杂度:O(nlogn)
空间复杂度:O(1)

花花酱 LeetCode 368. Largest Divisible Subset

也算是一道比较经典的DP题了,需要找到一个最大的子集,使得其中元素两两的余数为0。

我们假设有一个集合为{a1, a2, a3, …, an}, {a1 < a2 < … < an)

如果 a2 % a1 = 0, a3 % a2 == 0, 那么a3 % a1 一定也等于0。也就是说a2是a1的倍数,a3是a2的倍数,那么a3一定也是a1的倍数。所以我们并不需要测试任意两个元素之间的余数为0,我们只需要检测a[i]是否为a[i-1]的倍数即可,如果成立,则可以确保a[i]也是a[i-2], a[i-3], … a[1]的倍数。这样就可以大大降低问题的复杂度。

接下来就需要dp就发挥威力了。我们将原数组排序,用dp[i]来表示以a[i]结尾(集合中的最大值),能够构建的子集的最大长度。

转移方程:dp[j] = max(dp[j], dp[i] + 1) if nums[j] % nums[i] = 0.

这表示,如果nums[j] 是 nums[i]的倍数,那么我们可以把nums[j]加入以nums[i]结尾的最大子集中,构建一个新的最大子集,长度+1。当然对于j,可能有好多个满足条件的i,我们需要找一个最大的。

举个例子:
nums = {2, 3, 4, 12}
以3结尾的最大子集{3},长度为1。由于12%3==0,那么我们可以把12追加到{3} 中,构成{3,12}。
以4结尾的最大子集是{2,4},长度为2。由于12%4==0,那么我们可以把12追加到{2,4} 中,构成{2,4,12} 。得到最优解。

这样我们只需要双重循环,枚举i,再枚举j (0 <= i < j)。时间复杂度:O(n^2)。空间复杂度:O(n)。

最后需要输出一个最大子集,如果不记录递推过程,则需要稍微判断一下。

花花酱 LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]

Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.

Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

Constraints:

  • 1 <= nums.length <= 16
  • 1 <= nums[i] <= 105

Solution: Brute Force

Try all possible subsets

Time complexity: O(n*2n)
Space complexity: O(1)

C++

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

  • For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

  • 1 <= nums.length <= 12
  • 1 <= nums[i] <= 20

Solution 1: Brute Force

Use an array A to store all the xor subsets, for a given number x
A = A + [x ^ a for a in A]

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

Python3

花花酱 LeetCode 1452. People Whose List of Favorite Companies Is Not a Subset of Another List

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.

Example 1:

Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Output: [0,1,4] 
Explanation: 
Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. 
Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. 
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].

Example 2:

Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
Output: [0,1] 
Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].

Example 3:

Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
Output: [0,1,2,3]

Constraints:

  • 1 <= favoriteCompanies.length <= 100
  • 1 <= favoriteCompanies[i].length <= 500
  • 1 <= favoriteCompanies[i][j].length <= 20
  • All strings in favoriteCompanies[i] are distinct.
  • All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j].
  • All strings consist of lowercase English letters only.

Solution: Hashtable

Time complexity: O(n*n*m)
Space complexity: O(n*m)
where n is the # of people, m is the # of companies

C++

Use int as key to make it faster.

C++