LeetCode 刷题 -- Day 5

时间：2024-04-29 17:20:45

今日题目

题目 难度 备注
232. 用栈实现队列 简单
225. 用队列实现栈 简单
20. 有效的括号 简单
1047. 删除字符串中的所有相邻重复项 简单 有所得：string也为栈
150. 逆波兰表达式求值 中等
239. 滑动窗口最大值 困难 通过模拟优化代码
347. 前 K 个高频元素 中等 ⭐⭐⭐

栈和队列篇

  • 今日题目
  • 题目：232. 用栈实现队列
    • 一、源代码
    • 二、代码思路
  • 题目：225. 用队列实现栈
    • 一、源代码
    • 二、代码思路
  • 题目：20. 有效的括号
    • 一、源代码
    • 二、代码思路
  • 题目：1047. 删除字符串中的所有相邻重复项
    • 一、源代码
    • 二、优化思路
    • 三、优化代码
  • 题目：150. 逆波兰表达式求值
    • 一、源代码
    • 二、代码思路
    • 三、优化思路
  • 题目：239. 滑动窗口最大值
    • 一、源代码
    • 二、代码思路
    • 三、优化思路
    • 四、优化代码
    • 五、所得
  • 题目：347. 前 K 个高频元素
    • 一、源代码
    • 二、思路与问题
    • 三、优化思路
    • 四、优化代码

题目：232. 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

一、源代码

class MyQueue {
private:
    stack<int> inStk, OutStk;
    void inToOut() {
        while (!inStk.empty()) {
            OutStk.push(inStk.top());
            inStk.pop();
        }
    }

public:
    MyQueue() {}
    void push(int x) { inStk.push(x); }
    int pop() {
        if (OutStk.empty()) {
            inToOut();
        }
        int x = OutStk.top();
        OutStk.pop();
        return x;
    }
    int peek() {
        if (OutStk.empty()) {
            inToOut();
        }
        return OutStk.top();
    }
    bool empty() {
        return inStk.empty() && OutStk.empty();
    }
};

二、代码思路

利用双栈实现先入先出队列，可以考虑如下规则：

① 设定输入栈 inStk 和 输出栈 outStk，inStk存输入，为倒序（先进后出）outStk存正序（先进先出）。

② 对于push 操作的实现，直接push存入 inStk，对于pop 操作，直接对outStk栈执行pop。队列的front 即为outStk 的top。若outStk栈为空，则把inStk中的元素都push 到outStk 中。

③ 若 inStk 和 outStk 都为空，则队列为空。

题目：225. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

一、源代码

class MyStack {
private:
    queue<int> q, temp;
    void inQue() {
        while (!temp.empty()) {   temp中暂存的元素还给 q
            int front = temp.front();
            q.push(front);
            temp.pop();
        }
    }

public:
    MyStack() {}
    void push(int x) { q.push(x); }
    int pop() {
        while (q.size() > 1) { // 使q只剩队尾一个元素,即为要pop的元素
            int front = q.front();
            temp.push(front); // temp 暂存q 的非队尾元素
            q.pop();
        }
        int x = q.front();
        q.pop();
        inQue(); 
        return x;
    }

    int top() { return q.back(); }

    bool empty() { return q.empty();}
};

二、代码思路

利用双队列实现先入后出栈，可以考虑如下规则：

① 设定操作队列q 和辅助队列temp , q 用于执行各种操作，temp 用于在执行pop 操作时，暂存q中的非队尾元素。

② 对于push 操作的实现，直接push存入q，对于pop 操作，先把q 中的非队尾元素按序存入 temp，q 的队尾即为要pop的元素，把队尾元素pop后，再将temp中的元素按序存入q。栈的top 即为 q的队尾元素。

③ 若 q为空，则队列为空。

题目：20. 有效的括号

20. 有效的括号 - 力扣（LeetCode）

一、源代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (int i = 0; i < s.size(); i++) {  
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {  //左括号进栈
                stk.push(s[i]);
            }else{    //右括号判断，当栈为空或者栈顶元素不匹配，则return false
                if(stk.empty()) return false;
                char top = stk.top();
                if (s[i] == ')') {
                    if (top != '(') return false;
                    else stk.pop();
                }
                if (s[i] == '}') {
                    if (top != '{') return false;
                    else stk.pop();
                }
                if (s[i] == ']') {
                    if (top != '[') return false;
                    else stk.pop();
                }
            }
        }
        return stk.empty();  //遍历字符串后，栈为空才有效
    }
};

