71. 简化路径

2022.1.6 每日一题

题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。

示例 1：

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

示例 2：

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

示例 3：

输入：path = “/home//foo/”
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = “/a/./b/…/…/c/”
输出："/c"

提示：

1 <= path.length <= 3000
path 由英文字母，数字，’.’，’/’ 或 ‘_’ 组成。
path 是一个有效的 Unix 风格绝对路径。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplify-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

class Solution {
    public String simplifyPath(String path) {
        //很久以前一道每日一题，栈

        int l = path.length();
        Stack<String> stack = new Stack<>();
        String[] ss = path.split("/");
        //stack.push("");
        for(String s : ss){
            //如果为null，那么不做操作
            if(s.equals(null) || s.equals(".") || s.equals("")){
                continue;
            }else if(s.equals("..")){
                if(stack.isEmpty())
                    continue;
                stack.pop();
            }else{
                stack.push(s);
            }
            //System.out.println(s);
        }
        int n = stack.size();
        String[] res = new String[n];

        for(int i = n - 1; i >= 0; i--){
            res[i] = stack.pop();
        }
        String ans = "/";
        for(String s : res){
            ans += s;
            ans += "/";
        }
        
        return ans.length() > 1 ? ans.substring(0, ans.length() - 1) : ans;
    }
}

1614. 括号的最大嵌套深度

2022.1.7 每日一题

题目描述

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：

字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

depth("") = 0
depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 “)(” 、"(()" 都不是 有效括号字符串 。

给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。

示例 1：

输入：s = “(1+(2*3)+((8)/4))+1”
输出：3
解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = “(1)+((2))+(((3)))”
输出：3

示例 3：

输入：s = “1+(2*3)/(2-1)”
输出：1

示例 4：

输入：s = “1”
输出：0

提示：

1 <= s.length <= 100
s 由数字 0-9 和字符 ‘+’、’-’、’*’、’/’、’(’、’)’ 组成
题目数据保证括号表达式 s 是 有效的括号表达式

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

用栈，其实不用栈用个变量也行

class Solution {
    public int maxDepth(String s) {
        int l = s.length();
        Stack<Character> stack = new Stack<>();
        int max = 0;
        for(char c : s.toCharArray()){
            if(c == '(')
                stack.push(c);
            else if(c == ')')
                stack.pop();
            max = Math.max(max, stack.size());
        }
        return max;
    }
}

89. 格雷编码

2022.1.8 每日一题

题目描述

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
-00 和 01 有一位不同
-01 和 11 有一位不同
-11 和 10 有一位不同
-10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
-00 和 10 有一位不同
-10 和 11 有一位不同
-11 和 01 有一位不同
-01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

提示：

1 <= n <= 16

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gray-code
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

不会做

class Solution {
    public List<Integer> grayCode(int n) {
        //实在想了半天，想不到好的列举办法
        //然后看答案了，发现太强了
        //设n位格雷编码的序列是Gn，倒序是Gnt
        //那么在Gn前面补0，在Gnt前面补1，得到的就是Gn+1
        //例如二位格雷编码是 00 01 11 10
        //按这个规律得到8位是 000 001 011 010 110 111 101 100
        //想想怎么写程序

        List<Integer> res = new ArrayList<>();
        res.add(0);

        for(int i = 1; i <= n; i++){
            for(int j = res.size() - 1; j >= 0; j--){
                int temp = res.get(j) | (1 << (i - 1));
                res.add(temp);
            }
        }
        return res;
    }
}

官解的第二个方法
构造规则是 第i个格雷码 可以用 i 的二进制表示中，相邻两位的异或值来得到
比如对于n=3，那么格雷码序列是：
000 001 011 010 110 111 101 100
比如第四个格雷码就是 110（从0开始）
那么怎么得到第四个格雷码呢，4的二进制表示是0100，那么相邻两位异或得到的结果是 110
刚好是格雷码的第四个
所以可以写程序：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < (1 << n); i++){
            res.add((i >> 1) ^ i);
        }
        return res;
    }
}