[数据结构与算法]leetcode 474 一和零

前言

题目：474. 一和零

参考题解：一和零-力扣官方题解

提交代码

无聊的题目。刷题没有意思，没有工程代码来的有趣。

回溯方法-超时

选 or 不选。可以使用回溯方法，暴力破解。但是这个方法会超时。下面为回溯代码。

看到题目的数据范围，使用回溯大概率会超时。只是写写回溯，避免对回溯手生。

class Solution {
public:
    void backTracking(const vector<pair<int,int>> nums, const int m, const int n, int start_index, int& zero_cnt, int& one_cnt, int& len, int& result){
        if(m>=zero_cnt && n>=one_cnt){
            if(len > result)
                result = len;
        }

        for(int i=start_index; i<nums.size(); i++){
            zero_cnt += nums[i].first;
            one_cnt += nums[i].second;
            len++;
            backTracking(nums,m,n,i+1,zero_cnt,one_cnt,len,result);
            len--;
            one_cnt -= nums[i].second;
            zero_cnt -= nums[i].first;
        }
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<pair<int,int>> nums(strs.size(),pair<int,int>(0,0));
        for(int i=0; i<strs.size(); i++){
            string str = strs[i];
            for(char zero_or_one : str)
                if(zero_or_one == '0')
                    nums[i].first++;
                else
                    nums[i].second++;
        }

        int zero_cnt=0, one_cnt=0, len=0, result=0;
        backTracking(nums,m,n,0,zero_cnt,one_cnt,len,result);

        return result;
    }
};

动态规划-通过

选 or 不选。01背包问题，使用动态规划。

常规的动态规划是两个维度：物体and背后容量。但是这道题目，有两个限制，所以是三维。

我想到使用三维来解决，但是没想好该如何处理数据的继承，即递推表达式。我瞅了瞅参考题解，之后自行实现了一遍。

参考题解，多用了一层来避免初始化。我没有多用一层，本本分分的进行初始化。

#include <string>
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    void zeroOneCnt(const string& str, pair<int,int>& zero_one_cnt){
        for(char ch : str)
            if(ch == '0')
                zero_one_cnt.first++;
            else
                zero_one_cnt.second++;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        // 动态规划：dp[i][j][k],表示从前i个物品中选择，其中0的个数不超过j，1的个数不超过k，的最多的物品个数
        vector<vector<vector<int>>> dp(strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,0)));

        // 初始化三维数组的一个面；其余两个面m=0 or n=0,时，一个也无法装入，为0
        pair<int,int> zero_one_cnt;
        zeroOneCnt(strs[0], zero_one_cnt);
        for(int i=zero_one_cnt.first; i<=m; i++){
            for(int j=zero_one_cnt.second; j<=n; j++)
                dp[0][i][j] = 1;
        }

        for(int i=1; i<strs.size(); i++){
            pair<int,int> zero_one_cnt;
            zeroOneCnt(strs[i], zero_one_cnt);
            for(int j=0; j<=m; j++){
                for(int k=0; k<=n; k++){
                    if(j>=zero_one_cnt.first && k>=zero_one_cnt.second)
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero_one_cnt.first][k-zero_one_cnt.second]+1); // 能放下，看放下值不值
                    else
                        dp[i][j][k] = dp[i-1][j][k]; // 无法放下，继承
                }
            }
        }

        return dp[strs.size()-1][m][n];
    }
};

int main(void){
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m =5, n = 3;
    Solution s;
    cout<<s.findMaxForm(strs,m,n);
}