成都网站建设定,可以怎么找回密码,四川清风建设工程有限公司网站,济南知名网站建设平台【LetMeFly】1487.保证文件名唯一
力扣题目链接#xff1a;https://leetcode.cn/problems/making-file-names-unique/
给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹#xff1a;在第 i 分钟#xff0c;新建名为 names[i] 的文件夹。
由于两个…【LetMeFly】1487.保证文件名唯一
力扣题目链接https://leetcode.cn/problems/making-file-names-unique/
给你一个长度为 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^41 names[i].length 20names[i] 由小写英文字母、数字和/或圆括号组成。
方法一哈希
使用一个哈希表或者说字典记录名字“xxx”下次该被重命名到几。
例如“hello”被重命名到了“hello(2)”那么哈希表中[hello]对应的值就为“3”
然后我们遍历名字列表names从哈希表中记录的“应该开始的数字”开始尝试命名若新名字已存在则尝试从下一个数字开始命名直到找到一个还未被占用过的名字为止。
时间复杂度O(N)O(N)O(N)其中NNN是名字列表中所有名字的字母个数之和。内层循环总次数不超过len(names)len(names)len(names)空间复杂度O(N)O(N)O(N)
AC代码
C
class Solution {
private:string nameAndSuffix(string name, int suffix) {if (suffix) {return name ( to_string(suffix) );}else {return name;}}
public:vectorstring getFolderNames(vectorstring names) {unordered_mapstring, int ma;vectorstring ans;for (string name : names) {if (!ma.count(name)) {ans.push_back(name);ma[name] 1;}else {int times ma[name];string newName nameAndSuffix(name, times);while (ma.count(newName)) {newName nameAndSuffix(name, times);}ans.push_back(newName);ma[name] times 1;ma[newName] 1;}}return ans;}
};Python
# from typing import Listclass Solution:def nameAndSuffix(self, name: str, suffix: int) - str:if not suffix:return nameelse:return name ( str(suffix) )def getFolderNames(self, names: List[str]) - List[str]:ma {}ans []for name in names:if name not in ma:ans.append(name)ma[name] 1else:times ma[name]newName self.nameAndSuffix(name, times)while newName in ma:times 1newName self.nameAndSuffix(name, times)ans.append(newName)ma[name] times 1ma[newName] 1return ans同步发文于CSDN原创不易转载请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/129317690
