软考算法
一：故事背景
最近正在准备五月份的软件工程师考试，上文我们总结了常用的8中排序算法。本文我们就来盘一盘软考中设计到的其他各种算法，这些算法体现的思想，是我们学习的核心。希望通过此篇文章可以让大家更深刻的理解什么是算法。领会不同算法的精妙之处。
二：分治法
2.1 概念
分治法，顾名思义就是分而治之的意思。就是把一个复杂的问题拆分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
2.2 题目描述
我们使用分支法的思想，在一个有序的数组内，搜索指定的数值。例如：
在下面的数组内搜索值为28的数组
2.3 代码实现
public static void main(String[] args) { int [] nums ={8,20,28,74,92,188,372,500}; int targetNumber = 28; int i = binarySearch(targetNumber, 0, nums.length, nums); System.out.println(i); } /** * 二分查找 * * @param targetNumber 要查找的目标数字 * @param beginIndex 查找区间的起始下标 * @param endIndex 查找区间的结束下标 * @param nums 给定的已排序数组 * @return 如果找到目标数字，返回目标数字的下标；否则返回 -1 */ public static int binarySearch(int targetNumber, int beginIndex, int endIndex, int[] nums) { // 计算中间位置 int middleIndex = (beginIndex + endIndex) / 2; // 如果找到目标数字，返回目标数字的下标 if (targetNumber == nums[middleIndex]) { return middleIndex; } // 如果目标数字比中间位置的数大，说明目标数字在右半区间 if (targetNumber > nums[middleIndex]) { return binarySearch(targetNumber, middleIndex, endIndex, nums); } // 如果目标数字比中间位置的数小，说明目标数字在左半区间 return binarySearch(targetNumber, beginIndex, middleIndex, nums); }
2.4 总结提升
我们的代码实现了一个经典的二分查找算法，使用递归的方式进行查找。以下为详细解释：
在 main 方法中定义了一个数组 nums 和一个目标数字 targetNumber，然后调用了 binarySearch 方法进行查找，并输出查找结果。
binarySearch 方法是一个递归函数，用于在已排序数组 nums 中查找目标数字 targetNumber。函数参数中的 beginIndex 和 endIndex 表示查找区间的起始下标和结束下标，nums 表示给定的已排序数组。
首先计算中间位置 middleIndex，如果找到目标数字，返回目标数字的下标 middleIndex。
如果目标数字比中间位置的数大，说明目标数字在右半区间，递归调用 binarySearch 方法，将查找区间的起始下标改为 middleIndex，结束下标不变。
如果目标数字比中间位置的数小，说明目标数字在左半区间，递归调用 binarySearch 方法，将查找区间的结束下标改为 middleIndex，起始下标不变。
如果没有找到目标数字，返回 -1。
该算法的时间复杂度为 O(log n)，其中 n 为数组的长度。这是因为每次查找都会将查找区间缩小一半，最多需要查找 log n 次。该算法是一种高效的查找算法，常用于对已排序数组的查找操作。
三：回溯法
3.1 概念
回溯法，可以系统的搜索一个问题的所有解或任一解。
回溯法通常涉及到对问题状态的深度优先搜索，在搜索过程中，算法尝试一步步地构建解决方案，每次决策都会将问题状态转移到下一步，并检查当前状态是否满足问题的要求。如果当前状态满足问题要求，则继续向下搜索；如果不满足要求，则回溯到上一个状态，并尝试其他的决策。
3.2 题目描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
输入：root = [1,2,3,4,5,6,7,8,9]
输出：[“1->2->4->8”,“1->2->4->9”,“1->2->5”,“1->3->6”,“1->3->7”]
提示：
树中节点的数目在范围 [1, 100] 内 -100 <= Node.val <= 100
3.3 代码实现
我们的代码实现将使用深度优先搜索和回溯的方法进行。
首先从根节点开始，对二叉树进行深度优先遍历。
遍历过程中使用一个字符串构建器 StringBuilder 记录当前路径
每当遍历到叶子节点时，将当前路径添加到结果列表中，并回溯到上一层节点。
3.3.1 TreeNode 类
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
3.3.2 将数组处理成二叉树结构并且返回根节点
public static TreeNode constructTree(int[] nums) { if (nums == null || nums.length == 0) { return null; } // 创建根节点 TreeNode root = new TreeNode(nums[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (i < nums.length) { // 取出队头元素 TreeNode parent = queue.poll(); if (i < nums.length && nums[i] != null) { // 创建左子节点 parent.left = new TreeNode(nums[i]); queue.offer(parent.left); } i++; if (i < nums.length && nums[i] != null) { // 创建右子节点 parent.right = new TreeNode(nums[i]); queue.offer(parent.right); } i++; } return root; }
3.3.3 进行搜索
class Solution { public List<String> binaryTreePaths(TreeNode root) { // 用于保存所有从根节点到叶子节点的路径 List<String> result = new ArrayList<String>(); // 处理特殊情况，如果根节点为空，则返回空路径列表 if (root == null) { return result; } // 开始深度优先搜索 dfs(root, new StringBuilder(), result); return result; } private void dfs(TreeNode node, StringBuilder path, List<String> result) { // 如果当前节点为空，返回 if (node == null) { return; } // 保存当前路径的长度 int len = path.length(); // 如果当前节点是叶子节点，则将当前路径添加到结果列表中 if (node.left == null && node.right == null) { result.add(path.append(node.val).toString()); // 恢复当前路径的长度 path.setLength(len); return; } // 将当前节点添加到路径中，并加上箭头 path.append(node.val).append("->"); // 递归遍历左子树 dfs(node.left, path, result); // 递归遍历右子树 dfs(node.right, path, result); // 恢复当前路径的长度 path.setLength(len); } }
3.4 总结提升
这个了例子里，我们需要将当前节点添加到当前路径中
然后递归遍历该节点的左右子树
在回溯的过程中，需要将当前节点从当前路径中删除，同时选择其它分支继续搜索，直到找到所有的路径。
本问题体现了回溯算法的核心思想，即通过试错的方式搜索问题的解空间。
