605. Can Place Flowers种花问题【leetcode】
Suppose 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 - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if nnew flowers can be planted in it 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
Note:
- The input array won't violate no-adjacent-flowers rule.
- The input array size is in the range of [1, 20000].
- n is a non-negative integer which won't exceed the input array size.
枚举法写出来 答案，计算可以种花总数是否比n大即可,有投机的成分
//如果这个东西是奇偶数，如果里面的客房偶数比b大即可
/*
左为0 当前为0 且右边为0或边界 这时改为1 count++
左为0 当前为1 继续
左为1 当前为0 继续
左为1 当前为1 继续
*/
public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count =0;
int len=flowerbed.length; if(len==1&&flowerbed[0]==0){
count++;
}
if(len==2&&(flowerbed[0]==0&&flowerbed[1]==0)){
count++;
}
for(int i=1;len>1&&i<len-1;i++){
if(i==1&&flowerbed[i]==0&&flowerbed[i-1]==0){
flowerbed[i-1] =1;
count++;
}
if((flowerbed[i]==0)&&(flowerbed[i]==flowerbed[i-1])&&(flowerbed[i]==flowerbed[i+1])){
flowerbed[i]=1;
count++;
}
if(i==len-2&&flowerbed[i]==0&&flowerbed[i+1]==0){
flowerbed[i+1] =1;
count++;
}
}
if(count>=n)
{return true;}
return false;
}
}
第二种办法，根据一次写的边界值进行归类
因为只需要判断当前元素如果是0的时候与左、右边界值（如果存在着）进行对比
//如果这个东西是奇偶数，如果里面的客房偶数比b大即可
/*
左为0 当前为0 且右边为0或边界 这时改为1 count++
左为0 当前为1 继续
左为1 当前为0 继续
左为1 当前为1 继续
*/
public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count =0;
int len=flowerbed.length;
//boolean flag =flase;
int right=-1;
int left =-1;
for(int i=0;i<len;i++){
//判断当前是否为0，如果为0，且右边有值则比较 否则直接改
int mid=flowerbed[i]; if(mid==0){
//右边界
if(i==0){
if(i+1<len){
right =flowerbed[i+1];
if(mid==right){
flowerbed[i]=1;
count++;
} }
else {
flowerbed[i]=1;
count++;
} }
//右边界
if(i==len-1){
if(i-1>=0){
left =flowerbed[i-1];
if(mid==left){
flowerbed[i]=1;
count++;
}
}
else {
flowerbed[i]=1;
count++;
}
}
//中间值
if(i-1>=0&&i+1<len){
left =flowerbed[i-1];
right =flowerbed[i+1];
if(left==mid&&mid==right){
flowerbed[i]=1;
count++;
}
} } }
if(count>=n)
{return true;}
return false;
}
}
官方答案1
public class Solution {
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++;
}
if(count>=n)
return true;
i++;
}
return false;
}
}
T :o(n) Space:O(1)
精简的写法
public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count =0;
int len=flowerbed.length;
for(int i=0;i<len;i++){
//判断当前是否为0，如果为0，且左右相邻均为0则可以种花，种花后修改花盆属性和种花数量
if(flowerbed[i]==0){
int right=(i==len-1)?0:flowerbed[i+1];
int left=(i==0)?0:flowerbed[i-1];
if(left==right&&right==0){
flowerbed[i]=1;
count++;
}
}
if(count>=n){
return true;
}
}
return false;
}
}
最新文章
- Lesson 20 One man in a boat
- MyBatis通过JDBC生成的执行语句问题
- Ajax全面基础学习（一）
- HTML5--拖动02-dragstart、drag、dragenter、dragover、dragleave、drop、dragend属性
- ZZUOJ 1199 大小关系(拓扑排序，两种方法_判断入度和dfs回路判断)
- mysql数据库性能调优总结积累
- Freemarker-数字默认格式化问题
- Shell_Shell调用SQLPlus简介（案例）
- pthread_attr_t 线程属性(一)
- props 和 state的区别
- POJ 1273 || HDU 1532 Drainage Ditches (最大流模型)
- 关于Git里程碑
- HTML 5结构
- HTML及简单标签介绍
- SQL server 如何修改登录名和密码
- android 视频播放器的INTENT-FILTER属性
- 软通动力C语言机试题
- Azkaban使用简单笔记
- evak购物车-课程设计（201521123034陈凯欣）
- JavaWeb框架SSH_Struts2_(一)