二、代码思路

定义 char型栈，遍历字符串s，遇到左括号则进栈，遇到右括号判断：当栈为空或者栈顶元素不匹配，则return false。当遍历完字符串时，此时栈为空才有效。

题目：1047. 删除字符串中的所有相邻重复项

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

一、源代码

class Solution {
public:
    string removeDuplicates(string s) {
        stack<int> stk;
        for (int i = 0; i < s.size(); i++) {
            if (stk.empty()) {      //栈为空或者栈顶元素不等于s[i] ，则将s[i] 压入栈
                stk.push(s[i]);
            }else {
                int top = stk.top();
                if (s[i] != top) {
                    stk.push(s[i]);
                }else {           //否则对栈执行pop 操作
                    stk.pop();
                }
            }
        }
        s = "";    //最后将栈中元素倒着输出。
        while (!stk.empty()) {  
            s += stk.top();
            stk.pop();
        }
        reverse(s.begin(),s.end());
        return s;
    }
};

二、优化思路

本题思路很简单，用栈实现。遍历字符串s，栈为空或者栈顶元素不等于s[i] ，则将s[i] 压入栈。否则对栈执行pop 操作。最后将栈中元素倒着输出就行。

但其实本题不需要定义栈，string 本身就有类似 进栈、出栈的存在，直接定义string就行

三、优化代码

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;
        for (char ch : s) {
            if (!stk.empty() && stk.back() == ch) {
                stk.pop_back();
            } else {
                stk.push_back(ch);
            }
        }
        return stk;
    }
};

题目：150. 逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

一、源代码

class Solution {
private:
    int getNum(string s) {  //将字符串转化为数字
        int sum = 0, i = 0, flag = 0; // 初始假定为正数，从 i = 0 开始遍历
        if (s[i] == '-') { // 为负数，则置 flag 为 1，从 i = 1 开始遍历
            i = 1;
            flag = 1;
        }
        while (i < s.size()) {
            sum *= 10;
            sum += s[i++] - '0';
        }
        return (flag = =0) ? sum : -sum;
    }

public:
    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        for (int i = 0; i < tokens.size(); i++) {
            if ((tokens[i][0] >= '0' && tokens[i][0] <= '9') || (tokens[i][0] == '-' && tokens[i] != "-")) {  //为数字，则压栈
                int x = getNum(tokens[i]);
                nums.push(x);
            } else if(nums.size() > 1) { //为操作符则计算
                int num1 = nums.top(); nums.pop();
                int num2 = nums.top(); nums.pop();
                if (tokens[i] == "+") nums.push(num2 + num1);
                if (tokens[i] == "-") nums.push(num2 - num1);
                if (tokens[i] == "*") nums.push(num2 * num1);
                if (tokens[i] == "/") nums.push(num2 / num1);
            }
        }
        return nums.top();
    }
};

二、代码思路

逆波兰式求值，可遍历字符串并采用如下方法：

① 定义存储 int 数据类型的栈，遇到 数字 则压入栈。

② 遇到操作符则取出栈顶两个元素，进行相应操作（注意顺序），然后再压入栈。

三、优化思路

利用库函数 atoi(token.c_str()) ，可直接将 string 数字串转化为相应的 int 型整数（token为string 类串）

// 把参数 str 所指向的字符串转换为一个整数（类型为 int 型）。但不适用于string类串
// 可以使用string对象中的c_str()函数进行转换
int atoi(const char *str)
    
// 返回一个指向正规c字符串的指针，内容与string串相同。将string对象转换为c中的字符串样式。
const char *c_str()
    
//案例
    char s[5]="123";
    int a = atoi(s);
    cout << a << endl;     // 输出：123
    string ss="abcd";
    char b[20];
    strcpy(b,ss.c_str());  // c_str()函数返回的是一个指针，可以使用字符串复制函数strcpy()来操作返回的指针。
    cout<<b<<endl;         // 输出：abcd
    return 0;

题目：239. 滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

一、源代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<int> q;
        vector<int> ans;
        for (int left = 0, right = k-1; right < nums.size(); ++left, ++right) {
           while(!q.empty()) q.pop();
            for (int i = left; i <=right ; ++i) {
                q.push(nums[i]);
            }
            ans.push_back(q.top());
        }
        return ans;
    }
};

