LeetCode 1166. 设计文件系统

Categories:

题目描述
思路分析
1. 解法一：哈希表记录路径（推荐）
相似题目

题目描述

✅ 1166. 设计文件系统

思路分析

解法一：哈希表记录路径（推荐）

核心思路：

用哈希表保存 path -> value，将已创建路径视作已存在节点。

创建路径时校验：当前路径未存在，且父路径已存在（根路径视为已存在）。

get 直接从哈希表读取，不存在返回 -1。

复杂度分析：

时间复杂度：O(L)，其中 L 为路径长度，主要用于解析父路径。

空间复杂度：O(n)，其中 n 为已创建路径数量。

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 (path == null || path.isEmpty() || "/".equals(path)) {
            return false;
        }

        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 path == "" || path == "/" {
        return false
    }

    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
}

相似题目

题目	难度	考察点
588. 设计内存文件系统	困难	设计、字典树
208. 实现 Trie (前缀树)	中等	字典树
211. 添加与搜索单词 - 数据结构设计	中等	字典树
677. 键值映射	中等	前缀统计
676. 实现一个魔法字典	中等	设计、字典树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/41243551