小奥的学习笔记

  • 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题目解析(191025)

2019年10月25日 692点热度 0人点赞 0条评论

Leetcode 347:前k个高频元素

题目描述

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

说明:

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

示例

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

解题思路

一看到这种出现频率最高的k个数字这种题目,就会想到key-value pair,就自然想到map,然后就可以使用map来做。

所以我需要做的就是两步:第一步,将元素插入map中,元素值为key,出现次数为value。第二步,将map按照value进行降序排序。

由于我们没办法使用sort直接对map进行排序,这一点之前也说过,所以依旧是将其转换为一个vector,然后进行排序,只不过我这里使用lambda函数。

最后,将map前k项的key值push到result即可。

代码实现

vector<int> topKFrequent(vector<int>& nums, int k) {
    map<int, int> mymap;
    for (int i = 0; i < nums.size(); i++)
    {
        if (mymap.find(nums[i]) != mymap.end())//复杂度O(1)
            ++mymap[nums[i]];
        else
        {
            mymap.insert(pair<int, int>(nums[i], 1));
        }
    }
    vector<int>result;
    vector<pair<int, int>>mapsort(mymap.begin(), mymap.end());
    sort(mapsort.begin(), mapsort.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second; });
    int count = 0;
    for (auto it = mapsort.begin(); count < k; count++, ++it)
    {
        result.push_back(it->first);
    }
    return result;
}

代码性能

插入性能:O(logn),n个元素为O(nlogn)
排序为O(nlogn)
总的来说,时间复杂度为O(nlogn)。
符合要求
执行用时有一些高,内存消耗尚可。

复杂度配图

Leetcode 394 字符串解码

题目描述

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解题思路

这个题其实之前在做某次笔试的时候遇到过更复杂的,但是这里简单多了。利用两个栈,一个栈num用来存放存储的数字,一个栈str用来存放字符串,当识别到[的时候,将数字和前面以后的字母分别push进入两个栈,然后遇到]的时候,pop出数字,这个数字就对应着str中最上面的字符串重复的次数。

代码实现

string decodeString(string s) {
    string result = "";
    stack<int>nums;
    stack<string>str;
    int num = 0;
    int len = s.size();
    for (int i = 0; i < len; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            num = num * 10 + s[i] - '0';
        }
        else if ((s[i] >= 'a' && s[i] <= 'z')||(s[i]>='A'&&s[i]<='Z')) {
            result = result + s[i];

        }
        else if (s[i] == '[')//将‘[’前的数字压入nums栈内, 字母字符串压入strs栈内
        {
            nums.push(num);
            num = 0;
            str.push(result);
            result = "";
        }
        else if (s[i] == ']') //遇到‘]’时,操作与之相配的‘[’之间的字符,使用分配律
        {
            int times = nums.top();
            nums.pop();
            for (int j = 0; j < times; j++)
            {
                str.top() += result; //之后若还是字母,就会直接加到res之后,因为它们是同一级的运算
                 //若是左括号,res会被压入strs栈,作为上一层的运算
            }
            result = str.top();
            str.pop();
        }
    }
    return result;

}

复杂度

复杂度配图

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
算法笔记之线性规划网络流问题(1) 全国首条市内高铁济莱高铁开工建设 Leetcode题目解析(191107) leetcode题目解析(191031) 莱芜一中高三(51级)毕业生学习成果汇报 “中国国际航空体育节专题站”正式开启!
标签聚合
生活 鸟哥的linux私房菜 python学习 算法 leetcode 学习 Python linux 高中 Java
最近评论
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号