网站开发asp 视频教程网站建设集团

网站开发asp 视频教程,网站建设集团,赣州爆炸事故,网站描述技巧目录 一、回溯算法核心共性 二、分题详解 #xff08;一#xff09;题目 1#xff1a;电话号码的字母组合#xff08;LeetCode 17#xff09; 1. 题目描述 2. 解题思路 3. 难点 重点 4. Java 实现 5. 拓展延伸 #xff08;二#xff09;题目 2#xff1…目录一、回溯算法核心共性二、分题详解一题目 1电话号码的字母组合LeetCode 171. 题目描述2. 解题思路3. 难点 重点4. Java 实现5. 拓展延伸二题目 2子集LeetCode 781. 题目描述2. 解题思路3. 难点 重点4. Java 实现5. 拓展延伸三题目 3分割回文串LeetCode 1311. 题目描述2. 解题思路3. 难点 重点4. Java 实现5. 拓展延伸三、三道题对比总结四、回溯算法通用技巧一、回溯算法核心共性回溯算法本质是「暴力枚举 状态回退」核心流程为选择当前节点 → 递归探索后续分支 → 撤销选择回溯 → 探索下一分支。隐式回溯依赖不可变对象如 String递归传递新对象无需手动撤销自动回退状态显式回溯依赖可变对象如 List需手动添加 / 删除元素完成状态回退核心要素终止条件、选择范围避免重复、状态维护。二、分题详解一题目 1电话号码的字母组合LeetCode 171. 题目描述给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。数字到字母的映射与电话按键一致如2→abc、3→def空输入返回空列表。2. 解题思路核心隐式回溯利用 String 不可变性递归传递新字符串自动回退状态步骤定义数字→字母的映射表索引对应数字值对应字母串递归处理每个数字遍历当前数字的所有字母拼接成新字符串传递给下一层递归终止条件递归深度等于数字字符串长度所有数字处理完毕收集当前组合。3. 难点 重点类型具体内容重点数字字符转映射表索引char - 0、隐式回溯的理解String 不可变难点区分「递归索引处理第几个数字」和「映射表索引数字对应的字母」避免索引错位边界空输入直接返回空列表避免递归进入无效分支4. Java 实现最终可运行版import java.util.ArrayList; import java.util.List; class Solution { // 数字→字母映射表索引数字值对应字母串 private String[] dataToLetter {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; // 全局结果列表存储所有合法字母组合 private ListString result new ArrayList(); public ListString letterCombinations(String digits) { // 边界条件空输入直接返回空列表 if (digits null || digits.length() 0) { return result; } // 启动回溯从第0个数字开始初始组合为空串 backtrack(digits, 0, ); return result; } /** * 回溯核心函数 * param digits 输入的数字字符串 * param index 当前处理到第几个数字递归深度 * param current 当前已拼接的字母组合不可变隐式回溯 */ private void backtrack(String digits, int index, String current) { // 终止条件所有数字处理完毕收集结果 if (index digits.length()) { result.add(current); return; } // 步骤1获取当前数字字符并转为映射表索引 char currDigit digits.charAt(index); int mapIndex currDigit - 0; // 字符2→数字2对应映射表的abc String letters dataToLetter[mapIndex]; // 步骤2遍历当前数字的所有字母递归拼接 for (int i 0; i letters.length(); i) { // 拼接新字符串String不可变生成新对象隐式回溯 backtrack(digits, index 1, current letters.charAt(i)); } } }5. 拓展延伸显式回溯优化用StringBuilder替代 String减少字符串拼接的内存开销手动append/delete完成回溯private void backtrack(String digits, int index, StringBuilder current) { if (index digits.length()) { result.add(current.toString()); return; } char currDigit digits.charAt(index); int mapIndex currDigit - 0; String letters dataToLetter[mapIndex]; for (int i 0; i letters.length(); i) { current.append(letters.charAt(i)); // 选 backtrack(digits, index 1, current); current.deleteCharAt(current.length() - 1); // 撤显式回溯 } }异常处理输入含0/1时跳过无效数字迭代实现用队列模拟递归逐层拼接字母非回溯思路拓展解题视角。二题目 2子集LeetCode 781. 题目描述给定一个整数数组nums元素互不相同返回该数组的所有子集幂集包含空集且子集无重复。2. 解题思路核心显式回溯利用 List 可变性手动添加 / 删除元素步骤递归遍历数组start控制当前层的起始选择位置避免重复子集每进入一层递归先收集当前状态当前 List 即为一个子集遍历从start开始的元素选择后递归下一层起始位置更新为i1递归返回后删除该元素回溯。3. 难点 重点类型具体内容重点用start和i1控制选择范围避免生成重复子集如[1,2]和[2,1]难点终止条件无显式判断无需等长度达标每一步都是有效子集空集自动收集关键收集结果时需新建 Listnew ArrayList(current)避免后续回溯修改已收集的结果4. Java 实现最终可运行版import java.util.ArrayList; import java.util.List; class Solution { public ListListInteger subsets(int[] nums) { // 最终结果存储所有子集 ListListInteger result new ArrayList(); // 当前状态存储递归过程中的临时子集 ListInteger current new ArrayList(); // 边界条件空数组直接返回空列表空集已在回溯中自动收集 if (nums null || nums.length 0) { return result; } // 启动回溯从第0个元素开始 backtrack(nums, 0, current, result); return result; } /** * 回溯核心函数 * param nums 输入数组 * param start 当前层的起始选择索引避免重复 * param current 当前临时子集 * param result 最终结果集 */ private void backtrack(int[] nums, int start, ListInteger current, ListListInteger result) { // 关键每一层递归先收集当前状态初始current为空自动收集空集 result.add(new ArrayList(current)); // 遍历从start开始的元素控制选择范围 for (int i start; i nums.length; i) { current.add(nums[i]); // 选添加当前元素 backtrack(nums, i 1, current, result); // 递归下一层从i1开始避免重复选前面的元素 current.remove(current.size() - 1); // 撤回溯删除最后一个元素 } } }5. 拓展延伸子集 IILeetCode 90数组含重复元素需去重排序后跳过相同元素if (i start nums[i] nums[i-1]) continue选 / 不选思路另一种回溯写法对每个元素选或不选无需 start 控制private void backtrack(int[] nums, int index, ListInteger current, ListListInteger result) { if (index nums.length) { result.add(new ArrayList(current)); return; } // 选当前元素 current.add(nums[index]); backtrack(nums, index 1, current, result); current.remove(current.size() - 1); // 不选当前元素 backtrack(nums, index 1, current, result); }位运算实现用二进制数表示元素是否被选中如nums[1,2,3]二进制000→[]001→[3]。三题目 3分割回文串LeetCode 1311. 题目描述给定一个字符串s将s分割成若干子串使得每个子串都是回文串返回所有可能的分割方案。2. 解题思路核心显式回溯 回文判断步骤递归遍历字符串start控制当前分割的起始位置枚举从start到末尾的分割点i截取子串s[start..i]判断子串是否为回文是则加入当前列表递归处理剩余部分起始位置更新为i1终止条件start等于字符串长度所有字符分割完毕收集当前分割方案。3. 难点 重点类型具体内容重点分割点枚举start→i1、回文子串的判断双指针法难点字符串截取的边界substring(start, i1)左闭右开优化重复回文判断耗时可提前用 DP 预处理所有子串是否为回文4. Java 实现最终可运行版import java.util.ArrayList; import java.util.List; class Solution { public ListListString partition(String s) { // 最终结果存储所有合法分割方案 ListListString result new ArrayList(); // 当前状态存储递归过程中的临时分割方案 ListString current new ArrayList(); // 边界条件空字符串直接返回空列表 if (s null || s.length() 0) { return result; } // 启动回溯从第0个字符开始分割 backtrack(s, 0, current, result); return result; } /** * 回溯核心函数 * param s 输入字符串 * param start 当前分割的起始位置 * param current 当前临时分割方案 * param result 最终结果集 */ private void backtrack(String s, int start, ListString current, ListListString result) { // 终止条件所有字符分割完毕收集结果 if (start s.length()) { result.add(new ArrayList(current)); return; } // 枚举所有分割点从start到字符串末尾 for (int i start; i s.length(); i) { // 截取子串s[start..i]substring左闭右开故结束索引为i1 String subStr s.substring(start, i 1); // 判断子串是否为回文非回文则跳过 if (isHuiWen(subStr)) { current.add(subStr); // 选添加回文子串 backtrack(s, i 1, current, result); // 递归处理剩余字符 current.remove(current.size() - 1); // 撤回溯删除最后一个子串 } } } /** * 双指针法判断单个字符串是否为回文 * param s 待判断字符串 * return true回文false非回文 */ private boolean isHuiWen(String s) { int left 0; int right s.length() - 1; // 左右指针相向移动逐一比较字符 while (left right) { if (s.charAt(left) ! s.charAt(right)) { return false; } left; right--; } return true; } }5. 拓展延伸DP 预处理回文子串避免重复截取判断提升长字符串效率构建dp[i][j]表示s[i..j]是否为回文// 预处理回文DP表 private boolean[][] preProcessPalindrome(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; // 单个字符都是回文 for (int i 0; i n; i) dp[i][i] true; // 从后往前填充DP表 for (int i n - 2; i 0; i--) { for (int j i 1; j n; j) { if (s.charAt(i) s.charAt(j)) { // 长度为2或中间子串是回文则当前子串是回文 dp[i][j] (j - i 1) || dp[i 1][j - 1]; } } } return dp; }分割回文串 IILeetCode 132求最少分割次数动态规划 贪心非回溯回文判断优化预处理后回溯中直接查dp[start][i]无需重复调用isHuiWen。三、三道题对比总结维度电话号码的字母组合子集分割回文串回溯类型隐式回溯String 不可变显式回溯List 可变显式回溯List 可变终止条件递归深度 数字长度需拼接完成无显式终止每步都收集结果分割起始位置 字符串长度分割完成核心逻辑数字→字母映射 逐层拼接控制起始索引避免重复 选 / 不选枚举分割点 回文判断去重方式天然无重复按数字顺序拼接start→i1控制选择范围非回文子串直接跳过关键数据结构String不可变、ListStringListInteger可变ListString可变、双指针拓展方向显式回溯优化、迭代法含重复元素去重、位运算DP 预处理回文、最少分割次数核心易错点数字索引映射错误start1误写应为i1字符串截取边界错误、回文判断遗漏四、回溯算法通用技巧状态维护可变对象List/StringBuilder需手动回溯不可变对象String自动回溯避免重复用start索引控制选择范围或排序后跳过重复元素结果收集可变对象需新建副本new ArrayList(current)避免后续修改终止条件根据题目要求要么 “长度达标”要么 “索引越界”要么 “每步收集”效率优化预处理重复计算如回文 DP 表、剪枝如非回文子串跳过。用宏大的世界稀释痛苦用微小的事情感知幸福