605. Can Place Flowers

發表於 | 分類於

problem

solution

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
26
27
28
29
30
31
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int len = flowerbed.size();
        
        // corner case
        if(len==1){
            if(flowerbed[0] == 1) return n>0?false:true;
            else if(flowerbed[0]==0) return n>1?false:true;
        }
        vector<int> ret = flowerbed;
        int m = n;
        if(flowerbed[1] == 0  &&  flowerbed[0]==0){
            m--;
            ret[0] = 1;
        }
        for(int i = 1;i<len-1 ; ++i)
        {
            if(flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1]==0 && ret[i-1]==0)
            {
                ret[i] =1;
                m--;
            }
        }
        if(flowerbed[len-2] == 0 && ret[len-2]==0 && flowerbed[len-1] == 0){
            m--;
            ret[len-1] =1;
        }
        return m>0?false:true;
    }
};
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
26
27
28
29
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int len = flowerbed.size();
        
        // corner case
        if(len==1){
            if(flowerbed[0] == 1) return n>0?false:true;
            else if(flowerbed[0]==0) return n>1?false:true;
        }
        int m = n;
        if(flowerbed[1] == 0  &&  flowerbed[0]==0){
            m--;
            flowerbed[0] = 1;
        }
        for(int i = 1;i<len-1 ; ++i)
        {
            if(flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1]==0){
                flowerbed[i] = 1;
                m--;
            }
        }
        if(flowerbed[len-2] == 0 && flowerbed[len-1] == 0) {
            flowerbed[len-1] = 1;
            m--;
        }
        return m>0?false:true;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n) -> O(1)