📝算法解释

表达式问题

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

241. 为运算表达式设计优先级 - 力扣（LeetCode）

241. 为运算表达式设计优先级 - 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。   示例 1： 输入：expression = "2-1-1" 输出：[0,2] 解释： ((2-1)-1) = 0 (2-(1-1)) = 2 示例 2： 输入：expression = "2*3-4*5" 输出：[-34,-14,-10,-10,10] 解释： (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10   提示： * 1 <= expression.length <= 20 * expression 由数字和算符 '+'、'-' 和 '*' 组成。 * 输入表达式中的所有整数值在范围 [0, 99]  * 输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。

https://leetcode.cn/problems/different-ways-to-add-parentheses/

题目描述

输入输出样例

题解

为什么用分治法（Divide and Conquer）？

• 问题本质：表达式是一个“序列”，括号分组相当于在不同操作符处“分割”表达式为左右子表达式，然后递归求解子表达式的所有可能值，最后根据分割处的操作符“合并”（combine）左右结果。

• 分治核心：
• Divide（分解）：在每个操作符处将表达式分成左子表达式和右子表达式。
• Conquer（求解）：递归计算左/右子表达式的所有可能值。
• Combine（合并）：根据操作符（+、-、*），对左右所有值对进行运算，生成新结果。

• 优势：
• 避免枚举所有括号位置（指数爆炸），而是用操作符作为自然分割点（操作符数量 ≤19，n≤20）。
• 时间复杂度：O(4^k * k^2)，k=操作符数（≤19），实际因缓存可控（≤10^4 结果）。
• 空间：O(k^2)（递归栈 + 缓存）。

• 基线条件：如果表达式是单个数字，直接返回 [其值]。

• 优化：用 memo（字典，key=子字符串）缓存结果，避免重复子问题（表达式可重叠）。

解题步骤（分治框架）

1. 预处理：定义一个辅助函数 compute(expression)，返回该子表达式的所有可能值列表。

2. 基线：如果 expression 是纯数字（无操作符），返回 [int(expression)]。

3. 分解与递归：
• 遍历字符串每个字符：
• 遇到操作符 op（如 '+'），则：
• 左子 = expression[0 : 当前索引]（递归 compute(左子) → left_res）。
• 右子 = expression[当前索引+1 : ]（递归 compute(右子) → right_res）。
• 合并：对每个 left ∈ left_res, right ∈ right_res：
• 如果 op=='+'：res.append(left + right)
• 如果 op=='-'：res.append(left - right)
• 如果 op=='*'：res.append(left * right)
• 用 memo[expression] = res 缓存，避免重复计算。

4. 返回：所有合并结果的列表（任意顺序）。

• 为什么遍历所有操作符？ 每个操作符代表一种可能的“主分割点”（相当于括号将左右分组），递归处理子部分的所有可能。

• 数字处理：输入无前导符号，数字≤99，用循环累积数字（e.g., "12" →12），但基线直接 int()。

代码运行示例（示例 1）

• compute("2-1-1")：
• i=1, c='-'：左="2" → [2]；右="1-1" → compute("1-1")：
• i=1, c='-'：左="1"→[1]；右="1"→[1] → 1-1=[0]
• 合并：2 - 0 = [2]
• i=3, c='-'：左="2-1" → compute("2-1")：
• i=1, c='-'：左="2"→[2]；右="1"→[1] → 2-1=[1]
• 右="1"→[1]；合并：1 - 1 = [0]

• res = [2, 0]（匹配输出）。

示例 2 简析："23-45"

• 分治会生成多个分割，如在第一个 ：左[2], 右"3-45"（递归多分支）→ 2*(3-(45))=2(-11)=-22? 等，实际计算出 -34 等。

• 重复 -10 来自不同分组如 (2*(3-4))5 和 2((3-4)*5)。

分治可视化（"2-1-1"）

注意事项

• 缓存关键：子表达式如 "1-1" 可能多次出现，无缓存 TLE。

• 结果重复：直接 append，允许（如 -10 两次）。

• 边界：n=1（如 "2"）→[2]；无操作符 OK。

• 扩展：若加 /，需处理除零，但题目无。

🤗练习

基础难度

932. 漂亮数组

932. 漂亮数组 - 力扣（LeetCode）

932. 漂亮数组 - 如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ： * nums 是由范围 [1, n] 的整数组成的一个排列。 * 对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。 给你整数 n ，返回长度为 n 的任一 漂亮数组 。本题保证对于给定的 n 至少存在一个有效答案。   示例 1 ： 输入：n = 4 输出：[2,1,4,3] 示例 2 ： 输入：n = 5 输出：[3,1,2,5,4]   提示： * 1 <= n <= 1000

https://leetcode.cn/problems/beautiful-array/description/

• 约束：1 ≤ n ≤ 1000，保证至少一个解存在。

• 输出：任意一个有效漂亮数组（不唯一）。

• 为什么难？ 直接枚举排列 O(n!) 太慢（n=1000 不可能）。需要数学构造。

解题思路（递归构造 + 奇偶分离）

• 核心观察：如果将数组分成奇数部分（左）和偶数部分（右），则：
• 同组内：递归构造子数组为漂亮数组，保证无三元组。
• 跨组：奇 + 奇 = 偶，偶 + 偶 = 偶，奇 + 偶 = 奇。
• 2 * 奇 = 偶（可能 = 奇 + 奇 或 偶 + 偶）。
• 2 * 偶 = 偶（可能 = 奇 + 奇 或 偶 + 偶）。
• 但如果 k 在左（奇），2k=偶，不能 = i(左奇)+j(右偶)=奇（矛盾）。
• 如果 k 在右（偶），2k=偶，不能 = i(左奇)+j(左奇)=偶？等下，需仔细。

• 实际证明：这种分离确保跨组无 2k=i+j，因为：
• i,j 都在左（奇）：k 必须在左（递归保证）。
• i,j 都在右（偶）：k 在右（递归）。
• i 左 j 右：i+j=奇，2k=偶（无论 k 奇偶），矛盾。
• i 右 j 左：同上。

• 构造规则：
• 对于 n=1：返回 [1]。
• 递归：left = 漂亮数组(ceil(n/2)) → 映射为奇数：每个 x → 2x - 1。
• right = 漂亮数组(floor(n/2)) → 映射为偶数：每个 x → 2x。
• 返回 left + right（奇在前，偶在后）。

• 为什么有效？ 映射保持相对顺序，且生成 [1..n] 唯一排列。递归深度 O(log n)，总时间 O(n log n)（但实际 O(n)，因每个层 O(n)）。

• 空间：O(log n) 递归栈。

代码运行示例

• 示例 1：n=4
• helper(4)：left=helper(3)，right=helper(2)
• helper(3)：left=helper(2)=[1,2]? 逐步：
• helper(2)：left=helper(1)=[1]，right=helper(1)=[1] → [21-1, 21] = [1,2]
• helper(3)：left=helper(2)=[1,2] → [1,3]；right=helper(1)=[1] → [2] → [1,3] + [2] = [1,3,2]
• helper(4)：left=helper(3)=[1,3,2] → [1,5,3] 但 n=4，22=4? 映射：[21-1=1, 2*3-1=5>4? 等下。
• 实际运行：[1, 3, 2, 4]
• 验证：排列 [1,2,3,4]，检查三元：无 i<k<j 2k=i+j（e.g., 2*3=6≠1+2=3 等）。
• 示例输出 [2,1,4,3] 也有效（本题任一）。

• 示例 2：n=5
• 运行：[1, 5, 3, 2, 4]
• 验证：奇[1,5,3] + 偶[2,4]，无三元组。
• 示例 [3,1,2,5,4] 类似。

构造过程可视化（n=4）

注意事项

• 唯一性：构造不唯一，但这个总是有效（数学证明：诱导法，基线 n=1 OK，假设子漂亮则整体 OK）。

• 效率：n=1000，递归快；可用迭代（从 1 建起），但递归简洁。

• 扩展：若需所有漂亮数组，需 DP，但本题只需一个。

进阶难度

312. 戳气球

312. 戳气球 - 力扣（LeetCode）

312. 戳气球 - 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。 求所能获得硬币的最大数量。   示例 1： 输入：nums = [3,1,5,8] 输出：167 解释： nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167 示例 2： 输入：nums = [1,5] 输出：10   提示： * n == nums.length * 1 <= n <= 300 * 0 <= nums[i] <= 100

https://leetcode.cn/problems/burst-balloons/description/

问题分析

• 挑战：戳破顺序影响硬币（因为相邻边界动态变化），暴力枚举顺序 O(n!) 太慢（n≤300 不可能）。

• 关键观察：这是一个“区间”问题——考虑在某个子区间内戳破所有气球，最后戳的那个气球会用区间的左右边界计算硬币。

• DP 状态定义：
• dp[i][j]：戳破气球 i 到 j（不包括 i 和 j）之间的所有气球，获得的最大硬币数。其中 nums[i] 和 nums[j] 作为固定边界（假设 i 和 j 不戳）。

• 为什么这样定义？ 边界固定，便于转移；实际戳的是 i+1 到 j-1。

• 预处理：为了边界统一，添加虚拟气球：nums = [1] + nums + [1]（原 nums 索引 0..n-1 → 新 1..n，虚拟 0 和 n+1 为 1）。
• 新 nums 长度 n+2，dp 是 (n+2) x (n+2) 矩阵。

• 基线：dp[i][i+1] = 0（区间内无气球戳）。

• 转移方程：
• 对于区间 [i, j]（j > i+1），枚举最后戳的 k（i < k < j）：
• dp[i][j] = max( dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j] )
• 解释：先戳 [i,k] 和 [k,j] 的所有（递归），最后戳 k（此时边界是 nums[i] 和 nums[j]，硬币 = nums[i]*nums[k]*nums[j]）。

• 答案：dp[0][n+1]（整个区间，边界 1）。

• 复杂度：
• 时间：O(n^3)，枚举区间 O(n^2)，内层 k 枚举 O(n)。
• 空间：O(n^2)，dp 表。
• n=300，27e6 操作，高效。

解题步骤（自底向上 DP）

1. 初始化：添加边界，创建 dp 零矩阵。

2. 填充 dp：从小区间到大区间（长度 len 从 2 到 n+1）：
• for i in 0 to (n+1 - len):
• j = i + len
• for k in i+1 to j-1:
• 更新 dp[i][j] = max(..., dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])

3. 返回 dp[0][n+1]。

代码实现（Python）

代码运行示例（示例 1）

• 新 nums = [1, 3, 1, 5, 8, 1]（索引 0..5）

• dp 初始化全 0。

• 小区间（len=2）：如 [0,2]（戳 1）：k=1，dp[0][2] = 0 + 0 + 131 = 3

• 逐步填充：最终 dp[0][5] = 167
• 解释：顺序如戳 1 (315=15)，剩 [3,5,8]；戳 5 (358=120)，剩 [3,8]；戳 3 (138=24)；戳 8 (181=8)；总 15+120+24+8=167（代码计算所有可能，取 max）。

• 输出：167。

DP 填充可视化（n=4 示例，简化部分）

• 每个 dp[i][j] 枚举 k，max 所有可能“最后戳”。

注意事项

• 顺序重要：从小到大 len，确保子区间已算（自底向上）。

• 边界处理：虚拟 1 避免越界。

• 优化：O(n^3) 已优；若 n 大，可 memo 化递归，但迭代更稳。