LeetCode Notes: Can Place Flowers

#leetcode

Question

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2

Output: false

Constraints:

  • 1 <= flowerbed.length <= 2 * 104
  • flowerbed[i] is 0 or 1.
  • There are no two adjacent flowers in flowerbed.
  • 0 <= n <= flowerbed.length

Solution

Analysis:

  1. First of all, we can find a rule. The zeros on the both sides of the array are different from the zeros between the two 1, and the corresponding rules for the number of flowers that can be planted are different.

Looking for patterns

  • The number of 0 in the middle is converted into the number of flowers that can be planted:

The situation when a small amount of 0 is manually calculated

The number of 0The number of flowers that can be planted
00
10
20
31
41
52
62
73
83
94

After trying, it is determined that the relationship between the number n of 0 and the number of flowers that can be planted is Math.floor((n-1) / 2), paste the following code into the console and run it to verify the result:

var a = `
0-0
1-0
2-0
3-1
4-1
5-2
6-2
7-3
8-3
9-4`;

function get(n) {
  console.log(Math.floor((n - 1) / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
  • The number of 0 on both sides is converted into the number of flowers that can be planted:

The situation when a small amount of 0 is manually calculated

The number of 0The number of flowers that can be planted
00
10
21
31
42
52
63
73
84
94

After trying, it is determined that the relationship between the number n of 0 and the number of flowers that can be planted is Math.floor(n / 2), paste the following code into the console and run it to verify the result:

var a = `
0-0
1-0
2-1
3-1
4-2
5-2
6-3
7-3
8-4
9-4`;

function get(n) {
  console.log(Math.floor(n / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
  1. With these two rules, next we need to find the combination of 0 on both sides and 0 in the middle of the array, calculate and transform them respectively, and then calculate the sum
  2. After testing, it is found that there is a special case - all 0. At this time we choose to deal with it separately, as above, we observe the rule that the array is all 0
  • The number of all 0s is converted into the number of flowers that can be planted:

The situation when a small amount of 0 is manually calculated

The number of 0The number of flowers that can be planted
00
11
21
32
42
53
63
74
84
95

After trying, it is determined that the relationship between the number n of 0 and the number of flowers that can be planted is Math.floor((n + 1) / 2), paste the following code into the console and run it to verify the result:

var a = `
0-0
1-1
2-1
3-2
4-2
5-3
6-3
7-4
8-4
9-5`;

function get(n) {
  console.log(Math.floor((n + 1) / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);

Code:

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
  // The code commented out below is the original logical division of the 0 in the middle and the 0 on both sides. It is found to be more redundant. Directly use join+split to quickly combine the adjacent 0s. The method is more concise

  // // The position of the leftmost 1
  // const index = flowerbed.indexOf(1)
  // // The position of the rightmost 1
  // const lastIndex = flowerbed.lastIndexOf(1)

  // // Intercept all 0s to the left of the leftmost 1
  // const before = flowerbed.slice(0,index)
  // // Intercept the number in the middle of the both sides 1
  // const middle = flowerbed.slice(index,lastIndex + 1)
  // // Intercept all 0s to the right of the rightmost 1
  // const after = flowerbed.slice(lastIndex + 1)

  // Count the total number of flowers allowed
  let sum = 0;

  // Adjacent 0s are combined together to form an array
  const zeroArray = flowerbed.join("").split("1");

  // In special cases, the original array is only composed of 0, and the number of flowers allowed to be planted can be directly judged
  if (zeroArray.length === 1) {
    return getFlowersAll(zeroArray[0].length) >= n;
  }

  // Get all 0s to the left of the leftmost 1
  const startZero = zeroArray.shift();
  // Intercept all 0s to the right of the rightmost 1
  const endZero = zeroArray.pop();

  // Count the number of 0 on the left of the leftmost 1 corresponds to the number of flowers that can be planted
  if (startZero !== "") {
    sum += getFlowersSide(startZero.length);
  }
  // Count the number of 0 on the right of the rightmost 1 corresponds to the number of flowers that can be planted
  if (endZero !== "") {
    sum += getFlowersSide(endZero.length);
  }

  // The remaining 0 number in the middle corresponds to the number of flowers that can be planted
  zeroArray.forEach((item, i) => {
    sum += getFlowersMiddle(item.length);
  });

  // return result
  return sum >= n;

  /**
    The number of 0 in the middle is converted into the number of flowers that can be planted
     */
  function getFlowersMiddle(n) {
    return Math.floor((n - 1) / 2);
  }

  /**
    The number of 0 on both sides is converted into the number of flowers that can be planted
     */
  function getFlowersSide(n) {
    return Math.floor(n / 2);
  }

  /**
    The number of all 0s is converted into the number of flowers that can be planted
     */
  function getFlowersAll(n) {
    return Math.floor((n + 1) / 2);
  }
};

Reference

Comments