堆栈基础知识（2 天）

栈的简介

• 栈的插入
• 栈的删除

栈的定义

1. 线性表
2. 后进先出原则

栈的顺序存储和链式存储

• 顺序栈
  地址连续单元

• 链式栈
  利用单链表的方式来实现堆栈

堆栈的基本操作

1.初始化空栈
定义栈的大小size以及栈顶指针top
2.判断栈是否为空
当堆栈为空的时候返回true，堆栈不为空的时候返回false
3.判断栈是否已满
4.插入元素
在线性表最后元素后面插入一个新的数据元素
5.删除元素
在线性表最后元素后面删除最后一个数据元素
6.获取栈顶元素

顺序存储
初始化空栈：使用列表创建一个空栈，定义栈的大小 self.size，并令栈顶元素指针 self.top 指向 -1，即 self.top = -1。
判断栈是否为空：当 self.top $==$ -1 时，说明堆栈为空，返回 True，否则返回 False。
判断栈是否已满：当 self.top $==$ self.size - 1，说明堆栈已满，返回 True，否则返回返回 False。
获取栈顶元素：先判断队列是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶元素，即 self.stack[self.top]。
插入元素（进栈、入栈）：先判断队列是否已满，已满直接抛出异常。如果队列未满，则在 self.stack 末尾插入新的数据元素，并令 self.top 向右移动 1 位。
删除元素（出栈、退栈）：先判断队列是否为空，为空直接抛出异常。如果队列不为空，则令 self.top 向左移动 1 位，并返回 self.stack[self.top]。

链式存储
初始化空栈：使用列表创建一个空栈，并令栈顶元素指针 self.top 指向 None，即 self.top = None。
判断栈是否为空：当 self.top == None 时，说明堆栈为空，返回 True，否则返回 False。
获取栈顶元素：先判断队列是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶节点，即 self.top.value。
插入元素（进栈、入栈）：创建值为 value 的链表节点，插入到链表头节点之前，并令栈顶指针 self.top 指向新的头节点。
删除元素（出栈、退栈）：先判断队列是否为空，为空直接抛出异常。如果队列不为空，则令 self.top 链表移动 1 位，并返回 self.top.value。

、

堆栈的应用

• 保存和取用信息，算法和程序的辅助存储结构。临时保存信息
  • 函数调用栈。浏览器中的前进和后退功能
• 堆栈的后进先出规则，保证特定的存取顺序

155最小栈

1. 使用两个栈

class MinStack {
Deque<Integer>xStack;
Deque<Integer>minStack;public MinStack() {
xStack  = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);}public void push(int val) {
xStack.push(val);
minStack.push(Math.min(minStack.peek(),val));}public void pop() {
xStack.pop();
minStack.pop();}public int top() {
return xStack.peek();}public int getMin() {
return minStack.peek();}
}

一个是存储所有值，一个维持最小值

有效括号

class Solution {public boolean isValid(String ss) {
Stack<Character> Sstack = new Stack<>();
Integer len = ss.length();
char[] s = ss.toCharArray();//转换为字符数组
for(int i=0;i<len;i++){if(s[i]=='['||s[i]=='('||s[i]=='{'){Sstack.push(s[i]);//放入字符put和push}else if(s[i]==']'&&!Sstack.empty()&&Sstack.peek()=='['){
Sstack.pop();//peek和top}else if(s[i]==')'&&!Sstack.empty()&&Sstack.peek()=='('){
Sstack.pop();}else if(s[i]=='}'&&!Sstack.empty()&&Sstack.peek()=='{'){
Sstack.pop();}else{
return false;}}
return Sstack.empty();}
}

基本计算器

