算法4
栈和队列的使用
栈的基础使用
例题20：Valid Parentheses
给定一个字符串，只包含(,{,[,],},),判定字符串中的括号匹配是否合法
如（}不合法
#include<stack>
#include<string>
#include<cassert>
#include<iostream>
using namespace std;
class Solution{
public:
bool isValid(string s)
{
stack<char>stack;
for(int i= 0;i<s.size();i++)
{
if(s[i] == '('||s[i]=='{'||s[i] == '[')
stack.push(s[i]);
else
{
if(stack.size()==0 )
return false;
char c = stack.top();//将栈顶元素存储
stack.pop();//将栈顶元素推出
char match;
if(s[i] == ')')
match = '(';
else if(s[i] == ']')
match = '[';
else{
assert (s[i] == '}');
match = '{';
}
if(c != match)
return false;
}
}
if(stack.size() != 0)
return false;
return true;
}
};例题150： Evaluate Reverse polish Notation
给定一个数组逆波兰表达式求值
例题71： Simplify path
给定一个unix系统下的路径，简化这个路径
如/home/ 简化后/home
如/a/./b/../../c/ 简化后为/c
- 给定路径是否一定合法
- 不能回退的情况？（如/../,返回/)
- 多余的/?
栈和递归的紧密联系
例题144：Binary Tree Preorder Traversal
void preorder(TreeNode *node){
if(node){
cout<<node->val;
preorder(node->left);
preorder(node->right);
}
};使用栈模拟系统栈，写出非递归程序
前序遍历
先打印，再访问左孩子，再访问右孩子
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
}
struct Command{
string s; //go,print
TreeNode *node;
Command(string s,TreeNode *node):s(s),node(node){}
//构造函数 然后s(s)和node(node)去初始化
};
class Solution{
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();
//分析栈顶推出的元素command
if(command.s == "print")
res.push_back(command.node->val);
else{
assert(command.s == "go");
if(command.node->right) //判断当前节点的子节点右孩子是否存在
stack.push(Command("go",command.node->right));
if(command.node->left) //判断当前节点的子节点右孩子是否存在
stack.push(Command("go",command.node->left));
//输出按照先输出左再输出右，则压入的时候先压入右再压入左
stack.push(Command("print",command.node));
}
}
return res;
}
};中序遍历
先访问左孩子 再打印节点 再访问右孩子
所以三条命令反向压入栈中
右孩子->打印->左孩子
struct Command{
string s; //go,print
TreeNode *node;
Command(string s,TreeNode *node):s(s),node(node){}
//构造函数 然后s(s)和node(node)去初始化
};
class Solution{
public:
vector<int>inorderTraversal(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();
//分析栈顶推出的元素command
if(command.s == "print")
res.push_back(command.node->val);
else{
assert(command.s == "go");
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));
//输出按照先输出左再输出右，则压入的时候先压入右再压入左
}
}
return res;
}
};后序遍历
先访问左孩子，再访问右孩子，再打印
struct Command{
string s; //go,print
TreeNode *node;
Command(string s,TreeNode *node):s(s),node(node){}
//构造函数 然后s(s)和node(node)去初始化
};
class Solution{
public:
vector<int>postorderTraversal(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();
//分析栈顶推出的元素command
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));
if(command.node->left) //判断当前节点的子节点右孩子是否存在
stack.push(Command("go",command.node->left));
//输出按照先输出左再输出右，则压入的时候先压入右再压入左
}
}
return res;
}
};例题 341：
给出一个嵌套的整型列表。列表中的项或者为一个整数，或许是另一个列表。设计一个
迭代器，遍历这个整型列表中的所有整数
如[[1,1],2,[1,1]]
如[1,[4,[6]]]
hasNext()为true的情况下，不断调用next()，依次获得元素
class NestedInteger{
public:
bool isInteger()const;//判断是否为整型
int getInteger()const;//获得整型的值
const vector<NestedInteger>&getlist()const;
}
class NestedIterator{
public:
NestedIterator(vector<NestedInteger>&nestedList){ }
int next(){ }
bool hasNext(){ }
队列 Queue
队列的基本应用-广度优先遍历
-树：层序遍历
-图：无权图的最短路径
层序遍历
例题102：
对于一个二叉树进行层序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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(level >= res.size()) //弹出的这个元素的这个节点在新的层中
res.push_back(vector<int>());
res[level].push_back(node->val);//当level>res.size()的时候，添加一个向量，然后将节点的值放进去
if(node->left)
q.push(make_pair(node->left,level+1));
if(node->right)
q.push(make_pair(node->right,level+1));
}
return res;
}
};例题103
对一个二叉树进行层序遍历，按照“之”字型的顺序返回所有节点
例题199
想象你站在一棵二叉树的右侧，返回你能看见的节点
BFS和图的最短路径
例题279
给出一个正整数n，寻找最少的完全平方数，使得他们的和为n
完全平方数：1，4，9，16
12=4+4+4
13=4+9
-不可能没有解，因为存在1
12=9+1+1+1
12=4+4+4
class Solution{
public:
int numSquares(int n){
assert(n>0);
queue<pair<int,int>> q;
q.push(make_pair(n,0)); //初始化
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
if(num == 0)
return step;
for(int i =1;num-i*i>=0;i++)
//某一个数可以从多种途径获得，造成冗余
//因为这是一个图而不是树
q.push(make_pair(num-i*i,step+1));
}
throw invalid_argument("No Solution.");
}
};BFS广度优先搜索
讲解：
深度优先搜索要尽可能的远离起始点，而广度优先搜索则要尽可能的靠近起始点，
它首先访问起始顶点的所有邻接点，然后再访问较远的区域，这种搜索不能用栈实现，
而是用队列实现。
规则1：访问下一个未访问的邻接点（如果存在），这个顶点必须是当前顶点的邻接点，
标记它，并把它插入到队列中。
规则2：如果已经没有未访问的邻接点而不能执行规则 1 时，那么从队列列头取出一个顶点（如果存在），并使其成为当前顶点。
规则3：如果因为队列为空而不能执行规则 2，则搜索结束。
上述代码在实现过程中数值num-i* i的数值可能存在多种途径获得
通过画图可以加深理解
算法优化，解决冗杂问题。
这个问题的重点在于
队列实现BFS(广度优先搜索)
在入队过程中，只有未被访问过的数值可以入队，防止重复入队
这里最短路径的获取：
在队列中，如果某一个路径优先使num-i* i的值达到0，则该数字0优先入队，在取出的时候，返回该数字对应的step值
class Solution{
public:
int numSquares(int n){
assert(n>0);
queue<pair<int,int>> q;
q.push(make_pair(n,0)); //初始化
vector<bool> visited(n+1,false); //初始的n+1个元素均没有被访问
visited[n] = true; //最初压入的n存在了，所以这里将其设为true，说明被访问过
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
for(int i =1; ;i++) {
int a = num - i*i;
if(a<0)
break;
if(a == 0)
return step+1;
if(!visited[a]) //如果该数字没有被访问过
{
q.push(make_pair(a,step+1)); //将这个数字压入
visited[a] = true; //这个数已经存在一个父节点，被访问过了，所以为true
}
}
}
throw invalid_argument("No Solution.");
}
};例题127：word ladder
例题126： word ladder 2
#include <vector>
#include <string>
#include "time_interval.h"
int main() {
std::vector<std::string> v;
int count = 10000000;
v.reserve(count); //预分配十万大小，排除掉分配内存的时间
{
TIME_INTERVAL_SCOPE("push_back string:");
for (int i = 0; i < count; i++)
{
std::string temp("ceshi");
v.push_back(temp);// push_back(const string&)，参数是左值引用
}
}
v.clear();
{
TIME_INTERVAL_SCOPE("push_back move(string):");
for (int i = 0; i < count; i++)
{
std::string temp("ceshi");
v.push_back(std::move(temp));// push_back(string &&), 参数是右值引用
}
}
v.clear();
{
TIME_INTERVAL_SCOPE("push_back(string):");
for (int i = 0; i < count; i++)
{
v.push_back(std::string("ceshi"));// push_back(string &&), 参数是右值引用
}
}
v.clear();
{
TIME_INTERVAL_SCOPE("push_back(c string):");
for (int i = 0; i < count; i++)
{
v.push_back("ceshi");// push_back(string &&), 参数是右值引用
}
}
v.clear();
{
TIME_INTERVAL_SCOPE("emplace_back(c string):");
for (int i = 0; i < count; i++)
{
v.emplace_back("ceshi");// 只有一次构造函数，不调用拷贝构造函数，速度最快
}
}
}第1中方法耗时最长，原因显而易见，将调用左值引用的push_back，且将会调用一次string的拷贝构造函数，比较耗时，这里的string还算很短的，如果很长的话，差异会更大
第2、3、4中方法耗时基本一样，参数为右值，将调用右值引用的push_back，故调用string的移动构造函数，移动构造函数耗时比拷贝构造函数少，因为不需要重新分配内存空间。
第5中方法耗时最少，因为emplace_back只调用构造函数，没有移动构造函数，也没有拷贝构造函数。
优先队列
优先队列的底层实现：堆
学习使用语言中的优先级队列容器
C++：priority_queue
#include<iostream>
#include<queue>
#include<ctime>
#include<functional>
using namespace std;
bool myCmp(int a,int b){
return a%10<b%10;
}
int main(){
srand(time(NULL)); //随机种子
//默认情况下，最大堆
priority_queue<int>pq;
for(int i = 0;i<10;i++){
int num = rand()%100 ;//0-100中随机选取一个数
pq.push(num);
cout<<"insert"<<num<<" in priority queue."<<endl;
}
while(!pq.empty()){
cout<<pq.top()<<" ";
pq.pop();
}
cout<<endl<<endl;
//底层是最小堆
priority_queue<int,vector<int>,greater<int>>pq2;
//底层为vector 最小堆greater<int>
for(int i = 0;i<10;i++){
int num = rand()%100 ;//0-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 ;//0-100中随机选取一个数
pq3.push(num);
cout<<"insert"<<num<<" in priority queue."<<endl;
}
while(!pq3.empty()){
cout<<pq3.top()<<" ";
pq3.pop();
}
cout<<endl<<endl;
return 0;
}结果：
insert20 in priority queue.
insert63 in priority queue.
insert74 in priority queue.
insert20 in priority queue.
insert41 in priority queue.
insert38 in priority queue.
insert26 in priority queue.
insert95 in priority queue.
insert87 in priority queue.
insert19 in priority queue.
95 87 74 63 41 38 26 20 20 19
insert57 in priority queue.
insert41 in priority queue.
insert58 in priority queue.
insert34 in priority queue.
insert79 in priority queue.
insert80 in priority queue.
insert97 in priority queue.
insert85 in priority queue.
insert69 in priority queue.
insert25 in priority queue.
25 34 41 57 58 69 79 80 85 97
这个是return a%10< b% 10
insert57 in priority queue.
insert28 in priority queue.
insert31 in priority queue.
insert20 in priority queue.
insert18 in priority queue.
insert77 in priority queue.
insert34 in priority queue.
insert81 in priority queue.
insert4 in priority queue.
insert59 in priority queue.
59 28 18 77 57 34 4 31 81 20
如果是return a% 10 >b % 10
则按照从小到大进行排列
程序正常返回需要return 0
所以对于bool型而言，子函数需要返回0 也就是false。
return a>b，就需要让b>a.
例题 347：
给定一个非空数组，返回前k个出现频率最高的元素
如给定[1,1,1,2,2,3] k = 2
返回[1,2]
注意k的合法性问题
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[numsi]]++;
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(); //弹出队列首元素，并将iter迭代器所对应元素压入
pq.push_back(make_pair(iter->second,iter->first));
}
}
else
pq.push_back(make_pair(iter->second,iter->first));
}
//这里为了输出最后结果还需要定义一个数组res
vector<int>res;
while(!pq.empty()){
res.push_back(pq.top().second); //优先队列的第二列是元素本身
pq.pop();
}
return res;
}
};例题23：
有k个有序数组，将他们归并为一个有序数组
