LeetCode 388. 文件的最长绝对路径(不用栈,前缀和)
发布日期:2021-07-01 03:25:53
浏览次数:2
分类:技术文章
本文共 2038 字,大约阅读时间需要 6 分钟。
1. 题目
假设我们以下述方式将我们的文件系统抽象成一个字符串:
字符串 "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 包含两个子目录 subdir1 和 subdir2。
subdir1 包含一个文件 file1.ext 和一个空的二级子目录 subsubdir1。 subdir2 包含一个二级子目录 subsubdir2 ,其中包含一个文件 file2.ext。我们致力于寻找我们文件系统中文件的最长 (按字符的数量统计) 绝对路径。例如,在上述的第二个例子中,最长路径为 "dir/subdir2/subsubdir2/file2.ext"
,其长度为 32 (不包含双引号)。
给定一个以上述格式表示文件系统的字符串,返回文件系统中文件的最长绝对路径的长度。 如果系统中没有文件,返回 0。
说明:
文件名至少存在一个.
和一个扩展名。 目录或者子目录的名字不能包含 .
。 要求时间复杂度为 O(n) ,其中 n 是输入字符串的大小。 请注意,如果存在路径 aaaaaaaaaaaaaaaaaaaaa/sth.png
的话,那么 a/aa/aaa/file1.txt
就不是一个最长的路径。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-absolute-file-path 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 用一个数组记录到当前层的字符个数,利用前缀累加
\t
的个数表示层数,注意字符个数也包括\t
测试样例
"dir\n file.txt" "di r\n file.txt" "dir\n file.txt""a.aaa\n\tfile.txt""dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext""dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
class Solution { public: int lengthLongestPath(string input) { int maxlen=0, i, lv = 0, count=0; vector len(50,0); bool foundfile = false; for(i = 0; i < input.size(); ++i) { if(input[i]=='\n') { len[lv] = lv>0 ? len[lv-1]+count : count;//利用前缀求当前长度 if(foundfile)//找到文件了 { maxlen = max(maxlen, len[lv]+lv);//更新最大长度,lv为\t个数 foundfile = false; } lv = 0; count = 0; } else if(input[i]=='\t') lv++; else { if(i>0 && input[i-1]=='.' && (isalpha(input[i])||isdigit(input[i]))) foundfile = true; count++; } } len[lv] = lv>0 ? len[lv-1]+count : count; if(foundfile) maxlen = max(maxlen, len[lv]+lv); return maxlen; }};
0 ms 6.6 MB
转载地址:https://michael.blog.csdn.net/article/details/106210795 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年05月05日 16时50分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux中的tty,pty与pts以及/dev下各种tty设备
2019-05-02
gdbserver远程调试
2019-05-02
openlog、syslog和closelog函数
2019-05-02
syslog详解
2019-05-02
Linux下shell的远程协助
2019-05-02
fastcgi中的多线程使用
2019-05-02
实现spawn-fcgi的守护监控功能
2019-05-02
JavaScript window.location对象
2019-05-02
业务流程图的绘制流程分享(一)
2019-05-02
W25Q64Flash芯片
2019-05-02
STM32唯一ID(Unique Device ID)的读取方法
2019-05-02
rtthread 函数学习
2019-05-02
关于RT-Thread调度器锁
2019-05-02
使用j_Flash合并bin文件
2019-05-02
STM32 备份域(备份寄存器、备份SRAM)详解及数据丢失问题处理
2019-05-02
MicroPython入门指南
2019-05-02
x265-1.7版本-common/bitstream.h注释
2019-05-02
x265-1.7版本-common/frame.h注释
2019-05-02
x265-1.7版本-common/framedata.cpp注释
2019-05-02
x265-1.7版本-common/framedata.h注释
2019-05-02