【字典树（前缀树) 哈希映射 后序序列化】1948. 删除系统中的重复文件夹

本文涉及知识点

字典树（前缀树) 哈希映射 后序序列化

LeetCode 1948. 删除系统中的重复文件夹

由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 paths，其中 paths[i] 是一个表示文件系统中第 i 个文件夹的绝对路径的数组。
例如，[“one”, “two”, “three”] 表示路径 “/one/two/three” 。
如果两个文件夹（不需要在同一层级）包含 非空且相同的 子文件夹 集合 并具有相同的子文件夹结构，则认为这两个文件夹是相同文件夹。相同文件夹的根层级 不 需要相同。如果存在两个（或两个以上）相同 文件夹，则需要将这些文件夹和所有它们的子文件夹 标记 为待删除。

例如，下面文件结构中的文件夹 “/a” 和 “/b” 相同。它们（以及它们的子文件夹）应该被 全部 标记为待删除：
/a
/a/x
/a/x/y
/a/z
/b
/b/x
/b/x/y
/b/z
然而，如果文件结构中还包含路径 “/b/w” ，那么文件夹 “/a” 和 “/b” 就不相同。注意，即便添加了新的文件夹 “/b/w” ，仍然认为 “/a/x” 和 “/b/x” 相同。
一旦所有的相同文件夹和它们的子文件夹都被标记为待删除，文件系统将会 删除 所有上述文件夹。文件系统只会执行一次删除操作。执行完这一次删除操作后，不会删除新出现的相同文件夹。
返回二维数组 ans ，该数组包含删除所有标记文件夹之后剩余文件夹的路径。路径可以按 任意顺序 返回。
示例 1：
在这里插入图片描述

输入：paths = [[“a”],[“c”],[“d”],[“a”,“b”],[“c”,“b”],[“d”,“a”]]
输出：[[“d”],[“d”,“a”]]
解释：文件结构如上所示。
文件夹 “/a” 和 “/c”（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 “b” 的空文件夹。
示例 2：

在这里插入图片描述

输入：paths = [[“a”],[“c”],[“a”,“b”],[“c”,“b”],[“a”,“b”,“x”],[“a”,“b”,“x”,“y”],[“w”],[“w”,“y”]]
输出：[[“c”],[“c”,“b”],[“a”],[“a”,“b”]]
解释：文件结构如上所示。
文件夹 “/a/b/x” 和 “/w”（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 “y” 的空文件夹。
注意，文件夹 “/a” 和 “/c” 在删除后变为相同文件夹，但这两个文件夹不会被删除，因为删除只会进行一次，且它们没有在删除前被标记。
示例 3：
在这里插入图片描述

输入：paths = [[“a”,“b”],[“c”,“d”],[“c”],[“a”]]
输出：[[“c”],[“c”,“d”],[“a”],[“a”,“b”]]
解释：文件系统中所有文件夹互不相同。
注意，返回的数组可以按不同顺序返回文件夹路径，因为题目对顺序没有要求。
示例 4：
在这里插入图片描述

输入：paths = [[“a”],[“a”,“x”],[“a”,“x”,“y”],[“a”,“z”],[“b”],[“b”,“x”],[“b”,“x”,“y”],[“b”,“z”]]
输出：[]
解释：文件结构如上所示。
文件夹 “/a/x” 和 “/b/x”（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 “y” 的空文件夹。
文件夹 “/a” 和 “/b”（以及它们的子文件夹）都会被标记为待删除，因为它们都包含一个名为 “z” 的空文件夹以及上面提到的文件夹 “x” 。
示例 5：
在这里插入图片描述

输入：paths = [[“a”],[“a”,“x”],[“a”,“x”,“y”],[“a”,“z”],[“b”],[“b”,“x”],[“b”,“x”,“y”],[“b”,“z”],[“b”,“w”]]
输出：[[“b”],[“b”,“w”],[“b”,“z”],[“a”],[“a”,“z”]]
解释：本例与上例的结构基本相同，除了新增 “/b/w” 文件夹。
文件夹 “/a/x” 和 “/b/x” 仍然会被标记，但 “/a” 和 “/b” 不再被标记，因为 “/b” 中有名为 “w” 的空文件夹而 “/a” 没有。
注意，“/a/z” 和 “/b/z” 不会被标记，因为相同子文件夹的集合必须是非空集合，但这两个文件夹都是空的。