class Solution {public int calculate(String s) {
Deque<Integer>stack = new LinkedList<Integer>();
char preSign = '+';
int num = 0;
int n = s.length();
for(int i=0;i<n;++i){if(Character.isDigit(s.charAt(i))){num = num*10+s.charAt(i)-'0';}if(!Character.isDigit(s.charAt(i))&&s.charAt(i)!=' '||i==n-1){//不是数字，不是空格switch(preSign){case '+':stack.push(num);break;case '-':stack.push(-num);break;case '*':stack.push(stack.pop()*num);break;default:stack.push(stack.pop()/num);}preSign = s.charAt(i);num=0;}
}
int ans = 0;
while(!stack.isEmpty()){ans+=stack.pop();
}
return ans;}
}

逆波兰表达式求值

整数除法只保留整数部分，给定逆波兰表达式总是有效的，换句话说，表达式总会得出有效数值且不存在除数为零的情况

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

class Solution {public int evalRPN(String[] tokens) {
Deque<Integer>stack = new LinkedList<Integer>();
//定义整数双向队列
int n = tokens.length;//数组的性质
for(int i=0;i<n;i++){String token = tokens[i];if(isNumber(token)){//是整数，将之放入双向队列中stack.push(Integer.parseInt(token));}else{//如果不是整数int num2 = stack.pop();int num1 = stack.pop();switch(token){case"+":stack.push(num1+num2);break;case"-":stack.push(num1-num2);break;case"*":stack.push(num1*num2);break;case"/":stack.push(num1/num2);break;default:}}
}
return stack.pop();}public boolean isNumber(String token){return !("+".equals(token)||"-".equals(token)||"*".equals(token)||"/".equals(token));}
}

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

可能出现的问题：
括号嵌套

利用栈来解决问题

1. 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
2. 如果当前的字符为字母或者左括号，直接进栈
3. 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字

class Solution {public String decodeString(String s) {
Stack<Character>stack = new Stack<Character>();for(char c:s.toCharArray()){
String t = "";if(c==']'){
char temp;
while(!stack.isEmpty()&&'['!=(temp = stack.pop())){
t+=String.valueOf(temp);
}
StringBuffer sb = new StringBuffer();
while(!stack.isEmpty()&&Character.isDigit(stack.peek())){sb.insert(0,stack.pop());
}
int count = Integer.valueOf(sb.toString());
String ss = new StringBuffer(t).reverse().toString(); 
for(int i=0;i<count;i++){
for(char ch:ss.toCharArray()){stack.push(ch);
}
}}else{stack.push(c);}}StringBuffer retv = new StringBuffer();while(!stack.isEmpty()){retv.insert(0,stack.pop());}return retv.toString();
}}

验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

方法一： 贪心
思路

所有的元素一定是按顺序 push 进去的，重要的是怎么 pop 出来？

假设当前栈顶元素值为 2，同时对应的 popped 序列中下一个要 pop 的值也为 2，那就必须立刻把这个值 pop 出来。因为之后的 push 都会让栈顶元素变成不同于 2 的其他值，这样再 pop 出来的数 popped 序列就不对应了。

算法

将 pushed 队列中的每个数都 push 到栈中，同时检查这个数是不是 popped 序列中下一个要 pop 的值，如果是就把它 pop 出来。

最后，检查不是所有的该 pop 出来的值都是 pop 出来了。

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {
int N = pushed.length;
int M = popped.length;
if(M!=N)return false;
Stack<Integer>stack = new Stack<>();
int j=0;
for(int x:pushed){stack.push(x);while(!stack.isEmpty()&&j<N&&stack.peek()==popped[j]){stack.pop();j++;}
}
return j==N;}
}

堆栈与深度优先搜索（5 天）

深度优先搜索

回溯思想(递归实现)
后进先出（堆栈实现）

基于递归实现的深度优先搜索

graph 为存储无向图的字典变量，
visited 为标记访问节点的 set 集合变量。
start 为当前遍历边的开始节点。
dfs_recursive(graph, start, visited): 为递归实现的深度优先搜索方法。
将 start 标记为已访问，即将 start 节点放入 visited 中（visited.add(start)）。
访问节点 start，并对节点进行相关操作（看具体题目要求）。
遍历与节点 start 相连并构成边的节点 end。
如果 end 没有被访问过，则从 end 节点调用递归实现的深度优先搜索方法，即 dfs_recursive(graph, end, visited)。

def dfs_recursive(graph, start, visited):# 标记节点visited.add(start)# 访问节点print(start)for end in graph[start]:if end not in visited:# 深度优先遍历节点,递归调用函数dfs_recursive(graph, end, visited)

基于堆栈实现的深度优先搜索

def dfs_stack(graph, start):visited = set(start)stack = [start]while stack:node_u = stack.pop()# 访问节点print(node_u)for node_v in graph[node_u]:if node_v not in visited:stack.append(node_v)visited.add(node_v)

200岛屿数量

class Solution {//深度遍历函数void dfs(char[][]grid,int r,int c){int nr = grid.length;int nc = grid[0].length;if(r<0||c<0||r>=nr||c>=nc||grid[r][c]=='0'){return;//递归结束条件}grid[r][c]='0';dfs(grid,r-1,c);dfs(grid,r+1,c);dfs(grid,r,c-1);dfs(grid,r,c+1);}public int numIslands(char[][] grid) {
if(grid==null||grid.length==0){return 0;
}
int nr = grid.length;
//行数
int nc = grid[0].length;
//列数
int num_islands=0;
//岛屿的数目
for(int r=0;r<nr;++r){for(int c=0;c<nc;++c){if(grid[r][c]=='1'){++num_islands;`在这里插入代码片`dfs(grid,r,c);}}
}
return num_islands;}
}

