杂七杂八的练习（3）
杂七杂八的练习（3）
一、种花
1、问题描述
假设你有一个长的花坛，其中一些地块种植着花，另一些没有。 然而，花不能种植在相邻的地块否则他们会争取水导致两者都死亡。 给定一个花坛（表示为包含0和1的数组，其中0表示没有种花，1表示种植着花）以及数字n。如果n个新鲜花可以种植在其中则返回真，否则返回假。
输入格式：
第一行输入数字m，表示花坛的地块数目，可以输入花坛目前的状态（用0,1）表示，第三行输入还需要种植的花的数目n。
输出格式：
为每个测试用例单独输出一行。
输入样例 :
5
1 0 0 0 1
1
输出样例 :
1
2、算法思路
用数组存储花坛，并用一个变量计数。
直接遍历一次数组，当第i个元素为0时，若其相邻元素均为0，则可以种花，将其赋值为1，并将计数变量+1。最后判断计数变量和n的大小即可输出结果。
为了处理边界情况，可以将数组长度设置为m+2，并将首尾均置为0；遍历时从i=1开始即可。
3、代码实现
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
int main(){
int n,m;
cin>>m;
bool flower[m+2];
flower[0] = flower[m+1] = 0;
for(int i=1;i<=m;i++){
cin >> flower[i];
}
cin>>n;
int res=0;
for(int i=1;i<=m;i++){
if(flower[i] == 0){
if(flower[i-1] == 0 && flower[i+1] == 0){
res++;
flower[i] = 1;
}
}
}
cout<<(res>=n);
return 0;
}二、1的块数
1、问题描述
输入一个NxM矩阵（0或1），找出其中’1’的块数，互相相邻（包括对角线）的1称为一个块。
输入：第一行为两个正整数N，M（1<=N<= 100,1<=M<= 100），代表该矩阵的行列； 接下来输入一个NxM矩阵（0或1）。
输出：该矩阵中’1’的块数。
输入样例 :
4 4 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0
输出样例 :
2（左上角的1作为一块，其余的1由于相连，也作为一块）
2、算法思路
此题如果能够理解题目，就很好解决。将每一组相邻的1作为一块，计算矩阵中1的块数。
在主函数中遍历一遍矩阵，遇到1的时候可以将块数+1并进入递归，在递归内将当前块的所有1都置为0。遍历完整个矩阵后即可得到结果。
同样是处理边界问题，也是在矩阵外围加上一圈，并置为0，这样在讨论时可以避免讨论边界条件。或者将判断条件设置为如下：
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
tx = x + i;
ty = y + j;
if (tx >= 0
&& tx < n
&& ty >= 0
&& ty < m
&& map[tx][ty] == true)
{
fun(tx, ty);
}
}
}3、代码实现
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
bool M[100][100];//全局变量自动初始化为0
int x,y;
void fun(int i,int j){
M[i][j]=0;
if(M[i-1][j-1] == 1){
fun(i-1,j-1);
}
if(M[i-1][j] == 1){
fun(i-1,j);
}
if(M[i-1][j+1] == 1){
fun(i-1,j+1);
}
if(M[i][j-1] == 1){
fun(i,j-1);
}
if(M[i][j+1] == 1){
fun(i,j+1);
}
if(M[i+1][j-1] == 1){
fun(i+1,j-1);
}
if(M[i+1][j] == 1){
fun(i+1,j);
}
if(M[i+1][j+1] == 1){
fun(i+1,j+1);
}
}
int main(){
cin >> x >> y;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){//留下一个边界
cin >> M[i][j];
}
}
int res = 0;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(M[i][j] == 1){
fun(i,j);//处理一个块
res++;//块数+1
}
}
}
cout << res << endl;
return 0;
}三、找出和最接近的数
1、问题描述
输入一个整型数组S，以及一个目标整数target，从数组中找出三个数，使得他们的和最接近target，假设对于每一组输入，均对应唯一一个结果。
输入描述：
输入为三行，第一行为数组大小N；第二行为整型数组；第三行为目标整数target。
输出描述：
输出最接近target的三个数的和（假设输出的结果唯一）。
输入样例 :
4 -1 1 2 4 1
输出样例 :
2
2、算法思路
原来使用了3个for循环实现，不过效率实在过低，接下来说明一下标答的思路：
得到输入的数组后，先从小到大进行排序，取第一个数front、最后一个数rear作为三个数的首尾，然后取1<=i<=n-2作为三个数的中间数依次进行讨论。每次讨论时，比较三个数的和与target的大小，如果大于taeget，将rear--；若小于target，将front++。每次还需要比较temp - target的绝对值大小，取最小的值作为我们的结果。
3、代码实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int sim = 999999999;
int result = 0;
for (int i = 1; i < nums.size() - 1; i++)
{
int temp = 0;
int front = 0;
int rear = nums.size() - 1;
while (i > front && i < rear)
{
temp = nums[front] + nums[i] + nums[rear];
if (temp == target) return target;
if(abs(temp - target) < sim)
{
sim = abs(temp - target);
result = temp;
}
(temp < target) ? (front++) : (rear--);
}
}
return result;
}
int main()
{
std::vector<int> v;
int N;
cin >> N;
int temp;
for (int i = 0; i < N; ++i)
{
cin >> temp;
v.push_back(temp);
}
int target;
cin >> target;
cout << threeSumClosest(v, target);
return 0;
}
腾讯云开发者