提示：

1 <= paths.length <= 2 * 104
1 <= paths[i].length <= 500
1 <= paths[i][j].length <= 10
1 <= sum(paths[i][j].length) <= 2 * 105
path[i][j] 由小写英文字母组成
不会存在两个路径都指向同一个文件夹的情况
对于不在根层级的任意文件夹，其父文件夹也会包含在输入中

字典树

如何判断两个文件夹是否相等？ 除子树根节点外的序列化是否相等。后序序列化更简单。序列化完子孙后就比较。
分三步：
一，将所有path放到字典树中。字典树的节点包括path[i][j]，i。
二，DFS字典树，将各路径不包括当前节点的后序序列化放到哈希映射m_mSer中，并记录数量。注意：序列时，要排序。不如：直接用有序映射。
三，DFS字典树，看各节点是否有相等的哈希，标记此节点需要删除。
四，复制不需要删除的节点到vRet中。

复杂度

主要复杂度在序列化。
令 ∀ i ∀ j \forall i\forall j ∀i∀j path[i][i]的层次是leve(从0开始），则它序列化leve+1次，它会被它及它的祖先序列化。
它及它的祖先分别被序列化： leve+1 ,leve ⋯ \cdots ⋯ 1 次
它及它的祖先分别在path出现的次数： 1 ,2 ⋯ \cdots ⋯ leve+1 次。
次数相同，等于 path[i][j] 元素的个数，我们假设最极端情况下： ∀ i ∀ j \forall i\forall j ∀i∀j path[i][j].length==1。令o=sum(path[i][j].lenght()) ，则 ∑ \sum ∑path[i][j]序列的次数 <= o。再次假设极端情况下： ∀ i ∀ j \forall i\forall j ∀i∀j path[i][j] == 10。 则序列化的空间复制度和时间复杂度等于O(o × \times × 10) ≈ \approx ≈ 2 × \times × 106

代码

核心代码

class CStrToIndex
{
public:
	CStrToIndex() {

	}
	CStrToIndex(const vector<string>& wordList) {
		for (const auto& str : wordList)
		{
			Add(str);
		}
	}
	int Add(const string& str)
	{
		if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
		m_mIndexs[str] = m_strs.size();
		m_strs.push_back(str);
		return  m_strs.size()-1;
	}
	vector<string> m_strs;
	int GetIndex(const string& str)
	{
		if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
		return -1;
	}
protected:
	unordered_map<string, int> m_mIndexs;
};

class CPathTrieNode
{
public:
	CPathTrieNode* Add(string str) {
		if (!m_mChild.count(str)) {
			m_mChild[str] = new CPathTrieNode();
		}
		return m_mChild[str];
	}
	int m_iSerIndex =-1;
	map<string, CPathTrieNode*> m_mChild;
};

class CPathTrie {
public:
	void Add(const vector<string>& path) {
		auto ptr = &m_root;
		for (auto& s : path) {
			ptr = ptr->Add(s);
		}
	}
	CPathTrieNode m_root;
};
class Solution {
public:
	vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
		CPathTrie trie;
		for (const auto& path : paths) {
			trie.Add(path);
		}
		DFSForSer("", &trie.m_root);
		vector<string> stack;
		DFS(stack, &trie.m_root);
		return m_vRet;
	}
	string DFSForSer (string strName,CPathTrieNode* cur) {
		string str;
		for (const auto& [tmp, child] : cur->m_mChild) {
			str += "(" + DFSForSer(tmp,child) + ")";
		}
		if ("" != str)	{
			cur->m_iSerIndex = m_strIndex.Add(str);	
			m_mIndexCount[cur->m_iSerIndex]++;
		}
		str += strName;
		return str ;
	};
	void DFS(vector<string>& stack, CPathTrieNode* cur)
	{
		for (const auto& [tmp, child] : cur->m_mChild) {
			if ((-1 != child->m_iSerIndex) && (m_mIndexCount[child->m_iSerIndex] > 1)) {
				continue;
			}
			stack.emplace_back(tmp);
			m_vRet.emplace_back(stack);
			DFS(stack, child);
			stack.pop_back();
		}
	}
	vector<vector<string>> m_vRet;
	unordered_map<int, int> m_mIndexCount;
	CStrToIndex m_strIndex;
};

