深圳幻海软件技术有限公司 欢迎您！
更多

【蓝桥杯】高频算法考点及真题详解小结

2023-04-02

int 算法 new
🙊🙊作者主页：🔗求不脱发的博客📔📔精选专栏：🔗数据结构与算法📋📋精彩摘要：考前看一看，AC手拿软。蓝桥杯高频算法考点小结，包括各大算法、排序算法及图的优先遍历原则知识点小结。预祝大家取得优异成绩。💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞📚目录📖【

🙊🙊作者主页：🔗求不脱发的博客

📔📔 精选专栏：🔗数据结构与算法

📋📋 精彩摘要：考前看一看，AC手拿软。蓝桥杯高频算法考点小结，包括各大算法、排序算法及图的优先遍历原则知识点小结。预祝大家取得优异成绩。

💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞

📚目录

📖【蓝桥杯】高频算法考点及例题详解小结

📝1️⃣贪心算法之区间问题详解

📝2️⃣动态规划之经典包子凑数

📝3️⃣动态规划解决最大乘积系列问题（碾压暴力枚举）

📝4️⃣分治算法实现经典归并排序

📝5️⃣枚举算法经典日期问题详解

📝6️⃣BFS广搜解决迷宫问题

📝7️⃣DFS连通块问题

📝8️⃣DFS方格分割

📝9️⃣迪杰斯特拉 (Dijkstra)算法求最短路径问题

📖【蓝桥杯】高频算法考点及例题详解小结

📝1️⃣贪心算法之区间问题详解

1.什么是贪心算法

基本思想

1）贪婪算法（贪心算法）是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的算法。
2）贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似（接近）最优解的结果。

局限性

贪心算法失效的很大一个原因在于它明显的局限性：它几乎只考虑局部最优解。 所谓局部最优，就是只考虑当前的最大利益，既不向前多看一步，也不向后多看一步，导致每次都只用当前阶段的最优解。 因此在绝大多数情况下，贪心算法不能得到整体最优解，但它的解是最优解的一个很好近似。

2.经典例题

区间问题

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

输入输出样例

输入：是一个数组，数组由多个长度固定为2的数组组成，表示区间的开始和结尾。

输出：一个整数，表示需要移除的区间数量。

Input :[1,2],[2,4],[1,3]]
Output :1

在这个样例中，我们可以移除区间［1,3]，使得剩余的区间［1,2],[2,4]]互不重叠。

贪心策略

在选择要保留区间时，区间的结尾很重要：选择的区间结尾越小，余留给其它区间的空间
就越大，就越能保留更多的区间。
因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。具体实现方法为：

1.先把区间按照结尾的大小进行增序排序，

2.每次选择结尾最小且和前一个选择的区间不重叠的区间。

在样例中，排序后的数组为［1,2],[1,3],[2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于［1,3］与［1,2］相交，我们跳过该区间；由于［2,4］与［1,2］不相交，我们将其保留。因此最终保留的区间为［1,2],[2,4]。

3.代码实现

  1. import java.util.Arrays;
  2. import java.util.Comparator;
  3.  
  4. public class Solution {
  5. public static int merge(int[][] intervals) {
  6. //先按照区间结尾的大小进行升序排序
  7. Arrays.sort(intervals, new Comparator<int[]>() {
  8. @Override
  9. public int compare(int[] o1, int[] o2) {
  10. return o1[1] - o2[1];
  11. }
  12. });
  13. int count =1;//区间不重合的个数，默认第一个满足题意，初始化为1
  14. int cur = intervals[0][1];//排序完成后贪心选择的最小的区间结尾
  15. for (int i = 1; i < intervals.length; i++) {
  16. if(intervals[i][0] >= cur) {
  17. count++;
  18. cur=intervals[i][1];
  19. }
  20. }
  21.         //所有区间的个数减去不重叠区间的个数，就是重叠区间的个数。
  22. return intervals.length - count;
  23.     }
  24. }

📝2️⃣动态规划之经典包子凑数

题目 包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有NN种蒸笼，其中第ii种蒸笼恰好能放A_iAi​个包子。每种蒸笼都有非常多笼，可以认为是无限笼。 

