服装网站建设分析商洛建设公司网站

当前位置： 首页 > news >正文

服装网站建设分析,商洛建设公司网站,网站建设招标书,新民电商网站建设程序文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法思路和算法代码复杂度分析 进阶问题答案后记 题目 标题和出处 标题#xff1a;在系统中查找重复文件 出处#xff1a;609. 在系统中查找重复文件 难度 6 级 题目描述 要求 给定一个目录信息列表 paths… 文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法思路和算法代码复杂度分析 进阶问题答案后记 题目 标题和出处 标题在系统中查找重复文件 出处609. 在系统中查找重复文件 难度 6 级 题目描述 要求 给定一个目录信息列表 paths \texttt{paths} paths包括目录路径和该目录中的所有包含内容的文件返回文件系统中的所有重复文件组的路径。你可以按任意顺序返回结果。 一组重复的文件至少包括两个具有完全相同内容的文件。 输入列表中的单个目录信息字符串的格式如下 root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content) \texttt{root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)} root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content) 这意味着在目录 root/d1/d2/…/dm \texttt{root/d1/d2/…/dm} root/d1/d2/…/dm 下有 n \texttt{n} n 个文件 (f1.txt, f2.txt … fn.txt) \texttt{(f1.txt, f2.txt … fn.txt)} (f1.txt, f2.txt … fn.txt)内容分别是 (f1_content, f2_content … fn_content) \texttt{(f1_content, f2_content … fn_content)} (f1_content, f2_content … fn_content)。注意 n ≥ 1 \texttt{n} \ge \texttt{1} n≥1 且 m ≥ 0 \texttt{m} \ge \texttt{0} m≥0。如果 m 0 \texttt{m} \texttt{0} m0则表示该目录是根目录。 输出是重复文件路径组的列表。对于每个组它包含具有相同内容的文件的所有文件路径。文件路径是具有下列格式的字符串 directory_path/file_name.txt \texttt{directory_path/file_name.txt} directory_path/file_name.txt 示例 示例 1 输入 paths [root/a 1.txt(abcd) 2.txt(efgh), root/c 3.txt(abcd), root/c/d 4.txt(efgh), root 4.txt(efgh)] \texttt{paths [root/a 1.txt(abcd) 2.txt(efgh), root/c 3.txt(abcd), root/c/d 4.txt(efgh), root 4.txt(efgh)]} paths  [root/a 1.txt(abcd) 2.txt(efgh), root/c 3.txt(abcd), root/c/d 4.txt(efgh), root 4.txt(efgh)] 输出 [[root/a/2.txt,root/c/d/4.txt,root/4.txt],[root/a/1.txt,root/c/3.txt]] \texttt{[[root/a/2.txt,root/c/d/4.txt,root/4.txt],[root/a/1.txt,root/c/3.txt]]} [[root/a/2.txt,root/c/d/4.txt,root/4.txt],[root/a/1.txt,root/c/3.txt]] 示例 2 输入 paths [root/a 1.txt(abcd) 2.txt(efgh),root/c 3.txt(abcd),root/c/d 4.txt(efgh)] \texttt{paths [root/a 1.txt(abcd) 2.txt(efgh),root/c 3.txt(abcd),root/c/d 4.txt(efgh)]} paths  [root/a 1.txt(abcd) 2.txt(efgh),root/c 3.txt(abcd),root/c/d 4.txt(efgh)] 输出 [[root/a/2.txt,root/c/d/4.txt],[root/a/1.txt,root/c/3.txt]] \texttt{[[root/a/2.txt,root/c/d/4.txt],[root/a/1.txt,root/c/3.txt]]} [[root/a/2.txt,root/c/d/4.txt],[root/a/1.txt,root/c/3.txt]] 数据范围 1 ≤ paths.length ≤ 2 × 10 4 \texttt{1} \le \texttt{paths.length} \le \texttt{2} \times \texttt{10}^\texttt{4} 1≤paths.length≤2×104 1 ≤ paths[i].length ≤ 3000 \texttt{1} \le \texttt{paths[i].length} \le \texttt{3000} 1≤paths[i].length≤3000 1 ≤ sum(paths[i].length) ≤ 5 × 10 5 \texttt{1} \le \texttt{sum(paths[i].length)} \le \texttt{5} \times \texttt{10}^\texttt{5} 1≤sum(paths[i].length)≤5×105 paths[i] \texttt{paths[i]} paths[i] 由英语字母、数字、 ‘/’ \texttt{/} ‘/’、 ‘.’ \texttt{.} ‘.’、 ‘(’ \texttt{(} ‘(’、 ‘)’ \texttt{)} ‘)’ 和 ‘ ’ \texttt{ } ‘ ’ 组成你可以假设在同一目录中没有任何文件或目录共享相同的名称你可以假设每个给定的目录信息代表一个唯一的目录目录路径和文件信息用一个空格分隔 进阶 假设给你一个真正的文件系统你将如何搜索文件深度优先搜索还是广度优先搜索如果文件内容非常大GB 级别你将如何修改你的解决方案如果每次只能读取 1 KB 的文件你将如何修改你的解决方案修改后的解决方案的时间复杂度是多少其中最消耗时间的部分和最消耗内存的部分是什么如何优化如何确保你发现的重复文件不是误报 解法 思路和算法 给定的数组 paths \textit{paths} paths 中的每个元素表示一个目录的路径以及该目录中的所有文件的文件名和文件内容。如果一个元素包含用空格分隔的 m m m 项则可以将该元素使用空格作为分隔符创建长度为 m m m 的数组数组中的第 0 0 0 项为目录路径其余 m − 1 m - 1 m−1 项分别为该目录中的每个文件的文件信息包括文件名和文件内容可以根据数组中的每个元素得到每个文件的绝对路径和文件内容。 为了找到重复文件需要找到每种文件内容对应的文件列表并判断文件列表中的文件个数如果文件个数大于 1 1 1 则该文件列表为一组重复文件。可以使用哈希表记录每种文件内容对应的文件列表。 由于文件系统中的任意两个目录的路径都不同任意两个文件的绝对路径都不同因此不需要对目录的路径和文件的绝对路径做排重操作使用列表表示每种文件内容的文件列表即可。 对于数组 paths \textit{paths} paths 中的每个元素首先将该元素使用空格作为分隔符创建文件数组然后对文件数组中的除了第 0 0 0 项以外的每一项得到文件的绝对路径和文件内容在哈希表中将文件的绝对路径添加到文件内容的文件列表中。 遍历结束数组 paths \textit{paths} paths 之后遍历哈希表对于哈希表中的每种文件内容如果对应的文件列表中的文件个数大于 1 1 1则将该文件列表添加到结果中。 代码 class Solution {public ListListString findDuplicate(String[] paths) {MapString, ListString map new HashMapString, ListString();for (String path : paths) {String[] array path.split( );StringBuffer directoryBuffer new StringBuffer(array[0]);if (directoryBuffer.charAt(directoryBuffer.length() - 1) ! /) {directoryBuffer.append(/);}String directory directoryBuffer.toString();int length array.length;for (int i 1; i length; i) {String fileNameContent array[i];int fileNameContentLength fileNameContent.length();int leftParenthesisIndex -1;StringBuffer fileNameBuffer new StringBuffer();for (int j 0; j fileNameContentLength leftParenthesisIndex 0; j) {char c fileNameContent.charAt(j);if (c () {leftParenthesisIndex j;} else {fileNameBuffer.append©;}}String fileName fileNameBuffer.toString();String content fileNameContent.substring(leftParenthesisIndex 1, fileNameContentLength - 1);String completeFileName directory fileName;map.putIfAbsent(content, new ArrayListString());map.get(content).add(completeFileName);}}ListListString duplicates new ArrayListListString();SetMap.EntryString, ListString entries map.entrySet();for (Map.EntryString, ListString entry : entries) {String content entry.getKey();ListString files entry.getValue();if (files.size() 1) {duplicates.add(files);}}return duplicates;} }复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是文件系统中的文件总数。遍历文件系统中的全部文件并将每种文件内容和对应的文件列表存入哈希表需要 O ( n ) O(n) O(n) 的时间遍历哈希表得到结果也需要 O ( n ) O(n) O(n) 的时间。这里将字符串操作的时间视为 O ( 1 ) O(1) O(1)。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是文件系统中的文件总数。空间复杂度主要取决于哈希表哈希表中需要存储每种文件内容对应的文件列表空间是 O ( n ) O(n) O(n)。这里将字符串占用的空间视为 O ( 1 ) O(1) O(1)。
进阶问题答案 假设给你一个真正的文件系统你将如何搜索文件深度优先搜索还是广度优先搜索 深度优先搜索和广度优先搜索的时间复杂度相同因此应该根据空间复杂度决定使用哪种搜索方法。 如果文件系统树结构的深度是 d d d平均分支数是 f f f即树结构中的每个目录结点平均有 f f f 个子结点则深度优先搜索的空间复杂度是 O ( d ) O(d) O(d)广度优先搜索的空间复杂度是 O ( f d ) O(f^d) O(fd)。大多数情况下 O ( d ) O(d) O(d) 优于 O ( f d ) O(f^d) O(fd)因此大多数情况下应该使用深度优先搜索。 如果文件内容非常大GB 级别你将如何修改你的解决方案 如果文件内容非常大则不能一次性存储文件的完整内容因此需要将文件内容分块存储并存储元数据元数据包括文件名、文件大小、各分块的偏移量、各分块的哈希值等。 其中一个分块的哈希值等于该分块的内容使用特定哈希函数计算得到的结果每个文件的所有分块的哈希值计算都使用同一个哈希函数。 如果两个文件的内容相同则这两个文件的大小一定也相同。因此比较两个文件的内容是否相同时首先比较两个文件的大小是否相同如果大小不同则内容一定不同如果大小相同再依次比较每个分块的哈希值是否相同只要有一个分块的哈希值不同则两个文件的内容不同只有当每个分块的哈希值都相同时才能认为两个文件的内容可能相同。使用哈希值进行比较虽然可以降低内存空间只需要将哈希值存入内存不需要将文件内容直接存入内存但是可能存在误报的情况问题 5 将提供解决方案。 如果每次只能读取 1 KB 的文件你将如何修改你的解决方案 每次只能读取 1 KB 的文件则每个分块的大小最多为 1 KB因此使用问题 2 的解决方案将每个分块的大小设为 1 KB。 修改后的解决方案的时间复杂度是多少其中最消耗时间的部分和最消耗内存的部分是什么如何优化 如果文件系统中的文件个数是 n n n每个文件的平均大小是 k k k则时间复杂度是 O ( k n 2 ) O(kn^2) O(kn2)。对于每个文件需要 O ( k ) O(k) O(k) 的时间计算元数据其中计算每个分块哈希值的时间复杂度最高共需要 O ( k n ) O(kn) O(kn) 的时间计算元数据。每两个文件之间都需要比较比较次数是 n ( n − 1 ) 2 \dfrac{n(n - 1)}{2} 2n(n−1)​每次比较首先比较文件大小然后比较每个分块的哈希值因此最坏情况下每次比较的时间复杂度是 O ( k ) O(k) O(k)总时间复杂度是 O ( k n 2 ) O(kn^2) O(kn2)。 最消耗时间和内存的部分是哈希值的计算和存储。 由于文件个数 n n n 和比较次数 n ( n − 1 ) 2 \dfrac{n(n - 1)}{2} 2n(n−1)​ 无法减少因此可以优化的方面只有哈希值的计算。在条件允许的情况下将每个分块的大小增加即可减少分块个数。 如何确保你发现的重复文件不是误报 误报的情况为两个文件的内容不同但是两个文件中的每个分块的哈希值对应相同。为了避免误报当两个文件中的每个分块的哈希值都对应相同时需要比较两个文件的内容只有当内容相同时才能认为是重复文件。
后记 这道题的进阶问题涉及到搜索搜索是在树和图中常用的算法。由于文件系统是一个树的结构因此搜索文件需要使用到搜索算法。常见的搜索算法有深度优先搜索和广度优先搜索。 深度优先搜索的做法是从起点出发沿着一条路搜索到底然后依次回退到之前遍历的每一个位置寻找其他尚未遍历的路并继续搜索直到搜索完所有的位置。 广度优先搜索的做法是从起点出发按照距离从近到远的顺序依次搜索每个位置。 关于树的搜索将在树结构部分具体讲解。关于其他场景下的搜索将在搜索算法部分具体讲解。