【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。

devtools/2024/9/25 3:23:23/

在这里插入图片描述

文章目录

    • 71.【中等】简化路径
    • 155.【中等】最小栈
    • 150.【中等】逆波兰表达式求值
    • 224.【困难】基本计算器
    • 2.【中等】两数相加

🌈你好呀！我是 山顶风景独好
💕欢迎来到我的博客，很高兴能够在这里和您见面！
💕希望您在这里可以感受到一份轻松愉快的氛围！
💕这里不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
🚀 欢迎一起踏上探险之旅，挖掘无限可能，共同成长！

71.【中等】简化路径

  • 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
  • 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。
  • 请注意，返回的 规范路径 必须遵循下述格式：
  • 始终以斜杠 ‘/’ 开头。
    两个目录名之间必须只有一个斜杠 ‘/’ 。
    最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
    此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
    返回简化后得到的 规范路径 。

示例 1：

  • 输入：path = “/home/”
  • 输出：“/home”
  • 解释：注意，最后一个目录名后面没有斜杠。

示例 2：

  • 输入：path = “/…/”
  • 输出：“/”
  • 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

  • 输入：path = “/home//foo/”
  • 输出：“/home/foo”
  • 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
    示例 4：
  • 输入：path = “/a/./b/…/…/c/”
  • 输出：“/c”

解题思路：
思路与算法
我们首先将给定的字符串 path\textit{path}path 根据 /\texttt{/}/ 分割成一个由若干字符串组成的列表，记为 names\textit{names}names。根据题目中规定的「规范路径的下述格式」，names\textit{names}names 中包含的字符串只能为以下几种：

  • 空字符串。例如当出现多个连续的 /\texttt{/}/，就会分割出空字符串；
  • 一个点 .
  • 两个点 . .
  • 只包含英文字母、数字或 \texttt{_} 的目录名。

对于「空字符串」以及「一个点」，我们实际上无需对它们进行处理，因为「空字符串」没有任何含义，而「一个点」表示当前目录本身，我们无需切换目录。
对于「两个点」或者「目录名」，我们则可以用一个栈来维护路径中的每一个目录名。当我们遇到「两个点」时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。当我们遇到「目录名」时，就把它放入栈。
这样一来，我们只需要遍历 names 中的每个字符串并进行上述操作即可。在所有的操作完成后，我们将从栈底到栈顶的字符串用 /进行连接，再在最前面加上 /表示根目录，就可以得到简化后的规范路径。

java">class Solution {  // 简化文件路径的方法  public String simplifyPath(String path) {  // 使用"/"作为分隔符将路径分割成多个部分  String[] names = path.split("/");  // 使用双端队列（Deque）来模拟栈，存储路径中的目录名  Deque<String> stack = new ArrayDeque<String>();  // 遍历分割后的每个部分  for (String name : names) {  // 如果当前部分表示上级目录（".."）  if ("..".equals(name)) {  // 如果栈不为空，则弹出栈顶元素（表示进入上一级目录）  if (!stack.isEmpty()) {  stack.pollLast();  }  // 如果当前部分长度大于0且不是当前目录（"."）  } else if (name.length() > 0 && !".".equals(name)) {  // 将当前部分压入栈中（表示进入下一级目录）  stack.offerLast(name);  }  }  // 创建一个StringBuffer对象来构建简化后的路径  StringBuffer ans = new StringBuffer();  // 如果栈为空（即原始路径只包含"/"或空字符串），则简化后的路径应为"/"  if (stack.isEmpty()) {  ans.append('/');  } else {  // 如果栈不为空，则从栈底到栈顶依次弹出元素，并添加到StringBuffer中  // 以此构建从根目录开始的简化路径  while (!stack.isEmpty()) {  ans.append('/');  ans.append(stack.pollFirst());  }  }  // 将StringBuffer转换为String并返回  return ans.toString();  }  
}

