LeetCode Solutions (161 серия деталей)
Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет
Проблема LeetCode #609 (Medium): Найдите дубликат файла в системе
Описание:
( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++
Дал список пути Информации о каталоге, включая путь каталога и все файлы содержимым в этом каталоге, возвращайте Все дубликаты файлов в файловой системе с точки зрения их путей Анкет Вы можете вернуть ответ в любой заказ Анкет
Группа дублирующих файлов состоит как минимум из двух файлов, которые имеют одинаковый контент.
Одноразмерная строка информации в списке ввода имеет следующий формат:
-
"Root/D1/D2/.../dm f1.txt (f1_content) f2.txt (f2_content) ... fn.txt (fn_content) "
Это означает, что есть n файлы ( f1.txt, f2.txt ... fn.txt ) с содержанием ( f1_content, f2_content ... fn_content ) соответственно в каталоге "Root/D1/D2/.../дм " . Обратите внимание, что n и m Анкет Если m , это означает, что каталог – это просто корневой каталог.
Вывод – это список групп дублирующих путей файла. Для каждой группы он содержит все пути файлов файлов, которые имеют одинаковый контент. Путь файла – это строка, которая имеет следующий формат:
-
"Directory_Path/file_name.txt"
Примеры:
| Вход: | пути = [“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 .текст”]] |
| Вход: | пути = [“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”]]]]] |
Ограничения:
1.length * 10^41 [i].1 (пути [i] .length) * 10^5Пути [i]состоят из английских букв, цифр,'/','.','(',')'и''Анкет- Вы можете предположить, что никакие файлы или каталоги не имеют одинакового имени в том же каталоге.
- Вы можете предположить, что каждая данная информация о каталоге представляет собой уникальный каталог. Одно пустое пространство разделяет путь к каталогу и информацию о файле.
Идея:
( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++
Заказ на группу дублирования файлов, мы должны использовать карта Чтобы сохранить пути файла по значению контента. Для каждой строки ( pstr ) в пути , мы можем перевернуть через строку до первого пространства, чтобы найти Путь Анкет Тогда мы сможем перевернуть через оставшуюся часть PSTR и используйте еще два указателя ( j, k ), чтобы отметить индексы вокруг имени файла ( file ) и contents ( cont ).
Когда мы находим ‘)’ , мы нашли конец полной записи, поэтому мы должны добавить его в нашу карту контента ( contmap ), объединив Путь и файл (с ‘/’ между) и хранение результата в ContMap под Продолжение Анкет
Как только мы добавили все файлы в продолжение , мы можем итерации через его значения и добавить любые группы, которые больше, чем 1 (Указывая дубликаты) на наш массив ответов ( ans ), прежде чем мы вернуть ANS Анкет
- Сложность времени: O (n + c) куда N общее количество файлов и C количество разных ключей в продолжение
- Сложность пространства: O (n) за N файлы в продолжение
Реализация:
Python намного быстрее при использовании split () в отличие от прямой итерации через строки.
Java быстрее при использовании StringBuilder Скомпилировать Путь + Файл Перед входом в ContMap Анкет
Код JavaScript:
( Прыгните к : Описание задачи Идея решения
var findDuplicate = function(paths) {
let contMap = new Map(), ans = []
for (let pStr of paths) {
let i = 0, j, k
while (pStr.charAt(i) !== ' ') i++
let path = pStr.slice(0,i)
for (j = ++i; i < pStr.length; i++)
if (pStr.charAt(i) === '(') k = i
else if (pStr.charAt(i) === ')') {
let pathfile = path + '/' + pStr.slice(j, k),
cont = pStr.slice(k+1, i)
if (!contMap.has(cont))
contMap.set(cont, [pathfile])
else contMap.get(cont).push(pathfile)
j = i + 2
}
}
for (let v of contMap.values())
if (v.length > 1) ans.push(v)
return ans
};
Код Python:
( Прыгните к : Описание задачи Идея решения
class Solution:
def findDuplicate(self, paths: List[str]) -> List[List[str]]:
contMap, ans = defaultdict(list), []
for pStr in paths:
sep = pStr.split(" ")
for i in range(1, len(sep)):
parts = sep[i].split('(')
cont = parts[1][:-1]
contMap[cont].append(sep[0] + '/' + parts[0])
for v in contMap.values():
if len(v) > 1: ans.append(v)
return ans
Код Java:
( Прыгните к : Описание задачи Идея решения
class Solution {
public List> findDuplicate(String[] paths) {
Map> contMap = new HashMap<>();
StringBuilder pathfile = new StringBuilder();
for (String pStr : paths) {
int i = 0;
pathfile.setLength(0);
while (pStr.charAt(i) != ' ') i++;
pathfile.append(pStr.substring(0,i)).append('/');
int pLen = ++i;
for (int j = i, k = 0; i < pStr.length(); i++)
if (pStr.charAt(i) == '(') {
pathfile.append(pStr.substring(j,i));
k = i + 1;
} else if (pStr.charAt(i) == ')') {
String cont = pStr.substring(k, i);
if (!contMap.containsKey(cont))
contMap.put(cont, new ArrayList<>());
contMap.get(cont).add(pathfile.toString());
j = i + 2;
pathfile.setLength(pLen);
}
}
List> ans = new ArrayList<>();
for (List v : contMap.values())
if (v.size() > 1) ans.add(v);
return ans;
}
}
C ++ Код:
( Прыгните к : Описание задачи Идея решения
class Solution {
public:
vector> findDuplicate(vector& paths) {
unordered_map> contMap;
for (auto &pStr : paths) {
int i = 0;
while (pStr[i] != ' ') i++;
string path = pStr.substr(0,i);
for (int j = i + 1, k = 0; i < pStr.size(); i++)
if (pStr[i] == '(') k = i+1;
else if (pStr[i] == ')') {
string pathfile = path + '/' + pStr.substr(j, k-j-1),
cont = pStr.substr(k, i-k);
if (contMap.find(cont) == contMap.end())
contMap[cont] = vector();
contMap[cont].push_back(pathfile);
j = i + 2;
}
}
vector> ans;
for (auto &kv : contMap)
if (kv.second.size() > 1) ans.push_back(kv.second);
return ans;
}
};
LeetCode Solutions (161 серия деталей)
Оригинал: “https://dev.to/seanpgallivan/solution-find-duplicate-file-in-system-1ofi”