Хотя стеки и очереди являются простыми структурами данных, проблемы алгоритма, решаемые с использованием этих простых структур данных, не обязательно просты.В основном мы представляем проблемы алгоритма leetcode, связанные со стеками и очередями.
Основное применение стека
leetcode 20. Действительные круглые скобки
Идеи решения проблем
- Используйте структуру данных стека для хранения «левого знака»
- Верхний элемент стека отражает ближайший соответствующий элемент во вложенной иерархии.
Код
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for (int i = 0; i < s.size(); i++){
//只有左符号才入栈
if (s[i] == '(' || s[i] == '{'|| s[i] == '['){
st.push(s[i]);
}else{
if (st.size() == 0){
return false;
}
char top = st.top();
st.pop();
char match;
if (s[i] == ')'){
match = '(';
}else if(s[i] == '}'){
match = '{';
}else{
assert(s[i] == ']');
match = '[';
}
if (top != match){
return false;
}
}
}
if (st.size() != 0){
return false;
}
return true;
}
};
аналогичная проблема
leetcode 150. Обратное вычисление польского выражения
leetcode 71. Упрощенные пути
Тесная связь между стеком и рекурсией
Давайте сначала посмотрим на предварительный обход бинарного дерева.
function preorder(node){
if(node){
cout << node -> val;
preorder(node.left);
preorder(node.right);
}
}
анализировать
Давайте посмотрим на конкретный обход, предположив, что у нас есть только три узла, родительский узел — 1, левый узел — 2, а правый узел — 3. Сначала мы вызываем функцию preorder с корневым узлом, затем вызываем функцию preorder с узлом 2, а затем вызываем функцию preorder с узлом 3. Входящие параметры трех предварительных заказов различны, так каков же порядок вызова этих трех функций? Мы можем абстрагироваться от этого, когда вызывается корневой узел, выполнение останавливается при вызове узла 2, а затем выполняется подфункция, которая является вызовом узла 2, до конца вызова узла 2, а затем вызывает подфункцию узла 3. Затем операционная система реализует такую операцию через стек. Функция, вызываемая корневым узлом, сначала помещается в стек для начала выполнения, а затем встречается узел 2 стека функций. Выполнить сразу после того, как функция узла 2 будет помещена в стек, дождаться, пока она вернет значение (или нет) после выполнения, а затем функция узла 2 будет извлечена. После того, как функция узла 2 выталкивается, функция узла 1 продолжает выполняться, а функция узла 3 активируется и выполняется немедленно.
leetcode144. Предзаказ обхода бинарных деревьев
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
preHelp(root, vec);
return vec;
}
private:
void preHelp(TreeNode* root, vector<int> &vec){
if(root){
vec.push_back(root->val);
preHelp(root->left, vec);
preHelp(root->right, vec);
}
}
};
аналогичная проблема
leetcode 94. Неупорядоченный обход бинарных деревьев
leetcode 145. Постпорядковый обход бинарных деревьев
Эмулировать рекурсию с помощью стеков
Теперь воспользуемся стеком для имитации системного стека и напишем нерекурсивную программу: сначала запихиваем правого потомка, потом левого потомка, и, наконец, заталкиваем печать, так что предварительный обход завершается за счет последнего в , первым из стека.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
struct Command{
string s; // go, print
TreeNode* node;
Command(string s, TreeNode* node): s(s), node(node){}
};
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
stack<Command> stack;
stack.push(Command("go", root));
while(!stack.empty()){
Command command = stack.top();
stack.pop();
if(command.s == "print")
res.push_back(command.node->val);
else{
assert(command.s == "go");
//stack.push(Command("print", command.node));//后序遍历
if(command.node->right)
stack.push(Command("go",command.node->right));
//stack.push(Command("print", command.node));//中序遍历
if(command.node->left)
stack.push(Command("go",command.node->left));
stack.push(Command("print", command.node));//先序遍历
}
}
return res;
}
};
int main() {
return 0;
}
аналогичная проблема
leetcode 341
Типичные области применения очередей
leetcode 102. Иерархический обход бинарных деревьев
Фактически, для очереди Queue проблема алгоритма, с которой он в основном имеет дело, - это обход в ширину (дерево: обход по порядку слоев, граф: кратчайший путь невзвешенного графа) На самом деле это обход бинарного дерева по уровням, но это вопрос собеседования для многих компаний.В обычное время мы должны уделять больше внимания применению типичных базовых структур данных.
Код
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL){
return res;
}
queue<pair<TreeNode*, int>> q;//存储节点和层级
q.push(make_pair(root, 0));
while(!q.empty()){
TreeNode* node = q.front().first;
int level = q.front().second;
q.pop();
if (res.size() == level){
res.push_back(vector<int>());
}
res[level].push_back(node->val);
if (node->left){
q.push(make_pair(node->left, level+1));
}
if (node -> right){
q.push(make_pair(node->right, level+1));
}
}
return res;
}
};
аналогичная проблема
leetcode 107
leetcode 103
leetcode 199
Обход в ширину (BFS) графов и кратчайшие пути графов
Задача о кратчайшем пути может быть решена путем обхода графа в ширину. Но на самом деле, многие алгоритмические задачи, мы используем для решения идею кратчайшего пути графа, но эта задача на первый взгляд не похожа на задачу теории графов, описание задачи не говорит нам явно, что нам нужно использовать график для решения проблемы, в этом случае нам нужно глубоко проанализировать и смоделировать проблему.
leetcode279. Идеальные квадраты
Решения
Интуитивное решение? жадный?
12 = 9 + 1 + 1 + 1
12 = 4 + 4 + 4
Мы представим жадный алгоритм в будущем Жадный алгоритм относительно прост в реализации, но мы можем легко впасть в заблуждение Проблема не может быть решена жадным алгоритмом, но мы думаем, что можем использовать жадный алгоритм для ее решения .
Расширенное моделирование обхода
Моделирование этой проблемы: вся проблема преобразуется в задачу теории графов, от n до 0, каждое число представляет собой узел, если есть два числа от x до y, которые отличаются на идеальный квадрат, затем соедините ребро, и мы получим невзвешенный граф, в который трансформируется исходная задача, найти кратчайший путь от n до 0 в этом невзвешенном графе
class Solution {
public:
int numSquares(int n) {
queue<pair<int, int>> q;
q.push(make_pair(n, 0));//从n出发，到达n需要0步
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
if (num == 0){
return step;
}else{
for(int i = 1; num - i *i >= 0; i++){
q.push(make_pair(num - i *i, step + 1));
}
}
}
throw invalid_argument("no answer!");
}
};
анализировать
Программа, реализованная таким образом, не является стандартной реализацией в ширину, у нее есть проблемы с производительностью, проблема заключается в том, что мы каждый раз проталкиваем в очередь num-i*i, которая содержит много повторений, потому что для каждого числа До нас можно добраться разными путями.
- Чтобы справиться с избыточностью, мы создали новый массив посещений, чтобы указать, были ли посещены n+1 чисел от 0 до n.
class Solution {
public:
int numSquares(int n) {
queue<pair<int, int>> q;
q.push(make_pair(n, 0));//从n出发，到达n需要0步
vector<bool> visited(n + 1, false);
visited[n] = true;
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
if (num == 0){
return step;
}else{
for(int i = 1; ; i++){
int tmp = num - i *i;
if (tmp < 0){
break;
}
if (!visited[tmp]){
q.push(make_pair(tmp, step + 1));
visited[tmp] = true;
}
}
}
}
throw invalid_argument("no answer!");
}
};
аналогичная проблема
leetcode 127
leetcode 126
Очередь с приоритетом (С++)
Очередь с приоритетом — это особый вид очереди, обычно основной реализацией очереди с приоритетом является куча. Мы можем использовать программирование на доске для базовых потребностей реализации кучи.
библиотека c++ priority_queue
#include <iostream>
#include <queue>
#include <ctime>
using namespace std;
bool myCmp(int a , int b){
if(a%10 != b%10)
return a%10 > b%10;
return a > b;
}
int main() {
srand(time(NULL));
// 默认的priority queue, 底层是最大堆
priority_queue<int> pq;
for(int i = 0 ; i < 10 ; i ++){
int num = rand() % 100;
pq.push(num);
cout << "insert " << num << " in priority queue." << endl;
}
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << endl << endl;
// 使用greater的priority queue, 底层是最小堆
priority_queue<int, vector<int>, greater<int>> pq2;
for(int i = 0; i < 10; i ++){
int num = rand() % 100;
pq2.push(num);
cout << "insert " << num << " in priority queue." << endl;
}
while(!pq2.empty()){
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl << endl;
// 使用自定义Comparator的priority queue
priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCmp);
for(int i = 0; i < 10; i ++){
int num = rand() % 100;
pq3.push(num);
cout << "insert " << num << " in priority queue." << endl;
}
while(!pq3.empty()){
cout << pq3.top() << " ";
pq3.pop();
}
return 0;
}
Алгоритмы, связанные с приоритетными очередями
leetcode 347. Top K High Frequency Elements
Простейшая идея: сканировать частоту статистики: отсортировать, чтобы найти первые k элементов с наибольшей частотой, O(nlogn).
Подумав об этом, мы действительно можем поддерживать приоритетную очередь с k элементами. Если частота пройденного элемента выше частоты элемента с минимальной частотой в очереди, элемент с минимальной частотой в очереди вынимается, а в очередь ставится новый элемент. В итоге в очереди остаются k самых часто встречающихся элементов.
Код
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cassert>
using namespace std;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
assert( k > 0 );
// 统计每个元素出现的频率
unordered_map<int,int> freq;
for(int i = 0 ; i < nums.size() ; i ++ )
freq[nums[i]] ++;
assert( k <= freq.size() );
// 扫描freq,维护当前出现频率最高的k个元素
// 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > pq;
for( unordered_map<int,int>::iterator iter = freq.begin() ;
iter != freq.end() ; iter ++ ){
if( pq.size() == k ){
if( iter->second > pq.top().first ){
pq.pop();
pq.push( make_pair( iter->second , iter->first) );
}
}
else
pq.push( make_pair( iter->second , iter->first ) );
}
vector<int> res;
while( !pq.empty() ){
res.push_back( pq.top().second );
pq.pop();
}
return res;
}
};
анализировать
- Временная сложность приведенного выше кода составляет O(N*longK).
- Но если k близко к N, временная сложность вырождается до O(N*N)
- Приведенный выше код можно изменить, когда k близко к N, временная сложность составляет O (nlog (n-k))
аналогичная проблема
leetcode 23
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологии
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.