VS自带的单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	vector<vector<string>> paths;
	TEST_CLASS(UnitTest)
	{
	public:
		
		TEST_METHOD(TestMethod1)
		{
			paths = { {"a"},{"c"},{"d"},{"a","b"},{"c","b"},{"d","a"} };
			auto res = Solution().deleteDuplicateFolder(paths);			
			AssertV2(res,{ {"d"},{"d","a"} });
		}
		TEST_METHOD(TestMethod2)
		{
			paths = { {"a"},{"c"},{"a","b"},{"c","b"},{"a","b","x"},{"a","b","x","y"},{"w"},{"w","y"} };
			auto res = Solution().deleteDuplicateFolder(paths);
			AssertV2(res, { {"c"},{"c","b"},{"a"},{"a","b"} });
		}
		TEST_METHOD(TestMethod3)
		{
			paths = { {"a","b"},{"c","d"},{"c"},{"a"} };
			auto res = Solution().deleteDuplicateFolder(paths);
			AssertV2(res, { {"c"},{"c","d"},{"a"},{"a","b"} });
		}
		TEST_METHOD(TestMethod4)
		{
			paths = { {"a"},{"a","x"},{"a","x","y"},{"a","z"},{"b"},{"b","x"},{"b","x","y"},{"b","z"} };
			auto res = Solution().deleteDuplicateFolder(paths);
			AssertV2(res, {  });
		}
		TEST_METHOD(TestMethod5)
		{
			paths = { {"a"},{"a","x"},{"a","x","y"},{"a","z"},{"b"},{"b","x"},{"b","x","y"},{"b","z"},{"b","w"} };
			auto res = Solution().deleteDuplicateFolder(paths);
			AssertV2(res, { {"b"},{"b","w"},{"b","z"},{"a"},{"a","z"} });
		}
	};
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/665572.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Codeforces Round 949 (Div. 2) （A~C）

Codeforces Round 949 (Div. 2) （A~C）

1981A - Turtle and Piggy Are Playing a Game 贪心&#xff0c;每次取x 2&#xff0c;求最大分数 // Problem: B. Turtle and an Infinite Sequence // Contest: Codeforces - Codeforces Round 949 (Div. 2) // URL: https://codeforces.com/contest/1981/problem/B // Me…
阅读更多...
iOS组件化 方案 实现

iOS组件化 方案 实现

iOS组件化 组件化的原因现在流行的组件化方案方案一、url-block &#xff08;基于 URL Router&#xff09;方案二、protocol调用方式解读 方案三、target-action调用方式解读 gitHub代码链接参考 组件化的原因 模块间解耦模块重用提高团队协作开发效率单元测试 当项目App处于…
阅读更多...
2024最新群智能优化算法：大甘蔗鼠算法（Greater Cane Rat Algorithm，GCRA）求解23个函数，提供MATLAB代码

2024最新群智能优化算法：大甘蔗鼠算法（Greater Cane Rat Algorithm，GCRA）求解23个函数，提供MATLAB代码

一、大甘蔗鼠算法 大甘蔗鼠算法&#xff08;Greater Cane Rat Algorithm&#xff0c;GCRA&#xff09;由Jeffrey O. Agushaka等人于2024年提出&#xff0c;该算法模拟大甘蔗鼠的智能觅食行为。 参考文献 [1]Agushaka J O, Ezugwu A E, Saha A K, et al. Greater Cane Rat Alg…
阅读更多...
LAMMPS - 分子动力学模拟器

LAMMPS - 分子动力学模拟器

