leetcode113

LCP 07.
首先用邻接存储每个人可以传送到的人。然后可以使用深度优先搜索，找出所有可能的传递方案。枚举每一轮传递玩家的编号和被传递玩家的编号。若当前是最后一轮且信息位于k 处，则方案总数加1。

c++

class Solution {
public:
    int res=0;
    map<int,vector<int>>g;
    int numWays(int n, vector<vector<int>>& relation, int k) {
        for(int i=0;i<relation.size();i++){
            g[relation[i][0]].push_back(relation[i][1]);
        }
        dfs(0,0,k,n);
        return res;
        
    }
    void dfs(int i,int count,int k,int n){
        if(i==n-1&&count==k){
            res++;
            return;
        }
        if(count>k)return;
        if(g[i].size()==0)return;
        for(int j=0;j<g[i].size();j++){
            dfs(g[i][j],count+1,k,n);
        }
    }
};

22. 括号生成

c++

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>res;
        string cur="(";
        dfs(cur,n,res,1,0);
        return res;
    }
    void dfs(string &cur,int n,vector<string>&res,int left,int right){
        if(cur.size()==2*n){
            res.push_back(cur);
            return;
        }
        if(left<n){
            cur=cur+'(';
            dfs(cur,n,res,left+1,right);
            cur.pop_back();
        }
        if(right<left){
            cur=cur+')';
            dfs(cur,n,res,left,right+1);
            cur.pop_back();
        }
        
    }
};

面试题13. 机器人的运动范围

c++

class Solution {
public:
    int res=0;
    int get(int n){
        int sums=0;
        while(n!=0){
            sums+=n%10;
            n/=10;
        }
        return sums;
    }
    int movingCount(int m, int n, int k) {
        vector<vector<int>> cur(m, vector<int>(n, 0));
        dfs(0,0,m,n,k,cur);
        return res;
    }
   void dfs(int x,int y,int m, int n, int k,vector<vector<int> >&cur) {
     if(x>=m||y>=n||x<0||y<0||cur[x][y]==1||get(x)+get(y)>k)return;
     res++;
     cur[x][y]=1;
     dfs(x+1,y,m,n,k,cur);
     dfs(x,y+1,m,n,k,cur);   
   }
};

python

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int res=0;
        dfs(root,res);
        return res;
    }
    int dfs(TreeNode* root,int &res){
        if(root==NULL)return 0;
        else
        {
            int leftdepth=dfs(root->left,res);
            int rightdepth=dfs(root->right,res);
            res= max(res,leftdepth+rightdepth);
            return max(leftdepth,rightdepth)+1;
        }
    }
};

112. 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

c++

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL)return false;
        sum=sum-root->val;
        if(root->left==NULL&&root->right==NULL&&sum==0)return true;
        return hasPathSum(root->left,sum)||hasPathSum(root->right,sum);
    }
};

对于113题，做一点思考，看下面两段代码：

c++

class Solution {
    vector<vector<int>>res;
    vector<int>path;
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(!root) return res;
        DFS(path,root,sum);
        return res;
    }
    void DFS(vector<int>&path,TreeNode* root, int sum)
    {
        if(root==NULL)
            return;
        path.push_back(root->val);
        sum=sum-root->val;
        if(root->left==NULL&&root->right==NULL&&sum==0)res.push_back(path);
        else
        {  
            if(root->left)
            {
                 DFS(path,root->left,sum);
                 path.pop_back();
            }
            if(root->right)
            {
                DFS(path,root->right,sum);
                path.pop_back();
            }
        }
    }
};

c++

 class Solution {
    vector<vector<int>>res;
    vector<int>path;
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {//!!!!!!
        if(!root) return res;
        DFS(path,root,sum);
        return res;
    }
    void DFS(vector<int>path,TreeNode* root, int sum)
    {
        if(root==NULL)
            return;
        path.push_back(root->val);
        sum=sum-root->val;
        if(sum==0&&root->left==NULL&&root->right==NULL)res.push_back(path);
        else
        {  
            if(root->left)
            {
                 DFS(path,root->left,sum); //!!!!!!
            }
            if(root->right)
            {
                DFS(path,root->right,sum);//!!!!!!
            }
        }
    }
};
![](2.png)

区别主要是，第一种每层递归函数都使用的一个容器，所以要加上引用，递归返回需要弹出之前的元素，而第二种是每次递归函数都复制一个容器。

17.电话号码的字母组合

c++

class Solution {
public:
   map<char,string> mp={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    vector<string>res;
    void DFS(string cur,string next_word)
    {
        if(next_word.size()==0)
            res.push_back(cur);
        else
        {
            char digit=next_word[0];
            string letters=mp[digit];
            for(int i=0;i<letters.size();i++)
            {
                cur=cur+letters.substr(i,1);
                next_word=next_word.substr(1);
                DFS(cur,next_word);
            }
        }
    }
      vector<string> letterCombinations(string digits){
          if(digits.size()==0)
              return {};
          else
              DFS("",digits);
          return res;
      }
};

93.复原IP地址

python

class Solution {
public:
       vector<string> res;
    
    vector<string> restoreIpAddresses(string s) {
        string temp;
        dfs(s,temp,0);
        return res;
    }
    
    void dfs(string s,string &temp,int num)
    {
        if(num==4){
           if(s.empty())res.push_back(temp);
        }
        else{
            if(num>0)temp+='.';
            for(int i=1;i<4&& i <= s.length();i++){
                if(valid(s.substr(0,i)))
                {
                      temp=temp+s.substr(0,i);
                     dfs(s.substr(i,s.length()-i),temp,num+1);
                     temp.erase(temp.length()-i,i);
                }
              }
                  temp.pop_back();       
           }
        }
        
 bool valid(const string& s){
        if(s.empty() || (s[0] == '0' && s.size()>1) ) return false;
        int val = stoi(s);
        if(val >= 0 && val <= 255) return true;
        return false;
    }
};