最长绝对文件路径——算法面试刷题1(google),字符串处理,使用tree遍历dfs类似思路

假设我们通过以下的方式用字符串来抽象我们的文件系统:
字符串"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"代表了:

dir
subdir1
subdir2
file.ext

目录 dir 包含一个空子目录 subdir1 和一个包含文件file.ext的子目录 subdir2
字符串

"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

代表了:

dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext

目录 dir 包含两个子目录 subdir1subdir2subdir1 包含一个文件 file1.ext 和一个空的二级子目录 subsubdir1subdir2 包含一个包含文件 file2.ext 的二级子目录 subsubdir2
我们有兴趣找到文件系统中文件的最长绝对路径(字符数)。例如,在上面的第二个例子中,最长的绝对路径是“dir/subdir2/subsubdir2/file2.ext”,其长度为 32 (不包括双引号)。
给定一个以上述格式表示文件系统的字符串,返回抽象文件系统中文件最长绝对路径的长度。如果系统中没有文件,则返回 0

 
  • 一个文件的名称至少包含一个 . 和扩展名。
  • 目录或子目录的名称不会包含 .
  • 时间复杂度要求: O(n) 其中 n 是输入字符串的大小。
  • 请注意如果有另一条路径 aaaaaaaaaaaaaaaaaaaaa / sth.png 存在的话, a/aa/aaa/file1.txt 不是最长的文件路径。---这个东西巨坑!!!以为是树的最长路径,结果还不是!!!。   ****我写的代码:
    class Solution:
    """
    @param input: an abstract file system
    @return: return the length of the longest absolute path to file
    """
    def lengthLongestPath(self, input):
    # write your code here
    ans = 0
    path = []
    lines = input.split("\n")
    for line in lines:
    cnt = self.count_tab(line)
    path_name = self.get_path_name(line)
    if cnt < len(path):
    path[cnt] = path_name
    else:
    path.append(path_name)
    if self.is_file(path_name):
    length = len("/".join(path[:cnt+1]))
    if length > ans: ans = length
    return ans def count_tab(self, s):
    return s.count("\t") def get_path_name(self, s):
    index = s.rfind("\t")
    if index >= 0:
    return s[index+1:] # +2 is error. \t is a char!!!
    else:
    return s def is_file(self, f):
    return f.find(".") >= 0

    参考代码:

    import re
    
    class Solution:
    # @param {string} input an abstract file system
    # @return {int} return the length of the longest absolute path to file
    def lengthLongestPath(self, input):
    # Write your code here
    dict = collections.defaultdict(lambda: "")
    lines = input.split("\n") n = len(lines)
    result = 0
    for i in xrange(n):
    count = lines[i].count("\t") lines[i] = dict[count - 1] + re.sub("\\t+","/", lines[i])
    if "." in lines[i]:
    result = max(result, len(lines[i]))
    dict[count] = lines[i] return result

    值得借鉴的地方:

    1、re.sub() 替换连续\t为/

    2、使用dict来存储路径长度

上一篇:【BZOJ1857】传送带(分治经典:三分套三分)


下一篇:loj10017. 「一本通 1.2 练习 4」传送带(三分套三分)