企业官网建设流程全解析

新宾区网站建设,做网站必须要购买空间吗,博客营销案例,wordpress如何创建分类一、回溯算法简介回溯算法#xff08;Backtracking#xff09;是一种基于递归的穷举搜索算法#xff0c;核心思想是 “尝试 - 回退 - 再尝试”#xff1a;从初始状态出发#xff0c;逐步探索所有可能的路径#xff0c;当发现当前路径无法满足条件时#xff08;剪枝…一、回溯算法简介回溯算法Backtracking是一种基于递归的穷举搜索算法核心思想是 “尝试 - 回退 - 再尝试”从初始状态出发逐步探索所有可能的路径当发现当前路径无法满足条件时剪枝撤销当前选择回溯回到上一步继续探索其他路径直到找到解或遍历完所有可能。回溯算法天然适配 “组合、排列、子集、切割、棋盘如 N 皇后” 等多选择、多约束的问题是数据结构与算法中解决 “穷举类” 问题的核心方法。二、核心要素回溯算法的执行过程可类比 “走迷宫”走一步→发现不通→退回来→换方向再走。其核心包含 4 个要素要素说明路径已做出的选择如已选的组合、排列元素已放置皇后的位置选择列表当前步骤可选择的选项如剩余未选的元素、皇后可放置的列结束条件到达决策树的叶子节点路径满足要求如组合长度达标、排列完成剪枝提前排除无效路径如重复组合、皇后冲突减少不必要的穷举优化核心三、应用场景以下通过 4 类经典问题讲解回溯算法的具体实现覆盖 “组合、排列、子集、棋盘” 四大核心场景。场景 1组合问题无重复元素不考虑顺序问题给定数组nums [1,2,3]找出所有长度为 2 的组合如[1,2]、[1,3]、[2,3]。核心组合不考虑顺序需通过 “起始索引” 避免重复如选 1 后只选 1 之后的元素。场景 2排列问题无重复元素考虑顺序问题给定数组nums [1,2,3]找出所有全排列如[1,2,3]、[1,3,2]、[2,1,3]等。核心排列考虑顺序需通过 “已选集合” 避免重复选择同一元素。场景 3子集问题所有可能的子集包括空集问题给定数组nums [1,2,3]找出所有子集如[]、[1]、[1,2]、[1,2,3]、[2]等。核心子集是 “选或不选” 的结果结束条件可省略每次递归都将当前路径加入结果。场景 4棋盘问题N 皇后带复杂约束问题N 皇后问题在 N×N 的棋盘上放置 N 个皇后使得任意两个皇后不在同一行、同一列、同一斜线找出所有合法的放置方案。核心通过剪枝快速排除无效位置同行 / 同列 / 同斜线减少穷举次数。四、案例分享题目给定一个整型数组其中所有元素都各不相同返回这些元素所有可能的排列。如[123]返回[[123] [132] [213] [231] [312] [321]]。import java.util.LinkedList; import java.util.List; public class Solution { ListListInteger result null; ListBoolean used null; // p中保存了一个有index个元素的排列向这个排列末尾添加第index1个元素 // 获得一个有index1个元素的排列 void generatePermutation(int[] nums, int index, ListInteger p) { if (index nums.length) { result.add(new LinkedList(p)); return; } for (int i 0; i nums.length; i) if (!used.get(i)) { // 将nums[i]添加到p中 p.add(nums[i]); used.set(i, true); // 递归 generatePermutation(nums, index 1, p); // 下面两行实现回溯因为以后还会使用到nums[i]是逐个元素进行回溯 p.remove(p.size() - 1); used.set(i, false); } return; } // 46 使用递归和回溯的算法完成该题 public ListListInteger permute(int[] nums) { result new LinkedListListInteger(); if (nums.length 0) return result; LinkedListInteger p new LinkedList(); used new LinkedList(); // 初始化used for (int i 0; i nums.length; i) used.add(i, false); generatePermutation(nums, 0, p); return result; } public static void main(String[] args) { int[] nums { 1, 2, 3 }; System.out.println(new Solution().permute(nums)); } }