leetcode 474 一和零

- 日理万妓 2022-09-16 14:23 135阅读 0赞

## 前言 ##

题目：[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);
    }

[474.]: https://leetcode-cn.com/problems/ones-and-zeroes/
[-]: https://leetcode-cn.com/problems/ones-and-zeroes/solution/yi-he-ling-by-leetcode-solution-u2z2/