LeetCode 1166. 设计文件系统

2021-08-12 HGNULB 约 7 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1166. 设计文件系统

题意分析

设计一个支持两个操作的文件系统：createPath(path, value) 给一条形如 /a/b/c 的路径关联一个整数值，成功返回 true；get(path) 返回该路径上的值，不存在则返回 -1。

创建的规则有三条，缺一不可。第一，路径不能已经存在——重复创建返回 false。第二，父路径必须已经存在——想创建 /a/b 就得先有 /a；这一条把文件系统的树形结构约束了出来，不允许凭空产生「悬空」的深层路径。第三，根路径 / 不能被创建，它天生存在但没有值。

路径的格式题目已经保证：以 / 开头、不以 / 结尾、中间不会有连续的 //、至少含一个字符的名字。这条保证很关键——它意味着不需要写任何路径规范化或非法输入的解析代码，可以放心地把路径当作一个普通字符串来处理。

再看一个容易被忽略的点：题目从头到尾没有要求列目录、遍历子节点或删除。所有操作都是「给定一条完整路径，问它在不在、值是多少」。这个观察决定了数据结构的选择——既然从来不需要沿着树往下走，就没必要真的建一棵树。

边界：/a 这种一级路径的父路径是根 /，截取父路径时会得到空串，必须映射回 /；get 一个从未创建过的路径要返回 -1 而不是抛异常；值可以是任意整数，包括负数与 0。

解法：哈希表记录路径

核心思路

两个接口都按完整路径访问，题目没有列目录、前缀查询或删除子树，因此无需真正构造字典树。用哈希表保存 完整路径 -> 值，键是否存在就代表路径是否已创建。

核心不变量是：表中只有根 / 和所有成功创建的路径，而且每个非根键的父路径也在表中。初始预置根；创建时先验证父键存在，再写入新键，所以该不变量可由归纳法保持。

/a/b/c 的父路径是最后一个 / 之前的 "/a/b"。一级路径 /a 截取得到空串，把它映射为根 /，之后所有层级都走同一套父存在性判断。

重复创建必须用 containsKey 判断，不能用返回值是否为 -1 代替存在性判断；写入只能发生在查重和父校验全部通过之后。get 则按接口约定在缺失时返回 -1。

解题步骤

构造函数放哨兵：values.put("/", -1)。根只表示“存在”，占位值不会参与业务判断。

先查重：if (values.containsKey(path)) return false;。根已经在表中，所以 createPath("/", ...) 也会自然失败。题目保证路径格式合法，不额外编写规范化或空值分支。

截取父路径：idx = path.lastIndexOf('/')，parent = path.substring(0, idx)。用最后一个 / 而不是第一个：/a/b/c 的父是 /a/b，取第一个 / 会得到空串。因为题目保证路径不以 / 结尾，lastIndexOf 找到的一定是分隔父与子的那个斜杠。

把空父路径映射回根：if (parent.isEmpty()) parent = "/";。这一步对应 /a 这类一级路径——lastIndexOf('/') 返回 0，截取 [0, 0) 得到空串，而它真正的父是根。漏掉这行会让所有一级路径都创建失败，进而整个测试全线崩溃。

校验父存在：if (!values.containsKey(parent)) return false;。这是树形结构的唯一守卫。

写入并返回 true：values.put(path, value)。

get 直接查表：values.getOrDefault(path, -1)。

以一组操作走一遍：

初始表为 { "/": -1 }。创建 /leet 时父路径映射为 /，成功；再创建 /leet/code 时父路径 /leet 已存在，也成功。直接创建 /c/d 时父路径 /c 缺失，返回 false 且表不变。重复创建 /leet 同样返回 false，原值仍为 1。

代码实现

import java.util.HashMap;
import java.util.Map;

class FileSystem {
    private final Map<String, Integer> values;

    public FileSystem() {
        // 根作为哨兵预置，让一级路径的父检查自然命中。
        this.values = new HashMap<>();
        values.put("/", -1);
    }

    public boolean createPath(String path, int value) {
        if (values.containsKey(path)) {
            return false;
        }

        // 父路径是最后一个 '/' 之前的部分；一级路径截出空串，映射回根。
        int idx = path.lastIndexOf('/');
        String parent = path.substring(0, idx);
        if (parent.isEmpty()) {
            parent = "/";
        }

        if (!values.containsKey(parent)) {
            return false;
        }

        values.put(path, value);
        return true;
    }

