Cinte's Leetcode Record
0%

605. 种花问题

Posted on Edited on In Disqus:
Symbols count in article: 717 Reading time ≈ 1 mins.

605. 种花问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int m = flowerbed.size();
        for(int i = 0; i < m; ++i)
        {
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] != 1) && (i == m - 1 || flowerbed[i + 1] != 1))
            {
                flowerbed[i] = 1;
                --n;
            }
        }
        return n <= 0;
    }
};

答案

通过2个1之间的0直接来计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int m = flowerbed.size();
        int prev{ -1};
        for(int i = 0; i < m; ++i)
        {
            if(flowerbed[i] == 1)
            {
                if(prev < 0)
                    n -= i / 2;
                else
                    n -= (i - prev - 2) / 2;
                if(n <= 0)
                    return true;
                prev = i;
            }
        }
        if(prev == -1)
            n -= (m + 1) / 2;
        else
            n -= (m - prev - 1) / 2;
        return n <= 0;
    }
};