155.【中等】最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。
java">class MinStack {  // 链表栈，用于存储每个元素与未压入该元素时栈中最小元素的差值  LinkedList<Long> stack;  // 当前已压入栈中元素的最小值  private long min;  // 构造函数，初始化栈  public MinStack() {  stack = new LinkedList<>(); // 创建一个空的LinkedList实例作为栈  }  // 将元素压入栈  public void push(int val) {  // 如果栈为空  if(stack.isEmpty()){  // 第一个元素压入时，min直接赋值为该元素  min = val;  // 压入一个0，因为此时没有与min的差值（因为是第一个元素）  stack.addFirst(0L);  return;  }  // 栈不为空时，计算当前元素与min的差值，并压入差值  stack.addFirst((long)val-min); // 压入差值，因为addFirst是头插法，所以这里是从链表头部插入  // 更新min为当前元素与min的较小值  min = Math.min((long)val,min);  }  // 弹出栈顶元素  public void pop() {  long pop = stack.removeFirst(); // 弹出栈顶元素（差值）  // 如果弹出的差值小于0，说明弹出的是当前栈中的最小值  if(pop<0){  // 原来的min减去差值就是新的min（因为pop是之前的最小值与当前弹出元素的差值）  long lastMin = min;  min = lastMin - pop;  }  // 若差值大于等于0，说明弹出的不是最小值，min不变  }  // 获取栈顶元素  public int top() {  long peek = stack.getFirst(); // 获取栈顶元素（差值），但不出栈  // 如果栈顶元素小于等于0，说明栈顶元素就是当前最小值  if(peek<=0) return (int)min;  // 否则，当前元素的值是min加上差值  return (int)(min+peek);  }  // 获取栈中当前的最小值  public int getMin() {  return (int)min;  }  
}

150.【中等】逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：

  • 有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

  • 输入：tokens = [“2”,“1”,“+”,“3”,“*”]
  • 输出：9
  • 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

  • 输入：tokens = [“4”,“13”,“5”,“/”,“+”]
  • 输出：6
  • 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

解题思路
逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

  • 如果遇到操作数，则将操作数入栈；
  • 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

java">class Solution {  // 根据逆波兰表达式（RPN）计算表达式的值  public int evalRPN(String[] tokens) {  // 使用双端队列（Deque）模拟栈，存储整数  Deque<Integer> stack = new LinkedList<Integer>();  // 表达式中token的数量  int n = tokens.length;  // 遍历表达式中的每个token  for (int i = 0; i < n; i++) {  // 获取当前token  String token = tokens[i];  // 如果token是数字  if (isNumber(token)) {  // 将数字转换为整数并压入栈中  stack.push(Integer.parseInt(token));  } else {  // 如果token是运算符，则弹出两个数字  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 "/":  // 除法运算（注意：这里没有处理除数为0的情况）  stack.push(num1 / num2);  break;  default:  // 如果遇到非法的运算符，这里默认没有处理，实际中可能需要抛出异常  }  }  }  // 最终栈中剩下的元素即为表达式的值  return stack.pop();  }  // 判断一个token是否是数字  public boolean isNumber(String token) {  // 如果token不是运算符，则认为是数字  return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));  }  
}

性能最好

java">class Solution {  // 声明一个全局索引变量，用于迭代访问tokens数组  public int index = 0;  // evalRPN方法：根据逆波兰表达式（RPN）计算表达式的值  public int evalRPN(String[] tokens) {  // 将index初始化为tokens数组的最后一个元素的索引  index = tokens.length - 1;  // 调用iter方法进行递归计算  return iter(tokens);  }  // iter方法：递归计算逆波兰表达式的值  public int iter(String[] tokens) {  // 从tokens数组中取出当前索引对应的元素，并将索引减一  String item = tokens[index--];  // 如果当前元素是运算符  if (item.equals("+") || item.equals("-") || item.equals("*") || item.equals("/")) {  // 递归调用iter方法计算第二个操作数  int num2 = iter(tokens);  // 递归调用iter方法计算第一个操作数（注意此时index已经指向了第一个操作数）  int num1 = iter(tokens);  // 根据运算符进行相应的计算  switch (item) {  case "+":  // 返回加法结果  return num1 + num2;  case "-":  // 返回减法结果  return num1 - num2;  case "*":  // 返回乘法结果  return num1 * num2;  case "/":  // 返回除法结果（注意：这里没有处理除数为0的情况）  return num1 / num2;  // 如果遇到非法的运算符（实际上这里不会进入，因为前面已经判断过了）  }  }  // 如果当前元素是数字，则直接返回其整数值  return Integer.parseInt(item);  }  // isNumber方法：判断一个字符串是否是数字（注意：此方法在类中是静态的，但在当前解法中并未被使用）  public static boolean isNumber(String s) {  // 如果字符串不是运算符，则认为是数字  return !(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));  }  
}

