普通视图

发现新文章,点击刷新页面。
昨天以前首页

基于 Node.js 的短视频制作神器 ——FFCreator

作者 一支鱼
2025年9月7日 22:38

在当今短视频盛行的时代,快速高效地制作短视频成为了很多开发者和内容创作者的需求。FFCreator 就是一款基于 Node.js 的强大短视频制作工具库,它能帮助我们轻松实现短视频的制作与编辑。

一、FFCreator 简介

FFCreator 是一个轻量级、灵活的基于 Node.js 的短视频制作库。它将复杂的视频处理操作封装成简单易用的 API,让开发者只需添加一些图片、音乐或视频片段,就可以快速创建出令人兴奋的视频作品。

二、安装与配置

1.安装前提

  • 确保已经安装 Node.js,推荐版本 >= 14。

  • 安装 FFmpeg。对于不同系统,安装方式如下:

    • Windows:从 FFmpeg 官网下载对应版本,解压后将其 bin 目录添加到系统环境变量%PATH%中。
    • Mac OS:可以使用 Homebrew 安装,执行brew install ffmpeg
    • Linux:如 CentOS、Debian 等,可以通过相关社区文档进行安装部署。

2.安装 FFCreator

  • 通过 npm 安装:npm install ffcreator
  • 也可通过 yarn 安装:yarn add ffcreator

3.配置

在使用 FFCreator 时,可能需要根据需求进行一些配置。例如:

const { FFCreator } = require("ffcreator");

// 初始化FFCreator实例
const creator = new FFCreator({
    width: 1280, // 视频宽度
    height: 720, // 视频高度
    fps: 30, // 帧率
    render: "gl", // 渲染方式
    outputDir: "./videos" // 输出目录
});

三、功能特点

1.丰富的元素支持

  • 图片元素(FFImage) :可加载图片并进行位置、缩放、旋转、透明度等设置。
  • 视频元素(FFVideo) :支持加载视频片段,设置是否有音频、是否循环播放,还能截取特定时长。
  • 文本元素(FFText) :可以创建文本,设置文本内容、颜色、背景色、对齐方式、样式等,并且能添加动画效果。
  • 音频元素:能添加全局背景音乐,也可为每个场景单独设置声音或配乐。
  • 其他元素:还支持相册元素(FFAlbum)、虚拟主播元素(FFVtuber)等。

2.多样的动画与过渡效果

  • 场景过渡动画:内置近百种场景过渡动画效果,如fade(淡入淡出)等。
  • 元素动画效果:兼容animate.css的大部分动画效果,如fadeIn(淡入)、slideInDown(下滑进入)等,可方便地为元素添加各种动画。

3.其他功能

  • 字幕组件:支持添加字幕组件,可与语音 TTS 结合合成音频新闻。
  • 图表组件:能够将图表、统计信息等转换为动态视频,方便进行数据可视化展示。

四、使用示例

基本使用流程

const { FFCreator, FFVideo, FFImage, FFText } = require("ffcreator");
const fs = require("fs");

// 初始化FFCreator实例
const creator = new FFCreator({
    width: 1280,
    height: 720,
    fps: 30,
    render: "gl",
    outputDir: "./videos"
});

// 加载背景音乐
const audioPath = "/path/to/your/audio.mp3";
creator.addAudio({ path: audioPath });

// 创建场景并加载图像
const imagePaths = ["./images/image1.jpg", "./images/image2.jpg"];
imagePaths.forEach((imagePath) => {
    const scene = new FFCreator.FFScene();
    const image = new FFImage({ path: imagePath });
    scene.addChild(image);
    // 设置过渡动画
    scene.setTransition({ type: "fade", duration: 2000 });
    // 将场景添加至FFCreator实例
    creator.addScene(scene);
});

// 创建文本场景
const textScene = new FFCreator.FFScene();
const text = new FFText({ text: '这是一个文字', x: 250, y: 80 });
text.setColor('#ffffff');
text.setBackgroundColor('#b33771');
text.addEffect("fadeIn", 1, 1);
text.alignCenter();
textScene.addChild(text);
creator.addScene(textScene);

// 输出设置
const outputPath = "./videos/output.mp4";
creator.output(outputPath)
    .then(() => {
        console.log("视频生成成功!");
    })
    .catch((error) => {
        console.log("视频生成失败", error);
    });

