Go Java算法之简化路径实例详解

2024-12-01 15:29:53

简化路径

给你一个字符串 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 风格绝对路径。

方法一：栈（Java）

我们首先将给定的字符串 path 根据 / 分割成一个由若干字符串组成的列表，记为 names。

对于「空字符串」以及「一个点」，我们实际上无需对它们进行处理，因为「空字符串」没有任何含义，而「一个点」表示当前目录本身，我们无需切换目录。

对于「两个点」或者「目录名」，我们则可以用一个栈来维护路径中的每一个目录名。当我们遇到「两个点」时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。当我们遇到「目录名」时，就把它放入栈。

class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<String>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        StringBuffer ans = new StringBuffer();
        if (stack.isEmpty()) {
            ans.append('/');
        } else {
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());
            }
        }
        return ans.toString();
    }
}

时间复杂度：O（N）

空间复杂度：O（N）

方法二：标准库（Go）

具体的方法思路请看上文中的表述。由于Go本身的标准库已经具备该能力，所以只需调用标准库即可完成。

import (
	path2 "path"
)
func simplifyPath(path string) string {
	return path2.Clean(path)
}

时间复杂度：O（N）

空间复杂度：O（N）

以上就是Go Java算法之简化路径实例详解的详细内容，更多关于Go Java算法简化路径的资料请关注我们其它相关文章！

Go Java算法之单词搜索示例详解

目录单词搜索算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo
Go Java算法之找不同示例详解

目录找不同方法一:计数(Java) 方法二:求和(Go) 找不同给定两个字符串 s 和 t ,它们只包含小写字母. 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母. 请找出在 t 中被添加的字母. 示例 1: 输入:s = "abcd", t = "abcde" 输出:"e" 解释:'e' 是那个被添加的字母. 示例 2: 输入:s = "", t = "y" 输出:"y&q
Go Java算法之K个重复字符最长子串详解

目录至少有K个重复字符的最长子串方法一:分治(Java) 方法二:滑动窗口(go) 至少有K个重复字符的最长子串给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k .返回这一子串的长度. 示例 1: 输入:s = "aaabb", k = 3 输出:3 解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次. 示例 2: 输入:s = "ababbc", k = 2 输出:5
Go Java算法之字符串中第一个唯一字符详解

目录字符串中第一个唯一字符方法一:哈希表(Java) 方法二:队列(Go) 字符串中第一个唯一字符给定一个字符串 s ,找到它的第一个不重复的字符,并返回它的索引 .如果不存在,则返回 -1 . 示例 1: 输入: s = "leetcode" 输出: 0 示例 2: 输入: s = "loveleetcode" 输出: 2 示例 3: 输入: s = "aabb" 输出: -1 提示: 1 <= s.length <= 10
Go java 算法之括号生成示例详解

目录括号生成方法一:深度优先遍历(java) 方法一:深度优先遍历(go) 括号生成数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合. 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <=
Go Java 算法之字符串解码示例详解

目录字符串解码方法一:栈(Java) 方法二:递归(Go) 字符串解码给定一个经过编码的字符串,返回它解码后的字符串. 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正重复 k 次.注意 k 保证为正整数. 你可以认为输入字符串总是有效的:输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的. 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入. 示例 1: 输入:
Go Java算法之简化路径实例详解

目录简化路径方法一:栈(Java) 方法二:标准库(Go) 简化路径给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径. 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身:此外,两个点 (..) 表示将目录切换到上一级(指向父目录):两者都可以是复杂相对路径的组成部分. 任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' . 对于此问题,任何其他格式的点(例如,'...')均被视为文件/
java 中自定义OutputFormat的实例详解

java 中自定义OutputFormat的实例详解实例代码: package com.ccse.hadoop.outputformat; import java.io.IOException; import java.net.URI; import java.net.URISyntaxException; import java.util.StringTokenizer; import org.apache.hadoop.conf.Configuration; import org.apa
java中Spring Security的实例详解

java中Spring Security的实例详解 spring security是一个多方面的安全认证框架,提供了基于JavaEE规范的完整的安全认证解决方案.并且可以很好与目前主流的认证框架(如CAS,中央授权系统)集成.使用spring security的初衷是解决不同用户登录不同应用程序的权限问题,说到权限包括两部分:认证和授权.认证是告诉系统你是谁,授权是指知道你是谁后是否有权限访问系统(授权后一般会在服务端创建一个token,之后用这个token进行后续行为的交互). spring
Java Web请求与响应实例详解

Servlet最主要作用就是处理客户端请求并作出回应,为此,针对每次请求,Web容器在调用service()之前都会创建两个对象,分别是HttpServletRequest和HttpServletResponse.其中HttpServletRequest封装HTTP请求消息,HttpServletResponse封装HTTP响应消息.需要注意的是,Web服务器运行过程中,每个Servlet都会只创建一个实例对象,不过每次请求都会调用Servlet实例的service(ServletRequest
Java 获取服务器环境的实例详解

Java 获取服务器环境的实例详解废话不多说,直接上代码,代码中的注释写的比较清楚,请大家好好看, package com.rapido.utils; import java.util.Properties; /** * 获取服务器环境信息 * @author X-rapido * */ public class SystemDataUtil { public static Properties getSystemProperties() { Properties props = System
Java基础之Filter的实例详解

Java基础之Filter的实例详解定义: Filter,是Servlet的一种,接口类为javax.servlet.Filter,以一种模块化或者可重用的方法封装公共行为,本质是可复用的代码片段. 职责:在请求到达Servlet之前对请求头作预处理,或者在服务器响应完成之后对响应内容作后处理.分界线为chain.doFilter的调用.该调用是将请求处理权交给其Filter列表链上的其它Filter. 生命周期: Filter在Web容器启动时被容器实例化,并调用其init方法完成初始化,
Java打印流原理及实例详解

这篇文章主要介绍了Java打印流原理及实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下平时我们在控制台打印输出,是调用print方法和println方法完成的,这两个方法都来自于java.io.PrintStream类,该类能够方便地打印各种数据类型的值,是一种便捷的输岀方式. PrintStream类 PrintStream类,为其他输出流添加了功能,使他们能够方便的打印各种数据值表示格式. PrintStream类的特点: 只负责数
java操作mongoDB查询的实例详解

java操作mongo查询的实例详解前言: MongoDB是一个基于分布式文件存储的数据库.由C++语言编写.旨在为WEB应用提供可扩展的高性能数据存储解决方案. MongoDB是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的.他支持的数据结构非常松散,是类似json的bson格式,因此可以存储比较复杂的数据类型.Mongo最大的特点是他支持的查询语言非常强大,其语法有点类似于面向对象的查询语言,几乎可以实现类似关系数据库单表查询的绝大部分功能,而且
Java 中This用法的实例详解

Java 中This用法的实例详解用类名定义一个变量的时候,定义的只是一个引用,外面可以通过这个引用来访问这个类里面的属性和方法. 那们类里面是够也应该有一个引用来访问自己的属性和方法纳? 呵呵,Java提供了一个很好的东西,就是 this 对象,它可以在类里面来引用这个类的属性和方法.先来个简单的例子: public class ThisDemo { String name="Mick"; public void print(String name){ System.out.pr

Go Java算法之简化路径实例详解

目录

简化路径

方法一：栈（Java）

方法二：标准库（Go）

相关推荐

随机推荐