每当有顾客想买XX个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有XX个包子。比如一共有33种蒸笼，分别能放3、43、4和55个包子。当顾客想买1111个包子时，大叔就会选22笼33个的再加11笼55个的（也可能选出11笼33个的再加22笼44个的）。 

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有33种蒸笼，分别能放4、54、5和66个包子。而顾客想买77个包子时，大叔就凑不出来了。 

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入

第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100) 

2  
4  
5  

输出

 一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

6  

动态规划思想

在讲动态规划思想前，本题还使用到了经典数论Ax+By=C（x,y>0）问题：若A，B互质，则有无限个C时的方程无解。否则可能有解。推广到a,b,...,n同时成立。可以利用这个思想求是否有无穷个包子数凑不出来。

所以本题中可以类似的用a1,a2,...an表示能放的包子的个数，找到合适的x，y，.......n凑出C。如果方程有解则能凑出，否则不能凑出。至于求最大公约数可以利用辗转相除法求。

然后本题就可以类似背包问题，使用到一个boolean[] dp，下标index表示index个包子是否能够凑出。当dp[i] 即i个包子可以凑出的话，那么j个包子+第i种蒸笼恰好能放Ai个包子：arr[i]也能够凑出来即index=(j+arr[i])个包子也能够凑出来：dp[j + arr[i]] = true;动态规划的思想就体现在这，另外为了节省时间，在录入数据的同时，就可以对dp[]数据进行更新。

具体代码

  1. import java.util.Scanner;
  2.  
  3. public class _包子凑数 {
  4. public static void main(String[] args) {
  5. Scanner scanner = new Scanner(System.in);
  6. int n = scanner.nextInt();//N种蒸笼
  7. int yueshu = 0;//最大公约数
  8. int[] arr = new int[n + 1];//以下N行每行包含一个整数Ai
  9. boolean[] dp = new boolean[10000];//下标index表示index个包子是否能够凑出
  10. dp[0] = true;//默认0个包子可以凑出来
  11. //在录入数据的同时，即可对dp[index]index个包子是否能够凑出来进行更新处理。
  12. for (int i = 1; i <= n; i++) {
  13. arr[i] = scanner.nextInt();//录入数据
  14. /**
  15.  * 下面if-else语句动态求输入的数据的最大公约数
  16.  * 求当前第i种蒸笼恰好能放Ai个包子和前一个蒸笼能放的包子个数的最大公约数
  17.  */
  18. if (i == 1)
  19. yueshu = arr[1];
  20. else
  21. yueshu = yue(arr[i], yueshu);
  22. //更新dp[]数组
  23. for (int j = 0; j < 10000; j++) {
  24. /**
  25.  * 如果dp[j]，即j个包子能够凑出来，
  26.  * 那么j个包子+第i种蒸笼恰好能放Ai个包子：arr[i]也能够凑出来
  27.  * 即index=(j+arr[i])个包子也能够凑出来。
  28.  */
  29. if (dp[j])
  30. dp[j + arr[i]] = true;//向后递推，动态规划的体现
  31. }
  32. }
  33. //当最大公约数！=1  说明Ai不互质，则有无限个包子数凑不出来
  34. if (yueshu != 1)
  35. System.out.println("INF");
  36. else {
  37. //否则统计个数
  38. int sum = 0;
  39. for (int i = 0; i < dp.length; i++) {
  40. if (!dp[i])
  41. sum++;
  42. }
  43. System.out.println(sum);
  44. }
  45. }
  46. /**
  47.  * 辗转相除法求a，b两个数的最大公约数
  48.  * @param a
  49.  * @param b
  50.  * @return
  51.  */
  52. public static int yue(int a, int b) {
  53. if (b == 0)
  54. return a;
  55. else
  56. return yue(b, a % b);
  57. }
  58. }

📝3️⃣动态规划解决最大乘积系列问题（碾压暴力枚举）

1.例题

题目描述

输入n个元素组成的子串S，你需要找出一个乘积最大的连续的子串。

如果这个最大的乘积不是正数，应输出0(表示无解)。

输入

第一行是一个整数n(1<=n<=18)。

第二行是n个整数。其中每个整数的范围是[-10,10]。

输出 

输出一行包含一个整数，输出最大乘积。

测试数据 

见代码。

2. 思路分析

基本思想

题目类似背包问题，，其基本思想可以使用动态规划：记住已经解决过的子问题的解。求解，即在遍历数据的时候，将遍历过程中求得的最大乘积记录下来，再继续遍历，通过每次遍历，动态的更新最大乘积，最终求得的就是最终解。

