1、150逆波兰表达式求值
我的思路： 看了代码随想录才做的。就觉得比较简单。
代码随想录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> com;
for(int i = 0;i<tokens.size();i++){
int a,b;
if(tokens[i]=="*"){
b = com.top();
com.pop();
a = com.top();
com.pop();
com.push(a*b);
}else if(tokens[i]=="/"){
b = com.top();
com.pop();
a = com.top();
com.pop();
com.push(a/b);
}
else if(tokens[i]=="+"){
b = com.top();
com.pop();
a = com.top();
com.pop();
com.push(a+b);
}else if(tokens[i]=="-"){
b = com.top();
com.pop();
a = com.top();
com.pop();
com.push(a-b);
}else{
com.push(std::stoi(tokens[i]));
}
}
return com.top();
}
};
|
2、239滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
我的思路： 没做出来。首先最直接能想到的是对每个滑动窗口都求一遍最大值，这样是挺简单的。但是，我们在滑动窗口的时候其实后面的窗口和前面的窗口是重叠的，如果对每个滑动窗口都求一遍最大值无疑是有很多重复计算。其实前面窗口排好序之后，后面的窗口也只需比较最后一个元素就能排序，再退一步，我们其实我们除了需要知道窗口里的元素，额外只要知道第二大的的元素就行，下一个窗口只要和第二大的元素或最大的元素比较就可以。
代码随想录： 单调队列。单调队列维护所有具有单调性的元素。不更改元素的顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
int right = 0,left = 0;
for(right = 0;right<nums.size();right++){
if(right >= k && nums[right-k]==dq.front()){
dq.pop_front();
}
while(1){
if(!dq.empty() && nums[right]>dq.back()){
dq.pop_back();
}else{
dq.emplace_back(nums[right]);
break;
}
}
if(right >= k-1){
res.emplace_back(dq.front());
}
}
return res;
}
}
class Solution {
private:
class MyQueue {
public:
deque<int> que;
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
int front() {
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
for (int i = 0; i < k; i++) {
que.push(nums[i]);
}
result.push_back(que.front());
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]);
que.push(nums[i]);
result.push_back(que.front());
}
return result;
}
};
|
3、347前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。
我的思路： 很容易想到的思路，用一个map存储元素出现次数，最后对map排序一遍。如果使用unordered_map则不支持排序需要重新拷贝到vector里。
代码随想录： 同样使用map去记录元素的频率，然后用一个优先级队列（小顶堆）去排序，优先级队列维持k的大小，这样排序只需要对k个元素排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
auto cmp = [](pair<int,int> &last,pair<int,int> &cur){
return last.second > cur.second;
};
unordered_map<int,int> mp;
for(int i = 0;i<nums.size();i++){
mp[nums[i]]++;
}
std::vector<std::pair<int, int>> vec(mp.begin(), mp.end());
std::sort(vec.begin(),vec.end(),cmp);
vector<int> res;
int i = 0;
for(auto &it:vec){
if(i++>=k)break;
res.emplace_back(it.first);
}
return res;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
auto cmp = [](pair<int,int> &newit,pair<int,int> &oldit){
return newit.second > oldit.second;
};
unordered_map<int,int> mp;
for(int i = 0;i<nums.size();i++){
mp[nums[i]]++;
}
priority_queue<pair<int,int>,deque<pair<int,int>>,decltype(cmp)> pq(cmp);
int i=1;
for(auto &it:mp){
if(i>k){
if(it.second > pq.top().second){
pq.emplace(it);
pq.pop();
}
}else{
pq.emplace(it);
}
i++;
}
vector<int> res(pq.size());
for(int j = res.size()-1;j>=0;j--){
res[j] = pq.top().first;
pq.pop();
}
return res;
}
};
|
代码随想录算法训练第十一天|150逆波兰表达式求值|239滑动窗口最大值|347前K个高频元素
