leetcode
leetcode 1351 ~ 1400
保证文件名唯一

保证文件名唯一

难度:

标签:

题目描述

代码结果

运行时间: 75 ms, 内存: 30.4 MB


/*
 * 思路:
 * 使用Java Stream的方式实现相同的逻辑。
 * 使用一个HashMap来记录每个文件名出现的次数。
 * 遍历每个文件名,如果当前文件名已经存在于HashMap中,则找到一个唯一的文件名(通过在文件名后添加后缀(k))并更新HashMap。
 * 如果文件名不存在,则直接添加到结果列表中。
 */
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> nameCount = new HashMap<>();
        return IntStream.range(0, names.length)
                .mapToObj(i -> {
                    String name = names[i];
                    if (!nameCount.containsKey(name)) {
                        nameCount.put(name, 1);
                        return name;
                    } else {
                        int k = nameCount.get(name);
                        String newName = name + "(" + k + ")";
                        while (nameCount.containsKey(newName)) {
                            k++;
                            newName = name + "(" + k + ")";
                        }
                        nameCount.put(name, k + 1);
                        nameCount.put(newName, 1);
                        return newName;
                    }
                })
                .toArray(String[]::new);
    }
}

解释

方法:

此题解使用一个哈希表(defaultdict)来跟踪每个文件名以及其后缀形式的使用情况。对于每个输入的文件名,如果它尚未被使用过,直接使用它并在哈希表中做标记。如果已被使用,则通过循环增加后缀的编号,生成一个新的唯一文件名。使用格式'name(k)',其中k是最小未被使用的正整数,确保文件名的唯一性。通过不断检查新生成的文件名是否被占用,直到找到一个未被使用的为止。

时间复杂度:

O(n) 在平均情况下; O(n*k) 在最坏情况下,其中k是某个文件名的最大重复次数

空间复杂度:

O(n)

代码细节讲解

🦆
在哈希表中,您是如何处理文件名和后缀形式的映射关系?是否存在一种情况下,可能会误将原始文件名和修改后的文件名视为不同的两个键?
在此题解中,每个文件名(无论是原始的还是带后缀的)都作为哈希表的键。例如,'file'和'file(1)'在哈希表中是不同的键。这种设计可以避免将原始文件名和修改后的文件名混淆。因此不存在将它们视为同一个键的情况。当检查一个新文件名是否已使用时,会分别检查其作为原始名称和作为修改后名称的情况。
🦆
代码中使用了defaultdict(int),具体是如何初始化每个文件名的计数的?例如,当一个全新的文件名首次出现时,其值是如何被设置的?
在Python中,使用`defaultdict`时可以通过传递一个类型(如`int`),默认将每个新键的值初始化为该类型的默认值。对于`int`类型,其默认值是`0`。因此,在`used_names`哈希表中,当首次引用一个文件名时,如果它之前未出现过,其计数自动初始化为`0`。这便于检查一个文件名是否首次使用,并在首次使用时将其计数设为`1`。
🦆
题解中未详细解释如何处理输入中已存在形如'name(k)'的文件名。如果输入中包含'pes(1)',而后又出现'pes',处理逻辑会有何不同?
题解中的逻辑首先会将'pes(1)'作为一个独立的文件名处理并存储,此时'pes(1)'在哈希表中计数为1。当后续出现'pes'时,代码会检查'pes'是否已使用。如果'pes'未被使用,则直接添加'pes'并将其计数设为1。如果'pes'已使用,代码会尝试生成新的文件名,如'pes(1)','pes(2)'等。在这个例子中,由于'pes(1)'已经存在,代码会检测到这一点并尝试更高的后缀,比如'pes(2)'。这种处理确保了即使输入中包含形如'name(k)'的文件名,生成的文件名依然是唯一的。

相关问题