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

今天药忘吃喽~ 2022-04-23 09:02 198阅读 0赞

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