力扣每日一题

605. 种花问题 - 力扣（LeetCode）

动态规划

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int m = flowerbed.size();if(1 == m)return !flowerbed[0] >= n;else if(2 == m)return ((!flowerbed[0] && !flowerbed[1]) >= n);int dp[m][2];//第i个位置种|不种最大的收获数memset(dp, 0, sizeof dp);if(!flowerbed[0] && !flowerbed[1]){dp[0][1] = 1;dp[1][0] = 1;dp[1][1] = 1 - flowerbed[2];}for(int i = 2; i < m - 1; i++){if(!flowerbed[i] && !flowerbed[i + 1] && !flowerbed[i - 1]){dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + 1);dp[i][0] = dp[i - 1][1];}else{dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]);dp[i][0] = max(dp[i - 1][1], dp[i - 2][1]);}}if(!flowerbed[m - 1] && !flowerbed[m - 2]){dp[m - 1][1] = max(dp[m - 2][0] + 1,dp[m - 2][0]);dp[m - 1][0] = max(dp[m - 1][1], dp[m - 2][1]);}elsedp[m - 1][0] = max(dp[m - 2][1],dp[m - 2][0]);return max(dp[m - 1][0], dp[m - 1][1]) >= n;}
};

贪心

class Solution {
public:bool canPlaceFlowers(vector<int> &flowerbed, int n) {int m = flowerbed.size();flowerbed.insert(flowerbed.begin(),0);flowerbed.emplace_back(0);for(int i = 1; i <= m; i++){if(!flowerbed[i] && !flowerbed[i - 1] && !flowerbed[i + 1]){flowerbed[i] = 1;n--;}}return n <= 0;}
};