第078节 2023年7月4周流行算法题目解析

给你一个正整数数组 nums

每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半

注意，在后续操作中你可以对减半过的数继续执行操作

请你返回将 nums 数组和 至少 减少一半的 最少 操作数

测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/

自 01背包问世之后，小 A 对此深感兴趣

一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组

每组中的物品只能选择1件，现在他想知道最大的利用价值是多少

测试链接 : www.luogu.com.cn/problem/P1757

一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币

每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里

给你一个列表 piles ，其中 piles[i] 是一个整数数组

分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k

请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少

测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/

给你一个二进制字符串数组 strs 和两个整数 m 和 n

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集

测试链接 : https://leetcode.cn/problems/ones-and-zeroes/

集团里有 n 名员工，他们可以完成各种各样的工作创造利润

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与

如果成员参与了其中一项工作，就不能参与另一项工作

工作的任何至少产生 minProfit 利润的子集称为 盈利计划

并且工作的成员总数最多为 n

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

测试链接 : https://leetcode.cn/problems/profitable-schemes/

在一个小城市里，有 m 个房子排成一排

你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n )

有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色

我们将连续相同颜色尽可能多的房子称为一个街区

比方说 houses = [1,2,2,3,3,2,1,1]

它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}]

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target，其中：

houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色

cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区

如果没有可用的涂色方案，请返回 -1

测试链接 : https://leetcode.cn/problems/paint-house-iii/