深度优先搜索算法练习入门

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 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);
        }
    }
};