还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入: [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
注意:
给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。</font>
#include <iostream>
#include <vector>
#include <algorithm>
#include<numeric>
using namespace std;
class Solution {
public:
bool makesquare(vector<int>& nums) {
if(nums.size() < 4)
return false;
int sum =0;
for(int i =0;i<(int)nums.size();++i)
sum += nums[i];
if(sum%4 !=0)
return false;
//按照长度从大到小的顺序排列火柴
sort(nums.rbegin(),nums.rend());
//设置四条边的集合
int line[4] ={0};
return IsOk(0,nums,sum/4,line);
}
bool IsOk(int i,vector<int>& nums, int target,int line[])
{
if(i ==(int)nums.size())
return line[0] == target && line[1] == target && line[2] == target && line[3] == target;
for(int j =0;j<4;++j)
{
//要是当前边与火柴长度的和比期望长度大,就将当前火柴与下一条边匹配
if(line[j] + nums[i] > target)
continue;
//拼凑期望边长
line[j] += nums[i];
//递归调用,和下一个火柴匹配
if(IsOk(i + 1,nums,target,line))
return true;
//说明该边长的所有火柴组合不恰当 ,应该拆开重新组合
line[j] -= nums[i];
}
return false;
}
};
int main()
{
Solution ss ;
vector<int>s ;
int a ;
while(cin>>a){
if(a==-1)break ;
s.push_back(a);
}
cout<<ss.makesquare(s)<<endl;
return 0;
}
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.size()==0)return;
vector<vector<char>>ll ;
int len=(int)board.size();
int wid = (int)board[0].size();
//将ll数组全部初始化为长宽和board相等的有X组成的数组
Init(len,wid,ll);
//要是找被X围绕的O,可以在Board四条边上找深搜没被围绕的O,将ll相应位置置为O
for(int i= 0;i<wid;i++){
Dfs(0,i,board,ll);
Dfs(len-1,i,board,ll);
}
for(int i= 1;i<len-1;i++){
Dfs(i,0,board,ll);
Dfs(i,wid-1,board,ll);
}
//将ll赋值给board即可
board=ll;
}
void Dfs(int i,int j,vector<vector<char>>& board,vector<vector<char>>& ll){
if(i<0||j<0||i>(int)board.size()-1||j>(int)board[0].size()-1||board[i][j]!='O')return ;
//将遍历的原先为O的位置置为不为O的字符
board[i][j]='X';
ll[i][j]='O';
Dfs(i-1,j,board,ll);
Dfs(i,j+1,board,ll);
Dfs(i+1,j,board,ll);
Dfs(i,j-1,board,ll);
}
void Init(int len,int wid,vector<vector<char>>& ll){
for(int i = 0;i<len;i++){
vector<char>s ;
for(int j=0;j<wid;j++){
char ch ='X';
s.push_back(ch);
}
ll.push_back(s);
}
}
};
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int res = 0 ;
for(int i =0 ;i < (int)grid.size();i++){
for(int j= 0;j<(int)grid[i].size();j++){
if(grid[i][j]=='0'){
continue;
}
//记录深搜的次数即为岛屿的个数
res++;
Dfs(i,j,grid);
}
}
return res;
}
void Dfs(int i,int j,vector<vector<char>>& grid){
if(i<0||j<0||i>(int)grid.size()-1||j>(int)grid[0].size()-1||grid[i][j]!='1'){
return ;
}
grid[i][j]='0';
Dfs(i-1,j,grid);
Dfs(i,j+1,grid);
Dfs(i+1,j,grid);
Dfs(i,j-1,grid);
}
};
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
#include <iostream>
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root){
bool same = true ;
if(root)
DTree(root->left,root->right,same);
return same ;
}
void DTree(TreeNode* l,TreeNode* r,bool &same){
if((l==NULL&&r!=NULL)||(r==NULL&&l!=NULL)){
same=false;
}
if(l&&r){
if(r->val!=l->val){
same = false ;
}
DTree(l->left,r->right,same);
DTree(l->right,r->left,same);
}
}
};
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root){
bool same = true ;
if(root)
DTree(root->left,root->right,same);
return same ;
}
void DTree(TreeNode* l,TreeNode* r,bool &same){
if((l==NULL&&r!=NULL)||(r==NULL&&l!=NULL)){
same=false;
}
if(l&&r){
if(r->val!=l->val){
same = false ;
}
DTree(l->left,r->right,same);
DTree(l->right,r->left,same);
}
}
};
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
bool same = true;
STree(p,q,same);
return same ;
}
void STree(TreeNode* p, TreeNode* q,bool& same){
if((q==NULL&&p!=NULL)||(q!=NULL&&p==NULL))same=false;
if(p&&q){
if((q->val!=p->val))same = false ;
STree(p->left,q->left,same);
STree(p->right,q->right,same);
}
}
};