对于此类题目可以定义两个变量max和min，用来记录过程中的最大值和最小值。cur表示计算过程中的当前要计算的数据。每次计算过程中，max取Max.(cur，cur*max，cur*min)中的最大值，min取Min.(cur，cur*max，cur*min)中的最小值。

具体步骤

1） 初始化cur，max，min数据，默认都为第一个数。

2）循环计算数组元素。

3）每次循环max，min都乘以当前元素cur。并用临时变量保存。

4）计算新的max和min并重新赋值。

5）计算过程中新的最大值ans=Max(max，ans)。

6）遍历完后打印ans。

3.代码实现

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4. static long[] nums;// 用来存放数据
  5.  
  6. public static void main(String[] args) {
  7. Scanner scanner = new Scanner(System.in);
  8. int m = scanner.nextInt();
  9. /**
  10.  * long cur 当前数据 long max 最大数 long min 最小数 long ans 最终结果
  11.  */
  12. long cur, max, min, ans = 0;
  13. // 录入数据
  14. for (int i = 0; i < m; i++)
  15. nums[i] = scanner.nextLong();
  16. // 初始化数据，默认都为第一个数
  17. cur = nums[0];
  18. max = nums[0];
  19. min = nums[0];
  20. for (int i = 1; i < m; i++) {
  21. cur = nums[i];// 当前处理的数
  22. long tempmax = max * cur;// 当前数cur乘以最大数max，定义一个临时变量tempmax储存
  23. long tempmin = min * cur;// 当前数cur乘以最小数min，定义一个临时变量tempmin储存
  24. // 新的max在上面三个数中产生
  25. /* 因为max在下一步求min时还要用到，因此这里定义一个临时变量储存newmax */
  26. long newmax = Math.max(cur, Math.max(tempmax, tempmin));
  27. min = Math.min(cur, Math.min(tempmax, tempmin));
  28. max = newmax;// max使用完后，将新的newmax赋值给max
  29. ans = Math.max(ans, max);// 数据处理过程中的答案在ans和max中产生
  30. }
  31. System.out.println(ans);
  32. }
  33.  
  34. }

4.DP小结

注意

动态规划（ Dynamic Programming ）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）
动态规划可以通过填表的方式来逐步推进，得到最优解．

📝4️⃣分治算法实现经典归并排序

1.什么是分治算法

分治法

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。

基本思想

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

2.分治算法的体现:归并排序

归并排序

归并排序（ MERGE － SORT ）是利用归并的思想实现的排序方法，该算法采用经典的分治（ divide - and - conquer )策略（分治法将问题分（ divide ）成一些小的问题然后递归求解，而治（ conquer ）的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之）。

基本思想

流程图（以对数组[8,4,5,7,1,3,6,2]排序为例）

​

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将
[4,5,7,8］和［1,2,3,6］两个已经有序的子序列，合并为最终序列［1,2,3,4,5,6,7,8]，来看下实现步骤。

​

 3.代码实现

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4. /**
  5.  * 归并排序：
  6.  * 
  7.  * 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，
  8.  * 
  9.  * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
  10.  * @author lenovo
  11.  *
  12.  */
  13. public class MergeSort {
  14. public static void main(String[] args) {
  15. int[] a= {5,8,6,3,9,8,7,1,4,21,-8,46};
  16. int[] temp=new int[a.length];
  17. mergeSort(a, 0, a.length-1, temp);
  18. System.out.println(Arrays.toString(a));
  19. }
  20. public static void mergeSort(int[] arr,int left,int right,int[] temp) {
  21. if(left<right) {
  22. int mid=(left+right)/2;
  23. mergeSort(arr, left, mid, temp);
  24. mergeSort(arr, mid+1,right, temp);
  25. merge(arr, left, mid, right, temp);
  26. }
  27. }
  28. public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
  29. int l=left;//左边序列的起始位置
  30. int r=mid+1;//右边序列的起始位置
  31. int t=0;//中间数组的当前元素下标
  32. while(l<=mid &&r<=right ) {//左边或右边没结束
  33. //那边小就将那边的元素放入到临时数组中
  34. if(arr[l]<=arr[r]) {
  35. temp[t++]=arr[l++];
  36. }else {
  37. temp[t++]=arr[r++];
  38. }
  39. }
  40. //while循环结束，说明有一边已经遍历完毕，将另一边剩余的元素放入到临时数组中
  41. while(l<=mid) {
  42. temp[t++]=arr[l++];
  43. }
  44. while(r<=right) {
  45. temp[t++]=arr[r++];
  46. }
  47. //将临时数组中的有序序列copy到原数组中
  48. t=0;
  49. int templeft=left;
  50. while(templeft<=right) {
  51. arr[templeft++]=temp[t++];
  52. }
  53. }
  54. }

