webpack+vite前端构建工具全掌握（中篇）

$\texttt{/a}$ 不可能是任何文件夹 $A$ 的子文件夹（否则 $A$ 会排在 $\texttt{/a}$ 前面）。
$\texttt{/a/b}$ 是 $\texttt{/a}$ 的子文件夹，删除。
$\texttt{/c}$ 不是 $\texttt{/a}$ 的子文件夹。
$\texttt{/d}$ 不是 $\texttt{/c}$ 的子文件夹。注意，不需要判断 $\texttt{/d}$ 是否为 $\texttt{/a}$ 的子文件夹。因为一定不是，为什么？如果 $\texttt{/d}$ 是 $\texttt{/a}$ 的子文件夹，由于列表是有序的，$\texttt{/a}$ 的下一个字符串到 $\texttt{/d}$ 之间的字符串都是以 $\texttt{/a/}$ 开头的，所以上一个文件夹 $\texttt{/c}$ 也是以 $\texttt{/a/}$ 开头的，一定是 $\texttt{/a}$ 的子文件夹，一定会被删除，但这与实际矛盾。

因此，排序后，只需比较当前路径与上一个未被删除的路径。

代码实现时，为避免 $A + \texttt{/}$ 生成新字符串花费额外时间和空间，判断 $A + \texttt{/}$ 是否为 $B$ 的前缀，可以分解为：

判断 $A$ 是否为 $B$ 的前缀。
判断 $B[m]$ 是否为 $\texttt{/}$，其中 $m$ 是 $A$ 的长度。注意题目保证所有字符串互不相同，所以如果 $A$ 是 $B$ 的前缀，那么 $B$ 的长度一定大于 $A$ 的长度。所以 $B[m]$ 不会下标越界。

###py

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for s in folder[1:]:  # 切片可以用 for i in range(1, n) 代替，做到 O(1) 空间
            last = ans[-1]
            if not s.startswith(last) or s[len(last)] != '/':
                ans.append(s)
        return ans

###java

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> ans = new ArrayList<>();
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; i++) {
            String s = folder[i];
            String last = ans.getLast();
            if (!s.startsWith(last) || s.charAt(last.length()) != '/') {
                ans.add(s);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        ranges::sort(folder);
        vector<string> ans = {folder[0]};
        for (int i = 1; i < folder.size(); i++) {
            string& s = folder[i];
            string& last = ans.back();
            if (!s.starts_with(last) || s[last.size()] != '/') {
                ans.emplace_back(s);
            }
        }
        return ans;
    }
};

###c

int cmp(const void* a, const void* b) {
    return strcmp(*(char**)a, *(char**)b);
}

char** removeSubfolders(char** folder, int folderSize, int* returnSize) {
    qsort(folder, folderSize, sizeof(char*), cmp);

    *returnSize = 1;
    for (int i = 1; i < folderSize; i++) {
        char* s = folder[i];
        char* last = folder[*returnSize - 1];
        int len = strlen(last);
        if (strncmp(last, s, len) != 0 || s[len] != '/') {
            folder[(*returnSize)++] = s; // 原地保存
        }
    }

    return folder;
}

###go

func removeSubfolders(folder []string) []string {
    slices.Sort(folder)
    ans := folder[:1]
    for _, s := range folder[1:] {
        last := ans[len(ans)-1]
        if !strings.HasPrefix(s, last) || s[len(last)] != '/' {
            ans = append(ans, s)
        }
    }
    return ans
}

###js

