国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] 609. Find Duplicate File in System

sf190404 / 2818人閱讀

Problem

Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.

A group of duplicate files consists of at least two files that have exactly the same content.

A single directory info string in the input list has the following format:

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

It means there are n files (f1.txt, f2.txt ... fn.txt with content f1_content, f2_content ... fn_content, respectively) in directory root/d1/d2/.../dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

"directory_path/file_name.txt"

Example 1:
Input:

["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]

Output:

[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Note:
No order is required for the final output.
You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50].
The number of files given is in the range of [1,20000].
You may assume no files or directories share the same name in the same directory.
You may assume each given directory info represents a unique directory. Directory path and file info are separated by a single blank space.

Follow-up beyond contest:

Imagine you are given a real file system, how will you search files? DFS or BFS?
If the file content is very large (GB level), how will you modify your solution?
If you can only read the file by 1kb each time, how will you modify your solution?
What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize?
How to make sure the duplicated files you find are not false positive?

Solution
class Solution {
    public List> findDuplicate(String[] paths) {
        List> res = new ArrayList<>();
        if (paths == null || paths.length == 0) return res;
        Map> map = new HashMap<>();
        
        for (String str: paths) {
            String[] parts = str.split(" ");
            String rootPath = parts[0];
            
            for (int i = 1; i < parts.length; i++) {
                String child = parts[i];
                for (int j = 0; j < child.length(); j++) {
                    //assuming there"s multiple "(", find the first
                    if (child.charAt(j) == "(") {
                        String childPath = child.substring(0, j);
                        String finalPath = rootPath + "/" + childPath;
                        String content = child.substring(j+1, child.length()-1);
                        if (!map.containsKey(content)) {
                            map.put(content, new ArrayList());
                        }
                        map.get(content).add(finalPath);
                    }
                    
                }
            }
            
        }
        
        for (Map.Entry> entry: map.entrySet()) {
            if (entry.getValue().size() > 1) res.add(entry.getValue());
        }
        return res;
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77161.html

相關文章

  • LeetCode[287] Find the Duplicate Number

    摘要:復雜度思路每次通過二分法找到一個值之后,搜索整個數組,觀察小于等于這個數的個數。考慮,小于這個位置的數的個數應該是小于等于這個位置的。要做的就是像找中的環一樣,考慮重復的點在哪里??紤]用快慢指針。代碼把一個指針放回到開頭的地方 LeetCode[287] Find the Duplicate Number Given an array nums containing n + 1 in...

    canopus4u 評論0 收藏0
  • [LeetCode] Find the Duplicate Number

    Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...

    MoAir 評論0 收藏0
  • [LeetCode] 287. Find the Duplicate Number

    Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...

    rickchen 評論0 收藏0
  • [Leetcode] Find the Duplicate Number 找到重復數字

    摘要:暴力法復雜度時間空間思路如果不用空間的話,最直接的方法就是選擇一個數,然后再遍歷整個數組看是否有跟這個數相同的數就行了。二分法復雜度時間空間思路實際上,我們可以根據抽屜原理簡化剛才的暴力法。 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is bet...

    chnmagnus 評論0 收藏0
  • [Leetcode] Contains Duplicate 包含重復

    摘要:代碼集合法復雜度時間空間思路同樣使用集合,但這次我們要維護集合的大小不超過,相當于是記錄一個寬度為的窗口中出現過的數字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

    rozbo 評論0 收藏0

發表評論

0條評論

sf190404

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<