濮阳做网站设计,wordpress 在裁剪您的图像时发生了错误.,小企业网站建设地点,设计网页的基本流程文章目录 150. 逆波兰表达式求值题目链接标签思路代码 112. 路径总和题目链接标签思路代码 130. 被围绕的区域题目链接标签思路代码 150. 逆波兰表达式求值
题目链接
150. 逆波兰表达式求值
标签
栈 数组 数学
思路
本题很像 JVM 中的 操作数栈#xff0c;当写出以下三行… 文章目录 150. 逆波兰表达式求值题目链接标签思路代码 112. 路径总和题目链接标签思路代码 130. 被围绕的区域题目链接标签思路代码 150. 逆波兰表达式求值
题目链接
150. 逆波兰表达式求值
标签
栈 数组 数学
思路
本题很像 JVM 中的 操作数栈当写出以下三行代码时
int i 3;
int j 4;
int k i j;会产生如下的字节码指令其中每行的数字代表指令的地址
0 iconst_3
1 istore_1
2 iconst_4
3 istore_2
4 iload_1 // 将 3 放入操作数栈
5 iload_2 // 将 4 放入操作数栈
6 iadd // 对 3、4 求和并将结果放入操作数栈
7 istore_3
8 return重点看 4, 5, 6 这几条指令这就是本题的解法使用一个栈来存储操作数遍历 tokens 中的每一个 token针对单个 token有以下操作
对于数字将其转化为 Integer 类型存入栈中。对于 , -, *, / 这四种运算符弹出栈中的两个 Integer 值作为操作数进行对应运算。注意由于栈是 先进后出 的所以弹出栈的第一个 Integer 值是第一个操作数第二个 Integer 值第二个操作数。
像这样遍历完所有 token 后对最后一个运算符的操作会将最后一次运算的结果存储到栈中也就是说栈在最后会存在一个元素这个元素就是运算结果。
代码
class Solution {public int evalRPN(String[] tokens) {LinkedListInteger stack new LinkedList(); // 存储 操作数 的栈for (String token : tokens) { // 取出每个 token 进行操作int operand1, operand2; // 第一个操作数、第二个操作数switch (token) { // 对不同的 token有不同的操作case :operand2 stack.pop(); // 取出第二个操作数operand1 stack.pop(); // 取出第一个操作数stack.push(operand1 operand2); // 将 两数之和 放到栈中break;case -:operand2 stack.pop();operand1 stack.pop();stack.push(operand1 - operand2); // 将 两数之差 放到栈中break;case *:operand2 stack.pop();operand1 stack.pop();stack.push(operand1 * operand2); // 将 两数之积 放到栈中break;case /:operand2 stack.pop();operand1 stack.pop();stack.push(operand1 / operand2); // 将 两数之商 放到栈中break;default:stack.push(Integer.valueOf(token)); // 将 这个数以 Integer 的类型 放到栈中}}return stack.pop(); // 返回栈中的最后一个数作为结果}
}112. 路径总和
题目链接
112. 路径总和
标签
树 深度优先搜索 广度优先搜索 二叉树
思路
本题是 从根节点开始向叶子节点找路径 的题最好使用 深度优先搜索。在搜索时可以 把每个节点都看作“根节点”在其左、右子树中分别寻找 减去本节点值的 剩余的 目标值。如果发现当前节点为 null则代表当前路径不是题目要求的路径返回 false如果发现当前节点的子节点都为 null说明该节点是 叶子节点则查看本次要找的目标值是否等于当前节点的值如果等于则说明存在题目所要求的路径返回 true。
代码
class Solution {// 判断是否能以 curr 为根节点找到节点值之和为 tar 的路径public boolean hasPathSum(TreeNode curr, int tar) {if (curr null) { // 如果当前节点为 nullreturn false; // 则该路径不是题目所要求的路径返回 false} else if (curr.left null curr.right null) { // 如果当前节点的子节点都为 nullreturn tar curr.val; // 则看 本次要找的值 是否等于 当前节点的值}// 分别在 左、右子树中寻找节点值之和为 剩余的 tar 的路径return hasPathSum(curr.left, tar - curr.val)|| hasPathSum(curr.right, tar - curr.val);}
}130. 被围绕的区域
题目链接
130. 被围绕的区域
标签
深度优先搜索 广度优先搜索 并查集 数组 矩阵
思路
题目描述挺抽象的本题就是将被 X 围绕的一片 O 全部改成 X围绕的定义是这一片 O 的上下左右都有 X就像一个漂在水面上的小岛。本题很像 LeetCode 200. 岛屿数量200题是求小岛的数量而本题像是将小岛淹没将这片岛屿从 O 改成 X除了与边界连通的小岛之外。
我们可以反着想对 与边界连通的小岛 做标记那么没有被标记的小岛就是要被淹没的区域在最后将标记取消并将没有被标记的小岛淹没即可。
做标记很简单由于被标记的小岛需要与边界连通所以可以从 第一行、最后一行、第一列、最后一列 入手使用 深度优先搜索 找到与边界的 O 所连通的区域并对其进行标记。这里的深度优先搜索很简单仅仅需要向上下左右搜索即可。
注意本题的 O 是大写字母 O而不是数字 0。
代码
class Solution {public void solve(char[][] board) {// 初始化成员变量this.board board;this.ROW board.length;this.COL board[0].length;if (ROW 0) { // 如果一行都没有return; // 则直接返回}// 标记与边界连通的小岛for (int r 0; r ROW; r) {dfs(r, 0); // 遍历第一列dfs(r, COL - 1); // 遍历最后一列}for (int c 1; c COL - 1; c) { // 由于上面的遍历将四角都遍历过了所以跳过四角dfs(0, c); // 遍历第一行dfs(ROW - 1, c); // 遍历最后一行}// 取消标记、淹没没有标记的小岛for (int r 0; r ROW; r) {for (int c 0; c COL; c) {if (board[r][c] U) { // 将被标记的方格改为 Oboard[r][c] O;} else if (board[r][c] O) { // 将没有被标记的方格 (被围绕) 改为 Xboard[r][c] X;}}}}private void dfs(int r, int c) {if (!(r 0 r ROW c 0 c COL) // 如果 (r, c) 指向的元素不在矩阵内|| board[r][c] ! O) { // 或者 这个元素不是 大写字母 Oreturn; // 则直接返回}board[r][c] U; // 标记方格表示它不是被围绕的方格for (int k 0; k 4; k) { // 分别向上下左右遍历int kr r dir[k][0], kc c dir[k][1];dfs(kr, kc);}}private int ROW; // 行数private int COL; // 列数private char[][] board; // 矩阵// 方向数组分别为 向右、向下、向左、向上private int[][] dir {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
}
