2019-10-25 118 views 评论

leetcode题目解析（191025）

标签：leetcode

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&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {
    map&lt;int, int&gt; mymap;
    for (int i = 0; i &lt; nums.size(); i++)
    {
        if (mymap.find(nums[i]) != mymap.end())//复杂度O(1)
            ++mymap[nums[i]];
        else
        {
            mymap.insert(pair&lt;int, int&gt;(nums[i], 1));
        }
    }
    vector&lt;int&gt;result;
    vector&lt;pair&lt;int, int&gt;&gt;mapsort(mymap.begin(), mymap.end());
    sort(mapsort.begin(), mapsort.end(), [](pair&lt;int, int&gt;&amp; a, pair&lt;int, int&gt;&amp; b) {return a.second &gt; b.second; });
    int count = 0;
    for (auto it = mapsort.begin(); count &lt; k; count++, ++it)
    {
        result.push_back(it-&gt;first);
    }
    return 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[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解题思路

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

代码实现

string decodeString(string s) {
    string result = "";
    stack&lt;int&gt;nums;
    stack&lt;string&gt;str;
    int num = 0;
    int len = s.size();
    for (int i = 0; i &lt; len; i++)
    {
        if (s[i] &gt;= '0' &amp;&amp; s[i] &lt;= '9')
        {
            num = num * 10 + s[i] - '0';
        }
        else if ((s[i] &gt;= 'a' &amp;&amp; s[i] &lt;= 'z')||(s[i]&gt;='A'&amp;&amp;s[i]&lt;='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 &lt; times; j++)
            {
                str.top() += result; //之后若还是字母，就会直接加到res之后，因为它们是同一级的运算
                 //若是左括号，res会被压入strs栈，作为上一层的运算
            }
            result = str.top();
            str.pop();
        }
    }
    return result;

}