克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {public int val;public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

算法

1.使用一个哈希表visited存储所有已被访问和克隆的节点。哈希表中的 key 是原始图中的节点，value 是克隆图中的对应节点。

2.从给定节点开始遍历图。如果某个节点已经被访问过，则返回其克隆图中的对应节点。

3.如果当前访问的节点不在哈希表中，则创建它的克隆节点并存储在哈希表中。注意：在进入递归之前，必须先创建克隆节点并保存在哈希表中。如果不保证这种顺序，可能会在递归中再次遇到同一个节点，再次遍历该节点时，陷入死循环。(注意先后顺序)

4.递归调用每个节点的邻接点。每个节点递归调用的次数等于邻接点的数量，每一次调用返回其对应邻接点的克隆节点，最终返回这些克隆邻接点的列表，将其放入对应克隆节点的邻接表中。这样就可以克隆给定的节点和其邻接点。

/*
// Definition for a Node.
class Node {public int val;public List<Node> neighbors;public Node() {val = 0;neighbors = new ArrayList<Node>();}public Node(int _val) {val = _val;neighbors = new ArrayList<Node>();}public Node(int _val, ArrayList<Node> _neighbors) {val = _val;neighbors = _neighbors;}
}
*/class Solution {//拷贝的结果private HashMap<Node,Node>visited = new HashMap<>();public Node cloneGraph(Node node) {if(node==null)return node;if(visited.containsKey(node)){//如果访问过了节点return visited.get(node);}//克隆节点,新建立一个ArrayList数组Node cloneNode = new Node(node.val,new ArrayList());visited.put(node,cloneNode);
//键值对放入
//遍历该节点的邻居并更新克隆节点的邻居列表
for(Node neighbor:node.neighbors){cloneNode.neighbors.add(cloneGraph(neighbor));//递归调用函数,将节点拷贝
}
return cloneNode;}
}

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

class Solution {int ways=0;//有多少种方法public int findTargetSumWays(int[] nums, int target) {backtrack(nums,target,0,0);return ways;}public void backtrack(int []nums,int target,int index,int sum){if(index==nums.length){if(sum==target)ways++;//可以有的方案}else{//递归回溯backtrack(nums,target,index+1,sum+nums[index]);backtrack(nums,target,index+1,sum-nums[index]);}}}

太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

class Solution {private int d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private List<List<Integer>> res;private int r,c;private boolean[][] pVisited,aVisited;private final static int DIRECTION =4;public List<List<Integer>> pacificAtlantic(int[][] matrix) {res = new ArrayList<>();if (matrix==null || matrix.length ==0 || matrix[0].length==0){return  res;}r=matrix.length;c=matrix[0].length;pVisited = new boolean[r][c];aVisited = new boolean[r][c];for (int i = 0; i <r ; i++) {for (int j = 0; j <c ; j++) {if (!pVisited[i][j] && inPacificCoast(i,j) ){//没有访问过//从太平洋海边，随便一个地点海浪倒灌入陆地pour(matrix,i,j,matrix[i][j],pVisited);}if (!aVisited[i][j] && inAtlanticCoast(i,j)){//大西洋海边随便一个点海浪倒灌入陆地pour(matrix,i,j,matrix[i][j],aVisited);}}}for (int i = 0; i < r; i++) {for (int j = 0; j <c ; j++) {if (pVisited[i][j] && aVisited[i][j]){res.add(Arrays.asList(i,j));}}}return res;}private void pour(int[][] matrix, int x, int y, int h, boolean[][] v) {v[x][y] =true;for (int i = 0; i < DIRECTION; i++) {int nextX = x+d[i][0];int nextY = y+d[i][1];if (inMatrix(nextX, nextY) && !v[nextX][nextY] && matrix[nextX][nextY] >= h) {pour(matrix, nextX, nextY, matrix[nextX][nextY], v);}}}private boolean inMatrix(int x, int y) {return x>=0 && x<r && y>=0 && y<c;}private boolean inAtlanticCoast(int x, int y) {return (y==c-1 )||( x==r-1 );}private boolean inPacificCoast(int x, int y) {return (x==0 )||(y==0 );}}

1020. 飞地的数量

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

class Solution {int[][] grid;//地图int m, n;int cnt;  // 每个封闭区域的飞地数量boolean ex; // 是否出街public int numEnclaves(int[][] grid) {
int ans=0;
this.grid = grid;
//地图
m = grid.length;
//行数
n = grid[0].length;
//列数
for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){cnt = 0;ex = false;dfs(i,j);if(!ex)ans+=cnt;}}
}return ans;}//递归函数private void dfs(int i, int j) {if (i < 0 || i >= m || j < 0 || j >= n){ // 出界ex = true;return;}//递归出口if (grid[i][j] != 1) return;grid[i][j] = 0;cnt++;dfs(i + 1, j);dfs(i, j + 1);dfs(i - 1, j);dfs(i, j - 1);}}

1254. 统计封闭岛屿的数目

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。

如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。

请返回封闭岛屿的数目。

class Solution {int ans=0;
int m,n;
int [][]grid ;public int closedIsland(int[][] grid) {
m = grid.length;
//行数
n = grid[0].length;
//列数
this.grid =grid;
for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==0&&dfs(i,j)){ans++;}}
}
return ans;}//递归函数
public boolean dfs(int i,int j){if (i < 0 || i >= m || j < 0 || j >= n){ // 出界return false;}if(grid[i][j]!=0){return true;}//是水域grid[i][j]=1;boolean b1= dfs(i-1,j);boolean b2= dfs(i+1,j);boolean b3= dfs(i,j-1);boolean b4= dfs(i,j+1);return b1&&b2&&b3&&b4;}
}

引用出处

https://algo.itcharge.cn/03.%E5%A0%86%E6%A0%88/01.%E5%A0%86%E6%A0%88%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/01.%E5%A0%86%E6%A0%88%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/