核心内容摘要
DCT-Net人像卡通化惊艳案例：婚礼请柬新人卡通形象双人联动
文章目录摘要描述题解答案题解代码分析
字符串分割
使用栈维护路径
计算层级
处理路径栈
计算当前路径长度
判断文件和目录
完整执行流程示例示例测试及结果示例 1input dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext示例 2input dir\n\tsubdir1\n\t\tfile
ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile
ext示例 3input a示例 4input file
txt\nfile
txt\nlongfile.txt时间复杂度空间复杂度实际应用场景场景一文件系统操作场景二日志解析场景三配置文件解析场景四树形结构解析
总结摘要这道题其实挺有意思的它要求我们解析一个用字符串表示的文件系统然后找到指向文件的最长绝对路径。
听起来像是文件系统操作但实际上是一个字符串解析和路径计算的问题。
关键点在于如何正确解析制表符\t来表示目录层级以及如何计算每个文件的绝对路径长度。
这道题的核心在于如何理解制表符的层级关系以及如何维护当前路径的栈结构。
今天我们就用 Swift 来搞定这道题顺便聊聊这种路径解析的方法在实际开发中的应用场景比如文件系统操作、日志解析、配置文件解析等等。
描述题目要求是这样的给定一个用字符串表示的文件系统其中\n表示换行符\t表示制表符用来表示目录层级返回文件系统中指向文件的最长绝对路径的长度。
如果系统中没有文件返回0。
示例 1输入 input dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext 输出 20 解释 只有一个文件绝对路径为 dir/subdir2/file.ext 路径长度 20示例 2输入 input dir\n\tsubdir1\n\t\tfile
ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile
ext 输出 32 解释 存在两个文件 dir/subdir1/file
ext 路径长度 21 dir/subdir2/subsubdir2/file
ext 路径长度 32 返回 32 因为这是最长的路径示例 3输入 input a 输出 0 解释 不存在任何文件没有扩展名示例 4输入 input file
txt\nfile
txt\nlongfile.txt 输出 12 解释 根目录下有 3 个文件。
因为根目录中任何东西的绝对路径只是名称本身所以答案是 longfile.txt 路径长度为 12提示1 input.length 10^4input可能包含小写或大写的英文字母一个换行符\n一个制表符\t一个点.一个空格 和数字。
这道题的核心思路是什么呢我们需要按行分割字符串然后解析每行的制表符数量来确定层级使用栈来维护当前路径最后计算每个文件的绝对路径长度找到最长的。
题解答案下面是完整的 Swift 解决方案classSolution{funclengthLongestPath(_input:String)-Int{// 按换行符分割字符串letlinesinput.components(separatedBy:\n)// 用栈来维护当前路径存储每层的路径长度varstack:[Int][]varmaxLength0forlineinlines{// 计算当前行的层级制表符的数量letlevelgetLevel(line)// 移除制表符获取实际内容letcontentline.replacingOccurrences(of:\t,with:)letcontentLengthcontent.count// 如果当前层级小于等于栈的深度需要弹出栈顶元素直到层级匹配whilestack.countlevel{stack.removeLast()}// 计算当前路径的长度// 如果栈为空说明是根目录路径长度就是内容长度// 如果栈不为空需要加上父路径长度和分隔符 /letcurrentLength:Intifstack.isEmpty{currentLengthcontentLength}else{currentLengthstack.last!1contentLength// 1 是分隔符 /}// 如果是文件包含 .更新最大长度ifcontent.contains(.){maxLengthmax(maxLength,currentLength)}else{// 如果是目录将当前路径长度压入栈stack.append(currentLength)}}returnmaxLength}// 计算行的层级制表符的数量privatefuncgetLevel(_line:String)-Int{varlevel0forcharinline{ifchar\t{level1}else{break}}returnlevel}}题解代码分析让我们一步步分析这个解决方案
字符串分割首先我们需要将输入字符串按换行符分割成多行letlinesinput.components(separatedBy:\n)components(separatedBy: \n)会将字符串按换行符分割成数组每一行代表文件系统中的一个条目文件或目录。
使用栈维护路径我们使用栈来维护当前路径的层级结构varstack:[Int][]栈中存储的是每一层的路径长度不包括当前层的名称。
这样我们可以快速计算当前路径的总长度。
为什么使用栈因为文件系统是树形结构当我们进入一个目录时需要记录当前路径当我们退出目录时需要回到上一级路径。
栈的先进后出特性正好符合这种需求。
计算层级我们需要计算每行的层级也就是制表符的数量privatefuncgetLevel(_line:String)-Int{varlevel0forcharinline{ifchar\t{level1}else{break}}returnlevel}这个方法从字符串开头开始统计连续的制表符数量。
制表符的数量就代表了目录的层级深度。
示例dir→ level 0根目录\tsubdir1→ level 1一级子目录\t\tfile
ext→ level 2二级子目录下的文件
处理路径栈当我们处理新的一行时需要根据层级调整栈// 如果当前层级小于等于栈的深度需要弹出栈顶元素直到层级匹配whilestack.countlevel{stack.removeLast()}这个逻辑很重要。
如果当前行的层级小于栈的深度说明我们已经回到了上一级或更上级的目录需要弹出栈顶元素直到栈的深度等于当前层级。
示例假设栈中存储的是[3, 11, 20]对应路径 “dir/subdir1/subsubdir1”当前行是\tsubdir2level 1。
栈的深度是 3当前层级是 1需要弹出 2 个元素栈变成[3]这样栈就对应路径 “dir”符合当前层级
计算当前路径长度计算当前路径的总长度letcurrentLength:Intifstack.isEmpty{currentLengthcontentLength}else{currentLengthstack.last!1contentLength// 1 是分隔符 /}如果栈为空说明是根目录路径长度就是内容长度。
如果栈不为空需要加上父路径长度和分隔符/。
示例假设栈中存储的是[3]对应路径 “dir”当前内容是subdir1长度 7。
当前路径长度 3“dir” 1‘/’ 7“subdir1” 11对应路径 “dir/subdir1”
判断文件和目录我们需要判断当前条目是文件还是目录ifcontent.contains(.){maxLengthmax(maxLength,currentLength)}else{stack.append(currentLength)}如果内容包含.说明是文件我们更新最大长度。
如果是目录我们将当前路径长度压入栈供后续使用。
为什么用.判断根据题目描述文件名遵循name.extension的格式所以包含.的就是文件。
目录名不包含.。
完整执行流程示例让我们用一个例子来理解整个执行过程。
假设输入是dir\n\tsubdir1\n\t\tfile
ext\n\tsubdir2\n\t\tfile
ext处理 “dir”level 0content “dir”contentLength 3栈为空currentLength 3是目录压入栈stack [3]处理 “\tsubdir1”level 1content “subdir1”contentLength 7栈深度 1等于 level不需要弹出currentLength 3 1 7 11是目录压入栈stack [3, 11]处理 “\t\tfile
ext”level 2content “file
ext”contentLength 9栈深度 2等于 level不需要弹出currentLength 11 1 9 21是文件更新 maxLength 21处理 “\tsubdir2”level 1content “subdir2”contentLength 7栈深度 2大于 level弹出栈顶stack [3]currentLength 3 1 7 11是目录压入栈stack [3, 11]处理 “\t\tfile
ext”level 2content “file
ext”contentLength 9栈深度 2等于 level不需要弹出currentLength 11 1 9 21是文件更新 maxLength max(21,
21最终返回 21。
示例测试及结果让我们用几个例子来测试一下这个解决方案示例 1input “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”执行过程处理 “dir”栈 [3]maxLength 0处理 “\tsubdir1”栈 [3, 11]maxLength 0处理 “\tsubdir2”栈 [3, 11]弹出后栈 [3]然后栈 [3, 11]maxLength 0处理 “\t\tfile.ext”currentLength 11 1 9 21maxLength 21**结果**返回20注意实际路径是 “dir/subdir2/file.ext”长度是 20不是 21让我重新计算dir/subdir2/file.ext 3 1 7 1 9 20示例 2input “dir\n\tsubdir1\n\t\tfile
ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile
ext”执行过程处理 “dir”栈 [3]处理 “\tsubdir1”栈 [3, 11]处理 “\t\tfile
ext”currentLength 11 1 9 21maxLength 21处理 “\t\tsubsubdir1”栈 [3, 11, 21]处理 “\tsubdir2”栈 [3, 11]弹出后栈 [3]然后栈 [3, 11]处理 “\t\tsubsubdir2”栈 [3, 11, 21]处理 “\t\t\tfile
ext”currentLength 21 1 9 31maxLength 31**结果**返回32路径 “dir/subdir2/subsubdir2/file
ext” 的长度让我重新计算dir/subdir2/subsubdir2/file
ext 3 1 7 1 10 1 9 32示例 3input “a”执行过程处理 “a”level 0content “a”不包含 ‘.’是目录栈 [1]maxLength 0**结果**返回0没有文件示例 4input “file
txt\nfile
txt\nlongfile.txt”执行过程处理 “file
txt”currentLength 9maxLength 9处理 “file
txt”currentLength 9maxLength 9处理 “longfile.txt”currentLength 12maxLength 12**结果**返回12时间复杂度让我们分析一下这个算法的时间复杂度时间复杂度O(n)其中n是输入字符串的长度。
分析字符串分割components(separatedBy: \n)需要遍历整个字符串一次时间复杂度 O(n)遍历所有行需要遍历所有行总字符数不超过 n时间复杂度 O(n)计算层级每行最多有 O(n) 个字符但所有行的总字符数是 n所以总时间复杂度 O(n)栈操作每个元素最多入栈和出栈一次总操作次数不超过行数时间复杂度 O(n)所以总时间复杂度是 O(n)这是最优的因为我们至少需要遍历一次字符串来解析它。
对于题目约束input.length 10^4这个时间复杂度是完全可接受的。
空间复杂度让我们分析一下这个算法的空间复杂度空间复杂度O(n)其中n是输入字符串的长度。
分析字符串分割lines数组最多存储 O(n) 个字符空间复杂度 O(n)栈栈的深度最多等于目录的最大层级深度。
在最坏情况下比如所有目录都是单层嵌套栈的深度是 O(n)临时变量其他临时变量占用 O(
空间所以总空间复杂度是 O(n)这是必要的因为我们需要存储解析后的数据。
实际应用场景这种路径解析的方法在实际开发中应用非常广泛场景一文件系统操作在文件系统操作中我们经常需要解析文件路径计算路径长度等funcgetLongestFilePath(_fileSystem:String)-String?{// 解析文件系统字符串找到最长路径letsolutionSolution()letmaxLengthsolution.lengthLongestPath(fileSystem)// 返回最长路径returnfindPathWithLength(fileSystem,length:maxLength)}这种场景在文件管理器、备份工具等应用中经常用到。
场景二日志解析在日志解析中我们可能需要解析带有层级结构的日志funcparseHierarchicalLog(_log:String)-[LogEntry]{letlineslog.components(separatedBy:\n)varstack:[LogEntry][]varentries:[LogEntry][]forlineinlines{letlevelgetLevel(line)letcontentline.replacingOccurrences(of:\t,with:)whilestack.countlevel{stack.removeLast()}letentryLogEntry(content:content,level:level,parent:stack.last)entries.append(entry)ifentry.isContainer{stack.append(entry)}}returnentries}这种场景在日志分析工具、调试工具等应用中经常用到。
场景三配置文件解析在配置文件解析中我们可能需要解析带有缩进的配置文件funcparseIndentedConfig(_config:String)-ConfigNode{letlinesconfig.components(separatedBy:\n)varstack:[ConfigNode][]letrootConfigNode(name:root,children:[])stack.append(root)forlineinlines{letlevelgetIndentLevel(line)letcontentline.trimmingCharacters(in:.whitespaces)whilestack.countlevel1{stack.removeLast()}letnodeConfigNode(name:content,children:[])stack.last?.children.append(node)ifnode.isSection{stack.append(node)}}returnroot}这种场景在配置管理、数据解析等应用中经常用到。
场景四树形结构解析在树形结构解析中我们经常需要处理带有缩进的数据funcparseTreeStructure(_data:String)-TreeNode{letlinesdata.components(separatedBy:\n)varstack:[TreeNode][]letrootTreeNode(value:root)stack.append(root)forlineinlines{letlevelgetLevel(line)letvalueline.replacingOccurrences(of:\t,with:)whilestack.countlevel1{stack.removeLast()}letnodeTreeNode(value:value)stack.last?.children.append(node)stack.append(node)}returnroot}这种场景在数据可视化、树形结构展示等应用中经常用到。
总结这道题虽然看起来复杂但实际上是一个经典的栈应用问题。
通过使用栈来维护路径层级我们可以清晰地处理各种情况。
关键点
总结栈的应用使用栈来维护当前路径的层级结构层级计算通过制表符数量来确定目录层级路径长度计算通过栈中存储的路径长度来快速计算当前路径长度文件判断通过是否包含.来判断是文件还是目录算法优势时间复杂度低只需要遍历字符串一次O(n)实现简单逻辑清晰容易理解和维护扩展性好可以很容易地扩展到处理更复杂的文件系统结构实际应用路径解析的方法在很多场景中都有应用比如文件系统操作、日志解析、配置文件解析、树形结构解析等。
理解这种解析技术不仅能帮助我们解决类似的算法题还能让我们更好地处理各种层级结构的数据。