蓝天网站建设,图表 wordpress,页面布局方式,深圳做网站最好题目
71简化路径
思路
这个题和逆波兰表达式求值很想#xff0c;都是通过使用栈来实现。 对于给定的绝对路径#xff0c;首先可以使用 “/” 将其分割#xff0c;分割后的字符串共包括四种情况#xff1a; 空字符串#xff08;例如当绝对路径为//时#x…题目
71简化路径
思路
这个题和逆波兰表达式求值很想都是通过使用栈来实现。 对于给定的绝对路径首先可以使用 “/” 将其分割分割后的字符串共包括四种情况 空字符串例如当绝对路径为//时分割后为空字符串 . “. .”目录名 对于第一种和第二种情况即「空字符串」和 “.”无需进行处理因为「空字符串」没有任何含义而 “.” 表示当前目录本身无需切换目录。 对于 第三种情况(即. .)表示返回上一级目录因此当栈不为空时直接弹出一个目录名即可对于第四种情况直接将该目录名入栈即可。
代码
这里列出 java 代码
public String simplifyPath (String path){// 定义栈来处理 pathDequeString stack new ArrayDeque();// 按 “/” 分割分割后的结果包括 空字符串、.、 .. 目录名String[] names path.split(/);for (String name : names) {// 空字符串和., 直接跳过if (name.length() 0 !name.equals(.)) {// 如果是 ..说明要返回上一级if (name.equals(..)) {// 栈非空时弹出一个元素模拟返回上一级if (!stack.isEmpty()) {stack.pollLast();}}// 若是目录名则入栈else {stack.offerLast(name);}}}// 保存最终路径StringBuilder sb new StringBuilder();if (!stack.isEmpty()) {while (!stack.isEmpty()) {sb.append(/);sb.append(stack.pollFirst());}}else {sb.append(/);}return sb.toString();}时空复杂度
时间复杂度O(n)其中 n 是字符串的长度。需要遍历字符串的每个字符对于每个字符入栈和出栈操作的时间复杂度为 O(1)因此总的时间复杂度为 O(n)。
空间复杂度O(n)其中 n 是字符串的长度。空间复杂度主要取决于字符串的分割和栈的使用。分割字符串需要 O(n) 的空间栈的最大空间大小为 O(n)。因此空间复杂度为 O(n)。
