✨ leetcode 第605题

fuyongde · fuyongde · commit b7b4eaa783a4 · 2020-02-28T22:33:13.000+08:00
diff --git a/leetcode/src/main/java/com/fuyd/other/Solution605.java b/leetcode/src/main/java/com/fuyd/other/Solution605.java
@@ -0,0 +1,49 @@
+package com.fuyd.other;
+
+/**
+ * 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
+ *
+ * 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
+ *
+ * 示例 1:
+ *
+ * 输入: flowerbed = [1,0,0,0,1], n = 1
+ * 输出: True
+ * 示例 2:
+ *
+ * 输入: flowerbed = [1,0,0,0,1], n = 2
+ * 输出: False
+ * 注意:
+ *
+ * 数组内已种好的花不会违反种植规则。
+ * 输入的数组长度范围为 [1, 20000]。
+ * n 是非负整数，且不会超过输入数组的大小。
+ *
+ * 来源：力扣（LeetCode）
+ * 链接：https://leetcode-cn.com/problems/can-place-flowers
+ * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+ *
+ * @author fuyongde
+ * @date 2020/2/28 22:22
+ */
+public class Solution605 {
+
+    /**
+     * 贪心算法
+     * 从左到右扫描数组，如果数组中有一个0，并且这个0的左右两侧都是0，则这个位置可以种花，
+     * 并将该位置置为1，针对计数增加1，当计数 >= n 时，则为 true，否则为 false
+     * 时间复杂度：O(n)，可以在循环中，增加计数与 n 的判断，来减少循环的次数，从而使程序执行效率更高
+     * 空间复杂度：O(1)
+     */
+    public boolean canPlaceFlowers(int[] flowerbed, int n) {
+        int i = 0, count = 0;
+        while (i < flowerbed.length) {
+            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
+                flowerbed[i] = 1;
+                count++;
+            }
+            i++;
+        }
+        return count >= n;
+    }
+}