本文翻译自&#xff1a;https://www.lammps.org/ 文章目录 一、关于 LAMMPS下载作者R&D 100 二、LAMMPS 亮点毛细血管中的血流 一、关于 LAMMPS 官网&#xff1a; https://www.lammps.org/ github &#xff1a;https://github.com/lammps/lammps LAMMPS 分子动力学模拟器…
阅读更多...
初识java——javaSE（8）异常

初识java——javaSE（8）异常

文章目录 一 异常的概念与体系结构1.1 什么是异常&#xff1f;1.2 异常的体系结构&#xff01;1.3 编译时异常与运行时异常与Error编译时异常&#xff1a;异常声明&#xff1a;throws关键字 运行时异常&#xff1a;什么是Error? 二 处理异常2.1 异常的抛出&#xff1a;throw(注…
阅读更多...
利用映射算子打印菱形

利用映射算子打印菱形

文章目录 一、利用RDD完成&#xff08;一&#xff09;右半菱形&#xff08;二&#xff09;左半菱形&#xff08;三&#xff09;完整菱形&#xff08;四&#xff09;输出任意大菱形 二、利用Java完成&#xff08;一&#xff09;右半菱形&#xff08;二&#xff09;左半菱形&…
阅读更多...
恒压频比开环控制系统Matlab/Simulink仿真分析（SPWM控制方式）

恒压频比开环控制系统Matlab/Simulink仿真分析（SPWM控制方式）

介绍恒压频比的开环控制方法驱动永磁同步电机的转动&#xff0c;首先分析恒压频比的控制原理&#xff0c;然后在Matlab/Simulink中进行永磁同步电机恒压频比开环控制系统的仿真分析&#xff0c;最后将Simulink中的恒压频比控制算法生成代码加载到实际工程中进行工程实现。 一、…
阅读更多...
react 表格实现拖拽功能

react 表格实现拖拽功能