📝5️⃣枚举算法经典日期问题详解

枚举算法

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。 枚举法的本质就是从所有候选答案中去搜索正确的解。

使用该算法需要满足两个条件：(1)可预先确定候选答案的数量；(2)候选答案的范围在求解之前必须有一个确定的集合。

枚举算法简单粗暴，他暴力的枚举所有可能，尽可能地尝试所有的方法。虽然枚举算法非常暴力，而且速度可能很慢，但确实我们最应该优先考虑的！因为枚举法变成实现最简单，并且得到的结果总是正确的。

日期问题

题目链接竞码编程_少儿编程培训_NOIP培训_CSP培训_蓝桥杯培训|编程教育机构

题目描述

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。   
比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。   
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入

一个日期，格式是"AA/BB/CC"。  (0 <= A, B, C <= 9)   

输出

输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。

样例

输入
02/03/04
输出

2002-03-04

2004-02-03

2003-03-02

枚举思想

日期问题一般思路都是根据我们的尝试枚举判断日期是否合法等，例如月份1-12，日期1-31或闰年的判断等等。重点在于枚举出所有日期的情况去判断，找出正确答案，避免重复枚举或缺项。

具体代码

  1. package Test;
  2.  
  3. import java.util.Iterator;
  4. import java.util.Scanner;
  5. import java.util.TreeSet;
  6.  
  7. public class _日期问题 {
  8. public static void main(String[] args) {
  9. Scanner scanner = new Scanner(System.in);
  10. String data = scanner.next();
  11. String[] str = data.split("/");//以字符 ' / ' 分割成字符串数组
  12. TreeSet<String> ans = new TreeSet<String>();//存放正确答案的集合，利用set集合去重
  13. // 01/02/03
  14. //枚举三种情况日/月/年 ，年/月/日，月/日/年
  15. String case1 = f(str[0], str[1], str[2]);
  16. String case2 = f(str[2], str[0], str[1]);
  17. String case3 = f(str[2], str[1], str[0]);
  18. //如果case字符串合法则加入结果集
  19. if (case1.length() > 0)
  20. ans.add(case1);
  21. if (case2.length() > 0)
  22. ans.add(case2);
  23. if (case3.length() > 0)
  24. ans.add(case3);
  25. //遍历输出结果
  26. Iterator<String> iterator = ans.iterator();
  27. for (String anser : ans) {
  28. System.out.println(anser);
  29. }
  30. }
  31. /**
  32.  * 判断是否合法，
  33.  * @param year
  34.  * @param month
  35.  * @param day
  36.  * @return 空字符串"" 表示不合法
  37.  */
  38. private static String f(String year, String month, String day) {
  39. int _year = Integer.parseInt(year);
  40. int _month = Integer.parseInt(month);
  41. int _day = Integer.parseInt(day);
  43. if (_year <= 59)//0-59表示2000年以后，要加上2000
  44. _year += 2000;
  45. else//60-99表示1960 - 1999年，加上1900
  46. _year += 1900;
  48. if (_month > 12 || _month < 1)//判断月份是否合法  <1或者>12均不合法
  49. return "";
  51. if (_day > 31 || _day < 1)//判断日期是否合法<1或者>31均不合法
  52. return "";
  53. /**
  54.  * 接下来判断每个月份对应的日期是否合法（前面已经保证月份1-31）
  55.  * 1,3,5,7,8,10,12每个月固定31天，一定合法
  56.  * 因此要判断其他月份的时候是否合法
  57.  */
  58. if(_month == 2) {
  59. //闰年>29不合法
  60. if ((_year % 4 == 0 && _year % 100 != 0) || _year % 400 == 0) {
  61. if (_day > 29)
  62. return "";
  63. }
  64. }else {
  65. //其他月份>30不合法
  66. if (_day > 30)
  67. return "";
  68. }
  69. //月份和日期不足10 要补0
  70. if (_month < 10) {
  71. month = "0" + _month;
  72. }
  73. if (_day < 10) {
  74. day = "0" + _day;
  75. }
  76. return _year + "-" + month + "-" + day;
  77. }
  78. }

