CS-Notes 分治算法题解精读用两道 Leetcode 经典题掌握「分解、求解、合并」【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 仓库中 Leetcode 题解 - 分治 一文展开围绕分治思想在算法题中的落地方式完整讲解两道中等难度经典题——Leetcode 241「给表达式加括号」与 Leetcode 95「不同的二叉搜索树」的完整 Java 解法并结合仓库内 数值的整数次方 等题解印证分治思想的通用范式。读完本篇你能掌握「划分问题 → 递归求解子问题 → 合并子问题解」三步法并能独立完成分治类题目的复杂度分析与代码实现。什么是分治三步范式分治Divide and Conquer的核心在于把一个规模为 N 的原问题拆成若干个规模更小的同类子问题对子问题递归求解后再把子问题的解合并成原问题的解。以 CS-Notes 仓库 算法 - 算法分析 等笔记为参照分治的三步范式可以概括为Divide分解将原问题划分为若干规模更小、相互独立的同类子问题Conquer求解递归地解决各子问题直到子问题小到可以直接求解即到达递归基Combine合并将子问题的解组合起来得到原问题的解。时间复杂度通常取决于「子问题个数 × 每个子问题规模」与「合并开销」满足主定理情形时多为 O(N log N) 或 O(log N)。下面两题分别体现了分治在「字符串表达式求值」与「树的递归构造」两个场景中的典型应用也是仓库原文档的全部内容主体。题一给表达式加括号Leetcode 241Different Ways to Add Parentheses (Medium)题目要求给定一个仅包含、-、*运算符号和非负整数的表达式字符串计算该表达式所有可能的括号添加方式对应的运算结果。原文档给出的示例Input: 2-1-1. ((2-1)-1) 0 (2-(1-1)) 2 Output : [0, 2]分治思路以运算符为分割点这道题的关键观察是任一运算符都可以作为「最后一步运算」的运算符。以 2-1-1 中第一个-为界表达式被划分成左子表达式 2 和右子表达式 1-1而左、右两侧各自又是一个规模更小的同类子问题可以再加括号的表达式。于是Divide遍历字符串每遇到一个运算符就在其两侧把表达式切分成两个子串Conquer对左右两个子串递归调用同一函数得到左右两侧各自所有可能的运算结果列表Combine用当前运算符把左侧每个结果与右侧每个结果做两两组合运算得到的值全部加入答案列表。递归基当子串中不再包含运算符ways.size() 0时说明子串就是一个完整的数字直接Integer.valueOf(input)返回。完整代码以下代码完整继承自仓库原文档public ListInteger diffWaysToCompute(String input) { ListInteger ways new ArrayList(); for (int i 0; i input.length(); i) { char c input.charAt(i); if (c || c - || c *) { ListInteger left diffWaysToCompute(input.substring(0, i)); ListInteger right diffWaysToCompute(input.substring(i 1)); for (int l : left) { for (int r : right) { switch (c) { case : ways.add(l r); break; case -: ways.add(l - r); break; case *: ways.add(l * r); break; } } } } } if (ways.size() 0) { ways.add(Integer.valueOf(input)); } return ways; }代码解读for (int i 0; i input.length(); i)逐字符扫描仅当c是、-、*时才把它视为候选分割点数字部分含多位数不会被误切分。input.substring(0, i)与input.substring(i 1)分别取出运算符左侧、右侧子串递归得到left、right两个结果列表——这就是「Divide Conquer」。双重for循环遍历左右结果的所有组合switch (c)按运算符类型做合并——这就是「Combine」。末尾的if (ways.size() 0)是递归基的判定没有任何运算符被处理过说明当前子串是纯数字将其转为整数放入列表返回避免空列表向上层传播。以 2-1-1 为例两个-各作为分割点第一个-得到左 {2}、右 {0, 2}合并得 {2, 4}……注意第二个分割点2-(1-1)中的右侧 1-1 还会再递归一次得到 {0, 2}最终合并出 {0, 2}与示例输出一致。题二不同的二叉搜索树Leetcode 95Unique Binary Search Trees II (Medium)题目要求给定一个数字 n生成所有值为 1...n 的二叉搜索树BST。BST 性质决定了「根为 i 时左子树只能由 [s, i-1] 构成右子树只能由 [i1, e] 构成」天然适合分治。原文档给出的示例Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]对应 n 3 时的 5 棵不同 BST1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3分治思路枚举根节点对闭区间 [s, e] 内的每个值 i 依次充当根节点Divide左子问题为生成 [s, i-1] 上所有 BST右子问题为生成 [i1, e] 上所有 BSTConquer递归生成左右两侧的候选子树列表Combine左子树列表与右子树列表做笛卡尔积每一对 (left, right) 接到新根节点 i 的左右孩子上构成一棵完整的 BST 加入结果集。递归基当s e区间为空时表示该侧没有节点返回一个包含null的列表。用「列表里放一个 null」而不是直接返回空列表是为了让笛卡尔积循环能正常进行——空子树也是一种合法的「选择」。完整代码以下代码完整继承自仓库原文档public ListTreeNode generateTrees(int n) { if (n 1) { return new LinkedListTreeNode(); } return generateSubtrees(1, n); } private ListTreeNode generateSubtrees(int s, int e) { ListTreeNode res new LinkedListTreeNode(); if (s e) { res.add(null); return res; } for (int i s; i e; i) { ListTreeNode leftSubtrees generateSubtrees(s, i - 1); ListTreeNode rightSubtrees generateSubtrees(i 1, e); for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root new TreeNode(i); root.left left; root.right right; res.add(root); } } } return res; }代码解读入口generateTrees(n)只做 n 1 的边界处理随后把 [1, n] 的生成任务委托给私有方法generateSubtrees(s, e)后者是真正承载分治逻辑的递归函数——这种「公开入口 区间递归」的写法是分治题的常见骨架。for (int i s; i e; i)枚举根节点每换一个 i左右子区间的划分随之改变对应「以 i 为根」这一类解。双重循环for (TreeNode left : leftSubtrees) for (TreeNode right : rightSubtrees)完成左右子树的笛卡尔积合并每个组合都new TreeNode(i)新建根节点保证输出的是 n 棵结构独立的树而不是共享节点。复杂度层面n 3 时共输出 5 棵树Catalan 数 C₃递归状态数为 O(n²) 个区间总开销随 Catalan 序列增长。值得一提的是仓库中 Leetcode 题解 - 树 开头即点明「树是一种递归结构很多树的问题可以使用递归来处理」——95 题正是这一论断在分治视角下的典型实例树问题的递归与分治的递归在此完全同构。同一思想的印证剑指 Offer 16「数值的整数次方」仓库 剑指 Offer 题解 - 目录 在「分治」分类下收录了 16. 数值的整数次方它展示了分治在「无合并结构、只有规模折半」场景中的形态可作为上面两题的补充印证。其思路求 x 的 n 次方直接连乘是 O(N)利用乘法可交换性把 n 次乘拆成两半(x^...x) * (x^...x)两半相同只需算一次对拆出来的子问题继续拆子问题规模减半后再平方合并即可。原文档中的核心递归实现public double Power(double x, int n) { boolean isNegative false; if (n 0) { n -n; isNegative true; } double res pow(x, n); return isNegative ? 1 / res : res; } private double pow(double x, int n) { if (n 0) return 1; if (n 1) return x; double res pow(x, n / 2); res res * res; if (n % 2 ! 0) res * x; return res; }每次递归 n 减半、返回时平方合并时间复杂度从 O(N) 降为 O(log N)——「Dividen 折半 Conquer递归 pow(x, n/2) Combine平方奇数再乘一个 x」与前述两题的节奏完全一致只是合并操作退化为一次乘法。小结与延伸阅读题目DivideConquerCombine关键细节Leetcode 241 给表达式加括号以每个运算符切分左右子串递归求左右两侧所有结果两两组合做 / - / *纯数字子串即递归基Leetcode 95 不同的二叉搜索树枚举 i ∈ [s, e] 为根递归生成 [s, i-1]、[i1, e] 子树左右子树笛卡尔积接根s e 时返回含 null 的列表剑指 16 数值的整数次方n 折半为 n/2递归求 x^(n/2)平方奇数补乘 x负指数取倒数从源码结构看仓库将 Leetcode 与剑指 Offer 两套题解按同一套「算法思想 数据结构」分类组织完整索引见 Leetcode 题解 - 目录其中分治与双指针、排序、贪心思想、二分查找、搜索、动态规划、数学等思想并列。若你在二分折半、区间划分之外还想练习「递归 合并」的写法可顺带查看 Leetcode 题解 - 树 中的递归系列题目它们与本文的分治框架互为表里。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 CS-Notes 分治算法题解精读：用两道 Leetcode 经典题掌握「分解、求解、合并」
CS-Notes 分治算法题解精读用两道 Leetcode 经典题掌握「分解、求解、合并」【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 仓库中 Leetcode 题解 - 分治 一文展开围绕分治思想在算法题中的落地方式完整讲解两道中等难度经典题——Leetcode 241「给表达式加括号」与 Leetcode 95「不同的二叉搜索树」的完整 Java 解法并结合仓库内 数值的整数次方 等题解印证分治思想的通用范式。读完本篇你能掌握「划分问题 → 递归求解子问题 → 合并子问题解」三步法并能独立完成分治类题目的复杂度分析与代码实现。什么是分治三步范式分治Divide and Conquer的核心在于把一个规模为 N 的原问题拆成若干个规模更小的同类子问题对子问题递归求解后再把子问题的解合并成原问题的解。以 CS-Notes 仓库 算法 - 算法分析 等笔记为参照分治的三步范式可以概括为Divide分解将原问题划分为若干规模更小、相互独立的同类子问题Conquer求解递归地解决各子问题直到子问题小到可以直接求解即到达递归基Combine合并将子问题的解组合起来得到原问题的解。时间复杂度通常取决于「子问题个数 × 每个子问题规模」与「合并开销」满足主定理情形时多为 O(N log N) 或 O(log N)。下面两题分别体现了分治在「字符串表达式求值」与「树的递归构造」两个场景中的典型应用也是仓库原文档的全部内容主体。题一给表达式加括号Leetcode 241Different Ways to Add Parentheses (Medium)题目要求给定一个仅包含、-、*运算符号和非负整数的表达式字符串计算该表达式所有可能的括号添加方式对应的运算结果。原文档给出的示例Input: 2-1-1. ((2-1)-1) 0 (2-(1-1)) 2 Output : [0, 2]分治思路以运算符为分割点这道题的关键观察是任一运算符都可以作为「最后一步运算」的运算符。以 2-1-1 中第一个-为界表达式被划分成左子表达式 2 和右子表达式 1-1而左、右两侧各自又是一个规模更小的同类子问题可以再加括号的表达式。于是Divide遍历字符串每遇到一个运算符就在其两侧把表达式切分成两个子串Conquer对左右两个子串递归调用同一函数得到左右两侧各自所有可能的运算结果列表Combine用当前运算符把左侧每个结果与右侧每个结果做两两组合运算得到的值全部加入答案列表。递归基当子串中不再包含运算符ways.size() 0时说明子串就是一个完整的数字直接Integer.valueOf(input)返回。完整代码以下代码完整继承自仓库原文档public ListInteger diffWaysToCompute(String input) { ListInteger ways new ArrayList(); for (int i 0; i input.length(); i) { char c input.charAt(i); if (c || c - || c *) { ListInteger left diffWaysToCompute(input.substring(0, i)); ListInteger right diffWaysToCompute(input.substring(i 1)); for (int l : left) { for (int r : right) { switch (c) { case : ways.add(l r); break; case -: ways.add(l - r); break; case *: ways.add(l * r); break; } } } } } if (ways.size() 0) { ways.add(Integer.valueOf(input)); } return ways; }代码解读for (int i 0; i input.length(); i)逐字符扫描仅当c是、-、*时才把它视为候选分割点数字部分含多位数不会被误切分。input.substring(0, i)与input.substring(i 1)分别取出运算符左侧、右侧子串递归得到left、right两个结果列表——这就是「Divide Conquer」。双重for循环遍历左右结果的所有组合switch (c)按运算符类型做合并——这就是「Combine」。末尾的if (ways.size() 0)是递归基的判定没有任何运算符被处理过说明当前子串是纯数字将其转为整数放入列表返回避免空列表向上层传播。以 2-1-1 为例两个-各作为分割点第一个-得到左 {2}、右 {0, 2}合并得 {2, 4}……注意第二个分割点2-(1-1)中的右侧 1-1 还会再递归一次得到 {0, 2}最终合并出 {0, 2}与示例输出一致。题二不同的二叉搜索树Leetcode 95Unique Binary Search Trees II (Medium)题目要求给定一个数字 n生成所有值为 1...n 的二叉搜索树BST。BST 性质决定了「根为 i 时左子树只能由 [s, i-1] 构成右子树只能由 [i1, e] 构成」天然适合分治。原文档给出的示例Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]对应 n 3 时的 5 棵不同 BST1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3分治思路枚举根节点对闭区间 [s, e] 内的每个值 i 依次充当根节点Divide左子问题为生成 [s, i-1] 上所有 BST右子问题为生成 [i1, e] 上所有 BSTConquer递归生成左右两侧的候选子树列表Combine左子树列表与右子树列表做笛卡尔积每一对 (left, right) 接到新根节点 i 的左右孩子上构成一棵完整的 BST 加入结果集。递归基当s e区间为空时表示该侧没有节点返回一个包含null的列表。用「列表里放一个 null」而不是直接返回空列表是为了让笛卡尔积循环能正常进行——空子树也是一种合法的「选择」。完整代码以下代码完整继承自仓库原文档public ListTreeNode generateTrees(int n) { if (n 1) { return new LinkedListTreeNode(); } return generateSubtrees(1, n); } private ListTreeNode generateSubtrees(int s, int e) { ListTreeNode res new LinkedListTreeNode(); if (s e) { res.add(null); return res; } for (int i s; i e; i) { ListTreeNode leftSubtrees generateSubtrees(s, i - 1); ListTreeNode rightSubtrees generateSubtrees(i 1, e); for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root new TreeNode(i); root.left left; root.right right; res.add(root); } } } return res; }代码解读入口generateTrees(n)只做 n 1 的边界处理随后把 [1, n] 的生成任务委托给私有方法generateSubtrees(s, e)后者是真正承载分治逻辑的递归函数——这种「公开入口 区间递归」的写法是分治题的常见骨架。for (int i s; i e; i)枚举根节点每换一个 i左右子区间的划分随之改变对应「以 i 为根」这一类解。双重循环for (TreeNode left : leftSubtrees) for (TreeNode right : rightSubtrees)完成左右子树的笛卡尔积合并每个组合都new TreeNode(i)新建根节点保证输出的是 n 棵结构独立的树而不是共享节点。复杂度层面n 3 时共输出 5 棵树Catalan 数 C₃递归状态数为 O(n²) 个区间总开销随 Catalan 序列增长。值得一提的是仓库中 Leetcode 题解 - 树 开头即点明「树是一种递归结构很多树的问题可以使用递归来处理」——95 题正是这一论断在分治视角下的典型实例树问题的递归与分治的递归在此完全同构。同一思想的印证剑指 Offer 16「数值的整数次方」仓库 剑指 Offer 题解 - 目录 在「分治」分类下收录了 16. 数值的整数次方它展示了分治在「无合并结构、只有规模折半」场景中的形态可作为上面两题的补充印证。其思路求 x 的 n 次方直接连乘是 O(N)利用乘法可交换性把 n 次乘拆成两半(x^...x) * (x^...x)两半相同只需算一次对拆出来的子问题继续拆子问题规模减半后再平方合并即可。原文档中的核心递归实现public double Power(double x, int n) { boolean isNegative false; if (n 0) { n -n; isNegative true; } double res pow(x, n); return isNegative ? 1 / res : res; } private double pow(double x, int n) { if (n 0) return 1; if (n 1) return x; double res pow(x, n / 2); res res * res; if (n % 2 ! 0) res * x; return res; }每次递归 n 减半、返回时平方合并时间复杂度从 O(N) 降为 O(log N)——「Dividen 折半 Conquer递归 pow(x, n/2) Combine平方奇数再乘一个 x」与前述两题的节奏完全一致只是合并操作退化为一次乘法。小结与延伸阅读题目DivideConquerCombine关键细节Leetcode 241 给表达式加括号以每个运算符切分左右子串递归求左右两侧所有结果两两组合做 / - / *纯数字子串即递归基Leetcode 95 不同的二叉搜索树枚举 i ∈ [s, e] 为根递归生成 [s, i-1]、[i1, e] 子树左右子树笛卡尔积接根s e 时返回含 null 的列表剑指 16 数值的整数次方n 折半为 n/2递归求 x^(n/2)平方奇数补乘 x负指数取倒数从源码结构看仓库将 Leetcode 与剑指 Offer 两套题解按同一套「算法思想 数据结构」分类组织完整索引见 Leetcode 题解 - 目录其中分治与双指针、排序、贪心思想、二分查找、搜索、动态规划、数学等思想并列。若你在二分折半、区间划分之外还想练习「递归 合并」的写法可顺带查看 Leetcode 题解 - 树 中的递归系列题目它们与本文的分治框架互为表里。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考