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; } }
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; } }
2022.1.8 每日一题
n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:
给你一个整数 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; } }