📝6️⃣BFS广搜解决迷宫问题

1.例题

题目描述

迷宫由 n 行 m 列的单元格组成，每个单元格要么是空地，要么是障碍物。其中1表示空地，可以走通，2表示障碍物。给定起点坐标startx,starty以及终点坐标endx，endy。现请你找到一条从起点到终点的最短路径长度。

输入

第一行包含两个整数n,m（1<=n,m<=1000）。接下来 n 行，每行包含m个整数（值1或2），用于表示这个二维迷宫。接下来一行包含四个整数startx，starty，endx，endy，分别表示起点坐标和终点坐标。

输出

如果可以从给定的起点到终点，输出最短路径长度，否则输出NO。 

测试数据 

输入

5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
输出

7

 

2. 思路分析

基本思想

这道题属于一道较为经典的BFS图的广度优先搜索算法例题。类似于一个分层搜索的过程，广度优先搜索需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序访问这些结点的邻接结点。即从给定的起点开始向四周扩散，判断是否能够到达终点，如果不能，就继续BFS广搜，直到能够到达终点或者将所有结点遍历完一遍。在搜索前定义一个flag变量用来标记是否到达终点。

具体步骤

1）访问初始结点 p 并标记结点 p 为已访问。

2）结点 p 入队列

3）当队列非空时，继续执行，否则算法结束。

4）出队列取得队头结点 first

5）查找结点 first 的第一个方向的邻接结点 newp 。

6）若结点 first 的邻接结点 newp 不存在，则转到步骤3：否则循环执行以下三个步骤：
        6.1若结点 newp 尚未被访问并且可以走通，则访问结点 newp 并标记为已访问。
        6.2结点 newp 入队列
        6.3查找结点 first 的继 newp 邻接结点后的下个邻接结点 newp ．转到步骤6

代码实现

  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5. //n*m的地图，(startx,starty)起点坐标，(endx,endy)终点坐标
  6. static int n, m, startx, starty, endx, endy;
  7. static int[][] map;//地图
  8. static boolean[][] vistied;//标记当前点是否已经走过
  9. static int[][] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
  10. /*
  11.  * 上下左右移动遍历搜索 1 ,0 表示 x + 1 ，y + 0 向右移动，其他同理 如果为八向连通 则加上, { 1, 1 }, { 1, -1 }, {
  12.  * -1, 1 }, { -1, -1 } 代表斜向移动
  13.  */
  14. public static void main(String[] args) {
  15. Scanner sc = new Scanner(System.in);
  16. n = sc.nextInt();
  17. m = sc.nextInt();
  18. map = new int[n + 2][m + 2];//+2是为了防止点在边界时，四方向移动造成下标出现-1越界。
  19. vistied = new boolean[n + 2][m + 2];
  20. // 录入数据图  下标（1~n）*（1~m）
  21. for (int i = 1; i <= n; i++) {
  22. for (int j = 1; j <= m; j++) {
  23. map[i][j] = sc.nextInt();
  24. }
  25. }
  26. //录入起点和终点坐标
  27. startx = sc.nextInt();
  28. starty = sc.nextInt();
  29. endx = sc.nextInt();
  30. endy = sc.nextInt();
  31. bfs(startx, starty);//BFS广搜
  32. }
  33.  
  34. private static void bfs(int x, int y) {
  35. point p = new point(x, y, 0);//初始化point类封装x，y坐标以及step步数
  36. LinkedList<point> queue = new LinkedList<point>();//需要用到的队列
  37. queue.add(p);//将当前点入队列
  38. vistied[x][y] = true;//标记成已访问
  39. boolean flag = false;//是否达到终点标记
  40. //只要队列不为空，就说明还有路可走
  41. while (!queue.isEmpty()) {
  42. point first = queue.getFirst();//取出队列的第一个点
  43. if (first.x == endx && first.y == endy) {//判断当前点是否与终点坐标重合
  44. System.out.println(first.step);//打印需要走的步数
  45. flag = true;//标记已经到达终点
  46. break;//结束BFS
  47. }
  48. //未到达终点则进行上下左右四个方向移动
  49. for (int i = 0; i < 4; i++) {
  50. //横纵坐标变换实现位置移动
  51. int newx = first.x + step[i][0];
  52. int newy = first.y + step[i][1];
  53. int newstep = first.step + 1;//每一动一次步数要+1
  54. //判断移动后的新位置可以走，并且没走过
  55. if (map[newx][newy] == 1 && vistied[newx][newy] == false) {
  56. point newp = new point(newx, newy, newstep);//封装数据
  57. queue.add(newp);//入队列
  58. vistied[newx][newy] = true;//标记已经走过
  59. }
  60. }
  61. queue.removeFirst();//四个方向判断完成后，要将队首元素出列
  62. }
  63. if (!flag)//如果无法到达终点提示
  64. System.out.println("NO");
  65. }
  66. }
  67. //定义一个位置点的class，方便封装数据入队列
  68. class point {
  69. int x;
  70. int y;
  71. int step;//从起点走到当前点需要走的步数
  72.  
  73. public point(int x, int y, int step) {
  74. this.x = x;
  75. this.y = y;
  76. this.step = step;
  77. }
  78. }

