LeetCode 1487. 保证文件名唯一

Categories:

题目描述
思路分析
1. 解法一：哈希表 + 计数（推荐）
相似题目

题目描述

✅ 1487. 保证文件名唯一

思路分析

解法一：哈希表 + 计数（推荐）

核心思路：

用哈希表记录每个名字的下一个可用编号。

若名字未出现，直接使用并记录为 1。

若已出现，从记录的编号开始尝试直到找到未使用名称。

复杂度分析：

时间复杂度：均摊 O(n)。

空间复杂度：O(n)。

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

class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> next = new HashMap<>();
        String[] res = new String[names.length];

        for (int i = 0; i < names.length; i++) {
            String name = names[i];
            if (!next.containsKey(name)) {
                res[i] = name;
                next.put(name, 1);
                continue;
            }

            int k = next.get(name);
            String candidate = name + "(" + k + ")";
            while (next.containsKey(candidate)) {
                k++;
                candidate = name + "(" + k + ")";
            }
            res[i] = candidate;
            next.put(name, k + 1);
            next.put(candidate, 1);
        }
        return res;
    }
}

func getFolderNames(names []string) []string {
    next := make(map[string]int)
    res := make([]string, len(names))

    for i, name := range names {
        if _, ok := next[name]; !ok {
            res[i] = name
            next[name] = 1
            continue
        }

        k := next[name]
        candidate := buildName(name, k)
        for {
            if _, ok := next[candidate]; !ok {
                break
            }
            k++
            candidate = buildName(name, k)
        }
        res[i] = candidate
        next[name] = k + 1
        next[candidate] = 1
    }
    return res
}

func buildName(name string, k int) string {
    return name + "(" + itoa(k) + ")"
}

func itoa(x int) string {
    if x == 0 {
        return "0"
    }
    buf := make([]byte, 0)
    for x > 0 {
        buf = append(buf, byte('0'+x%10))
        x /= 10
    }
    for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
        buf[i], buf[j] = buf[j], buf[i]
    }
    return string(buf)
}

相似题目

题目	难度	考察点
706. 设计哈希映射	简单	设计
705. 设计哈希集合	简单	设计
535. TinyURL 的加密与解密	中等	哈希
1396. 设计地铁系统	中等	设计
380. O(1) 时间插入、删除和获取随机元素	中等	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/33782512