682. 棒球比赛（简单）
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表
ops，其中ops[i]是你需要记录的第i项操作，ops遵循下述规则：
- 整数
x- 表示本回合新获得分数x"+"- 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。"D"- 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。"C"- 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。请你返回记录中所有得分的总和。
解法一、栈
利用了一下default处理数字部分
class Solution {
public static int calPoints(String[] operations) {
Stack<Integer> s = new Stack<>();
int res = 0;
for(String t : operations){
switch (t){
case "+":
int temp = s.size();
res+=s.lastElement() + s.get(temp - 2);
s.push(s.lastElement() + s.get(temp - 2));
break;
case"D":
res+=2 * s.lastElement();
s.push(2 * s.lastElement());
break;
case"C":
res-=s.lastElement();
s.pop();
break;
default:
int num= Integer.parseInt(t);
res+=num;
s.push(num);
}
}
return res;
}
}
解法二、变长数组
class Solution {
public int calPoints(String[] ops) {
int ret = 0;
List<Integer> points = new ArrayList<Integer>();
for (String op : ops) {
int n = points.size();
switch (op.charAt(0)) {
case '+':
ret += points.get(n - 1) + points.get(n - 2);
points.add(points.get(n - 1) + points.get(n - 2));
break;
case 'D':
ret += 2 * points.get(n - 1);
points.add(2 * points.get(n - 1));
break;
case 'C':
ret -= points.get(n - 1);
points.remove(n - 1);
break;
default:
ret += Integer.parseInt(op);
points.add(Integer.parseInt(op));
break;
}
}
return ret;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/baseball-game/solutions/1366145/bang-qiu-bi-sai-by-leetcode-solution-gxab/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。71. 简化路径（中等）
给你一个字符串
path，表示指向某一文件或目录的 Unix 风格 绝对路径 （以'/'开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中，一个点（
.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠'/'。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/'开头。- 两个目录名之间必须只有一个斜杠
'/'。- 最后一个目录名（如果存在）不能 以
'/'结尾。- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。返回简化后得到的 规范路径 。
解法一、栈模拟
先把各路径规范化放进栈，然后转化为String
注意边界时防止清空
class Solution {
public static String simplifyPath(String path) {
Stack<String> paths = new Stack<>();
StringBuffer sb = new StringBuffer("/");
String[] pa = path.split("/");
for(String s : pa){
switch (s){
case ".", "":
break;
case "..":
if(!paths.empty())paths.pop();
break;
default:
paths.push(s);
break;
}
}
for(String s : paths){
sb.append(s).append("/");
}
if(!sb.toString().equals("/"))sb.delete(sb.length()-1,sb.length());
return sb.toString();
}
}
解法二、api
public String simplifyPath(String path) {
return Path.of(path).normalize().toString();
}
388. 文件的最长绝对路径（中等）
假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：
这里将
dir作为根目录中的唯一目录。dir包含两个子目录subdir1和subdir2。subdir1包含文件file1.ext和子目录subsubdir1；subdir2包含子目录subsubdir2，该子目录下包含文件file2.ext。在文本格式中，如下所示(⟶表示制表符)：
dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 ⟶ ⟶ subsubdir2 ⟶ ⟶ ⟶ file2.ext如果是代码表示，上面的文件系统可以写为
"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"。'\n'和'\t'分别是换行符和制表符。文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用
'/'连接。上面例子中，指向file2.ext的 绝对路径 是"dir/subdir2/subsubdir2/file2.ext"。每个目录名由字母、数字和/或空格组成，每个文件名遵循name.extension的格式，其中name和extension由字母、数字和/或空格组成。给定一个以上述格式表示文件系统的字符串
input，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回0。
解法一、栈
栈相当于随时更新，深度低则回退，存放每一深度长度即可，模拟文件路径。这里depth从1开始，指直接考虑了根目录
class Solution {
public int lengthLongestPath(String input) {
int n = input.length();//长度
int pos = 0;//指针位置
int ans = 0;//答案
Deque<Integer> stack = new ArrayDeque<Integer>();//栈
while (pos < n) {
/* 检测当前文件的深度 */
int depth = 1;//深度默认为1
while (pos < n && input.charAt(pos) == '\t') {//如果有\t，加深度，加位置
pos++;
depth++;
}
/* 统计当前文件名的长度 */
boolean isFile = false;
int len = 0;
while (pos < n && input.charAt(pos) != '\n') {
if (input.charAt(pos) == '.') {
isFile = true;
}
len++;
pos++;
}
/* 跳过当前的换行符 */
pos++;
while (stack.size() >= depth) {
stack.pop();
}
if (!stack.isEmpty()) {
len += stack.peek() + 1;
}
if (isFile) {
ans = Math.max(ans, len);
} else {
stack.push(len);
}
}
return ans;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-absolute-file-path/solutions/1433141/wen-jian-de-zui-chang-jue-dui-lu-jing-by-fi0r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。解法二、哈希+模拟
这里采用了双指针结构，j用于遍历+统计名字长度。level是0，对于同一个路径，相较解法一错开一位，只是处理方式微弱地不同。对于新的目录，只要直接更新覆盖需要的长度，然后取用即可，和dp的思想稍微有些像。
class Solution {
static int[] hash = new int[10010];
public int lengthLongestPath(String s) {
Arrays.fill(hash, -1);
int n = s.length(), ans = 0;
for (int i = 0; i < n; ) {
int level = 0;
while (i < n && s.charAt(i) == '\t' && ++level >= 0) i++;
int j = i;
boolean isDir = true;
while (j < n && s.charAt(j) != '\n') {
if (s.charAt(j++) == '.') isDir = false;
}
int cur = j - i;
int prev = level - 1 >= 0 ? hash[level - 1] : -1;
int path = prev + 1 + cur;
if (isDir) hash[level] = path;
else if (path > ans) ans = path;
i = j + 1;
}
return ans;
}
}
作者：宫水三叶
链接：https://leetcode.cn/problems/longest-absolute-file-path/solutions/1434968/by-ac_oier-c55t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。碎碎念
- 重新回来了orzzzzz开始写栈，第一天写稍微少一点。距离上次写隔开很久，现在菜得switch还查半天
- 682只是熟悉数据结构，71中等偏简单，388感觉中等偏难。71学到了Path这个有点神奇的API。388Deque模拟栈在我看来其实还有点神奇，此外388要考虑的有点多，本质上是模拟+分类讨论