224.【困难】基本计算器

题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

  • 输入：s = “1 + 1”
  • 输出：2

示例 2：

  • 输入：s = “(1+(4+5+2)-3)+(6+8)”
  • 输出：23
java">class Solution {  // 私有变量index，用于记录当前处理的字符索引，初始化为-1  private int index = -1;  // 私有变量chars，用于存储输入的字符串转化为字符数组后的数据  private char[] chars;  // 私有变量len，用于记录输入字符串的长度  private int len;  // 公开方法calculate，接收一个字符串s作为输入，并返回计算结果  public int calculate(String s) {  // 将输入的字符串s转化为字符数组并赋值给chars  chars = s.toCharArray();  // 获取字符数组的长度并赋值给len  len = chars.length;  // 调用深度优先搜索方法dfs进行计算，并返回结果  return dfs();  }  // 私有方法dfs，用于执行深度优先搜索并计算结果  private int dfs() {  // num用于存储最终的计算结果  int num = 0;  // sign用于记录当前的符号，默认为正号1  int sign = 1;  // cur用于构建多位数  int cur = 0;  // 当索引index小于字符串长度且当前字符不是')'时，进行循环  while (++index < len && chars[index] != ')') {  // 获取当前字符  char c = chars[index];  // 如果当前字符是'('，则递归调用dfs计算括号内的表达式  if (c == '(') {  cur = dfs();  }   // 如果当前字符是'+'或'-'，则更新num和cur，并设置新的sign  else if (c == '+' || c == '-') {  // 将之前的计算结果和符号加到num中  num += sign * cur;  // 重置cur为0，准备构建下一个数字  cur = 0;  // 设置新的sign  sign = c == '+' ? 1 : -1;  }   // 如果当前字符不是空格，则将其加入到cur中构建多位数  else if (c != ' ') {  // 将字符c转化为数字并加到cur的末尾  cur = c - '0' + cur * 10;  }  }  // 返回最终的计算结果，即将最后一个数字cur和最后一个符号sign加到num中  return num + sign * cur;  }  
}

2.【中等】两数相加

  • 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
  • 请你将两个数相加，并以相同形式返回一个表示和的链表。
  • 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
在这里插入图片描述

  • 输入：l1 = [2,4,3], l2 = [5,6,4]
  • 输出：[7,0,8]
  • 解释：342 + 465 = 807.

示例 2：

  • 输入：l1 = [0], l2 = [0]
  • 输出：[0]

示例 3：

  • 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  • 输出：[8,9,9,9,0,0,0,1]
java">/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */  
class Solution {  // 定义一个方法，用于将两个链表表示的数字相加  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  // 创建一个哑节点（dummy node），也叫作哨兵节点，用于简化边界情况的处理  ListNode pre = new ListNode(0);  // cur 指针用于遍历新链表  ListNode cur = pre;  // carry 变量用于记录进位  int carry = 0;  // 当两个链表都不为空时，进行循环  while(l1 != null || l2 != null) {  // 如果链表l1为空，则取值为0，否则取l1当前节点的值  int x = l1 == null ? 0 : l1.val;  // 如果链表l2为空，则取值为0，否则取l2当前节点的值  int y = l2 == null ? 0 : l2.val;  // 计算当前位的和（包括进位）  int sum = x + y + carry;  // 更新进位  carry = sum / 10;  // 更新当前位的值（0-9）  sum = sum % 10;  // 在新链表的当前位置创建一个新节点，值为sum  cur.next = new ListNode(sum);  // 移动cur指针到下一个位置  cur = cur.next;  // 如果链表l1不为空，则移动到下一个节点  if(l1 != null)  l1 = l1.next;  // 如果链表l2不为空，则移动到下一个节点  if(l2 != null)  l2 = l2.next;  }  // 如果循环结束后还有进位，则在新链表的末尾添加一个节点，值为进位  if(carry == 1) {  cur.next = new ListNode(carry);  }  // 返回新链表的头节点（即哑节点的下一个节点）  return pre.next;  }  
}

✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊

🏠 我在CSDN等你哦！我的主页😍

在这里插入图片描述–


http://www.ppmy.cn/devtools/46467.html

相关文章

声明式事务原理，传播机制，事务失效情况二

声明式事务原理，传播机制，事务失效情况二

不同类中的方法互相调用&#xff1a; 当不同类中的方法相互调用时&#xff0c;如果这些方法都被 Transactional 注解标记&#xff0c;并且被 Spring 代理管理&#xff0c;那么 Spring 的事务管理通常仍然会按照预期进行。然而&#xff0c;为了确保事务按照预期工作&#xff0c;…
阅读更多...
提高篇（六）：利用Processing进行数据艺术创作：从数据获取到视觉表达

提高篇（六）：利用Processing进行数据艺术创作：从数据获取到视觉表达

提高篇（六）：利用Processing进行数据艺术创作：从数据获取到视觉表达 引言 数据艺术是一种结合数据和艺术的创作形式，通过将数据转化为视觉图像，表达出数据背后的故事和美感。Processing作为一种强大的创意编程工具，能够帮助艺术家和设计师将复杂的数据以直观和艺术化的方…
阅读更多...
【Linux】信号

【Linux】信号

一、信号的基本概念 1.1 信号生活中的例子&#xff1a; 信号在生活中&#xff0c;随时可以产生&#xff0c;信号的产生和我的认知是异步的我能认识这个信号我们知道信号产生了&#xff0c;信号该怎么处理&#xff0c;我可以识别并处理这个信号我们可能证字啊左着更重要的事情…
阅读更多...
TqdmWarning: IProgress not found. Please update jupyter and ipywidgets.

TqdmWarning: IProgress not found. Please update jupyter and ipywidgets.

jupyter notebook报错 在pycharm的terminal中 安装完成后就不会再报错了
阅读更多...
JVM学习-MAT

JVM学习-MAT

MAT(Memory Analyzer Tool) 基本概述 Java堆内存分析器&#xff0c;可以用于查找内存泄漏以及查看内存消耗情况MAT是基于Eclipse开发的&#xff0c;不仅可以单独使用&#xff0c;还能以插件方式嵌入Eclipse中使用&#xff0c;是一款免费的性能分析工具 获取堆dump文件 dump…
阅读更多...
NDIS网络接口

NDIS网络接口

在windows发行版本中&#xff0c;真的存在一个 ndis.sys 的驱动文件&#xff0c;和我们认知的不太一样&#xff0c;它真的是一个DLL&#xff0c;NDIS 库打包在 Ndis.sys&#xff08;一个内核模式导出库&#xff09;中&#xff0c;作为一组函数&#xff0c;强调宏以获得最佳性能…
阅读更多...
功能强大且专业的PDF转换软件PDF Shaper Professional 14.2

功能强大且专业的PDF转换软件PDF Shaper Professional 14.2

PDF Shaper Professional是一款适用于Windows的程序&#xff0c;可让您在计算机上处理PDF文件。 要开始使用PDF Shaper Professional&#xff0c;您需要在Windows计算机上下载并安装该程序。您还应该有合适的驱动程序和编解码器来处理计算机上的文本和图形。 安装程序后&#…
阅读更多...
ansible批量漏洞升级openssh版本

ansible批量漏洞升级openssh版本

1、ansible宿主机准备好环境&#xff0c;并写好hosts文件 [rootoxidized ansible]# cat hosts [all] 10.10.200.33 10.10.200.34 10.10.200.35跑playbook之前记得提前发送秘钥 ssh-copy-id 10.10.200.33/34/352、下载好安装包&#xff0c;然后编写yml [rootoxidized ansible]…
阅读更多...
最新文章

Copyright @ 2022~2023