LeetCode破解之文件夹系统

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

题目描述

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

我们这样定义「子文件夹」：

  • 如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的子文件夹。
    文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：
  • / 后跟一个或者多个小写英文字母。
    例如，/leetcode 和 /leetcode/problems 都是有效的路径，而空字符串和 / 不是。

示例 1：

输入：folder = [“/a”,”/a/b”,”/c/d”,”/c/d/e”,”/c/f”]
输出：[“/a”,”/c/d”,”/c/f”]
解释：”/a/b/“ 是 “/a” 的子文件夹，而 “/c/d/e” 是 “/c/d” 的子文件夹。

示例 2：

输入：folder = [“/a”,”/a/b/c”,”/a/b/d”]
输出：[“/a”]
解释：文件夹 “/a/b/c” 和 “/a/b/d/“ 都会被删除，因为它们都是 “/a” 的子文件夹。

提示：

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] 只包含小写字母和 /
  • folder[i] 总是以字符 / 起始
  • 每个文件夹名都是唯一的

思路

利用排序和Set数据结构，先对数据排序，同时定义一个Set和一个数组，存放排序后的第一个值。再用循环遍历数据，每次和数组最后一个比较，因为排序好了的，所以数组最后一项长度是要大于要比较那项的长度。

特殊情况：

  • /a/b和/a/c
  • /a/b和/a/bc

通过使用Set去重，最后return的结果再转为数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> list = new ArrayList<>();
        String ans = "";
        boolean findFirst = false;
        for (String s : folder) {
            if ("/".equals(s)) {
                continue;
            }
            if (!findFirst) {
                ans = s;
                findFirst = true;
                list.add(ans);
                continue;
            }
            if (s.startsWith(ans) && s.charAt(ans.length()) == '/') {
                continue;
            }
            ans = s;
            list.add(ans);
        }
        return list;
    }

分析：其实感觉题目想要我们搞个字典树出来，但我感觉没必要。这里在提供一种滑动窗口+排序的方法。c++版本的，还是c++写算法方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
cpp复制代码class Solution {
public:
    bool ispre(string s1,string s2){
        if(s1.size()==s2.size()) return false;
        int i;
        for(i=0;i<s1.size();i++){
            if(s2[i]!=s1[i]) return false;
        }
        return s2[i]=='/';
    }
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(),folder.end());
        vector<string> ans;
        int s=folder.size(),l=0,r=1;
        if(s<=1) return ans;
        ans.push_back(folder[0]);
        while(l<s&&r<s){
            if(ispre(folder[l],folder[r])) r++;
            else{
                l=r;
                r=l+1;
                ans.push_back(folder[l]);

            }
        }
        return ans;
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%