小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

leetcode题目解析(191106)

2019年11月7日 725点热度 0人点赞 0条评论

Leetcode 236:二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

解题思路

参考:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-jian-j/

两个节点p,q分为两种情况:
* p和q在相同子树中
* p和q在不同子树中

从根节点遍历,递归向左右子树查询节点信息
递归终止条件:如果当前节点为空或等于p或q,则返回当前节点

递归遍历左右子树,如果左右子树查到节点都不为空,则表明p和q分别在左右子树中,因此,当前节点即为最近公共祖先;
如果左右子树其中一个不为空,则返回非空节点。

代码实现

 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) {
        return root;
    }
    return left ? left : right;
}

算法性能

复杂度配图

Leetcode 238:除自身以外数组的乘积

题目描述

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例

输入: [1,2,3,4];输出: [24,12,8,6]

解题思路1

这个题不需要想太多,可以这样想,每一个输出结果的第i个值等于输入数组的0~i-1乘积和i+1~m(m为输入数组长度),然后进行相乘。具体看代码。

代码实现1

vector<int> productExceptSelf(vector<int>& nums) {
    //先左再右
    vector<int>resleft(nums.size(), 1);
    for (int i = 1; i < nums.size(); i++)
    {
        resleft[i] = resleft[i - 1] * nums[i - 1];
        //cout << resleft[i] << " ";
    }
    //cout << endl;
    vector<int>resright(nums.size(), 1);
    for (int i = nums.size() - 2; i >= 0; i--)
    {
        resright[i] = resright[i + 1] * nums[i + 1];
        //cout << resright[i] << " ";
    }
    //cout << endl;
    vector<int>result(nums.size(), 1);
    for (int i = 0; i < nums.size(); i++)
    {
        result[i] = resleft[i] * resright[i];
    }
    return result;
}

复杂度1

空间复杂度:O(n),时间复杂度O(n)

leetcode238resultzjz.jpg

解题思路2

用一个常数k代替resleft数组。

代码实现2

vector<int> productExceptSelf(vector<int>& nums) {
    //先左再右
    vector<int>result(nums.size(), 1);
    int k = 1;
    for (int i = 0; i < result.size(); i++) {
        result[i] = k;
        k *= nums[i];
    }
    k = 1;
    for (int i = result.size() - 1; i >= 0; i--)
    {
        result[i] *= k;
        k *= nums[i];
    }
    return result;
}

复杂度2

空间复杂度:O(1),时间复杂度O(n)

复杂度配图

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年11月7日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
吴恩达深度学习课程DeepLearning.ai笔记(2-1) WP 嘀:嘀咕的 WordPress 插件 vivo2018秋招软件开发笔试题 Python第四周内置函数等学习笔记 Java语言程序设计【学堂在线】编程作业(第二章) 2022年的第一篇碎碎念
标签聚合
python学习 鸟哥的linux私房菜 高中 Java linux leetcode 生活 Python 学习 算法
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号