3.BFS小结

求解思路：

将队首结点可拓展的点入队，如果没有可拓展的点，将队首结点出队。重复以上步骤，直到到达目标位置或者队列为空。

注意

bfs先找到的一定是最短的。但是如果是加权边的话这样就会出问题了，bfs传回的是经过 边数 最少的解，但是因为加权了，这个解到根节点的 距离 不一定最短。 比如1000+1000是只有两段，1+1+1+1有4段，由于bfs返回的经过边数最少的解，这里会返回总长度2000的那个解，显然不是距离最短的路径 。BFS 运用到了队列。

📝7️⃣DFS连通块问题

 前言  

连通块问题属于图的深度优先遍历dfs，本文章通过求连通块的个数简单案例，来介绍dfs解决连通块问题。

例题链接

竞码编程_少儿编程培训_NOIP培训_CSP培训_蓝桥杯培训|编程教育机构

例题中给到的是char类型地图，' . ' 代表不通路，' W ' 代表可连通，具体情况根据题目给的进行修改。

什么是连通块

如图整个表格为一个5*5二维数组，用来表示整个地图，白色填充为二维数组下标，最外层浅绿色代表地图的边界（为什么创建边界下文有提到），较为深颜色的为存放数据的二维数组，即下标（1~4）*（1~4）。而颜色最深的块就是连通块，图中给出的就有三个连通块（上下左右连通，不考虑斜对连通）。

具体思路

除了行数列数以及开辟二维数组地图，还需要一个与地图同样大小的二维数组visitied，用来表示当前节点是否已经被访问过了。具体思路同图的dfs类似，当遍历到一个结点为1表示该节点可以连通（根据题目给的可能不同）并且没被访问过就进行深度遍历。

具体看代码。