五、拓展应用

1.与前端框架结合

可以与 Vue.js、React 等前端框架结合,开发出可视化的视频制作工具,通过拖拽、选择等操作来制作短视频。比如在 Vue 项目中,利用 FFCreator 实现一个简单的视频制作页面,用户可以在页面上上传图片、视频、音频等素材,设置各种参数,然后调用 FFCreator 的 API 进行视频生成。

以下是一个在 Vue3 项目中利用 FFCreator 实现简单视频制作页面的示例:

1. 创建 Vue 3 项目并安装依赖

确保已安装 Node.js 和 npm,然后使用 Vue CLI 创建项目:

npm install -g @vue/cli
vue create ffcreator - vue3 - video - maker
cd ffcreator - vue3 - video - maker
npm install ffcreator

2. 编写模板(App.vue

<template>
  <div id="app">
    <h1>视频制作工具</h1>
    <div>
      <input type="file" @change="handleFileUpload('image')" accept="image/*" multiple>
      <input type="file" @change="handleFileUpload('video')" accept="video/*" multiple>
      <input type="file" @change="handleFileUpload('audio')" accept="audio/*">
    </div>
    <div>
      <label for="width">视频宽度:</label>
      <input type="number" v - model="width" id="width">
    </div>
    <div>
      <label for="height">视频高度:</label>
      <input type="number" v - model="height" id="height">
    </div>
    <div>
      <label for="fps">帧率:</label>
      <input type="number" v - model="fps" id="fps">
    </div>
    <button @click="generateVideo">生成视频</button>
    <div v - if="loading">视频生成中...</div>
    <div v - if="error">{{ error }}</div>
  </div>
</template>

3. 编写逻辑(App.vue<script setup>部分)

<script setup>
import { ref } from 'vue';
import { FFCreator, FFScene, FFImage, FFVideo } from 'ffcreator';
import fs from 'fs';
import path from 'path';

const width = ref(1280);
const height = ref(720);
const fps = ref(30);
const loading = ref(false);
const error = ref('');
const images = ref<string[]>([]);
const videos = ref<string[]>([]);
const audio = ref<string | null>(null);

const handleFileUpload = (type: string) => (e: Event) => {
  const target = e.target as HTMLInputElement;
  const files = target.files;
  if (files) {
    if (type === 'image') {
      images.value = Array.from(files).map(file => URL.createObjectURL(file));
    } else if (type === 'video') {
      videos.value = Array.from(files).map(file => URL.createObjectURL(file));
    } else if (type === 'audio') {
      audio.value = files.length > 0? URL.createObjectURL(files[0]) : null;
    }
  }
};

const generateVideo = async () => {
  loading.value = true;
  error.value = '';
  try {
    const creator = new FFCreator({
      width: width.value,
      height: height.value,
      fps: fps.value,
      render: 'gl',
      outputDir: './output'
    });

    if (audio.value) {
      creator.addAudio({ path: audio.value });
    }

    images.value.forEach((imagePath) => {
      const scene = new FFScene();
      const image = new FFImage({ path: imagePath });
      scene.addChild(image);
      creator.addScene(scene);
    });

    videos.value.forEach((videoPath) => {
      const scene = new FFScene();
      const video = new FFVideo({ path: videoPath });
      scene.addChild(video);
      creator.addScene(scene);
    });

    const outputPath = path.join('./output', 'generated - video.mp4');
    await creator.output(outputPath);
    console.log('视频生成成功');
  } catch (err: any) {
    error.value = `视频生成失败: ${err.message}`;
    console.error(err);
  } finally {
    loading.value = false;
  }
};
</script>

4. 样式(App.vue

<style scoped>
#app {
  font - family: Avenir, Helvetica, Arial, sans - serif;
  -webkit - font - smoothing: antialiased;
  -moz - osx - font - smoothing: grayscale;
  text - align: center;
  color: #2c3e50;
  margin - top: 60px;
}
</style>

5.注意事项

  1. 文件 URL 管理URL.createObjectURL生成的 URL 需要在适当的时候释放,例如在组件卸载时,可以使用beforeUnmount钩子函数来 revoke 这些 URL。
  2. 错误处理:当前的错误处理只是简单地记录和显示错误信息,可以根据实际需求进行更详细的错误处理,如针对不同类型的 FFCreator 错误进行不同提示。
  3. FFCreator 功能扩展:FFCreator 提供了丰富的功能,如场景过渡、元素动画等,可以进一步扩展此项目,为用户提供更多的视频编辑选项。
  4. 文件存储与安全性:在实际应用中,建议将上传的文件存储到服务器上,并进行必要的安全性检查,以防止恶意文件上传。

2.批量视频生成

在一些内容创作平台或营销场景中,可能需要批量生成大量短视频。可以利用 FFCreator 结合数据库或文件系统,读取大量的素材数据和配置信息,循环调用 FFCreator 的 API 来批量生成视频,提高工作效率。

以下是一个利用 FFCreator 结合文件系统,根据配置信息批量生成视频的示例:

假设配置信息存储在一个 JSON 文件中,素材文件(图片、视频、音频)存储在特定目录下。

1.示例代码

const FFCreator = require('ffcreator');
const fs = require('fs');
const path = require('path');

// 读取配置文件
const configPath = path.join(__dirname, 'config.json');
const config = JSON.parse(fs.readFileSync(configPath, 'utf8'));

// 批量生成视频
config.forEach(async (videoConfig) => {
    const { width, height, fps, outputPath, scenes } = videoConfig;
    const creator = new FFCreator({
        width,
        height,
        fps,
        render: 'gl',
        outputDir: path.dirname(outputPath)
    });

    // 添加音频(如果有)
    if (videoConfig.audio) {
        const audioPath = path.join(__dirname, 'audio', videoConfig.audio);
        creator.addAudio({ path: audioPath });
    }

    // 添加场景
    scenes.forEach((scene) => {
        const ffScene = new FFCreator.FFScene();
        scene.elements.forEach((element) => {
            if (element.type === 'image') {
                const imagePath = path.join(__dirname, 'images', element.path);
                const img = new FFCreator.FFImage({ path: imagePath });
                // 设置元素的属性,如位置、缩放等
                if (element.x) img.setX(element.x);
                if (element.y) img.setY(element.y);
                if (element.scale) img.setScale(element.scale);
                ffScene.addChild(img);
            } else if (element.type === 'video') {
                const videoPath = path.join(__dirname, 'videos', element.path);
                const vid = new FFCreator.FFVideo({ path: videoPath });
                // 设置视频元素的属性,如开始时间、时长等
                if (element.startTime) vid.setStartTime(element.startTime);
                if (element.duration) vid.setDuration(element.duration);
                ffScene.addChild(vid);
            } else if (element.type === 'text') {
                const text = new FFCreator.FFText({ text: element.content });
                // 设置文本元素的属性,如颜色、位置等
                if (element.color) text.setColor(element.color);
                if (element.x) text.setX(element.x);
                if (element.y) text.setY(element.y);
                ffScene.addChild(text);
            }
        });
        // 设置场景过渡
        if (scene.transition) {
            ffScene.setTransition(scene.transition);
        }
        creator.addScene(ffScene);
    });

    try {
        await creator.output(outputPath);
        console.log(`视频 ${outputPath} 生成成功`);
    } catch (error) {
        console.error(`视频 ${outputPath} 生成失败:`, error);
    }
});

2.配置文件示例 (config.json)

[
    {
        "width": 1280,
        "height": 720,
        "fps": 30,
        "outputPath": "output/vid1.mp4",
        "audio": "audio1.mp3",
        "scenes": [
            {
                "transition": {
                    "type": "fade",
                    "duration": 2000
                },
                "elements": [
                    {
                        "type": "image",
                        "path": "image1.jpg",
                        "x": 100,
                        "y": 100,
                        "scale": 0.8
                    }
                ]
            },
            {
                "elements": [
                    {
                        "type": "video",
                        "path": "video1.mp4",
                        "startTime": 0,
                        "duration": 5
                    }
                ]
            },
            {
                "elements": [
                    {
                        "type": "text",
                        "content": "这是一段文字",
                        "color": "#ffffff",
                        "x": 500,
                        "y": 300
                    }
                ]
            }
        ]
    },
    {
        "width": 1920,
        "height": 1080,
        "fps": 25,
        "outputPath": "output/vid2.mp4",
        "scenes": [
            {
                "elements": [
                    {
                        "type": "image",
                        "path": "image2.jpg"
                    }
                ]
            }
        ]
    }
]

3.说明

  1. 配置文件config.json文件定义了每个视频的参数,包括视频尺寸、帧率、输出路径、音频文件以及每个场景的元素和过渡效果。
  2. 文件路径:代码假设素材文件(图片、视频、音频)分别存储在imagesvideosaudio目录下,根据实际情况调整路径。
  3. FFCreator 配置:根据配置信息初始化 FFCreator 实例,并添加音频、场景和元素。每个元素的属性根据配置进行设置。
  4. 错误处理:在生成视频时捕获错误,并打印错误信息,以便调试。

3.与其他工具集成

可以与图像编辑工具、音频处理工具等其他相关工具集成。例如,在生成视频前,先使用图像编辑工具对图片进行预处理,或者使用音频处理工具对音频进行混音、降噪等操作,然后再将处理后的素材交给 FFCreator 进行视频制作,以实现更复杂、更专业的视频制作需求。

leetcode常用解题方案总结

作者 一支鱼
2025年9月6日 22:17

1.数组与字符串

1. 双指针法

1.思路

  • 通过两个指针在数组或字符串上按照特定规则移动,解决诸如查找、匹配、计算等问题。指针的移动方向和条件取决于具体问题,可相向、同向移动等。

2.经典案例

LeetCode 11. 盛最多水的容器

  • 在表示竖线高度的数组上,双指针分别指向数组两端,根据指针所指高度调整指针位置,计算并更新容器最大水量。

LeetCode 167. 两数之和 II - 输入有序数组

  • 在有序数组中,利用双指针从两端开始移动,根据两指针所指元素和与目标值的关系,找到和为目标值的两个数。

2.滑动窗口法

1.思路

  • 在字符串或数组上维护一个窗口,通过移动窗口的起始和结束位置,动态调整窗口内元素,以满足特定条件,如寻找特定子串、子数组等。窗口大小可固定或动态变化。

2.经典案例

LeetCode 3. 无重复字符的最长子串

  • 在字符串上通过滑动窗口,确保窗口内无重复字符,从而找到最长无重复子串。

LeetCode 76. 最小覆盖子串

  • 在字符串 s 上利用滑动窗口,先扩大窗口使其包含字符串 t 的所有字符,再缩小窗口找到覆盖 t 的最小子串。

3.前缀和法

1.思路

  • 对数组进行预处理,生成一个前缀和数组,其中每个元素表示原数组从起始位置到该位置的元素之和。利用前缀和数组可以高效解决子数组求和、特定和的子数组计数等问题。

2.经典案例

LeetCode 303. 区域和检索 - 数组不可变

  • 通过前缀和数组快速计算给定区间内的元素之和。

LeetCode 560. 和为 K 的子数组

  • 借助前缀和数组,统计和为 K 的子数组的个数。

2.链表

1.双指针法(链表场景)

1.思路

  • 在链表上使用两个指针,根据问题需求同步或异步移动指针,用于检测链表特性(如环)、查找特定节点等。

2.经典案例

  • 在判断链表是否有环的问题中(类似 LeetCode 141. 环形链表),快慢指针同时移动,快指针每次移动两步,若快慢指针相遇则存在环。

3.树

1.深度优先搜索(DFS) - 递归实现

1.思路

  • 沿着树的深度优先探索节点,先访问根节点,然后递归地访问左子树和右子树(对于二叉树)。可用于遍历树、计算节点值、查找特定节点等。

2.经典案例

  • 在二叉树的前序遍历(LeetCode 144. 二叉树的前序遍历)中,先访问根节点,再递归前序遍历左子树,最后递归前序遍历右子树。

2.广度优先搜索(BFS) - 队列实现

1.思路

  • 按树的层次逐层访问节点,使用队列辅助实现。先将根节点入队,每次从队列取出一个节点,访问它并将其孩子节点入队,直到队列为空。常用于按层遍历树、解决与层次相关的问题。

2.经典案例

  • 在二叉树的层序遍历(LeetCode 102. 二叉树的层序遍历)中,通过队列实现按层访问二叉树的所有节点。

4.栈

1.单调栈法

1.思路

  • 利用栈维护一个单调递增或递减的序列,通过入栈和出栈操作,解决寻找下一个更大元素、下一个更小元素等问题。

2.经典案例

LeetCode 496. 下一个更大元素 I

  • 遍历数组,利用单调栈记录每个元素的下一个更大元素。

LeetCode 84. 柱状图中最大的矩形

  • 通过单调栈维护柱子高度,计算柱状图中最大矩形面积。

5.堆

1.堆(优先队列)法

1.思路

  • 利用堆的特性维护数据的优先级,通过插入和删除操作,解决前 K 个最大或最小元素、中位数等问题。

2.经典案例

LeetCode 215. 数组中的第 K 个最大元素

  • 使用最小堆获取数组中第 K 个最大元素。

LeetCode 347. 前 K 个高频元素

  • 结合哈希表统计频率,利用优先队列(最大堆)获取前 K 个高频元素。

6.通用的算法策略

1.二分查找法

适用场景

  • 主要用于有序数组或可转化为有序结构的场景。

算法思路

  • 每次将搜索区间缩小一半,通过比较中间元素与目标值的大小关系,决定在左半部分还是右半部分继续搜索,从而快速定位目标元素或满足特定条件的位置。

经典案例

LeetCode 704. 二分查找

  • 在有序数组中查找目标值,每次比较中间元素与目标值,缩小搜索范围,直到找到目标值或确定目标值不存在。

LeetCode 33. 搜索旋转排序数组

  • 对于旋转排序数组,通过判断中间元素与两端元素的关系,确定有序部分,然后在有序部分进行二分查找。

2.动态规划法

适用场景

  • 适用于具有最优子结构和子问题重叠性质的问题,可用于数组、字符串、图等多种数据结构相关问题。

算法思路

  • 将复杂问题分解为相互关联的子问题,通过定义状态和状态转移方程,求解子问题并保存其解,避免重复计算,最终得到原问题的解。

经典案例

LeetCode 5. 最长回文子串

  • 定义二维状态 dp [i][j] 表示字符串 s 从 i 到 j 是否为回文串,通过状态转移方程和边界条件计算最长回文子串。

LeetCode 70. 爬楼梯

  • 定义状态 dp [i] 表示爬到第 i 阶楼梯的方法数,依据状态转移方程和边界条件计算爬到楼顶的方法总数。

3.回溯法

适用场景

  • 常用于解决组合、排列、路径搜索等问题,涉及对所有可能情况进行深度优先搜索。

算法思路

  • 从初始状态开始,逐步探索所有可能路径。若当前路径不符合要求,则回溯到上一个状态,尝试其他路径,直到找到所有解或满足条件的解。

经典案例

LeetCode 46. 全排列

  • 从空排列开始,通过回溯依次添加未使用数字,生成所有全排列。

LeetCode 93. 复原 IP 地址

  • 通过在字符串中回溯插入点,将字符串分成 4 段,判断每段合法性,得到所有有效 IP 地址。

4.贪心算法

适用场景

  • 适用于具有贪心选择性质的问题,即局部最优选择能导致全局最优解,常见于资源分配、调度等问题。

算法思路

  • 在每一步决策中,选择当前状态下的最优解,不考虑整体最优解,期望通过一系列局部最优选择达到全局最优。

经典案例

LeetCode 455. 分发饼干

  • 对孩子胃口值和饼干尺寸排序后,从胃口最小孩子和尺寸最小饼干开始匹配,每次选择能满足当前孩子的最小饼干。

LeetCode 122. 买卖股票的最佳时机 II

  • 每天判断当前价格与前一天价格,若当前价格高则进行买卖操作累加利润。

5.分治法

适用场景

  • 适用于可以分解为若干个规模较小、相互独立且与原问题形式相同的子问题的场景,如树的相关问题、数组划分问题等。

算法思路

  • 将问题分解为子问题,递归地解决子问题,然后合并子问题的解得到原问题的解。

经典案例

LeetCode 241. 为运算表达式设计优先级

  • 按运算符分割表达式为左右两部分,递归计算左右部分结果,再根据运算符组合结果。

LeetCode 53. 最大子数组和

  • 将数组分成左右两部分,分别计算左右部分最大子数组和以及跨越中点的最大子数组和,取三者最大值。

leetcode-6-正则表达式匹配

作者 一支鱼
2025年9月5日 21:37

正则表达式匹配

1.题目描述

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。

示例 1:

输入: s = "aa", p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: s = "aa", p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入: s = "ab", p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

提示:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母,以及字符 . 和 *
  • 保证每次出现字符 * 时,前面都匹配到有效的字符

2.解决方案

1.暴力递归解法

  1. 思路
  • 从字符串 s 和模式 p 的开头开始匹配。

  • 对于模式 p 中的每个字符,分情况讨论:

    • 如果 p 的当前字符不是 '*',那么 s 和 p 当前字符必须匹配(s 当前字符存在且与 p 当前字符相等或者 p 当前字符为 '.'),然后继续匹配下一个字符。

    • 如果 p 的当前字符是 '*',则有两种情况:

      • '*' 前面的字符匹配 0 次,此时跳过 p 中 '*' 及其前面的字符,继续匹配 p 的下一个字符。
      • '*' 前面的字符匹配至少 1 次,前提是 s 当前字符与 '*' 前面的字符匹配(s 当前字符存在且与 '*' 前面的字符相等或者 '*' 前面的字符为 '.'),然后 s 指针后移一位,继续尝试匹配。
    • 当 s 和 p 都匹配完时,返回 true;否则,返回 false

  1. 代码实现
function isMatch(s: string, p: string): boolean {
    if (!p) return!s;
    let firstMatch = s && (s[0] === p[0] || p[0] === '.');
    if (p.length >= 2 && p[1] === '*') {
        return isMatch(s, p.slice(2)) || (firstMatch && isMatch(s.slice(1), p));
    } else {
        return firstMatch && isMatch(s.slice(1), p.slice(1));
    }
}
  1. 分析
  • 时间复杂度:在最坏情况下,时间复杂度为指数级 (O(2^{m + n})),其中 m 和 n 分别是 s 和 p 的长度。因为对于每个字符,都可能有两种决策('*' 的两种情况)。
  • 空间复杂度:(O(m + n)),这是由于递归调用栈的深度最大为 m + n
  1. 缺点
  • 时间复杂度高,对于较长的字符串和模式,效率极低,容易超时。

2.动态规划解法

  1. 思路
  • 使用一个二维数组 dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。

  • 初始化 dp[0][0] = true,表示两个空字符串是匹配的。

  • 对于 dp[i][j] 的计算:

  • 如果 p[j - 1] 不是 '*',那么 dp[i][j] 为 true 当且仅当 dp[i - 1][j - 1] 为 true 且 s[i - 1] 与 p[j - 1] 匹配(s[i - 1] 存在且与 p[j - 1] 相等或者 p[j - 1] 为 '.')。

    • 如果 p[j - 1] 是 '*',则有两种情况:

      • '*' 前面的字符匹配 0 次,此时 dp[i][j] = dp[i][j - 2]
      • '*' 前面的字符匹配至少 1 次,前提是 s[i - 1] 与 p[j - 2] 匹配(s[i - 1] 存在且与 p[j - 2] 相等或者 p[j - 2] 为 '.'),此时 dp[i][j] = dp[i - 1][j]
  1. 代码实现
function isMatch(s: string, p: string): boolean {
    const m = s.length;
    const n = p.length;
    const dp: boolean[][] = new Array(m + 1).fill(false).map(() => new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2];
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    return dp[m][n];
}
  1. 分析
  • 时间复杂度:(O(m * n)),其中 m 和 n 分别是 s 和 p 的长度。需要填充整个 dp 数组。
  • 空间复杂度:(O(m * n)),用于存储 dp 数组。可以通过滚动数组优化到 (O(n)),因为 dp[i][j] 只依赖于 dp[i - 1][j] 和 dp[i][j - 1] 以及 dp[i - 1][j - 1]
  1. 优点
  • 相比暴力递归,时间复杂度大大降低,对于较长的字符串和模式,效率更高。

3.最优解及原因

  1. 最优解
  • 动态规划解法是最优解。
  1. 原因
  • 动态规划解法通过避免重复计算子问题,将时间复杂度从暴力递归的指数级 (O(2^{m + n})) 降低到 (O(m * n))。虽然空间复杂度也为 (O(m * n)),但在实际应用中,其效率的提升更为显著。滚动数组优化后的空间复杂度可进一步降低到 (O(n)),使得在处理长字符串时更具优势。

leetcode-5-最长回文子串

作者 一支鱼
2025年9月4日 21:50

最长回文子串

1.题目描述

给你一个字符串 s,找到 s 中最长的 回文 子串。

示例 1:

输入: s = "babad"
输出: "bab"
解释: "aba" 同样是符合题意的答案。

示例 2:

输入: s = "cbbd"
输出: "bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

2.解决方案

1.暴力解法

  1. 思路
  • 枚举字符串 s 的所有子串,对于每个子串,检查它是否是回文串。
  • 从长度为 1 的子串开始,逐渐增加子串长度,记录下最长的回文子串。
  1. 代码实现
function longestPalindromeBruteForce(s: string): string {
    let maxLength = 0;
    let result = '';
    const n = s.length;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            let isPalindrome = true;
            for (let k = 0; k < (j - i + 1) / 2; k++) {
                if (s[i + k]!== s[j - k]) {
                    isPalindrome = false;
                    break;
                }
            }
            if (isPalindrome && (j - i + 1) > maxLength) {
                maxLength = j - i + 1;
                result = s.slice(i, j + 1);
            }
        }
    }
    return result;
}
  1. 分析
  • 时间复杂度:(O(n^3))。外层循环遍历子串的起始位置 i,时间复杂度为 (O(n));中层循环遍历子串的结束位置 j,时间复杂度为 (O(n));内层循环检查子串是否为回文,时间复杂度为 (O(n))。所以总的时间复杂度为 (O(n \times n \times n))。
  • 空间复杂度:(O(1)),除了存储结果的字符串外,只使用了常数级别的额外空间。
  1. 缺点:时间复杂度极高,对于较长的字符串,运行效率极低,会导致超时。