项目背景 : react ant 单纯实现拖拽确实不难 , 我的需求是根据后台接口返回 , 生成对应的父子表格 , 并只可以拖拽子的位置 , 如图 后台返回的数据结构 (pid为0说明是父 , 子的pid等于父的id , 说明是父的子) 1 , 我先转成了树形结构且自己加上了key (注意 : key一定得是唯一的…
阅读更多...
异常（Exception）

异常（Exception）

捕获异常 public class test {public static void main(String [] args) {int[] arr {1,2,3,4,5};try {System.out.println(arr[10]);}catch (ArrayIndexOutOfBoundsException e) {//索引越界异常System.out.println("索引越界");}System.out.println("看看我是…
阅读更多...
测试FaceRecognitionDotNet报错“Error deserializing object of type int”

测试FaceRecognitionDotNet报错“Error deserializing object of type int”

FaceRecognitionDotNet宣称是最简单的.net人脸识别模块&#xff0c;其内部使用Dlib、DlibDotNet、OpenCVSharp等模块实现人脸识别&#xff0c;网上有不少介绍文章。实际测试过程中&#xff0c;在调用FaceRecognition.Create函数创建FaceRecognition实例对象时&#xff0c;会报如…
阅读更多...
AI入门：普通人可以利用AI做什么？休闲时间赚点小钱？(含多种实践案例)

AI入门：普通人可以利用AI做什么？休闲时间赚点小钱？(含多种实践案例)

大家好&#xff0c;我是影子&#xff0c;一名AI编程深耕者。 最近&#xff0c;有很多 AI 小白问我&#xff0c;AI到底可以做些什么&#xff1f;对我们普通人能有哪些帮助&#xff1f; 在我看来&#xff0c;对于我们刚接触 AI 的小伙伴而言。我们可以利用 AI 为我们工作提效&…
阅读更多...
构建 VPC 并启动 Web 服务器

构建 VPC 并启动 Web 服务器

实验 2&#xff1a;构建 VPC 并启动 Web 服务器 目标 完成本实验后&#xff0c;您可以&#xff1a; 创建 VPC。创建子网。配置安全组。在 VPC 中启动 EC2 实例。任务 1&#xff1a;创建 VPC 在本任务中&#xff0c;您将使用 VPC 向导在单个可用区中创建一个 VPC、一个互联网网关…
阅读更多...
神经网络---卷积神经网络CNN

神经网络---卷积神经网络CNN

一、从前馈神经网络到CNN 前馈神经网络&#xff08;Feedforward Neural Networks&#xff09;是最基础的神经网络模型&#xff0c;也被称为多层感知机&#xff08;MLP&#xff09;。 它由多个神经元组成&#xff0c;每个神经元与前一层的所有神经元相连&#xff0c;形成一个“…
阅读更多...
电子电气SCI期刊，中科院1区TOP，收稿范围广泛

电子电气SCI期刊，中科院1区TOP，收稿范围广泛

一、期刊名称 IEEE Transactions on Smart Grid 二、期刊简介概况 期刊类型&#xff1a;SCI 学科领域&#xff1a;工程技术 影响因子&#xff1a;9.6 中科院分区&#xff1a;1区 三、期刊征稿范围 IEEE Transactions on Smart Grid是一本跨学科期刊&#xff0c;旨在传播智…
阅读更多...
Gbase 国产数据库

Gbase 国产数据库

参考&#xff1a;参考&#xff1a; 5分钟学会Linux环境GBase 8t安装和部署 - 光洋山 - twt企业IT交流平台 (talkwithtrend.com)https://www.talkwithtrend.com/Article/197237 视频 GBase 8s快速入门-功能简介与演示-大数据教程-腾讯课堂 (qq.com)https://ke.qq.com/course/…
阅读更多...
Qt 插件机制使用及原理

Qt 插件机制使用及原理

目录 1.引言 2.插件原理 3.插件实现 3.1.定义一个接口集(只有纯虚函数的类) 3.2.实现接口 4.插件的加载 4.1.静态插件 4.1.1.静态插件实现方式 4.1.2.静态插件加载的过程 4.1.3.示例 4.2.动态插件 4.2.1.动态插件的加载过程 5.定位插件 6.插件开发的优势 7.总结…
阅读更多...
蓝桥杯高频考点-与日期相关的题目

蓝桥杯高频考点-与日期相关的题目

文章目录 前言1. 如何枚举合法日期1.1 预存每个月的天数1.2 封装一个判断日期是否合法的函数1.3 枚举日期并判断日期是否合法 2. 判断日期是否为回文日期2.1 将日期当作字符串进行处理2.2 将日期当作一个8位数进行处理 3. 给定初始日期&#xff0c;计算经过n天后对应的日期3.1 …
阅读更多...
Java集合【超详细】2 -- Map、可变参数、Collections类

Java集合【超详细】2 -- Map、可变参数、Collections类

文章目录 一、Map集合1.1 Map集合概述和特点【理解】1.2 Map集合的基本功能【应用】1.3 Map集合的获取功能【应用】1.4 Map集合的两种遍历方式 二、HashMap集合2.1 HashMap集合概述和特点【理解】2.2 HashMap的组成、构造函数2.3 put、查找方法2.4 HashMap集合应用案例【应用】…
阅读更多...
另一棵树的子树（oj题）

另一棵树的子树（oj题）

一、题目链接 https://leetcode.cn/problems/subtree-of-another-tree/submissions/536304222 二、题目思路 1.首先遍历大树&#xff0c;判断大树的根结点的值是否等于小树的根结点的值&#xff0c;如果不相等&#xff0c;就找大树的左孩子或者右孩子&#xff0c;以左孩子为根…
阅读更多...
博士毕业论文/CTEX/LATEX

博士毕业论文/CTEX/LATEX

LATEX环境安装 CTEX 安装 &#xff08;垃圾&#xff0c;不要装&#xff09; 运行 clean.batcomp.bat 缺少字体 Couldn’t find Adobe Heiti S.cfg’ miktex-maketfm: No creation rule for font “Adobe Heiti Std”.解决方法&#xff1a;其实就是下载这四个字体之后&…
阅读更多...
最新文章

Copyright @ 2022~2023