代码

  1. import java.util.Scanner;
  2. /**
  3.  * 注意本例题中 
  4.  * char[][]map地图   值为' . ' 代表不通，' W '代表可以连通
  5.  * int[][] visitied访问标记，初始值0未访问，1已访问
  6.  * @author lenovo
  7.  *
  8.  */
  9.  
  10. public class Main {
  11. static int n,m,ans;
  12. static char[][] map;
  13. static int[][] vistied;
  14. static int[][] step= {{1,0},{0,1},{-1,0},{0,-1}};
  15. /*
  16.  * 上下左右移动遍历搜索
  17.  *  1 ,0 表示 x + 1 ，y + 0 向右移动，其他同理
  18.  *  如果为八向连通 则加上, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } 代表斜向移动
  19.  */
  20. public static void main(String[] args) {
  21. Scanner sc=new Scanner(System.in);
  22. n=sc.nextInt();
  23. m=sc.nextInt();
  24. map=new char[n+2][m+2];
  25. vistied=new int[n+2][m+2];
  26. //初始化地图，创建边界
  27. for (int i = 0; i <= n+1; i++) {
  28. map[i][0] = '.';
  29. map[i][m+1] = '.';
  30. }
  31. for (int i = 0; i <= m+1; i++) {
  32. map[0][i] = '.';
  33. map[n+1][i] = '.';
  34. }
  35. //录入数据图（1~n）*（1~m）
  36. for (int i = 1; i <= n; i++) {
  37. String s=sc.next();
  38. int k=0;
  39. for (int j = 1; j <= m; j++) {
  40. map[i][j]=s.charAt(k++);
  41. }
  42. }
  43. //从1-n 1-m一次遍历整张数据图
  44. for (int x = 1; x <=n; x++) {
  45. for (int y =1; y <=m; y++) {
  46. //如果当前节点为'W'可以连通 并且为被访问则说明存在一个连通块
  47. if(vistied[x][y] ==0 && map[x][y] == 'W') {
  48. ans++;//连接块数量+1
  49. vistied[x][y] = 1;//当前节点标记为已经访问，以免重复判断
  50. dfs(x,y);//进行深度优先遍历，将与其连通的所有节点都标记为已经访问。
  51. //遍历完后从(1,1)到下一个节点(1,2)继续遍历，一次类推，直到所有节点全遍历完。
  52. }
  53. }
  54. }
  55. System.out.println(ans);
  56. }
  57. private static void dfs(int x, int y) {
  58. /**
  59.  * step.length - 1 = 3
  60.  * 0 1 2 3 四步代表上下左右均走一遍
  61.  */
  62. for (int i = 0; i <=(step.length - 1); i++) {
  63. int newx=x+step[i][0]; //x移动
  64. int newy=y+step[i][1];//y移动
  65. //如果移动后的节点 为 'W'可连通，并且未访问，则以移动后的节点为起点继续移动
  66. if(map[newx][newy] =='W' && vistied[newx][newy] ==0) {
  67. vistied[newx][newy] = 1;//标记为已访问
  68. dfs( newx, newy);
  69. }
  70. }
  71. }
  73. }

注意

       在实际应用时，为了防止当结点位于边界时，例如结点下标为(0,0)，其左结点下标为(-1,0),这时-1会越界。因此开辟二维数组的大小总是比题目中给到的n*m多两行，即开辟（n+2）*(m+2)大小的二维数组。

📝8️⃣DFS方格分割

问题描述

6x6的方格，沿着格子的边线剪开成两部分。 
要求这两部分的形状完全相同。 
试计算： 
一共有多少种不同的分割方法。 
注意：旋转对称的属于同一种分割法。 
请提交该整数，不要填写任何多余的内容或说明文字。

具体思路

既然要求剪下来的两部分完全相同，那么剪的路线一定通过图的中心点，并且分割线一定关于中心点对称。因此可以以图中的交点为元素，将6*6的方格转换成7*7的网格，从中心点开始对称的向边界dfs深度遍历，即从中心点开始向上下左右标记的同时，对称的位置也要标记。例如（3,3）->(4,3)的同时，(3,3) -> (2,3)也要标记。当遍历到网格的边界即剪完成，然后进行回溯。

代码

  1.  
  2. public class _方格分割 {
  3. static int[][] map = new int[7][7];//网格线
  4. static int[][] v = new int[7][7];//标记当前点是否访问过，即当前位置是否已经剪过
  5. static int ans = 0;//最终答案
  6. static int[][] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//上下左右坐标变换
  7.  
  8. static void dfs(int x, int y) {
  9. // 首先判断是否到达边界
  10. if (x == 0 || y == 0 || x == 6 || y == 6) {
  11. ans++;
  12. return;
  13. }
  14. // 对称标记已经剪过该位置
  15. v[x][y] = 1;
  16. v[6 - x][6 - y] = 1;
  17. // 依次上下左右剪
  18. for (int i = 0; i < 4; i++) {
  19. int newx = x + step[i][0];
  20. int newy = y + step[i][1];
  21. // 判断当前位置是否剪过并且没有越界
  22. if (v[newx][newy] == 0 && newx >= 0 && newx <= 6 && newy >= 0 && newy <= 6) {
  23. dfs(newx, newy);// 向下一步剪
  24. }
  25. }
  26. // 剪完过后记得回溯
  27. v[x][y] = 0;
  28. v[6 - x][6 - y] = 0;
  29. }
  30.  
  31. public static void main(String[] args) {
  32. dfs(3, 3);// 从(3,3)开始中心对称位置剪
  33. System.out.println(ans / 4);// 因为中心对称剪的话，每条路线可绕中心点旋转一周，因此一条路线重复了4次，所以要将最后结果/4
  34. }
  35. }

📝9️⃣迪杰斯特拉 (Dijkstra)算法求最短路径问题