2.中心扩展算法

  1. 思路
  • 回文串的特点是关于中心对称,所以可以以每个字符和相邻字符间隙为中心,向两边扩展,检查扩展出的子串是否为回文。
  • 对于长度为 n 的字符串,有 2n - 1 个可能的中心(n 个字符作为单字符中心,n - 1 个相邻字符间隙作为双字符中心)。
  1. 代码实现
function longestPalindrome(s: string): string {
    let start = 0;
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        // 以单个字符为中心扩展
        let left1 = i;
        let right1 = i;
        while (left1 >= 0 && right1 < n && s[left1] === s[right1]) {
            if (right1 - left1 + 1 > maxLength) {
                maxLength = right1 - left1 + 1;
                start = left1;
            }
            left1--;
            right1++;
        }
        // 以两个相邻字符为中心扩展
        let left2 = i;
        let right2 = i + 1;
        while (left2 >= 0 && right2 < n && s[left2] === s[right2]) {
            if (right2 - left2 + 1 > maxLength) {
                maxLength = right2 - left2 + 1;
                start = left2;
            }
            left2--;
            right2++;
        }
    }
    return s.slice(start, start + maxLength);
}
  1. 分析
  • 时间复杂度:(O(n^2))。对于每个可能的中心,最多需要扩展 n 次,而总共有 2n - 1 个中心,所以时间复杂度为 (O(n \times n))。
  • 空间复杂度:(O(1)),只使用了常数级别的额外空间。
  1. 优点:相比暴力解法,时间复杂度有所降低,在实际应用中效率更高。