    public int get(String path) {
        return values.getOrDefault(path, -1);
    }
}

import "strings"

type FileSystem struct {
	values map[string]int
}

func Constructor() FileSystem {
	// 根作为哨兵预置，让一级路径的父检查自然命中。
	return FileSystem{
		values: map[string]int{"/": -1},
	}
}

func (fs *FileSystem) CreatePath(path string, value int) bool {
	if _, ok := fs.values[path]; ok {
		return false
	}

	// 父路径是最后一个 '/' 之前的部分；一级路径截出空串，映射回根。
	idx := strings.LastIndex(path, "/")
	parent := path[:idx]
	if parent == "" {
		parent = "/"
	}

	if _, ok := fs.values[parent]; !ok {
		return false
	}

	fs.values[path] = value
	return true
}

func (fs *FileSystem) Get(path string) int {
	if v, ok := fs.values[path]; ok {
		return v
	}
	return -1
}

复杂度分析

时间复杂度：createPath 与 get 的平均时间都是 $O(L)$，$L$ 为传入路径长度；完整字符串键的哈希、父路径截取都至多线性。哈希表发生极端冲突时不承诺该平均界。

空间复杂度：$O(\sum \lvert path\rvert)$，即所有已创建路径字符串的总长度；哈希表不共享公共前缀。

关键点总结

设计题的第一步是读清访问模式：本题只有「整条路径的存在性与取值」两种查询，从不列目录、不遍历子项，所以扁平哈希表就够了，不必真的建树。需求决定结构，这是设计题最核心的判断。

树形约束不必用指针维护：只要每次插入都强制校验父键存在，键集合就归纳地保持为一棵合法的树。把不变量说出来，比画出树形图更能说服面试官。

父路径靠 lastIndexOf('/') 截取，父子关系天然编码在字符串里，无需额外结构。

预置根哨兵后，一级路径也走统一的“父路径必须存在”判断；createPath("/") 则由查重自然拒绝。

校验必须全部通过后才写入，任何「先写后判」的写法都会破坏结构不变量并污染后续操作。

面试视角：应主动说明取舍——当前只有完整路径操作，哈希表最直接；若增加列目录、前缀搜索或递归删除，再改为字典树节点结构。

易错点总结

错误写法：漏掉 parent.isEmpty() 到 "/" 的映射。用例 createPath("/leet", 1)：父被截成空串，表中没有空串键，返回 false，此后所有一级路径都建不出来，整套用例全线失败。

错误写法：用 indexOf('/') 而不是 lastIndexOf('/') 截父路径。用例 createPath("/leet/code", 2)：父被算成空串（第一个 / 在下标 0），映射到根后校验通过，于是绕过了「必须先有 /leet」的规则，createPath("/a/b/c") 在 /a 不存在时也会成功。

错误写法：先 values.put(path, value) 再做父存在性校验。用例 createPath("/c/d", 1)（/c 不存在）：虽然返回了 false，但 /c/d 已被写进表里，随后 get("/c/d") 返回 1、createPath("/c/d/e", 2) 也会成功，结构彻底失效。

错误写法：查重时用 get(path) != -1 判断是否已存在。用例 createPath("/a", -1) 后再 createPath("/a", 5)：第一次存的值恰好是 -1，查重误判为不存在，值被覆盖成 5，第二次还错误地返回 true。

错误写法：不预置根或重复创建时覆盖旧值。前者使 createPath("/a", 1) 失败，后者使第二次 createPath("/a", 2) 错误成功；根哨兵和先查重分别守住这两个边界。

错误写法：get 未命中返回 0。get("/missing") 必须返回 -1，否则会与值确实为 0 的已创建路径混淆。

相似题目

题目	难度	考察点
588. 设计内存文件系统	困难	需要 `ls` 列目录并区分文件与目录，此时必须真的建树，哈希表不再够用
208. 实现 Trie (前缀树)	中等	需要前缀查询，展示字典树相对扁平哈希表不可替代的能力
211. 添加与搜索单词 - 数据结构设计	中等	支持通配符匹配，必须在字典树上做 DFS，键级哈希彻底失效
677. 键值映射	中等	同为「键到值」的映射，但要按前缀求和，考察前缀聚合的维护方式
1268. 搜索推荐系统	中等	前缀检索 + 取字典序最小的若干项，字典树与排序数组两种方案的取舍
146. LRU 缓存	中等	另一类设计题，考察「按访问模式选结构」的同一种判断力