算法介绍

迪杰斯特拉（ Dijkstra ）算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。

应用实例

算法步骤

1）设置出发顶点为 v ，顶点集合 VfvI ,v2, vi .), v 到 V 各顶点的距离构成距离集合 Dis , Dis ( dI ,d2, di .), Dis 集合记录着 v 到图中各顶点的距离（到自身可以看作0, v 到 vi 距离对应为 di )
2）从 Dis 中选择值最小的 di 并移出 Dis 集合，同时移出 V 集合中对应的项点 vi ，此时的 v 到 vi 即为最短路径
3）更新 Dis 集合，更新规则为：比较 v 到 V 集合中顶点的距离值，与 v 通过 vi 到 V 集合中顶点的距离值，保留
值较小的一个（同时也应该更新顶点的前驱节点为 vi ，表明是通过 vi 到达的）
4）重复执行两步骤，直到最短路径顶点为目标顶点即可结束。

代码实现

  1.  
  2. import java.util.Arrays;
  3.  
  4. public class _最短路{
  5. static int[] vis;//标记已经访问的顶点  0未访问 1 访问
  6. static int[] dis;//出发顶点到各个下标对应顶点的最短距离
  7. static int[] pre;//每个下标对应的上一个顶点下标
  8. static char[] vertex;//顶点
  9. static int[][] matrix;//邻接矩阵
  10. public static void main(String[] args) {
  11. vertex= new char[]{'A','B','C','D','E','F','G'};
  12. matrix = new int[vertex.length][vertex.length];
  13. chushihua(matrix);//初始化邻接矩阵
  14. djstl(vertex.length,6);//调用算法
  15. }
  16. public static void djstl(int length,int start) {
  17. vis=new int[length];
  18. dis=new int[length];
  19. pre=new int[length];
  20. Arrays.fill(dis, 9999);//初始化距离为较大值
  21. dis[start] = 0;//初始化出发顶点到自身的距离0
  23. /*  先将起始点到与其连通的顶点的路径及pre前一个顶点进行更新*/
  24. update(start);
  25. //在以与起始点相连的顶点为起点  更新距离和路径
  26. for (int i = 1; i < vertex.length; i++) {
  27. int minIndex = -1;
  28. int mindis=9999;
  29. //找到一个最短路径
  30. for (int j = 0; j < vertex.length; j++) {
  31. if(vis[j]==0 && dis[j] < mindis) {
  32. minIndex = j;
  33. mindis = dis[j];
  34. }
  35. }
  36. vis[minIndex] = 1;
  37. update(minIndex);//继续更新
  38. }
  40. System.out.println(Arrays.toString(dis));
  41. }
  42. /**
  43.  * 以index顶点向下查找！！！以起点start到index附近的邻接结点的最短路径!!!
  44.  * @param index
  45.  */
  46. public static void update(int index) {
  47. vis[index] = 1;//index标记为已访问
  48. int len= 0;//len：从start顶点到index顶点的距离+上从index再到i顶点的距离
  49. //循环遍历每个邻接结点顶点，找到真正意义上的最短路径
  50. for (int i = 0; i < matrix[index].length; i++) {
  51. //记录从start顶点到index顶点的距离+上从index再到i顶点的距离
  52. len = dis[index] + matrix[index][i];
  53. //将dis[i] 即从start直接到i 的距离 与len进行比较 
  54. if(vis[i] == 0 && len < dis[i]) {
  55. dis[i] = len;//更新最短路径
  56. pre[i] = index;//更新前置顶点
  57. }
  58. }
  59. }
  60. /**
  61.  * 初始化邻接矩阵
  62.  * @param matrix
  63.  */
  64. public static void chushihua(int[][] matrix) {
  65. final int N = 9999;
  66. matrix[0]=new int[]{N,5,7,N,N,N,2};
  67. matrix[1]=new int[]{5,N,N,9,N,N,3};
  68. matrix[2]=new int[]{7,N,N,N,8,N,N};
  69. matrix[3]=new int[]{N,9,N,N,N,4,N};
  70. matrix[4]=new int[]{N,N,8,N,N,5,4};
  71. matrix[5]=new int[]{N,N,N,4,5,N,6};
  72. matrix[6]=new int[]{2,3,N,N,4,6,N};
  73. }
  74. }
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览42745 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