3.Manacher 算法

  1. 思路
  • Manacher 算法通过对字符串进行预处理,将奇数长度和偶数长度的回文串统一处理。
  • 它利用已经计算出的回文子串信息,避免了重复计算,从而将时间复杂度优化到 (O(n))。
  • 具体来说,算法使用一个数组 p 记录以每个字符为中心的回文半径,通过巧妙的计算和更新,快速找到最长回文子串。
  1. 代码实现
function longestPalindromeManacher(s: string): string {
    // 预处理字符串
    const newS = '#';
    for (const char of s) {
        newS += char + '#';
    }
    const n = newS.length;
    const p: number[] = new Array(n).fill(0);
    let center = 0;
    let right = 0;
    for (let i = 0; i < n; i++) {
        let iMirror = 2 * center - i;
        if (right > i) {
            p[i] = Math.min(right - i, p[iMirror]);
        } else {
            p[i] = 0;
        }
        // 尝试扩展
        while (i + (1 + p[i]) < n && i - (1 + p[i]) >= 0 && newS[i + (1 + p[i])] === newS[i - (1 + p[i])]) {
            p[i]++;
        }
        // 更新中心和右边界
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    let maxLen = 0;
    let maxCenter = 0;
    for (let i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenter = i;
        }
    }
    const start = (maxCenter - maxLen) / 2;
    return s.slice(start, start + maxLen);
}
  1. 分析
  • 时间复杂度:(O(n))。虽然代码中有多层循环,但由于巧妙地利用了已有的回文信息,每个字符最多被访问常数次,所以时间复杂度为 (O(n))。
  • 空间复杂度:(O(n)),需要一个数组 p 来记录回文半径。
  1. 优点:时间复杂度最优,在处理非常长的字符串时,性能远远优于暴力解法和中心扩展算法。

