• 代码随想录第七章 栈与队列

    1、leecode232 用栈实现队列

    使用栈模拟队列的行为，仅使用一个栈是不行的，所以需要两个栈，一个是输入栈，一个是输出栈。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. class MyQueue {
    9.  private:
    10. 	stack<int> stack_in;
    11. 	stack<int> stack_out;
    12.  public:
    13. 	void push(int value) {
    14. 		stack_in.push(value);
    15. 	}
    16. 	int pop() {
    17. 		if (stack_out.empty()) {
    18. 			while (!stack_in.empty()) {
    19. 				stack_out.push(stack_in.top());
    20. 				stack_in.pop();
    21. 			}
    22. 		}
    23. 		int result = stack_out.top();
    24. 		stack_out.pop();
    25. 		return result;
    26. 	}
    27. 	int top() {
    28. 		if (stack_out.empty()) {
    29. 			while (!stack_in.empty()) {
    30. 				stack_out.push(stack_in.top());
    31. 				stack_in.pop();
    32. 			}
    33. 		}
    34. 		int result = stack_out.top();
    35. 		return result;
    36. 	}
    37. 	bool empty() {
    38. 		return stack_in.empty() && stack_out.empty();
    39. 	}
    40. };
    41.  
    42.  
    43. void main() {
    44. 	
    45. 	MyQueue queue;
    46. 	queue.push(1);
    47. 	queue.push(2);
    48. 	queue.push(3);
    49. 	cout << "the first value: " << queue.pop() << endl;
    50. 	cout << "the next value: " << queue.pop() << endl;
    51. 	cout << "the next value: " << queue.pop() << endl;
    52. 	cout << "hello world" << endl;
    53. }

    2、用队列实现栈。 leetcode225

    队列的规则是先进先出，把一个队列中的数据导入另一个队列，数据的顺序并没有变。所以用栈实现队列和用队列实现栈的思路是不一样的，取决于这两个数据结构的性质。如果用两个对列实现栈，那么两个队列就没有输入队列和输出队列的关系，另一个队列完全是用来备份的。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. class MyStack {
    9.  private:
    10. 	queue<int> queue_fir;
    11. 	queue<int> queue_sec;
    12.  public:
    13. 	void push(int val) {
    14. 		queue_fir.push(val);
    15. 	}
    16. 	int pop() {
    17. 		int size = queue_fir.size();
    18. 		size--;
    19. 		while (size--) {
    20. 			queue_sec.push(queue_fir.front());
    21. 			queue_fir.pop();
    22. 		}
    23. 		int result = queue_fir.front();
    24. 		queue_fir.pop();
    25. 		queue_fir = queue_sec;
    26. 		while (!queue_sec.empty()) {
    27. 			queue_sec.pop();
    28. 		}
    29. 		return result;
    30. 	}
    31. 	int top() {
    32. 		return queue_fir.back();
    33. 	}
    34. 	bool empty() {
    35. 		return queue_fir.empty();
    36. 	}
    37. };
    38.  
    39.  
    40. void main() {
    41. 	
    42. 	MyStack stack;
    43. 	stack.push(1);
    44. 	stack.push(2);
    45. 	stack.push(3);
    46. 	cout << stack.pop() << endl;
    47. 	cout << stack.pop() << endl;
    48. 	cout << stack.pop() << endl;
    49. 	cout << "hello world" << endl;
    50. }

    3、匹配括号 leetcode20

    这里有三种不匹配的情况

    （1）、第一种情况，字符串中左方向的括号多余了，所以不匹配。

    第一种情况：已经遍历了字符串，但是栈不为空，说明有相应的左括号，但没有右括号，所以返回错误。

    （2）、第二种情况，括号没有多余，但是括号的类型不匹配。

    在遍历字符串的过程中，发现栈中没有要匹配的字符，返回错误。

    （3）、第三种情况，字符串中右方向的括号多余了，所以不匹配。

    在遍历字符串的过程中栈已经为空，没有匹配的字符了，说明右括号没有找到对应的左括号，返回错误。

    那么什么时候说明左括号和右括号全部匹配了呢？如果遍历字符串之后，栈是空的，则说明全都匹配了。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. class Solution {
    9.  private:
    10. 	stack<int> st;
    11.  public:
    12. 	bool IsValid(string& s) {
    13. 		for (int i = 0; i < s.size(); i++) {
    14. 			if (s[i] == '(') {
    15. 				st.push(')');
    16. 			}
    17. 			else if (s[i] == '{') {
    18. 				st.push('}');
    19. 			}
    20. 			else if (s[i] == '[') {
    21. 				st.push(']');
    22. 			}
    23. 			else if (st.empty() || st.top() != s[i]) {
    24. 				return false;
    25. 			}
    26. 			else {
    27. 				st.pop();
    28. 			}
    29. 		}
    30. 		return st.empty();
    31. 	}
    32. };
    33.  
    34.  
    35. void main() {
    36. 	string s = "(){}[]{[]}";
    37. 	Solution slo;
    38. 	slo.IsValid(s);
    39. 	cout << "hello world" << endl;
    40. }

    4、滑动窗口最大值 leetcode239

    一个大小为k的滑动窗口，从前向后在数组nums上移动，返回滑动窗口每移动一次时窗口中的最大值。

    （1）、设计单调对列，设计的时候，pop和push操作保持如下规则：

    pop()：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不进行任何操作。

    push()：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于或等于队列入口元素的数值。

    基于以上规则，每次窗口移动的时候，只要调用que.front()就可以返回当前窗口的最大值。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. using namespace std;
    8.  
    9. //单调队列，从大到小
    10. class MyQueue {
    11.  private:
    12. 	deque<int> que;
    13. 	//使用deque实现单调队列
    14.  public:
    15. 	//每次弹出元素时，比较当前要弹出元素的数值是否等于队列出口元素的数值，如果相等则弹出。
    16. 	//弹出元素之前，需要判断队列当前是否为空
    17. 	void pop(int value) {
    18. 		if (!que.empty() && value == que.front()) {
    19. 			que.pop_front();
    20. 		}
    21. 	}
    22. 	//如果要push的数组大于入口元素的数值，那么就将队列入口元素弹出，知道push的数值小于或等于对列入口元素的数值。
    23. 	//这样就保持了队列中的数值是从大到小的单调递减了。
    24. 	void push(int value) {
    25. 		while (!que.empty() && value > que.back()) {
    26. 			que.pop_back();
    27. 		}
    28. 		que.push_back(value);
    29. 	}
    30. 	int front() {
    31. 		return que.front();
    32. 	}
    33. };
    34.  
    35. void main() {
    36. 	cout << "hello world" << endl;
    37. }

    这样就用deque实现了一个单调队列，接下来解决求滑动窗口最大值的问题就简单了。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. using namespace std;
    8.  
    9. class Slotuion {
    10.  private:
    11. 	//单调队列，从大到小
    12. 	class MyQueue {
    13. 	 private:
    14. 		deque<int> que;
    15. 		//使用deque实现单调队列
    16. 	 public:
    17. 		//每次弹出元素时，比较当前要弹出元素的数值是否等于队列出口元素的数值，如果相等则弹出。
    18. 		//弹出元素之前，需要判断队列当前是否为空
    19. 		void pop(int value) {
    20. 			if (!que.empty() && value == que.front()) {
    21. 				que.pop_front();
    22. 			}
    23. 		}
    24. 		//如果要push的数组大于入口元素的数值，那么就将队列入口元素弹出，知道push的数值小于或等于对列入口元素的数值。
    25. 		//这样就保持了队列中的数值是从大到小的单调递减了。
    26. 		void push(int value) {
    27. 			while (!que.empty() && value > que.back()) {
    28. 				que.pop_back();
    29. 			}
    30. 			que.push_back(value);
    31. 		}
    32. 		int front() {
    33. 			return que.front();
    34. 		}
    35. 	};
    36.  private:
    37. 	MyQueue que;
    38.  public:
    39. 	vector<int> MaxSlidingWindow(vector<int> &input,int k) {
    40. 		vector<int> result;
    41. 		for (int i = 0; i < k; i++) {
    42. 			que.push(input[i]);
    43. 		}
    44. 		result.push_back(que.front());
    45. 		for (int i = k; i < input.size(); i++) {
    46. 			que.push(input[i]);
    47. 			que.pop(input[i - k]);
    48. 			result.push_back(que.front());
    49. 		}
    50. 		return result;
    51. 	}
    52. };
    53.  
    54. void main() {
    55. 	vector<int> input = { 2,4,-2,-4,3,1,5 };
    56. 	int k = 4;
    57. 	Slotuion slo;
    58. 	slo.MaxSlidingWindow(input, k);
    59. 	cout << "hello world" << endl;
    60. }

    5、前K个高频元素 leetcode347

    在一个数组中找到出现频率前k高的元素。

    这道题目主要涉及如下三个部分：

    (1)、统计元素出现的次数；

    (2)、对次数进行排序；

    (3)、找出前k个高频元素。

    首先统计元素出现的次数，可以使用map进行统计。然后对次数进行排序，这里可以使用一种容器适配器即优先级对列。

    优先级队列是一个拥有权值的queue，其内部元素按照元素的权值排列。权值较高者排在最前优先出队。其中缺省情况下系统是通过一个max-heap以堆实现完成排序特性，表现为一个vector表现的完全二叉树。

    1、优先级队列介绍

    这是一个queue，所以只允许在底端加入元素，并从顶端取出元素。
    但是优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。权值最高者排在最前面。
    缺省的情况下维护的是一个大堆，即权值以从高到低排列。

    其中Type代表数据类型，Container代表容器类型，缺省状态为vector; Functional是比较方式，默认采用的是大顶堆(less<>)。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8.  
    9.  
    10. class Solution {
    11.  public:
    12. 	class MyCompare {
    13. 	 public:
    14. 		bool operator()(const pair<int,int>& lhs, const pair<int, int>& rhs) {
    15. 			return lhs.second > rhs.second;
    16. 		}
    17. 	};
    18. 	vector<int> TopKFrequent(vector<int>& input, int k) {
    19. 		unordered_map<int, int> map;
    20. 		for (int i = 0; i < input.size(); i++) {
    21. 			map[input[i]]++;
    22. 		}
    23. 		priority_queueint,int>,vectorint,int>>, MyCompare> pri_que;
    24. 		for (auto iter = map.begin(); iter != map.end(); iter++) {
    25. 			pri_que.push(*iter);
    26. 			if (pri_que.size() > k) {
    27. 				pri_que.pop();
    28. 			}
    29. 		}
    30. 		vector<int>result(k);
    31. 		for (int i = k - 1; i >= 0; i--) {
    32. 			result[i] = pri_que.top().first;
    33. 			pri_que.pop();
    34. 		}
    35. 		return result;
    36. 	}
    37. 	
    38. };
    39.  
    40.  
    41.  
    42. void main() {
    43. 	vector<int> input = { 2,2,2,2,2,3,3,3,1 };
    44. 	int k = 2;
    45. 	Solution slo;
    46. 	slo.TopKFrequent(input, k);
    47. 	
    48. 	cout << "hello world" << endl;
    49. }

    5、接雨水 leetcode42

    给出一排宽度为1，高度为n的柱子，求可以接到雨水的面积。

    输入：height=[1,0,2,1,3,1,0,1,2,0,1]。输出为7.

    （1）、双指针解法

    从头遍历所有的列，注意第一个柱子和最后一个柱子不接雨水，整体代码如下。

    1. #include
    2. #include
    3.  
    4. using namespace std;
    5.  
    6. //双指针算法
    7. class Solution {
    8.  public:
    9. 	 int Trap(vector<int>& height) {
    10. 		 int sum = 0;
    11. 		 for (int i = 0; i < height.size(); i++) {
    12. 			 if (i == 0 || i == height.size() - 1) {
    13. 				 continue;
    14. 			 }
    15. 			 int rheight = height[i];
    16. 			 int lheight = height[i];
    17. 			 // 找到右边那个最大的柱子
    18. 			 for (int r = i + 1; r < height.size(); r++) {
    19. 				 if (height[r] > rheight) {
    20. 					 rheight = height[r];
    21. 				 }
    22. 			 }
    23. 			 //找到左边最大的柱子
    24. 			 for (int l = i - 1; l >= 0; l--) {
    25. 				 if (height[l] > lheight) {
    26. 					 lheight = height[l];
    27. 				 }
    28. 			 }
    29. 			 int h = min(rheight, lheight) - height[i];
    30. 			 if (h > 0) {
    31. 				 sum = sum + h;
    32. 			 }
    33. 		 }
    34. 		 return sum;
    35. 	}
    36. };
    37.  
    38. void main() {
    39. 	vector<int> height = { 1,0,2,1,3,1,0,1,2,0,1 };
    40. 	Solution slo;
    41. 	slo.Trap(height);
    42. 	cout << "hello world" << endl;
    43. }

  • 相关阅读:
    Android RecyclerView使用ListAdapter高效刷新数据
    【C++】运算符重载
    1 分钟 Serverless 搭建你的首个个人网站（完成就送猫超卡）
    什么是网络编程？
    Django后端开发——中间件
    EMI改善
    使用Testconainers来进行JAVA测试
    可视化学习：如何生成简单动画让图形动起来
    ChatGPT充值，银行卡被拒绝
    【考试】常见考点知悉
  • 原文地址：https://blog.csdn.net/qq_32565805/article/details/133247062