605. Planting flowers (Difficulty: Easy)

Suppose you have a very long flower bed, and one part of the plot is planted with flowers, but the other part is not. However, flowers cannot grow in adjacent plots. They compete for water and both die.

Flowerbed gives you an array of integers representing a flowerbed, consisting of zeros and ones, where 0 indicates no flowers and 1 indicates flowers. Another number, n, can I plant n flowers without breaking the planting rules? Returns true if yes, false if no.

Their thinking

  1. Find the location of the first flower, and then find the location of the next flower;
  2. Find the maximum number of plants that can be planted between two flowers;
  3. It is also necessary to calculate the maximum number of flowers that can be planted before the first flower in the bed and after the last pile of flowers in the bed;

Answer key

public boolean canPlaceFlowers(int[] flowerbed, int n) {
   int canBePlantedCount = 0;
   int prevIndex = -1;
   int flowerbedSize = flowerbed.length;

   for (int index = 0; index < flowerbedSize; index++) {
       if (flowerbed[index] == 0) continue;

       if (prevIndex < 0) {
           canBePlantedCount += index / 2;
       } else {
           int betweenSize = index - prevIndex - 1;
           canBePlantedCount += Math.abs(betweenSize - 1) / 2;
       }

       if (canBePlantedCount >= n) {
           return true;
       }

       prevIndex = index;
   }

   if (prevIndex < 0) {
       canBePlantedCount += (flowerbedSize + 1) / 2;
   } else {
       canBePlantedCount += (flowerbedSize - 1 - prevIndex) / 2;
   }
   return canBePlantedCount >= n;
}
Copy the code

test

CanPlaceFlowers canPlaceFlowers = new CanPlaceFlowers();

@Test
public void test_case1(a) {
    int[] flowerbed = new int[] {1.0.0.0.1};
    Assertions.assertTrue(canPlaceFlowers.canPlaceFlowers(flowerbed, 1));
}

@Test
public void test_case2(a) {
    int[] flowerbed = new int[] {1.0.0.0.1};
    Assertions.assertFalse(canPlaceFlowers.canPlaceFlowers(flowerbed, 2));
}

@Test
public void test_case3(a) {
    int[] flowerbed = new int[] {0.0.0.0};
    Assertions.assertTrue(canPlaceFlowers.canPlaceFlowers(flowerbed, 2));
}

@Test
public void test_case4(a) {
    int[] flowerbed = new int[] {0.0.0.0.0};
    Assertions.assertTrue(canPlaceFlowers.canPlaceFlowers(flowerbed, 3));
}

    @Test
public void test_case5(a) {
    int[] flowerbed = new int[] {1.0.0.1};
    Assertions.assertFalse(canPlaceFlowers.canPlaceFlowers(flowerbed, 1));
}

@Test
public void test_case6(a) {
    int[] flowerbed = new int[] {1.0.1.0};
    Assertions.assertFalse(canPlaceFlowers.canPlaceFlowers(flowerbed, 1));
}

@Test
public void test_case7(a) {
    int[] flowerbed = new int[] {1.0.0.0.0.0.1};
    Assertions.assertTrue(canPlaceFlowers.canPlaceFlowers(flowerbed, 2));
}

@Test
public void test_case8(a) {
    int[] flowerbed = new int[] {1.0.1.0.1.0.1};
    Assertions.assertFalse(canPlaceFlowers.canPlaceFlowers(flowerbed, 1));
}

@Test
public void test_case9(a) {
    int[] flowerbed = new int[] {0.0.1.0.1};
    Assertions.assertTrue(canPlaceFlowers.canPlaceFlowers(flowerbed, 1));
}

@Test
public void test_case10(a) {
    int[] flowerbed = new int[] {1.0.0.0.1.0.0};
    Assertions.assertTrue(canPlaceFlowers.canPlaceFlowers(flowerbed, 2));
}
Copy the code