4.最优解及原因

  1. 最优解:Manacher 算法是最优解。
  2. 原因:当字符串长度较大时,时间复杂度是衡量算法优劣的关键指标。Manacher 算法将时间复杂度优化到了线性的 (O(n)),相比暴力解法的 (O(n^3)) 和中心扩展算法的 (O(n^2)),在处理大规模数据时效率有显著提升。虽然它需要 (O(n)) 的额外空间,但对于追求高效的场景,这种以空间换时间的方式是值得的。

3.拓展和题目变形

拓展

  • 找到所有最长回文子串。

思路

  • 在 Manacher 算法的基础上,记录所有达到最大回文半径的中心位置,然后根据这些位置还原出所有最长回文子串。

代码实现

function findAllLongestPalindromes(s: string): string[] {
    const newS = '#';
    for (const char of s) {
        newS += char + '#';
    }
    const n = newS.length;
    const p: number[] = new Array(n).fill(0);
    let center = 0;
    let right = 0;
    for (let i = 0; i < n; i++) {
        let iMirror = 2 * center - i;
        if (right > i) {
            p[i] = Math.min(right - i, p[iMirror]);
        } else {
            p[i] = 0;
        }
        while (i + (1 + p[i]) < n && i - (1 + p[i]) >= 0 && newS[i + (1 + p[i])] === newS[i - (1 + p[i])]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    let maxLen = 0;
    const maxCenters: number[] = [];
    for (let i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenters.length = 0;
            maxCenters.push(i);
        } else if (p[i] === maxLen) {
            maxCenters.push(i);
        }
    }
    const results: string[] = [];
    for (const maxCenter of maxCenters) {
        const start = (maxCenter - maxLen) / 2;
        results.push(s.slice(start, start + maxLen));
    }
    return results;
}

题目变形

  • 给定一个字符串 s 和一个整数 k,找到长度至少为 k 的最长回文子串。

思路

  • 可以在中心扩展算法或 Manacher 算法的基础上进行修改。在扩展或计算回文半径时,当找到的回文子串长度达到或超过 k 时,记录下来并继续寻找更长的满足条件的回文子串。

代码实现(基于中心扩展算法)

function longestPalindromeWithMinLength(s: string, k: number): string {
    let start = 0;
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        let left1 = i;
        let right1 = i;
        while (left1 >= 0 && right1 < n && s[left1] === s[right1]) {
            if (right1 - left1 + 1 >= k && right1 - left1 + 1 > maxLength) {
                maxLength = right1 - left1 + 1;
                start = left1;
            }
            left1--;
            right1++;
        }
        let left2 = i;
        let right2 = i + 1;
        while (left2 >= 0 && right2 < n && s[left2] === s[right2]) {
            if (right2 - left2 + 1 >= k && right2 - left2 + 1 > maxLength) {
                maxLength = right2 - left2 + 1;
                start = left2;
            }
            left2--;
            right2++;
        }
    }
    return maxLength >= k? s.slice(start, start + maxLength) : '';
}
❌
❌