LeetCode刷题【1487】保证文件名唯一

给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。

由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。

返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。

 

示例 1：

输入：names = ["pes","fifa","gta","pes(2019)"]
输出：["pes","fifa","gta","pes(2019)"]
解释：文件系统将会这样创建文件名：
"pes" --> 之前未分配，仍为 "pes"
"fifa" --> 之前未分配，仍为 "fifa"
"gta" --> 之前未分配，仍为 "gta"
"pes(2019)" --> 之前未分配，仍为 "pes(2019)"

示例 2：

输入：names = ["gta","gta(1)","gta","avalon"]
输出：["gta","gta(1)","gta(2)","avalon"]
解释：文件系统将会这样创建文件名：
"gta" --> 之前未分配，仍为 "gta"
"gta(1)" --> 之前未分配，仍为 "gta(1)"
"gta" --> 文件名被占用，系统为该名称添加后缀 (k)，由于 "gta(1)" 也被占用，所以 k = 2 。实际创建的文件名为 "gta(2)" 。
"avalon" --> 之前未分配，仍为 "avalon"

示例 3：

输入：names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出：["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释：当创建最后一个文件夹时，最小的正有效 k 为 4 ，文件名变为 "onepiece(4)"。

示例 4：

输入：names = ["wano","wano","wano","wano"]
输出：["wano","wano(1)","wano(2)","wano(3)"]
解释：每次创建文件夹 "wano" 时，只需增加后缀中 k 的值即可。

示例 5：

输入：names = ["kaido","kaido(1)","kaido","kaido(1)"]
输出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
解释：注意，如果含后缀文件名被占用，那么系统也会按规则在名称后添加新的后缀 (k) 。

 

提示：

• 1 <= names.length <= 5 * 10^4
• 1 <= names[i].length <= 20
• names[i] 由小写英文字母、数字和/或圆括号组成。

题解

class Solution {
    HashMap<String,Integer> hashMap = new HashMap<>();
    public String[] getFolderNames(String[] names) {
        for (int i = 0; i < names.length; i++) {
            names[i] = putName(names[i], 0);
        }
        return names;
    }

    public String putName(String name, int num){
        String newName;
        while (true){
            newName= num==0?name:name+"("+num+")";
            if (!hashMap.containsKey(newName)){
                hashMap.put(newName,0);
                if (num>0){
                    hashMap.put(name,num);
                }
                break;
            }
            hashMap.put(name,hashMap.get(name)+1);
            num = hashMap.get(name);
        }
        return newName;
    }
}

原本在这个之前写过一版，超时，32 / 33 个通过测试用例，在最后一个超长的测试用力的时候超时了，所以再这个基础上再加改进，改原来的hashset为map，额外统计对应字符已经用过的次数，下次遇到冲突的时候根据之前的记忆来获取新的key。

class Solution {
    HashSet<String> hashSet = new HashSet<>();
    public String[] getFolderNames(String[] names) {
        for (int i = 0; i < names.length; i++) {
            names[i] = putName(names[i], 0);
        }
        return names;
    }

    public String putName(String name, int num){
        String newName = num==0?name:name+"("+num+")";
        if (!hashSet.contains(newName)){
            hashSet.add(newName);
            return newName;
        }
        return putName(name,num+1);
    }
}

有一点就是 如果在已经输入了“abc”,“abc(1)”的情况下，再次输入“abc”,
此时记录的数量应该为：
“abc”1次
“abc(1)”1次

需要新增一个key=“abc”的记录，发现已有再次尝试“abc(1)”还是已有的情况下，需要对“abc”的数量修正加1
此时变成：
“abc”2次
“abc(1)”1次

这样能把之前的输入“abc(1)”的时候没有去给“abc”加1的误差修正回来，便于本次插入的统计，而最终结果只要是能插入就行，后续还有其他的中间状态的统计不正确并不需要去修正处理。

当然这边你也可以选择对插入的文件名进行判断括号字符串，找到除去括号外的真实文件名，但是我觉得这种做法有点点点…..不大优雅….吧，或者说有点点傻….

还有一点就是在getFolderNames中的for循环遍历中，直接修改当前插入的字符串的存到对应位置，最终仍旧是返回String[] names数组，无需额外声明数组开辟新的内存空间。