本文主要是介绍LeetCode刷题实战609:在系统中查找重复文件,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 在系统中查找重复文件,我们先来看题面:
https://leetcode.cn/problems/find-duplicate-file-in-system/
给你一个目录信息列表 paths ,包括目录路径,以及该目录中的所有文件及其内容,请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。
一组重复的文件至少包括 两个 具有完全相同内容的文件。
输入 列表中的单个目录信息字符串的格式如下:
"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"
这意味着,在目录 root/d1/d2/.../dm 下,有 n 个文件 ( f1.txt, f2.txt ... fn.txt ) 的内容分别是 ( f1_content, f2_content ... fn_content ) 。注意:n >= 1 且 m >= 0 。如果 m = 0 ,则表示该目录是根目录。
输出 是由 重复文件路径组 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串:
"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)"]
输出:[["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)"]
输出:[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]
解题
https://blog.csdn.net/weixin_44389717/article/details/123266433
1、首先,通过字符串的split方法,以空格分割,将paths字符串分割各个values
2、接着循环将各个部分提取出来,以每个文件的内容作为map的key,使用HashMap的getOrDefault(key,defaultValue)方法查询该key是否有值,如果没有则新建一个空的list为其做准备,并且接着put一个以文件内容为key,list为value的map
3、此时,第一次循环遍历第一个文件内容就结束了,这时以Map类型为集合的第一个内容为(“abcd”,[“root/a/1.txt”])
如此反复不断遍历,如果查询有这个key,那么就add在该key的value后面
4、新建一个List
5、遍历完成后,循环每一个key,如果该key的value长度大于1,则表示有重复的内容,那么将其存入新的数组
6、最后返回即可
HashMap< String, List < String >> map = new HashMap < > ();for (String path: paths) {String[] values = path.split(" ");for (int i = 1; i < values.length; i++) {String[] name_cont = values[i].split("\\(");name_cont[1] = name_cont[1].replace(")", "");List < String > list = map.getOrDefault(name_cont[1], new ArrayList < String > ());list.add(values[0] + "/" + name_cont[0]);map.put(name_cont[1], list);}}List < List < String >> res = new ArrayList< >();for (String key: map.keySet()) {if (map.get(key).size() > 1)res.add(map.get(key));}return res;
上期推文:
LeetCode1-600题汇总,希望对你有点帮助!
LeetCode刷题实战601:体育馆的人流量
LeetCode刷题实战602:好友申请 II :谁有最多的好友
LeetCode刷题实战603:连续空余座位
LeetCode刷题实战604:迭代压缩字符串
LeetCode刷题实战605:种花问题
LeetCode刷题实战606:根据二叉树创建字符串
LeetCode刷题实战607:销售员
LeetCode刷题实战608:树节点
这篇关于LeetCode刷题实战609:在系统中查找重复文件的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!