当前位置:网站首页>Leetcode notes 605. can place flowers (easy) 605. planting flowers
Leetcode notes 605. can place flowers (easy) 605. planting flowers
2022-07-29 06:24:00 【Lu Yi, twelve】
Just started trying to write this thing , I hope you can point out the shortcomings after reading this article , thank you !!
1. Problem description :( You must be familiar with the topic ! But out of habit, I copied and pasted )
Suppose there's a very long flower bed , Part of the plot is planted with flowers , The other part didn't . But , Flowers cannot be planted on adjacent plots , They compete for water , Both will die .
Give you an array of integers flowerbed Indicates a flower bed , By a number of 0 and 1 form , among 0 No flowers ,1 It means flowers are planted . There's another number n , Can it be planted without breaking the planting rules n A flower ? Energy returns true , If not, return false.
2. Code :( I believe some people have ideas and everything , Just want to see the code , So put the code first )
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
// Two special cases
if(n == 0){
return true;
}
// When n > flowerbed.size()/2 + 1 when , It must be false.
if(n > flowerbed.size() / 2 + 1){
return false;
}
// Add 0, Avoid the trouble of classification discussion .
flowerbed.emplace(flowerbed.begin(), 0);
int count = 0; // The amount that can be planted
int num = 1; // Count whenever num == 3 when ,++count;
// Every three adjacent 0 You can plant a flower , notes : The next time num The count is from the third 0 At the beginning !!!
for(int i = 1; i < flowerbed.size(); ++i){
if(flowerbed[i] != 0){
num = 0;
}else{
++num;
if(num == 3){
++count;
num = 1;
}
}
}
// At the end of the array is 00 You can plant a pot .
if(num == 2){
++count;
}
return {count >= n? true:false};
}
};
3. Their thinking :
Since flowers cannot be planted on adjacent plots , Then every three adjacent open spaces can be planted with a pot of flowers , Turn the problem into traversing three adjacent 0, Each group can plant a pot , With num For the neighboring 0 Number of ,count For the number of pots of flowers that can be planted . When flowerbed[i]==0,++num, When num == 3 when ,++count, hold num Reset to 1; When flowerbed[i]== 1,num Zero clearing .
4. Details :
@. When the first value of the array is 1 Or is it 0 It seems that classification discussion is needed to accurately determine count Value , To avoid this trouble , I take to add one at the head of the array 0, In this way, there is no need to classify and discuss .
@. whenever num == 3( There are three consecutive 0) when ,count Add one to the value of , At this time num The value of is not zero , Instead, set it to 1( This is what I think is the most important point ), Because the third 0 Can participate in the following 0 In the count of , For example, the array is 010000010, After planting the most flowers, it becomes 010101010, That is to say 5 A continuous 0 It can be planted 2 basin , Without the need for 6 individual 0.( The expression here seems not very good , If I think of something better, I'll come back and change it .)
@. There are two situations in which the result can be directly judged : The first is n == 0, It must be true; The second is n>(flowerbed.size()/2 + 1), namely n The value has been greater than what the array can theoretically hold 1 The number of , It must be false.
5. Code section
@. adopt emplace() Function or insert() Functions can realize the function of adding elements .emplace() You can only add one element at a time , Faster ;insert() Function can add one or more elements or an array at a certain position , Slower . So I chose emplace() function .
@. In fact, add one at the end of the array 0 There is no need for final judgment count == 2 了 , But the speed is much slower , So I made a compromise .
边栏推荐
猜你喜欢
Jingwei Qili: development of heart rate and blood oxygen module based on hmep060 (1: FPGA sends multi bit instructions)
一些工具,插件,软件链接分享给大家~
官方教程 Redshift 06 Opt参数
动态规划总结
Simple code to realize PDF to word document
Redshift还原SP效果 - SP贴图导出设置及贴图导入配置
Dynamic planning summary
Multithreading and concurrency
ML7 self study notes
【软件工程之美 - 专栏笔记】14 | 项目管理工具:一切管理问题,都应思考能否通过工具解决
随机推荐
UE5 纹理系统讲解及常见问题设置及解决方案
FPGA based: moving target detection (supplementary simulation results, available)
[beauty of software engineering - column notes] 19 | as a programmer, you should have product awareness
官方教程 Redshift 08 Light
寒假集训总结 (1.23~1.28) [第一梯队]
leetcode刷题笔记 452. Minimum Number of Arrows to Burst Balloons (Medium) 452.用最少数量的箭引爆气球(中等)
scanBasePackages扫包范围配置
Redshift还原SP效果 - SP贴图导出设置及贴图导入配置
shell工具finalShell
SQLyog 安装和配置教程
TB6600+stm32F407测试
传统模型预测控制轨迹跟踪——波浪形轨迹(功能包已经更新)
LeetCode #876.链表的中间结点
#7110 数字走向2 题解
【软件工程之美 - 专栏笔记】23 | 架构师:不想当架构师的程序员不是好程序员
数学建模心得
网络安全学习篇
从头安装MYSQL(MYSQL安装文档-解压版)
【软件工程之美 - 专栏笔记】13 | 白天开会,加班写代码的节奏怎么破?
2022 spring recruit - Shanghai an road FPGA post Manager (and Lexin SOC interview)