小奥的学习笔记

  • 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题目解析(191114):155&160

2019年11月14日 731点热度 0人点赞 0条评论

Leetcode 155:最小栈

题目描述

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。

示例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解题思路

看到这个题,实际上可以想到使用辅助栈来进行操作。所谓辅助栈就是用来存储每一步的最小值,数据栈自然是存储所有的数据。我们使用辅助栈和数据栈同步来做,这样的好处是思路简单,但是可能要多存一些不必要的元素。

对于push来说,这个函数操作很关键,要保证这一步辅助栈push进去的都是当前为止最小的。所以有两种情况:①辅助栈为空,自然直接push进入;②辅助栈不为空,就判断当前要push的值是否小于stack2最上面的值,如果是的话则push进去,否则不push进去。但是数据栈是直接push进去。

对于pop来说,只有数据栈和辅助栈最上面的元素一样的时候,才会pop掉辅助栈的栈顶元素。

自然,在上面的操作下,一定保证了辅助栈最上面的元素是最小的元素。所以getMin()的时候直接返回辅助栈的栈顶元素即可。

代码实现

class MinStack {
private:
    stack<int> stack1;//数据栈
    stack<int> stack2;//辅助栈
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    void push(int x) {
        stack1.push(x);
        if (stack2.empty())
            stack2.push(x);
        else if (x <= stack2.top())
            stack2.push(x);
    }
    void pop() {
        if (stack1.top() == stack2.top())
            stack2.pop();
        stack1.pop();
    }
    int top() {
        return stack1.top();
    }
    int getMin() {
        return stack2.top();
    }
};

复杂度分析

运行时间

时间复杂度:O(1),“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大,都只是有限个步骤,因此时间复杂度是:O(1)。
空间复杂度:O(N),这里N是读出的数据的个数。

Leetcode 160:相交链表

题目描述

编写一个程序,找到两个单链表相交的起始节点。

示例

示例

在节点8处相交。

解题思路

我这是属于一个比较傻瓜的思路。观察上图可知,我们可以考虑把两个指针放到相对于交点前移相同数目的位置作为基准进行往后移动,然后当两个指针相等的时候,就找到了它们的相交点。

那怎样实现这样呢?我们可以统计A链表的长度,假设为alen,统计B链表的长度,假设为blen,然后计算它们的差值clen。这样的话,将较长的链表的指针先往后移动clen就可以达到我们的目标了。

代码实现


ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {         if(!headA||!headB)             return nullptr;         ListNode *countA=headA;         ListNode *countB=headB;         int cA=0;         int cB=0;         while(countA)         {             ++cA;             countA=countA->next;         }         while(countB)         {             ++cB;             countB=countB->next;         }         /*将较长的链表实现最后边与较短的对齐*/         int lLen,sLen;         ListNode *lList;         ListNode *sList;         if(cA>cB)         {             sLen=cB;             sList=headB;             lLen=cA;             lList=headA;         }         else         {             sLen=cA;             sList=headA;             lLen=cB;             lList=headB;         }         for(int i=0;i<lLen-sLen;i++,lList=lList->next);                  while(lList!=nullptr&&sList!=nullptr)         {             if(lList==sList)                 return lList;             lList=lList->next;             sList=sList->next;         }         return nullptr;         }

复杂度

运行时间

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
已修:英语写作指导Ⅱ【UC Berkeley】[2015-09-15] C++中的cin, cin.getline, getline等混合使用时不能输入直接执行下一行的问题 西霉们,为什么这些你们不报道? 关于留学美国的一点想法 递归读目录获取普通文件个数 数据结构【浙江大学】(第4节)整理
标签聚合
leetcode python学习 Python 学习 鸟哥的linux私房菜 算法 Java 生活 linux 高中
最近评论
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号