算法刷题记录 Day37

Date: 2024.04.03

lc 474. 一和零

// 优化为二维数组
class Solution {

public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int s_lens = strs.size();
        vector<pair<int, int>> nums;    //(0的个数, 1的个数)
        for(int i=0; i<s_lens; i++){
            string tmp = strs[i];
            int count_0 = 0;
            int count_1 = 0;
            for(int j=0; j<tmp.size(); j++){
                if(tmp[j] == '0')
                    count_0++;
                else
                    count_1++;
            }
            nums.push_back(make_pair(count_0, count_1));
        }

        // dp[j][k]表示可以容纳j个0和k个1的背包，最多容纳的字符串个数。
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        // dp[j][k] = max(dp[j][k], dp[j-nums[i].first][k-nums[i].second]);
        // dp初始化为0即可。
        for(int i=0; i<s_lens; i++){
            int count_zero = nums[i].first;
            int count_one = nums[i].second;
            for(int j=m; j>=count_zero; j--){
                for(int k=n; k>=count_one; k--){
                    dp[j][k] = max(dp[j][k], dp[j-count_zero][k-count_one]+1);
                }
            }
        }
        
        return dp[m][n];
    }
};

// 三维数组
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int s_lens = strs.size();
        vector<pair<int, int>> nums;    //(0的个数, 1的个数)
        for(int i=0; i<s_lens; i++){
            string tmp = strs[i];
            int count_0 = 0;
            int count_1 = 0;
            for(int j=0; j<tmp.size(); j++){
                if(tmp[j] == '0')
                    count_0++;
                else
                    count_1++;
            }
            nums.push_back(make_pair(count_0, count_1));
        }

        // dp[i][j][k]表示从前i个中取子集，重量小于等于(j,k)的最大价值(子集长度);
        // dp[i][j][k] = for(i) dp[i][j][k] = max(dp[i-1][j][k],  dp[i-1][j-nums[i].first][k-nums[i].second]+1);
        vector<vector<vector<int>>> dp(s_lens, vector<vector<int>>(m+1, vector<int>(n+1, 0)));
        // dp初始化:对第0个数中，j,k均符合条件的赋值1
        for(int j=0; j<=m; j++){
            for(int k=0; k<=n; k++){
                if(j>=nums[0].first && k>=nums[0].second)
                    dp[0][j][k] = 1;
            }
        }

        for(int i=1; i<s_lens; i++){
            for(int j=0; j<=m; j++){
                for(int k=0; k<=n; k++){
                    if(j<nums[i].first || k<nums[i].second)
                        dp[i][j][k] = dp[i-1][j][k];
                    else{
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-nums[i].first][k-nums[i].second]+1);
                    }
                }
            }
        }

        return dp[s_lens-1][m][n];

    }
};

lc 494. 目标和*（没理解dp初始化部分）

// 2. dp
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 将数组拆分为两个子集left和right，我们希望找到left+right=sum,left-right=target;
        // 由此，我们希望找到right = (sum - target) / 2;
        // 问题转化为数组中能组成right的子集个数。
        // 转为背包问题：
        // dp[i][j] 表示从[0, i]整数中取值，能取到j的不同集合的总数；
        // dp[i][j] = for(int i=0; i<n; i++) dp[i-1][j-nums[i]];
        int sum = 0;
        for(auto& num: nums)
            sum += num;

        if((sum - target) % 2 == 1 || sum < target)
            return 0;
        int right = (sum - target) / 2;

        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(right+1, 0));
        // dp初始化
        dp[0][0] = 1;

        for(int i=1; i<=n; i++){
            for(int j=0; j<=right; j++){                
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])
                    dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }

        return dp[n][right];

    }
};

// 1. 回溯
class Solution {
private:
    int res = 0;
public:
    void backTracking(vector<int>& nums, int& t, int cur_idx, int cur_v){
        if(cur_v == t)
            res++;
        if(cur_v > t)   //非负整数数组 剪枝
            return;
        if(cur_idx == nums.size())
            return;
        
        for(int i=cur_idx; i<nums.size(); i++){
            backTracking(nums, t, i+1, cur_v+nums[i]);
        }
        return;
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        // 将数组拆分为两个子集left和right，我们希望找到left+right=sum,left-right=target;
        // 由此，我们希望找到right = (sum - target) / 2;
        // 问题转化为数组中能组成right的个数。
        int sum = 0;
        for(auto& num: nums)
            sum += num;
        if((sum - target) % 2 == 1 || sum < target)
            return 0;
        int t = (sum - target) / 2;
        backTracking(nums, t, 0, 0);
        return res;
    }
};

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

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        // 转换为背包问题：从一组石头中，选出最接近但不超过一半重量的石头。
        int n = stones.size();
        int count = 0;
        for(auto& stone: stones){
            count += stone;
        }
        int half_count = count / 2;

        vector<int> dp(half_count+1, 0);

        for(int i=0; i<n; i++){
            for(int j=half_count; j>=stones[i]; j--){
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }

        return (count - 2*dp[half_count]);
    }
};