var removeSubfolders = function(folder) {
    folder.sort();
    const ans = [folder[0]];
    for (let i = 1; i < folder.length; i++) {
        const s = folder[i];
        const last = ans[ans.length - 1];
        if (!s.startsWith(last) || s[last.length] !== '/') {
            ans.push(s);
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn remove_subfolders(mut folder: Vec<String>) -> Vec<String> {
        folder.sort_unstable();
        let mut ans = vec![folder[0].clone()];
        for s in folder.into_iter().skip(1) {
            let last = ans.last().unwrap();
            if !s.starts_with(last) || s.as_bytes()[last.len()] != b'/' {
                ans.push(s);
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(\ell\cdot n\log n)$ 时间，$n$ 是 $\textit{folder}$ 的长度，$\ell\le 100$ 为单个字符串的长度。排序有 $\mathcal{O}(n\log n)$ 次比较，每次 $\mathcal{O}(\ell)$ 时间。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。忽略排序的栈开销。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

揭秘Chrome DevTools：从原理到自定义调试工具

掘金前端

京东云开发者

2025年7月18日 17:24

引言 Chrome DevTools 是前端开发者的必备工具，不仅可以用于调试 Chrome 网页，还支持 Android WebView、Roma (跨平台开发框架) 安卓&鸿蒙端 ****等平台的

我终于也是会写3d小游戏的人了，发个掘金显摆显摆

掘金前端

鬼鬼_静若为竹

2025年7月18日 17:03

先上代码块，代码共用4部分组成 1.就是代码的主体部分index.vue 第二部分是里面自己绘制的小房子部分miniHomeManager.ts 第三部分是房子的校验条件tsType.ts 最后是房子

WebSocket：断线、心跳与重连

掘金前端

前端微白

2025年7月18日 16:42

作为现代实时应用的通信基石，WebSocket解决了传统HTTP协议的诸多痛点。本文将深入剖析WebSocket的核心机制，通过真实案例解读其实现原理和故障处理方案。一、为何能解决断线问题？传统H

“移动端优先”在隐藏元素方面的问题 - tailwindcss 系列

掘金前端

Legend80s

2025年7月18日 15:05

🤕 问题 tailwind css 推崇移动端优先原则：也就是说默认情况我们的样式是针对移动端的，如果需要适配宽屏需要增加前缀 md: 或 lg: 等，看起来挺好的，但是在隐藏元素方面存在一些不方便

大屏应用中的动态缩放适配工具

掘金前端

早发白帝城

2025年7月18日 14:55

ScreenScaler 一个强大的大屏缩放适配器，专为大屏应用开发设计。支持多种缩放模式，提供完整的 TypeScript 类型支持。 ✨ 特性 🎯 多种缩放模式: 支持自动、宽度、高度、拉伸、无缩

别再硬啃文档了！用 AI 十分钟上手任意 GitHub 。文档不全，调用出错，快速解决

掘金前端

柒崽

2025年7月18日 10:53

不知道你有没有遇到过，使用github的仓库，但是很多文档写的不好，甚至什么都没写，让人根本不知道应该怎么使用。或者自己懒得去看大篇的文档，只想快速上手使用。今天介绍一个工具，可以读取github源

Three.js 滚动条 3D 视差动画原理解析

掘金前端

LeonGao

2025年7月18日 10:12

🌌 Three.js 滚动条 3D 视差动画原理教学：滚着滚着，就进了宇宙 🌠 前言：滚动条不只是滚动，它是时间的流动，是空间的扭曲在现代网页中，用户滚动页面的动作不仅能驱动页面滑动，更能驱动三维世

前端学C++可太简单了：预处理器

掘金前端

山河木马

2025年7月18日 09:29

1. 概念对比：JavaScript编译时 vs C++预处理 JS/TS 编译时处理 C++ 预处理器 2. 预处理器指令 2.1 文件包含 #include (类似 import) 与JavaSc

括号生成算法

掘金前端

前端微白

2025年7月19日 00:01

你在开发一个动态表单生成器，用户可以通过拖拽组件构建界面。当处理嵌套组件时（如折叠面板中的表格、弹窗内的表单），你需要生成所有可能的有效嵌套组合——这正是括号生成问题在前端的实际应用。

// 组件嵌套示例：
<Modal>                  // 开括号
  <Table>                // 开括号
    <Form />             // 内容
  </Table>               // 闭括号
</Modal>                 // 闭括号

问题定义：寻找有效括号组合

给定正整数 n，要求生成所有有效的括号组合，满足：

每个组合包含 n 对圆括号
每个开括号 ( 都有对应闭括号 )
闭括号不能出现在对应开括号之前

例如 n = 3 时：

有效的组合: ["((()))", "(()())", "(())()", "()(())", "()()()"]
无效的组合: ["())()(", "())(()"] // 括号不匹配

解法一：回溯法（深度优先搜索）

核心思路：递归构建所有可能的组合，同时确保每一步都符合有效条件。

function generateParenthesis(n) {
  const result = []; // 存储所有有效组合
  
  // 递归生成函数
  const backtrack = (str, openCount, closeCount) => {
    // 已生成完整组合
    if (str.length === 2 * n) {
      result.push(str);
      return;
    }
    
    // 添加开括号的条件：开括号数少于n
    if (openCount < n) {
      backtrack(str + '(', openCount + 1, closeCount);
    }
    
    // 添加闭括号的条件：闭括号数小于开括号数
    if (closeCount < openCount) {
      backtrack(str + ')', openCount, closeCount + 1);
    }
  };
  
  backtrack('', 0, 0); // 初始调用
  return result;
}

执行过程可视化（n=2）：

开始: "" (0开, 0闭)
├─ 添加( → "( "(1,0)
│   ├─ 添加( → "((" (2,0) → 闭括号只能添加)
│   │   └─ 添加) → "(()" (2,1)
│   │      └─ 添加) → "(())" (2,2) ✅
│   └─ 添加) → "()" (1,1)
│       └─ 添加( → "()(" (2,1)
│          └─ 添加) → "()()" (2,2) ✅
└─ 添加) → 无效路径（闭括号前无开括号）

复杂度分析：

时间复杂度：O(4^n/√n) - 卡特兰数增长速度
空间复杂度：O(n) - 递归栈深度

解法二：动态规划 - 优雅的递推解法

核心思路：n 对括号的组合 = ( + i 对括号的组合 + ) + n-1-i 对括号的组合

function generateDP(n) {
  // 存储不同数量组合的结果
  const dp = [...Array(n+1)].map(() => []);
  dp[0] = ['']; // 基础情况：0对括号为空字符串
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      // 内部组合可能有j种情况
      for (const left of dp[j]) {
        // 外部组合有i-1-j种情况
        for (const right of dp[i - 1 - j]) {
          // 构建新组合： (left)right
          dp[i].push(`(${left})${right}`);
        }
      }
    }
  }
  return dp[n];
}

计算过程展示（n=3）：

dp[0] = [""]
dp[1] = ["()"]
dp[2]:
  从dp[0]和dp[1]: ( ) + "" = "()" → 但需要外括号包裹 → 变为 "( )" + "" → 错误
  正确计算：
   j=0: ("")  → dp[2] 加入 ( ) + dp[1]的内容 → ( )() → "()()"
   j=1: (dp[1]内容) → (()) + dp[0]="" → "(())"
dp[3]:
   j=0: ("") → ( ) + dp[2]的内容 → ["()(())", "()()()"]
   j=1: 使用dp[1] → (dp[1]内容) + dp[1] → (())()
   j=2: 使用dp[2] → (dp[2]内容) → 包括两种情况：("(())")和("()()") 加上空外部
        → ["((()))", "(()())"]

两种方法对比：选择最优方案

特性	回溯法	动态规划
时间复杂度	O(4ⁿ/√n)	O(4ⁿ/√n)
空间复杂度	O(n) 调用栈	O(4ⁿ/√n) 存储所有组合
实现难度	★★★☆	★★★★
适用场景	仅需结果列表	需要中间结果集
优势	内存占用低，实现直观	数学证明清晰
前端适用度	⭐⭐⭐⭐	⭐⭐

前端推荐选择回溯法：动态规划需存储所有中间结果，当 n>10 时可占用数百MB内存，不适合前端环境。

实际项目应用：React状态管理优化

当组件有多层依赖关系时，我们需要生成有效依赖树：

// 动态生成嵌套组件结构
function DependencyTree({ dependencies }) {
  // 计算依赖关系树
  const generateTree = (level) => {
    const brackets = generateParenthesis(level);
    return brackets.map((pattern, index) => (
      <div key={index} className="dependency-branch">
        {renderPattern(pattern)}
      </div>
    ));
  };

  // 将括号模式转换为可视化组件
  const renderPattern = (pattern) => {
    return pattern.split('').map((char, i) => (
      char === '(' ? 
        <div className="nested-block"> : 
        </div>
    ));
  };

  return <div className="dependency-tree">{generateTree(dependencies)}</div>;
}

高级技巧：使用剪枝优化性能

对于大规模应用场景，可在回溯法中添加记忆化缓存：

function generateOptimized(n) {
  const memo = new Map();

  function backtrack(open, close) {
    const key = `${open}_${close}`;
    if (memo.has(key)) return memo.get(key);
    
    if (open === n && close === n) return [''];

    const results = [];
    if (open < n) {
      backtrack(open + 1, close).forEach(seq => {
        results.push('(' + seq);
      });
    }
    
    if (close < open) {
      backtrack(open, close + 1).forEach(seq => {
        results.push(')' + seq);
      });
    }

    memo.set(key, results);
    return results;
  }

  return backtrack(0, 0);
}

边界情况与问题处理

输入验证逻辑：

function safeGenerate(n) {
  if (typeof n !== 'number' || n < 0 || !Number.isInteger(n)) {
    throw new Error('输入必须是正整数');
  }
  if (n > 12) console.warn('n>12可能导致性能问题'); 
  return generateParenthesis(n);
}

空结果处理：

// 当n=0时应返回空数组还是包含空字符串？
// 根据实际需求决定：
function generateParenthesis(n) {
  if (n === 0) return []; // 或 return [''];
  // ...
}

扩展应用场景

CSS嵌套生成器：

function generateCSSNesting(depth) {
  return generateParenthesis(depth).map(seq => {
    return seq.split('').map(char => 
      char === '(' ? '.container' : '}'
    ).join('\n');
  });
}

// 输出：
// .container {
//   .container {
//   }
// }

代码缩进验证工具：

function validateCodeStructure(code) {
  const stack = [];
  for (const char of code) {
    if (char === '(') stack.push(char);
    if (char === ')') {
      if (stack.pop() !== '(') return false;
    }
  }
  return stack.length === 0;
}

前端框架中的实际应用：React Hooks依赖链

当需要动态生成Hook的执行顺序时：

function useNestedHooks(depth) {
  const hooks = generateParenthesis(depth);
  return hooks.map(pattern => {
    const hooksChain = [];
    pattern.split('').forEach(char => {
      if (char === '(') hooksChain.push(useState);
      // 模拟Hook执行顺序
    });
    return hooksChain;
  });
}

小结

关键：理解有效括号字符串在任何子串中开括号数量不少于闭括号的性质
方法选择指南：
- 需要所有组合 → 回溯法
- 需要数学推导 → 动态规划
- 内存敏感 → 迭代法

性能优化：

// 提前终止无效分支
function backtrack(str, open, close) {
  if (close > open) return; // 关键剪枝！
  // ...
}

前端适用技巧：

// 流式处理大n值的情况
function* generateLazy(n) {
  function* backtrack(...) { ... yield str; }
  yield* backtrack('', 0, 0);
}

掌握括号生成算法，能在开发动态布局、代码解析器等场景中提供高效解决方案。在保证有效性的前提下逐步构建，及时剪枝避免无效路径。

requestIdleCallback：让你的网页如丝般顺滑

掘金前端

前端微白

2025年7月18日 23:37

为什么我们需要 requestIdleCallback？在传统的前端开发中，当我们执行耗时任务时，很容易阻塞主线程，导致页面卡死甚至用户交互延迟：这种同步执行的后果：用户操作无响应：按钮点击、输

链表合并：双指针与递归

掘金前端

前端微白

2025年7月18日 23:22

作为前端工程师，链表操作看似与日常开发无关，实则隐藏在虚拟DOM对比、状态管理库等底层逻辑中。有序链表的合并正是理解这些关键机制的绝佳入口。本文将从真实场景出发，解析两种主流解法及其性能差异。用户行

阅读视图

复杂度分析

分类题单

问题定义：寻找有效括号组合

解法一：回溯法（深度优先搜索）

解法二：动态规划 - 优雅的递推解法

两种方法对比：选择最优方案

实际项目应用：React状态管理优化

高级技巧：使用剪枝优化性能

边界情况与问题处理

扩展应用场景

前端框架中的实际应用：React Hooks依赖链

小结