效果好的网站制作,郑州品牌设计公司排行,织梦 网站版权信息,小程序直播开发题目链接 Leetcode.1487 保证文件名唯一 Rating #xff1a; 1697 题目描述
给你一个长度为 n的字符串数组 names。你将会在文件系统中创建 n个文件夹#xff1a;在第 i 分钟#xff0c;新建名为 names[i]的文件夹。
由于两个文件 不能 共享相同的文件名#xff0c;因此如…题目链接 Leetcode.1487 保证文件名唯一 Rating 1697 题目描述
给你一个长度为 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) 。 提示
1names.length5∗1041 names.length 5 * 10^41names.length5∗1041names[i].length201 names[i].length 201names[i].length20names[i]由小写英文字母、数字和/或圆括号组成。
分析
我们用一个 哈希表map记录每一个文件名 对应的 最小后缀 即可。 对于每一个文件名 s
如果map中找不到s说明 s是唯一的直接将其记录到答案中即可更新 map.put( s , 1 )。如果map中存在s且 t map.get(s)那么我们需要不断增加 t直到 map中不包含 s ( t )并且此时 s的最小后缀要更新为新的 t即 map.put( s , t )那么此时的 name s ( t )就是最新的文件名记录到答案中更新 map.put( name , 1 )。
时间复杂度O(names.length∗nums[i].length)O(names.length * nums[i].length)O(names.length∗nums[i].length)
C代码
class Solution {
public:vectorstring getFolderNames(vectorstring names) {unordered_mapstring,int cnt;vectorstring ans;for(auto s:names){int t cnt[s];if(t){while(cnt.count(s ( to_string(t) ))) t;cnt[s] t;s ( to_string(t) );}cnt[s] 1;ans.push_back(s);}return ans;}
};Java代码
class Solution {public String[] getFolderNames(String[] names) {MapString, Integer map new HashMap();int n names.length;String[] ans new String[n];for (int i 0; i n; i) {String s names[i];if (map.containsKey(s)) {int t map.get(s);while (map.containsKey(s ( t ))) t;map.put(s , t);s ( t );}map.put(s, 1);ans[i] s;}return ans;}
}
