首页 > 编程学习 > 剑指offer-树2m栈队列2e1m1h-10

剑指offer-树2m栈队列2e1m1h-10

发布时间:2022/1/17 12:14:00

目录

  • [JZ86 (m)在二叉树中找到两个节点的最近公共祖先][1]
  • [JZ68 (m)二叉搜索树的最近公共祖先][2]
  • [JZ9 (e)用两个栈实现队列][3]
  • [JZ30 (e)包含min函数的栈][4]
  • [JZ31 (m)栈的压入、弹出序列][5]
  • [JZ73 (h)翻转单词序列][6]
  • 今天学到的知识


JZ86 (m)在二叉树中找到两个节点的最近公共祖先

  • 朴素的想法:先dfs,记录经过的路径,找到对应的值之后返回;然后比较dfs得到的两条路径(数组),从头开始找最后一个相同值;
  • 复杂度:时间 O ( n ) O(n) O(n)(两次dfs+一次遍历),空间 O ( n ) O(n) O(n)(递归调用栈+路径保存用的数组)
class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int> first,second;
        bool isfind=false;
        dfs(root, o1, isfind, first);
        isfind = false;
        dfs(root, o2, isfind, second);
        int i=0;
        for(;i<first.size()||i<second.size();++i){
            if(first[i]!=second[i])break;
        }
        return first[i-1];
    }
    
    void dfs(TreeNode *cur, int val, bool &isfind, vector<int> &path){
        if(!cur || isfind) return;
        path.push_back(cur->val);
        if(cur->val==val) {
            isfind=true;
            return;
        }
        if(!isfind) dfs(cur->left, val, isfind, path);
        if(!isfind) dfs(cur->right, val, isfind, path);
        if(!isfind) path.pop_back();
    }
};
  • 其实可以直接dfs,见下一题。

JZ68 (m)二叉搜索树的最近公共祖先

  • 直接dfs
  • 复杂度:时间 O ( n ) O(n) O(n)(一次dfs),空间 O ( n ) O(n) O(n)(递归调用栈)
  • 注意,使用!p判断指针p是否为空时,要将p显式初始化为nullptr,要不然编译器可能进行不可预知的初始化,导致判断出错
class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        return dfs(root, p, q)->val;
    }
    TreeNode* dfs(TreeNode *root, int p, int q){
        if(!root||root->val==p||root->val==q) return root;
        TreeNode *left=nullptr, *right=nullptr; // 此处注意
        // 下面两行的if判断是基于二叉搜索树的性质进行剪枝,若此树非二叉搜索树,也可以直接dfs,把if判断去掉即可
        if(p<root->val||q<root->val) left=dfs(root->left, p, q);  
        if(p>root->val||q>root->val) right=dfs(root->right, p, q);
        if(!left) return right;
        if(!right) return left;
        return root;
    }
};

JZ9 (e)用两个栈实现队列

  • 一个栈为主,一个栈辅助
    当需要pop的时候,若辅助栈不为空,直接pop辅助栈;若辅助栈为空,就将主栈的元素转移到辅助栈
  • 复杂度:时间 O ( 1 ) O(1) O(1)(插入和删除的平均复杂度均为),空间 O ( n ) O(n) O(n)(两个栈)

JZ30 (e)包含min函数的栈

  • 使用辅助栈记录当前最小值,只在push的时候进行处理
    若push进来的数比辅助栈顶数大,则将其赋值为栈顶元素值,再push;其他情况直接push
  • 复杂度:时间 O ( 1 ) O(1) O(1)(四种操作复杂度均为),空间 O ( n ) O(n) O(n)(两个栈)

JZ31 (m)栈的压入、弹出序列

  • 使用辅助栈+一个指针,模拟站的压入弹出操作,若遍历完成之后栈不为空或者指针没有指向弹栈序列末尾,就说明压入弹出序列不对应。
  • 复杂度:时间 O ( n ) O(n) O(n),空间 O ( n ) O(n) O(n)(辅助栈)

JZ73 (h)翻转单词序列

  • 使用stringstream处理
  • 复杂度:时间 O ( n ) O(n) O(n),空间 O ( n ) O(n) O(n)(两个stringstream流)
class Solution {
public:
    string ReverseSentence(string str) {
        istringstream iss(str);
        ostringstream oss;
        stack<string> s;
        string tmp;
        while(iss>>tmp) s.push(tmp);
        while(!s.empty()){
            oss<<s.top();
            s.pop();
            if(!s.empty()) oss<<' ';
        }
        return oss.str();
    }
};

今天学到的知识

  • std::stringstream
  • 使用!p判断指针p是否为空时,要将p显式初始化为nullptr,要不然编译器可能进行不可预知的初始化,导致判断出错
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000