保证文件名唯一

这道题感觉还是很有实际意义的，平时我们经常会新建文件，不过题意和win上的操作是有点区别的。比如win上已经有个叫1 (1).txt的文件，如果我们再建一个1 (1).txt，win会帮我们改成1 (2).txt，而这道题会改成1 (1)(1).txt。想一想确实win上的解决方案会更合理一些，不然会导致文件名过长，不好识别。

题解

题目链接

暴力

时间复杂度：

思路

用一个set维护所有的文件名，如果当前字符串不在set中，则直接添加，否则后缀从1开始递增直到不在set中，然后添加。

代码

class Solution {
    public String[] getFolderNames(String[] names) {
        int n = names.length;
        Set<String> set = new HashSet<>();
        List<String> ans = new ArrayList<>();
        for (String s : names) {
            if (set.contains(s)) {
                int k = 1;
                while (set.contains(s + "(" + k + ")")) k++;
                ans.add(s + "(" + k + ")");
                set.add(s + "(" + k + ")");
            } else {
                ans.add(s);
                set.add(s);
            }
        }
        return ans.toArray(new String[ans.size()]);
    }
}

优化

时间复杂度：

思路

用一个map记录一下，重复的文件名后缀开始的值，这样就可以将暴力中k从1开始那部分循环去掉，减少一维，将时间复杂度降到：。

代码

class Solution {
    public String[] getFolderNames(String[] names) {
        int n = names.length;
        Set<String> set = new HashSet<>();
        List<String> ans = new ArrayList<>();
        Map<String, Integer> cnt = new HashMap<>();
        for (String s : names) {
            if (set.contains(s)) {
                int k = cnt.getOrDefault(s, 1);
                while (set.contains(s + "(" + k + ")")) k++;
                cnt.put(s, k + 1);
                ans.add(s + "(" + k + ")");
                set.add(s + "(" + k + ")");
            } else {
                ans.add(s);
                set.add(s);
            }
        }
        return ans.toArray(new String[ans.size()]);
    }
}

模拟win上的新建文件夹

看似简单，还是有很多细节呀。

代码

import java.util.*;

/**
 * 默认加后缀前有空格。例如：xxx (xxx).xxx
 * win上的后缀默认从2开始。
 */
public class NewFileOnWin {
    public static String[] input;
    public static String[] output;
    public static Set<String> set = new HashSet<>();
    public static Map<String, Integer> start = new HashMap<>();

    public static void main(String[] args) {
        initInput();
        solve();
        for (String item : output) {
            System.out.println(item);
        }
    }

    public static void initInput() {
        input = new String[]{   // --> 预期结果
                "1.txt",        // --> 1.txt
                "1.txt",        // --> 1 (2).txt
                "2 (1).txt",    // --> 2 (1).txt
                "2 (1).txt",    // --> 2 (2).txt
                "3.txt",        // --> 3.txt
                "3 (3).txt",    // --> 3 (3).txt
                "3.txt",        // --> 3 (2).txt
                "3.txt",        // --> 3 (4).txt
                "3.txt",        // --> 3 (5).txt
                "2 (1).txt"     // --> 2 (3).txt
        };
    }

    public static void solve() {
        int n = input.length;
        output = new String[n];
        for (int i = 0; i < n; i++) {
            if (!set.contains(input[i])) {
                output[i] = input[i];
                set.add(output[i]);
            } else {
                int pointIdx = input[i].indexOf('.');
                int spaceIdx = input[i].indexOf(' ');
                if (pointIdx > 0 && input[i].charAt(pointIdx - 1) == ')') {
                    String name = input[i].substring(0, spaceIdx);
                    String suffix = input[i].substring(pointIdx, input[i].length());
                    String originalName = name + suffix;
                    int k = start.getOrDefault(originalName, 2);
                    while (true) {
                        String tmp = name + " (" + k + ")" + suffix;
                        if (!set.contains(tmp)) {
                            output[i] = tmp;
                            start.put(originalName, k + 1);
                            set.add(output[i]);
                            break;
                        } else {
                            k++;
                        }
                    }
                } else {
                    int k = start.getOrDefault(input[i], 2);
                    String name = input[i].substring(0, pointIdx);
                    String suffix = input[i].substring(pointIdx, input[i].length());
                    while (true) {
                        String tmp = name + " (" + k + ")" + suffix;
                        if (!set.contains(tmp)) {
                            output[i] = tmp;
                            start.put(input[i], k + 1);
                            set.add(output[i]);
                            break;
                        } else {
                            k++;
                        }
                    }
                }
            }
        }
    }
}

结果