LeetCode 71. 简化路径 / 1614. 括号的最大嵌套深度 / 89. 格雷编码(不会做)

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;
    }
}
上一篇:第 71 场双周赛


下一篇:7-71 求平方与倒数序列的部分和