赞
踩
最近正在准备五月份的软件工程师考试,上文我们总结了常用的8中排序算法。本文我们就来盘一盘软考中设计到的其他各种算法,这些算法体现的思想,是我们学习的核心。希望通过此篇文章可以让大家更深刻的理解什么是算法。领会不同算法的精妙之处。
分治法,顾名思义就是分而治之的意思。就是把一个复杂的问题拆分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
我们使用分支法的思想,在一个有序的数组内,搜索指定的数值。例如:
在下面的数组内搜索值为28的数组
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); }
我们的代码实现了一个经典的二分查找算法,使用递归的方式进行查找。以下为详细解释:
该算法的时间复杂度为 O(log n),其中 n 为数组的长度。这是因为每次查找都会将查找区间缩小一半,最多需要查找 log n 次。该算法是一种高效的查找算法,常用于对已排序数组的查找操作。
给你一个二叉树的根节点 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
我们的代码实现将使用深度优先搜索和回溯的方法进行。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
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; }
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); } }
可行解示例:
过程构造示例:
宏观:
使用深度搜索的方法,按照先行后列的顺序,查看每一个位置是否满足条件。
微观:
定义二维数组表示棋盘,定义一个变量n表示几个皇后
定义一个方法用来判断当前摆放的皇后是否与之前的皇后冲突(同列、左上方,右上方),冲突返回0;否则,返回1,表示此位置可以放置皇后。
定义一个递归函数,尝试在当前行放置皇后。
package com.lsn.NQueen; public class NQueens { // 定义一个二维数组表示棋盘 int[][] board; // 定义一个变量表示几个皇后 int n; // 构造函数,初始化棋盘和n public NQueens(int n) { board = new int[n][n]; this.n = n; } // 判断当前摆放的皇后是否与之前的皇后冲突 public boolean isSafe(int row, int col) { int i, j; // 检查当前列是否有皇后 for (i = 0; i < row; i++) { if (board[i][col] == 1) { return false; } } // 检查左上方是否有皇后 for (i = row, j = col; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 1) { return false; } } // 检查右上方是否有皇后 for (i = row, j = col; i >= 0 && j < n; i--, j++) { if (board[i][j] == 1) { return false; } } // 如果都没有冲突,则返回true return true; } // 递归函数,尝试在当前行放置皇后 public boolean solve(int row) { // 如果所有行都已经摆放完毕,则返回true(终止条件,收集结果) if (row == n) { return true; } // 尝试在当前行的每一列放置皇后(单层逻辑,处理节点) for (int col = 0; col < n; col++) { // 判断当前位置是否安全 if (isSafe(row, col)) { // 如果安全,则将皇后放置在当前位置 board[row][col] = 1; // 递归调用solve函数,尝试在下一行放置皇后 if (solve(row + 1)) { return true; } // 如果下一行无法放置皇后,则回溯到当前行,重新尝试放置皇后(撤销处理节点的情况) board[row][col] = 0; } } // 如果当前行的每一列都无法放置皇后,则返回false return false; } // 打印棋盘 public void printBoard() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { // 创建一个NQueens对象,并初始化规模为8 NQueens nQueens = new NQueens(3); // 调用solve函数,尝试解决N皇后问题 if (nQueens.solve(0)) { // 如果找到了解,则打印棋盘 nQueens.printBoard(); } else { // 如果没有找到解,则打印无解 System.out.println("无解."); } } }
通过上述代码,我们可以搜索到皇后的一个可行解。
皇后问题也是回溯法的一种体现。它使用了回溯法提高效率的减枝策略,不符合条件的就不必向下进行递归,大大的提高了算法的效率。相较于上文给出二叉树回溯法的例子,它更加的复杂,体现的是一个二维的搜索,但是其核心思想都是回溯。
总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解。
给你一个整数数组 ,请你找出一个具有的连续子数组最大和(子数组最少包含一个元素),返回其最大和。
注意:子数组是数组中的一个连续部分。
public class MaximumSubarray { public int maxSubArray(int[] nums) { int currentSum = 0; // 当前子数组的和 int maxSum = Integer.MIN_VALUE; // 最大子数组的和 // 遍历数组中的每个元素 for (int num : nums) { // 如果当前子数组的和加上当前元素小于当前元素本身,那么当前子数组的和不再对后续子数组产生正向影响,重新开始一个新的子数组 currentSum = Math.max(num, currentSum + num); // 更新最大子数组的和 maxSum = Math.max(maxSum, currentSum); } return maxSum; } public static void main(String[] args) { int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; MaximumSubarray solution = new MaximumSubarray(); int maxSum = solution.maxSubArray(nums); System.out.println("最大和为:" + maxSum); } }
在以上代码中,我们使用贪心法的思想,从数组的第一个元素开始遍历,计算当前子数组的和 currentSum 和最大子数组的和 maxSum。在每次遍历过程中,我们用 Math.max(num, currentSum + num) 更新 currentSum 的值,这样可以保证 currentSum 始终是以当前元素结尾的最大子数组的和。同时,我们用 Math.max(maxSum, currentSum) 更新 maxSum 的值,以保证最终得到的 maxSum 是整个数组中的最大子数组和。
贪心法是一种求解问题的策略,其核心思想是在每一步选择中都采取当前状态下最优的选择,从而希望最终达到全局最优解。贪心法通常适用于满足「最优子结构」和「贪心选择性质」的问题。
总结贪心法的思想可以归纳为以下几点:
最优子结构(Optimal Substructure):问题的最优解包含了子问题的最优解。这意味着通过选择当前最优的解,可以将原问题拆分为更小的子问题,并且每个子问题的最优解可以组合成原问题的最优解。
贪心选择性质(Greedy Choice Property):在每一步选择中,采取当前最优的选择,即局部最优解,希望通过局部最优解达到全局最优解。这意味着贪心法不会回退或撤销之前的选择,而是根据当前情况做出决策。
不可回退(不考虑后效性):贪心法做出的选择一旦确定就不可更改,不会对之前的选择进行修改。它只关注当前状态下的最优选择,并相信通过每一步的最优选择能够达到整体最优。
需要注意的是,贪心法并不适用于所有问题,因为某些问题无法通过贪心的方式获得最优解。在使用贪心法时,需要经过严格的推导和证明,以确保其正确性。
贪心法的优点是简单、高效,并且通常可以在较短的时间内得到一个近似最优解。然而,其缺点是不能保证一定能够得到全局最优解,因此在某些情况下可能得到次优解或错误的结果。
总而言之,贪心法通过选择当前最优解来逐步构建问题的解决方案,希望通过局部最优解达到全局最优解。它是一种简单而高效的求解问题的策略,但需要仔细分析问题的性质和特点,以确定贪心选择和最优子结构的存在性。
将待求问题划分为若干个子问题,按划分的顺序求解子阶段问题,前一个子问题的解,为后一个子问题的求解提供了有用的信息(最优子结构)。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其它局部解。依次解决各个子问题,最后求出原问题的最优解
这里以一个斐波那契数列举例
public class Fibonacci { public static void main(String[] args) { int numberArr = 10; // 求第10个斐波那契数 int result = fibonacci(numberArr); // 第10个斐波那契数的值 System.out.println("第10个斐波那契数值为:"+ result); // 输出第10个斐波那契数的值 } /** * 斐波那契数列的动态规划算法 * @paramn 第numberArr个斐波那契数,dp为数据处理后的值 * @return 第numberArr个斐波那契数的值 */ public static int fibonacci(int numberArr) { if (numberArr <= 1) { // 当numberArr小于等于1时,直接返回numberArr return numberArr; } //创建数组,用于记录子问题的解 //dp为数据处理后的值 int[] dp = new int[numberArr + 1]; dp[0] = 0; // 初始化第一个数 dp[1] = 1; // 初始化第二个数 // 递推求解子问题 for (int i = 2; i <= numberArr; i++) { //dp[i]:i为该求下标 //dp[i-1]:i为该求下标-1的下标的值 //dp{[i-2]:i为该求下标-2的下标的值 //算出两个下标的值后进行相加,最后得出该求下标的值 dp[i] = dp[i - 1] + dp[i - 2]; System.out.println("第"+i+"轮numberArr的值为"+ dp[i]); } // 返回第numberArr个斐波那契数的值 return dp[numberArr]; } }
动态规划(Dynamic Programming)是一种将复杂问题分解为更小子问题并以递推的方式求解的方法。它通常适用于具有「最优子结构」和「重叠子问题」性质的问题。
简单总结动态规划法的思想可以归纳为以下几点:
最优子结构(Optimal Substructure):问题的最优解可以通过子问题的最优解来构建。这意味着原问题的解可以由相关子问题的解组合而成。
重叠子问题(Overlapping Subproblems):在递归求解过程中,许多子问题会被重复计算多次。动态规划利用记忆化或者自底向上的方法,将子问题的解存储起来以避免重复计算,提高效率。
状态转移方程(State Transition Equation):动态规划通过定义状态和状态之间的转移方程来描述问题的求解过程。状态转移方程表示问题的当前状态与前一状态之间的关系,通过状态转移方程来推导出最优解。
自底向上的计算顺序:动态规划通常使用自底向上的计算顺序,从最小规模的子问题开始逐步求解,直到推导出原问题的解。这样可以保证所有的子问题在求解时都已经得到解决。
动态规划的优点是能够求解复杂问题并得到最优解,避免了重复计算,提高了计算效率。然而,动态规划的缺点是需要较大的空间来存储中间结果,有时会牺牲一定的空间复杂性来换取时间上的优化。
总而言之,动态规划通过将复杂问题分解为更小的子问题并以递推的方式求解,利用最优子结构和重叠子问题的性质,通过状态转移方程来推导最优解。它是一种常用的求解优化问题的方法,能够高效地求解多种问题。
用一个例子来说明0/1背包问题:
现有四个物品,小偷背包总容量为8,怎么样可以偷走价值最多的物品
物品编号:1 2 3 4
物品重量:2 3 4 5
物品价值:3 4 5 8
各种限定条件解决问题:
public static void main(String[] args) { String[] nameArr = {"鞋子", "音响", "电脑"}; // 商品重量数组 int[] weightArr = {1/*鞋子*/, 4/*音响*/, 3/*电脑*/}; // 商品价格数组 int[] priceArr = {1500/*鞋子*/, 3000/*音响*/, 2000/*电脑*/}; // 背包容量 int packageCapacity = 4; backpackWithoutRepeat(nameArr, weightArr, priceArr, packageCapacity); } private static void backpackWithoutRepeat(String[] nameArr, int[] weightArr, int[] priceArr, int packageCapacity) { /** * 声明一个能装入 0、1、2、3磅......的背包的二维价格表;举例:就好比 v数组是表2的数据 */ int[][] nameBackpack = new int[nameArr.length + 1][packageCapacity + 1]; // 构建可能装入背包的二维数组 // 值为0时说明不会装进背包, 值为1说明可能装入背包 int[][] contentArr = new int[nameArr.length + 1][packageCapacity + 1]; /** * 为什么i一开始是1不是0?看表2的数据,是不是第一行全是0啊 */ for (int i = 1; i < nameBackpack.length; i++) { /** * 为什么j一开始是1不是0?看表2的数据,是不是第一列全是0啊 */ System.out.println(nameBackpack[i]); for (int j = 1; j < nameBackpack[i].length; j++) { /** * 文章中当 w[i] > j 时,就有 nameBackpack[i][j] = nameBackpack[i-1][j]; * 因为我们程序i是从1开始的,因此原来公式中的w[i]修改成w[i-1]; * 当前商品 > 背包容量, 取同列上一行数据 */ if (weightArr[i - 1] > j) { nameBackpack[i][j] = nameBackpack[i - 1][j]; } else { /** * 当前商品 <= 背包容量, 对两部分内容进行比较; * 第一部分, 该列上一行数据 */ int onePart = nameBackpack[i - 1][j]; /** * 还记得文章中写的 当j >= w[i] 时,有 nameBackpack[i][j]=max{nameBackpack[i-1][j],nameBackpack[i-1][j-w[i]]+nameBackpack[i]} 这个公式成立吗? * priceArr[i - 1]: 当前商品价格; * w[i - 1]: 当前商品重量; * j - w[i - 1]: 去掉当前商品, 背包剩余容量; * 不可重复: nameBackpack[i - 1][j - w[i - 1]]: 在上一行, 取剩余重量下的价格最优解; */ int otherPart = priceArr[i - 1] + nameBackpack[i - 1][j - weightArr[i - 1]]; /** * 取最大值为当前位置的最优解 */ nameBackpack[i][j] = Math.max(onePart, otherPart); /** * 如果最优解包含当前商品, 则表示当前商品已经被使用, 进行记录 */ if (otherPart == nameBackpack[i][j]) { contentArr[i][j] = 1; } } } } // 不能重复的场景中 // 如果该位置的标志位为1, 说明该商品参与了最终的背包添加 // 如果该位置的标志位为0, 即使该位置的价格为最大价格, 也是从其他位置引用的价格 // 因为不能重复, 所以每行只取一个数据参与最终计算, 并只判断在最大位置该商品是否参与 // 该最大位置会随着已经遍历出其他元素而对应不断减小, 直到为0 // 二维数组最后一个元素必然是最大值, 但是需要知道该最大值是自身计算的 还是比较后引用其他的 int totalPrice = 0; // 最大行下标数, 即商品数 int maxLine = contentArr.length - 1; // 最大列下标数, 即重量 int maxColumn = contentArr[0].length - 1; for (;maxLine > 0 && maxColumn > 0;) { // 等于1表示在该位置该商品参与了计算 if (contentArr[maxLine][maxColumn] == 1) { // 遍历后, 对重量减少, 下一次从剩余重量中取参与商品 maxColumn -= weightArr[maxLine - 1]; totalPrice += priceArr[maxLine - 1]; System.out.println(nameArr[maxLine - 1] + "加入了背包"); } // 因为不能重复 // 所以如果该商品参与了背包容量, 则肯定剩余的最大位置处参与, // 否则跟该数据无关, 直接跳过 maxLine--; } System.out.println("背包可容纳的最大价值: " + totalPrice); }
动态规划的思想可以用以下步骤来解决01背包问题:
通过对算法的学习,利于锻炼我们的逻辑思维,并且指导开发,希望此篇博客可以让大家学会这几种经典的算法,领略其中的思想,应用到实践中。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。