1、栈的基础使用
1、给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
这道题是众多公司面试题：
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
这道题是众多公司面试题：
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
match = '{';
if(c != match)
return false;
}
}
if(stack.size() != 0)
return false;
return true;
}
}; 2、逆波兰表达式（后缀表达式求值） 从左向右扫描，遇到数字压栈，遇到操作符，弹出栈顶的两个元素，先弹出的元素在右边，后弹出来的在左边，进行计算后，将结果压栈，再往后扫描，直到扫描结束，输出栈顶元素，即为最终结果
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stack;
int i = 0;
while(i<tokens.size()){
if(tokens[i]!="+" && tokens[i]!="-" && tokens[i]!="*" && tokens[i]!="/"){
stack.push(stoi(tokens[i]));
}
else{
int x,y;
x = stack.top();
stack.pop();
y = stack.top();
stack.pop();
if(tokens[i] == "+")
stack.push(y+x);
else if(tokens[i] == "-")
stack.push(y-x);
else if(tokens[i] == "*")
stack.push(y*x);
else
stack.push(y/x);
}
i++;
}
int res = stack.top();
return res;
}
}; 2、栈和递归的紧密关系
1、二叉树中的算法给定一个二叉树，返回它的 前序 遍历。
1.1 这里模仿系统中的栈使用非递归的方式来实现
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){}//构造函数
};
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();
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;
}
}; 1.2 递归 class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
helper(root,res);
return res;
}
void helper(TreeNode* root,vector<int>& res){
if(root == NULL)
return;
res.push_back(root->val);
helper(root->left,res);
helper(root->right,res);
}
};
1.3 迭代 class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> sk;
vector<int> res;
while(root||sk.size()){
while(root){
sk.push(root);
res.push_back(root->val);
root=root->left;
}
root=sk.top();
sk.pop();
root=root->right;
}
return res;
}
};
2、二叉树中序遍历 递归：
/**
* 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> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
void inorder(TreeNode *root,vector<int>& res){
if(root == NULL)
return;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
}; 非递归：
/**
* 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> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stack;
while(root || stack.size()){
while(root){
stack.push(root);
root = root->left;
}
if(stack.size()){
root = stack.top();
stack.pop();
res.push_back(root->val);
root = root->right;
}
}
return res;
}
}; 3、二叉树后序遍历 递归：
/**
* 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> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root,res);
return res;
}
void postorder(TreeNode *root,vector<int>& res){
if(root ==NULL)
return;
postorder(root->left,res);
postorder(root->right,res);
res.push_back(root->val);
}
}; 非递归：
/**
* 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> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stack,result;
vector<int> res;
if(root == NULL)
return res;
stack.push(root);
while(stack.size()){
root = stack.top();
stack.pop();
result.push(root);
if(root->left)
stack.push(root->left);
if(root->right)
stack.push(root->right);
}
while(result.size()){
root = result.top();
result.pop();
res.push_back(root->val);
}
return res;
}
}; 3、队列
/**
* 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(level == res.size())
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;
}
}; 2、二叉树的锯齿形遍历 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
3.2 BFS（广度优先遍历）和图的最短路径
1、给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
可以使用动态规划的方法来实现
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1);
for (int i = 1; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= i; j++)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
return dp[n];
}
}; 127.126
3.3 优先队列（底层实现：堆）
1、给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
1.首先扫描一边数组并统计频率，排序找到前k个出现频率最高的元素
2.维护一个含有k个元素的优先队列。如果遍历到的元素比队列中的最小频率的元素的频率高，则取出队列中最小频率的元素，将新的元素入队。最终，队列中剩下的，就是前k个出现频率最高的元素。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int,int> freq;//第一个是元素，第二个是出现的频率
//统计每个元素出现的频率
for(int i =0;i<nums.size();i++)
freq[nums[i]] ++;
//扫描freq，维护当前出现频率最高的k个元素
//在优先队列中，按照频率排序，所以数据对是（频率，元素）的形式
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > pq;
for(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;
}
}; 2、合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
//vector中存放的是每个链表的头结点
if(lists.size() == 0)
return NULL;
if(lists.size() == 1)
return lists[0];
ListNode *p = lists[0];
for(int i =1;i<lists.size();i++)
p = merge2Lists(p,lists[i]);
return p;
}
ListNode* merge2Lists(ListNode* l1,ListNode* l2){
ListNode *head = new ListNode(0);
ListNode *p = head;
while(l1&&l2){
if(l1->val < l2->val){
p -> next = l1;
l1 = l1->next;
}
else{
p -> next = l2;
l2 = l2 -> next;
}
p = p->next;
}
while(l1){
p->next = l1;
l1 = l1->next;
p = p->next;
}
while(l2){
p->next = l2;
l2 = l2->next;
p = p->next;
}
return head->next;
}
}; 
京公网安备 11010502036488号