内容简介:要求从String字符串中找到最长的文件路径。这里要注意,要求的是文件路径,文件夹路径不予考虑。文件和文件夹的区别在于文件中一定包含这里以
题目要求
Suppose we abstract our file system by a string in the following manner: The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents: dir subdir1 subdir2 file.ext The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext. The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents: dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext. We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes). Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0. Note: The name of a file contains at least a . and an extension. The name of a directory or sub-directory will not contain a .. Time complexity required: O(n) where n is the size of the input string. Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.
要求从String字符串中找到最长的文件路径。这里要注意,要求的是文件路径,文件夹路径不予考虑。文件和文件夹的区别在于文件中一定包含 .
。
这里 \n
代表根目录平级,每多一个 \t
就多一层路径,这一层路径都是相对于当前的上层路径的。
以 dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext
为例
dir为第0层目录
\n\tsubdir1
代表subdir1是第一层目录,且其是当前父目录dir的子目录
\n\t\n\tsubdir2
代表subdir2为第一层目录,且其是当前父目录dir的子目录,此时的一级父目录从subdir1更新为subdir2
\n\t\tfile.ext
代表tfile.ext为二级目录,位于当前一级目录subdir2之下
思路和代码
综上分析,我们可以记录一个信息,即当前每一级的目录究竟是谁,每次只需要保留当前一级目录已有的路径长度即可。还是拿上面的例子 dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext
:
遍历完dir: 0级目录长度为3 遍历完\n\tsubdir: 0级目录长度为3, 1级目录长度为11(dir/subdir1) 遍历完\n\tsubdir2: 0级目录长度为3, 1级目录长度为11(dir/subdir2) 遍历完\n\t\tfile.ext: 0级目录长度为3, 1级目录长度为11(dir/subdir2), 2级目录长度为20 综上,最长的文件路径长为20
代码如下:
public int lengthLongestPath(String input) { if(input==null || input.isEmpty()) return 0; //记录当前每一级路径对应的路径长度 List<Integer> stack = new ArrayList<Integer>(); int left = 0, right = 0; int max = 0; int curDepth = 0; //当前遍历的是文件还是文件夹 boolean isFile = false; while(right < input.length()) { char c = input.charAt(right); if(c == '\n' || c == '\t') { //如果是文件分割符的起点,则处理前面的字符串 if(right-1>=0 && input.charAt(right-1)!='\n' && input.charAt(right-1)!='\t') { int length = right - left; if(stack.isEmpty()) { stack.add(length+1); }else if(curDepth == 0){ stack.set(0, length+1); }else{ int prev = stack.get(curDepth-1); int now = prev + length + 1; if(stack.size() <= curDepth) { stack.add(now); }else{ stack.set(curDepth, now); } } if(isFile) { max = Math.max(max, stack.get(curDepth)-1); } left = right; isFile = false; } //如果是文件分隔符的末尾,则处理文件分隔符,判断是几级路径 if(right+1<input.length() && input.charAt(right+1)!='\n' && input.charAt(right+1) !='\t'){ curDepth = right - left; left = right+1; } }else if(c == '.') { isFile = true; } right++; } //处理最后的字符串 if(left != right && isFile) { if(curDepth == 0) { max = Math.max(max, right - left); }else { max = Math.max(max, stack.get(curDepth-1) + right - left); } } return max; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Spring 3.x企业应用开发实战
陈雄华 / 电子工业出版社 / 2012-2-1 / 90.00元
内容简介 Spring 3.0是Spring在积蓄了3年之久后,隆重推出的一个重大升级版本,进一步加强了Spring作为Java领域第一开源平台的翘楚地位。 Spring 3.0引入了众多Java开发者翘首以盼的新功能和新特性,如OXM、校验及格式化框架、REST风格的Web编程模型等。这些新功能实用性强、易用性高,可大幅降低Java应用,特别是Java Web应用开发的难度,同时有效......一起来看看 《Spring 3.x企业应用开发实战》 这本书的介绍吧!