小奥的学习笔记

  • 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题目解析(191115):148&152

2019年11月15日 719点热度 0人点赞 0条评论

Leetcode 148:排序链表

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

由于题目要求复杂度为O(nlogn)且空间复杂度为常数级,我们可以想到的是堆排序,但是实际上,由于是链表,其不需要借助额外的数组来存储内容,只需要通过链表直接的链接调整即可,所以对于链表来说,归并排序的空间复杂度也是O(1)。当然在使用递归的时候就不是了。

归并排序的顺序是“二分”和“合并”。那么对于链表来说,由于我们不能使用递归,所以我们可以使用迭代来进行处理。首先是二分的步骤,其过程如下图所示。

cut

对于cut这个过程,我们要做的就是,首先记录下链表的长度n,其实每一次划分,其划分出来的长度都是n>>2,也就是二分之n,所以我们只需要将一个指针从头走n/2次即可,然后将该指针的next指向空,记录下一个节点的地址为right,并返回。这样我们就记录了两个子链表的开始地址left和right,如下图所示。

cut1

代码实现如下的cut函数所示。

在cut完成之后,就需要开始“合并”。合并这个工序可以参见之前做过的合并有序链表即可,其过程不再重述,如下图所示。

merge

整个过程如下图所示。

total

代码实现

class Solution {
public:
    ListNode* cut(ListNode* head, int n)
{
    auto p = head;
    while (--n && p) {
        p = p->next;
    }
    if (!p)
        return nullptr;
    auto next = p->next;
    p->next = nullptr;
    return next;
}
//合并两个有序链表的子程序即可
ListNode* merge(ListNode* l1, ListNode* l2)
{
    ListNode dummy(0);
    auto p = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val)
        {
            p->next = l1;
            p = l1;//或者写p=p->next也可以
            l1 = l1->next;
        }
        else {
            p->next = l2;
            p = l2;//或者写p=p->next也可以
            l2 = l2->next;
        }
    }
    p->next = (l1 ? l1 : l2);
    return dummy.next;
}
ListNode* sortList(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;//dummyHead
    auto p = head;
    int length = 0;
    while (p)// the length of this linkedlist
    {
        ++length;
        p=p->next;
    }

    for (int size = 1; size < length; size <<= 1)
    {
        auto cur = dummy.next;
        auto tail = &dummy;

        while (cur) {
            auto left = cur;
            auto right = cut(left, size);//left->@->@ |断开|right->@->@->@...
            cur = cut(right, size);//left->@->@|断开|right->@->@ |断开|cur->@->...
            tail->next = merge(left, right);
            while (tail->next) {
                tail = tail->next;
            }
        }
    }
    return dummy.next;
}
};

复杂度

运行时间

Leetcode 152:乘积最大子序列

题目描述

给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

示例

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路

通过做这么多题了,看到这个题的时候,能够第一时间想到要用动态规划去完成,其思想就是遍历数组同时计算当前的最大值,然后不断更新。如果使用dp[]数组倒也能完成,但是空间复杂度太高,其实我们可以直接用一个变量直接就可以完成,这样空间复杂度将至了O(1)。

我们令imax为最大值,那么imax的递推公式可以表述如下

imax = max(imax * nums[i], nums[i]);

但是,我们的数组可能存在负值,所以会带来最大值变最小值,最小值变最大值的情况,所以我们还需要维护一个imin,其递推公式如下:

 imin = min(imin * nums[i], nums[i]);

正因为上面的原因,所以当我们当前值为负数的时候,我们需要交换一下imax和imin的值再进行计算,否则会出现混乱。

代码实现


int maxProduct(vector<int>& nums) {     int maxvalue = INT_MIN, imax = 1, imin = 1;     for (int i = 0; i < nums.size(); i++)     {         if (nums[i] < 0)         {             int tmp = imax;             imax = imin;             imin = tmp;         }         imax = max(imax * nums[i], nums[i]);         imin = min(imin * nums[i], nums[i]);         maxvalue = max(maxvalue, imax);     }     return maxvalue; }

复杂度

时间复杂度为O(n)。

运行时间

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
第四章:类与对象(二)构造函数 Java数据库设计入门 2009 S.V Beijing Travel Finally:Bye-bye,Beijing! 平遥-灵石王家大院-太原三日游记 评评95后、96后 论文阅读笔记20190521
标签聚合
生活 python学习 算法 leetcode Java 学习 高中 Python 鸟哥的linux私房菜 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号