力扣10.21

474. 一和零

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

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

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

数据范围

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

分析

背包，分清楚背包容量，体积和价值，这道题的背包容量有两个：1的个数和0的个数，体积为每个字符对应的1的个数和0的个数，价值为1

代码

class Solution {
public:
    const static int N = 605, M = 105;
    int cnt[N][3];
    int dp[M][M];
    int findMaxForm(vector<string>& strs, int m, int n) {
        int nn = strs.size();
        for(int i = 1; i <= nn; i ++ ) {
            for(auto k : strs[i - 1]) {
                if(k == '0') cnt[i][0] ++ ;
                else cnt[i][1] ++ ;
            }
        }
        for(int i = 1; i <= nn; i ++ ) {
            for(int j = m; j >= cnt[i][0] ; j -- ) {
                for(int k = n; k >= cnt[i][1]; k -- ) {
                    dp[j][k] = max(dp[j][k], dp[j - cnt[i][0]][k - cnt[i][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

910. 最小差值 II

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

数据范围

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 104
• 0 <= k <= 104

分析

贪心，可以发现，一般的贪心方式就是小的元素+k，大的元素-k，最后相对趋于平衡，因此我们可以先排序一下，然后枚举这个点，计算对应的分数就行

代码

typedef long long LL;
class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        int maxx = 0, minx = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int res = nums[n - 1] - nums[0];
        for(int i = 0; i < n - 1; i ++ ) {
            maxx = max(nums[i] + k, nums[n - 1] - k);
            minx = min(nums[0] + k, nums[i + 1] - k);
            res = min(res, maxx - minx);
        }
        return res;
    }
};

1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

数据范围

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

分析

将问题转化为：石头分成两堆，重量分别为$w1$和$w2$，求$abs(w1-w2)$的最小值，因此分的策略一定是越靠近$sum/2$越好，此时可以设置一个背包容量为$sum/2$的背包，价值和体积都为石头的重量，最终答案为$sum-2\ast dp[n][sum/2]$

代码

class Solution {
public:
    const static int N = 35, M = 3e4 + 5;
    int dp[N][M];
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int sum = 0;
        for(int i = 0; i < n; i ++ ) sum += stones[i];
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j <= sum / 2; j ++ ) {
                dp[i + 1][j] = dp[i][j];
                if(j >= stones[i]) {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - stones[i]] + stones[i]);
                }
            }
        }
        return sum - 2 * dp[n][sum / 2];
    }
};