美文网首页
Day13 左旋转字符串+二叉树的深度+二叉树中和为某一值的路径

Day13 左旋转字符串+二叉树的深度+二叉树中和为某一值的路径

作者: 吃掉夏天的怪物 | 来源:发表于2021-06-24 13:50 被阅读0次

    TODO:

    1. 左旋转字符串,余数的方法可以再看看
    2. 重做 二叉树中和为某一值的路径(就是一道典型递归)

    剑指 Offer 58 - II. 左旋转字符串(简单)

    确实简单,但是感觉这样做面试的时候会不Okay。

    reverse函数功能是逆序(或反转),多用于字符串、数组、容器。头文件是#include <algorithm>
    reverse函数用于反转在[first,last)范围内的顺序(包括first指向的元素,不包括last指向的元素),reverse函数无返回值。

    class Solution {
    public:
        string reverseLeftWords(string s, int n) {
           if(s.empty() || n>s.size()) return s;
           if(n == s.size()) { reverse(s.begin(),s.end()); return s;}
           reverse(s.begin(),s.begin()+n);
           reverse(s.begin()+n,s.end());
           reverse(s.begin(),s.end());
           return s;
    
        }
    };
    

    然后又去看题解
    感觉取余数的方法就很妙

    class Solution {
    public:
        string reverseLeftWords(string s, int n) {
            string res = "";
            for(int i = n; i < n + s.size(); i++){
                res += s[i%s.size()];
            }
            return res;
    
        }
    };
    

    剑指 Offer 55 - I. 二叉树的深度(简单)

    超级简单的两行递归。在于树的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。
    动画演示

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if(root == nullptr) return 0;
            return max(maxDepth(root->left),maxDepth(root->right))+1;
        }
    };
    

    剑指 Offer 34. 二叉树中和为某一值的路径(中等)

    做了好久,大概四十多分钟?然而效果不怎么好,可能因为我是值传递?


    image.png
    class Solution {
    public:
        vector<vector<int>> res;
        vector<vector<int>> pathSum(TreeNode* root, int target) {
            if(root == nullptr)return{};
             vector<int> temp;
             dfs(root,target,temp);  
             return res;
        }
        void dfs(TreeNode* root, int target,vector<int> temp){
            if(root == nullptr) return ;
            else{      
                target = target-root->val;
                temp.push_back(root->val);
            }
            if((root->left ==nullptr) && target ==0 && (root->right ==nullptr) ){
                res.push_back(temp);
                return ;
            };
            dfs(root->left, target,temp);
            dfs(root->right,target,temp); 
        }
    };
    

    改良版:⭐

    class Solution {
    public:
        vector<vector<int>> res;
        vector<int> path;
        vector<vector<int>> pathSum(TreeNode* root, int target) {
            if(root == nullptr)return{};
             dfs(root,target);  
             return res;
        }
        void dfs(TreeNode* root, int target){
            if(root == nullptr) return ;      
            target = target-root->val;
            path.push_back(root->val);
            if((root->left ==nullptr) && target ==0 && (root->right ==nullptr) ){
                res.push_back(path);
                path.pop_back();//注意这个pop_back();因为return会导致不能pop_back();从而影响回溯
                return ;
            };
            dfs(root->left, target);
            dfs(root->right,target);
            path.pop_back(); 
        }
    };
    

    相关文章

      网友评论

          本文标题:Day13 左旋转字符串+二叉树的深度+二叉树中和为某一值的路径

          本文链接:https://www.haomeiwen.com/subject/wlipyltx.html