一、种花
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;
}
四、求和
1、问题描述
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
2、算法思路
第一次看到题感觉很有意思，利用递归+短路代替了循环和判断，题解的思路实际利用了短路原理：
&& 的短路特性
- A && B
- A 为 true，则返回表达式 B 的 bool 值
- A 为 false，则返回 false
3、代码实现
class Solution {
public:
int sumNums(int n) {
n && (n += sumNums(n-1));
return n;
}
};
class Solution:
def sumNums(self, n: int) -> int:
return n and n + self.sumNums(n-1)
五、无重复字符串的排列组合
1、问题描述
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
输入：S = "qwe"
输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:
输入：S = "ab"
输出：["ab", "ba"]
2、算法思路
事实上是一个不重复全排列问题，可以使用回溯算法，回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
3、代码实现
class Solution:
def permutation(self, S: str) -> List[str]:
v = {} # 字典
for c in S:
v[c] = False
res = [] # 列表
def dfs(path):
if len(path) == len(S):
res.append(path)
return
# 当结果达到指定长度，加入列表中
for c in v:
if not v[c]:
v[c] = True
dfs(path + c)
v[c] = False
dfs('')
return res
六、最大连续子序列和
1、问题描述
Problem: you are given n integers (there may be negative ones but not all) a1, a2, …, an, determine i and j which maximize the sum from ai to aj .
Case: 6 integers: (-2，11，-4，13，-5，-2)
Answer: i=2, j=4, max sum is 20.
2、算法思路
最大连续子序列和是一个很经典的题目，可以使用暴力算法，也可以使用分治算法或动态规划进行优化，最终降低为O(n)的时间复杂度。
a、暴力算法：
暴力算法即求出所有子序列的和，使用两次循环遍历数组，时间复杂度为$O(n^2)$，并使用一个变量记录最大值max和对应位置i、j，思路简单粗暴，就不给出代码了。
b、分治算法：
分治的思路是把数组分成前后两部分，对于这一数组，其最大连续子序列可能出现在三个地方：出现在数组的前半部（左），或出现在数组的后半部（右），或是跨越数组的中部从而占据左右两半部分。
前两种情况可以通过递归求解，第三种情况可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大和（包含后半部分的第一个元素）而得到，然后将这两个和加在一起即可。
通过分治算法的公式， 我们可以得到：
当N==1时，T(1) = 1；
当N>1时，T(N) = T(N/2) + O(N)；
计算得出时间复杂度为$O(NlogN)$。
c、动态规划算法：
动态规划的思想是——将问题的求解分割为子问题，独立子问题的求解又可再分为子问题。
在这道题中，我们要求长度为N的求出最大连续子序列，其结果为：
1、长度为N-1的最大连续子序列+第N个数字；
2、第N个数字本身；
这两个结果中的最大值，即：
$ MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]};$
这一实现方法只需要遍历一次数组，设置中间变量max和temp，即可求出结果，时间复杂度为$O(N)$。
3、代码实现
//TODO： 分治
动态规划：
N = int(input())
arr = [];
for i in range(0,N):
x = int(input());
arr.append(x);
max1 = 0;
r0 = l0 = 0;
temp = 0;
r = l = 0;
for i in range(0,N):
r0 = i;
temp = temp + arr[i];
if temp < 0:
l0 = r0+1;
temp = 0;
if temp > max1:
max1 = temp;
r = r0;
l = l0;
print (max1);
print (l);
print (r);
1、问题描述
2、算法思路
3、代码实现
1、问题描述
2、算法思路
3、代码实现