二、代码思路

定义优先级队列，自动排序，队首元素即为最大值。再定义双指针，不断移动窗口，并将窗口的最大值存入ans数组中。

三、优化思路

每次都将优先级队列清空，再把窗口元素全部存入队列中。这样耗时太多。其实是可以优化的，模拟过程，发现窗口的移动每次都是删除第一个，再增加一个。也就是说不用清空再重新存，而是删除一个增加一个就行了。

可是优先级队列已经打乱了元素顺序，要按排列顺序在队列中删除一个并增加一个怎么办呢？元素和下标的结合用pair，定义priority_queue<pair<int, int>> q;

四、优化代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {   //初始化窗口
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {           //移动窗口
            q.emplace(nums[i], i);              //按序增加一个
            while (q.top().second <= i - k) {   //按序删除一个
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

五、所得

c++11 新标准引入了三个新成员------- emplace_front，emplace 和 emplace_back，这些操作构造而不是拷贝元素，因此相比push_back 等函数能更好地避免内存的拷贝与移动，使容器插入元素的性能得到进一步提升。
这些操作分别对应 push_front，insert 和 push_back，能够让我们把元素放置在容器头部，一个指定位置之前或容器尾部

//用法
c.emplace_back(t)    // 在c的尾部创建一个值为t的元素
c.emplace_front(t)   // 在c的头部创建一个值为t的元素
c.emplace(p,t)       // 在迭代器p所指向的元素之前创建一个值为t的元素，返回指定新添加元素的迭代器

题目：347. 前 K 个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

一、源代码

class Solution {
private:
    typedef pair<int, int> PAIR;
    static bool cmp_val(const PAIR& left, const PAIR& right) {  // static 不可省略
        return left.second > right.second;
    }

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;                // 不能用 map，得用unordered_map
        for (int i = 0; i < nums.size(); i++) {    // 记录数组元素和出现的次数
            mp[nums[i]]++;
        }
        vector<PAIR> cnt(mp.begin(), mp.end());    // map不能直接对value 自定义排序，得化成 pair
        sort(cnt.begin(), cnt.end(), cmp_val);     // 自定义排序sort一下
        vector<int> ans;
        for (int i = 0; i < k; ++i) {              // 输出前 k 个
            int x = cnt[i].first;
            ans.push_back(x);
        }
        return ans;
    }
};

二、思路与问题

用map 记录数组元素和出现的次数，再对 map 的值自定义排序，最后输出前 k 个。其中出现以下问题：

① 自定义排序函数 cmp_val 得用 static 修饰，不然报错。

② 用map<int, int> 的话，当数组元素很多的话结果会出错。得用unordered_map

map内部使用红黑数（一种自平衡二叉查找树）来实现，而unordered_map则使用哈希表来实现。这意味着，在map中，元素是按照键的大小进行有序排列的，而在unordered_map中，则不保证元素的顺序。

③ map不能直接对值 value 自定义排序，得化成 pair，再对pair 的second 进行 自定义排序。

三、优化思路

当用unordered_map<int, int> 记录数组元素和出现的次数后，可用堆的思想来得到前 k 个。

利用优先级队列 priority_queue 来实现堆。因为要实现自定义排序，所以优先级队列的格式应该为：

priority_queue<int, vector<int> , cmp> q; 而 压入队列中的元素为 pair<int, int> 型数据，所以优先级队列的定义为：

 priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;

四、优化代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(auto& c:nums){
            map[c]++;
        }
        //2.利用优先队列，将出现次数排序
        //自定义优先队列的比较方式，小顶堆
        struct myComparison{
            bool operator()(pair<int,int>&p1,pair<int,int>&p2){
                return p1.second>p2.second;//小顶堆是大于号
            }
        };
        //创建优先队列
        priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison> q;
        //遍历map中的元素
        //1.管他是啥，先入队列，队列会自己排序将他放在合适的位置
        //2.若队列元素个数超过k，则将栈顶元素出栈（栈顶元素一定是最小的那个）
        for(auto& a:map){
            q.push(a);
            if(q.size()>k){
               q.pop(); 
            }
        }
        //将结果导出
        vector<int>res;
        while(!q.empty()){
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;
    }
};

相关文章