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

枚举算法

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。

枚举法的本质就是从所有候选答案中去搜索正确的解。

使用该算法需要满足两个条件：(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或闰年的判断等等。

重点在于枚举出所有日期的情况去判断，找出正确答案，避免重复枚举或缺项。

具体代码

package Test;

import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class _日期问题 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String data = scanner.next();
		String[] str = data.split("/");//以字符 ' / ' 分割成字符串数组
		TreeSet ans = new TreeSet();//存放正确答案的集合，利用set集合去重
		// 01/02/03
		//枚举三种情况日/月/年 ，年/月/日，月/日/年
		String case1 = f(str[0], str[1], str[2]);
		String case2 = f(str[2], str[0], str[1]);
		String case3 = f(str[2], str[1], str[0]);
		//如果case字符串合法则加入结果集
		if (case1.length() > 0)
			ans.add(case1);
		if (case2.length() > 0)
			ans.add(case2);
		if (case3.length() > 0)
			ans.add(case3);
		//遍历输出结果
		Iterator iterator = ans.iterator();
		for (String anser : ans) {
			System.out.println(anser);
		}
	}
	/**
	 * 判断是否合法，
	 * @param year
	 * @param month
	 * @param day
	 * @return 空字符串"" 表示不合法
	 */
	private static String f(String year, String month, String day) {
		int _year = Integer.parseInt(year);
		int _month = Integer.parseInt(month);
		int _day = Integer.parseInt(day);
		
		if (_year <= 59)//0-59表示2000年以后，要加上2000
			_year += 2000;
		else			//60-99表示1960 - 1999年，加上1900
			_year += 1900;
		
		if (_month > 12 || _month < 1)//判断月份是否合法  <1或者>12均不合法
			return "";
		
		if (_day > 31 || _day < 1)//判断日期是否合法<1或者>31均不合法
			return "";
		/**
		 * 接下来判断每个月份对应的日期是否合法（前面已经保证月份1-31）
		 * 1,3,5,7,8,10,12每个月固定31天，一定合法
		 * 因此要判断其他月份的时候是否合法
		 */
		if(_month == 2) {
			//闰年>29不合法
			if ((_year % 4 == 0 && _year % 100 != 0) || _year % 400 == 0) {
				if (_day > 29)
					return "";
			}
		}else {
			//其他月份>30不合法
			if (_day > 30)
				return "";
		}
		//月份和日期不足10 要补0
		if (_month < 10) {
			month = "0" + _month;
		}
		if (_day < 10) {
			day = "0" + _day;
		}
		return _year + "-" + month + "-" + day;
	}
}

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

代码实现

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	//n*m的地图，(startx,starty)起点坐标，(endx,endy)终点坐标
	static int n, m, startx, starty, endx, endy;
	static int[][] map;//地图
	static boolean[][] vistied;//标记当前点是否已经走过
	static int[][] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	/*
	 * 上下左右移动遍历搜索 1 ,0 表示 x + 1 ，y + 0 向右移动，其他同理 如果为八向连通 则加上, { 1, 1 }, { 1, -1 }, {
	 * -1, 1 }, { -1, -1 } 代表斜向移动
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n + 2][m + 2];//+2是为了防止点在边界时，四方向移动造成下标出现-1越界。


		vistied = new boolean[n + 2][m + 2];
		// 录入数据图  下标（1~n）*（1~m）
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		//录入起点和终点坐标
		startx = sc.nextInt();
		starty = sc.nextInt();
		endx = sc.nextInt();
		endy = sc.nextInt();
		bfs(startx, starty);//BFS广搜
	}

	private static void bfs(int x, int y) {
		point p = new point(x, y, 0);//初始化point类封装x，y坐标以及step步数
		LinkedList queue = new LinkedList();//需要用到的队列
		queue.add(p);//将当前点入队列
		vistied[x][y] = true;//标记成已访问
		boolean flag = false;//是否达到终点标记
		//只要队列不为空，就说明还有路可走
		while (!queue.isEmpty()) {
			point first = queue.getFirst();//取出队列的第一个点
			if (first.x == endx && first.y == endy) {//判断当前点是否与终点坐标重合
				System.out.println(first.step);//打印需要走的步数
				flag = true;//标记已经到达终点
				break;//结束BFS
			}
			//未到达终点则进行上下左右四个方向移动
			for (int i = 0; i < 4; i++) {
				//横纵坐标变换实现位置移动
				int newx = first.x + step[i][0];
				int newy = first.y + step[i][1];
				int newstep = first.step + 1;//每一动一次步数要+1
				//判断移动后的新位置可以走，并且没走过
				if (map[newx][newy] == 1 && vistied[newx][newy] == false) {
					point newp = new point(newx, newy, newstep);//封装数据
					queue.add(newp);//入队列
					vistied[newx][newy] = true;//标记已经走过
				}
			}
			queue.removeFirst();//四个方向判断完成后，要将队首元素出列
		}
		if (!flag)//如果无法到达终点提示
			System.out.println("NO");
	}
}
//定义一个位置点的class，方便封装数据入队列
class point {
	int x;
	int y;
	int step;//从起点走到当前点需要走的步数

	public point(int x, int y, int step) {
		this.x = x;
		this.y = y;
		this.step = step;
	}
}

3.BFS小结 求解思路：

将队首结点可拓展的点入队，如果没有可拓展的点，将队首结点出队。

重复以上步骤，直到到达目标位置或者队列为空。

注意

bfs先找到的一定是最短的。

但是如果是加权边的话这样就会出问题了，bfs传回的是经过 边数 最少的解，但是因为加权了，这个解到根节点的 距离 不一定最短。

比如1000+1000是只有两段，1+1+1+1有4段，由于bfs返回的经过边数最少的解，这里会返回总长度2000的那个解，显然不是距离最短的路径 。

BFS 运用到了队列。

 前言  

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

例题链接

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

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

什么是连通块

如图整个表格为一个5*5二维数组，用来表示整个地图，白色填充为二维数组下标，最外层浅绿色代表地图的边界（为什么创建边界下文有提到），较为深颜色的为存放数据的二维数组，即下标（1~4）*（1~4）。

而颜色最深的块就是连通块，图中给出的就有三个连通块（上下左右连通，不考虑斜对连通）。

具体思路

除了行数列数以及开辟二维数组地图，还需要一个与地图同样大小的二维数组visitied，用来表示当前节点是否已经被访问过了。

具体思路同图的dfs类似，当遍历到一个结点为1表示该节点可以连通（根据题目给的可能不同）并且没被访问过就进行深度遍历。

具体看代码。

代码

import java.util.Scanner;
/**
 * 注意本例题中 
 * char[][]map地图   值为' . ' 代表不通，' W '代表可以连通
 * int[][] visitied访问标记，初始值0未访问，1已访问
 * @author lenovo
 *
 */

public class Main {
	static int n,m,ans;
	static char[][] map;
	static int[][] vistied;
	static int[][] step= {{1,0},{0,1},{-1,0},{0,-1}};
	/*
	 * 上下左右移动遍历搜索
	 *  1 ,0 表示 x + 1 ，y + 0 向右移动，其他同理
	 *  如果为八向连通 则加上, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } 代表斜向移动
	 */
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new char[n+2][m+2];
		vistied=new int[n+2][m+2];
		//初始化地图，创建边界
		for (int i = 0; i <= n+1; i++) {
			map[i][0] = '.';
			map[i][m+1] = '.';
		}
		for (int i = 0; i <= m+1; i++) {
			map[0][i] = '.';
			map[n+1][i] = '.';
		}
		//录入数据图（1~n）*（1~m）
		for (int i = 1; i <= n; i++) {
			String s=sc.next();
			int k=0;
			for (int j = 1; j <= m; j++) {
				map[i][j]=s.charAt(k++);
			}
		}
		//从1-n 1-m一次遍历整张数据图
		for (int x = 1; x <=n; x++) {
			for (int y =1; y <=m; y++) {
				//如果当前节点为'W'可以连通 并且为被访问则说明存在一个连通块
				if(vistied[x][y] ==0 && map[x][y] == 'W') {
					ans++;//连接块数量+1
					vistied[x][y] = 1;//当前节点标记为已经访问，以免重复判断
					dfs(x,y);//进行深度优先遍历，将与其连通的所有节点都标记为已经访问。


					//遍历完后从(1,1)到下一个节点(1,2)继续遍历，一次类推，直到所有节点全遍历完。


				}
			}
		}
		System.out.println(ans);
	}
	private static void dfs(int x, int y) {
		/**
		 * step.length - 1 = 3
		 * 0 1 2 3 四步代表上下左右均走一遍
		 */
		for (int i = 0; i <=(step.length - 1); i++) {
			int newx=x+step[i][0]; //x移动
			int newy=y+step[i][1];//y移动
			//如果移动后的节点 为 'W'可连通，并且未访问，则以移动后的节点为起点继续移动
			if(map[newx][newy] =='W' && vistied[newx][newy] ==0) {
				vistied[newx][newy] = 1;//标记为已访问
				dfs( newx, newy);
			}
		}
	}
	
}

注意

       在实际应用时，为了防止当结点位于边界时，例如结点下标为(0,0)，其左结点下标为(-1,0),这时-1会越界。

因此开辟二维数组的大小总是比题目中给到的n*m多两行，即开辟（n+2）*(m+2)大小的二维数组。

问题描述

6x6的方格，沿着格子的边线剪开成两部分。

 
要求这两部分的形状完全相同。

 
试计算： 
一共有多少种不同的分割方法。

 
注意：旋转对称的属于同一种分割法。

 
请提交该整数，不要填写任何多余的内容或说明文字。

具体思路

既然要求剪下来的两部分完全相同，那么剪的路线一定通过图的中心点，并且分割线一定关于中心点对称。

因此可以以图中的交点为元素，将6*6的方格转换成7*7的网格，从中心点开始对称的向边界dfs深度遍历，即从中心点开始向上下左右标记的同时，对称的位置也要标记。

例如（3,3）->(4,3)的同时，(3,3) -> (2,3)也要标记。

当遍历到网格的边界即剪完成，然后进行回溯。

代码

public class _方格分割 {
	static int[][] map = new int[7][7];//网格线
	static int[][] v = new int[7][7];//标记当前点是否访问过，即当前位置是否已经剪过
	static int ans = 0;//最终答案
	static int[][] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//上下左右坐标变换

	static void dfs(int x, int y) {
		// 首先判断是否到达边界
		if (x == 0 || y == 0 || x == 6 || y == 6) {
			ans++;
			return;
		}
		// 对称标记已经剪过该位置
		v[x][y] = 1;
		v[6 - x][6 - y] = 1;
		// 依次上下左右剪
		for (int i = 0; i < 4; i++) {
			int newx = x + step[i][0];
			int newy = y + step[i][1];
			// 判断当前位置是否剪过并且没有越界
			if (v[newx][newy] == 0 && newx >= 0 && newx <= 6 && newy >= 0 && newy <= 6) {
				dfs(newx, newy);// 向下一步剪
			}
		}
		// 剪完过后记得回溯
		v[x][y] = 0;
		v[6 - x][6 - y] = 0;
	}

	public static void main(String[] args) {
		dfs(3, 3);// 从(3,3)开始中心对称位置剪
		System.out.println(ans / 4);// 因为中心对称剪的话，每条路线可绕中心点旋转一周，因此一条路线重复了4次，所以要将最后结果/4
	}
}

算法介绍

迪杰斯特拉（ 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）重复执行两步骤，直到最短路径顶点为目标顶点即可结束。

代码实现

import java.util.Arrays;

public class _最短路{
	static int[] vis;//标记已经访问的顶点  0未访问 1 访问
	static int[] dis;//出发顶点到各个下标对应顶点的最短距离
	static int[] pre;//每个下标对应的上一个顶点下标
	static char[] vertex;//顶点
	static int[][] matrix;//邻接矩阵
	public static void main(String[] args) {
		vertex= new char[]{'A','B','C','D','E','F','G'};
		matrix = new int[vertex.length][vertex.length];
		chushihua(matrix);//初始化邻接矩阵
		djstl(vertex.length,6);//调用算法
	}
	public static void djstl(int length,int start) {
		vis=new int[length];
		dis=new int[length];
		pre=new int[length];
		Arrays.fill(dis, 9999);//初始化距离为较大值
		dis[start] = 0;//初始化出发顶点到自身的距离0
		
		/*  先将起始点到与其连通的顶点的路径及pre前一个顶点进行更新*/
		update(start);
		//在以与起始点相连的顶点为起点  更新距离和路径
		for (int i = 1; i < vertex.length; i++) {
			int minIndex = -1;
			int mindis=9999;
			//找到一个最短路径
			for (int j = 0; j < vertex.length; j++) {
				if(vis[j]==0 && dis[j] < mindis) {
					minIndex = j;
					mindis = dis[j];
				}
			}
			vis[minIndex] = 1;
			update(minIndex);//继续更新
		}
		
		System.out.println(Arrays.toString(dis));
	}
	/**
	 * 以index顶点向下查找！！！以起点start到index附近的邻接结点的最短路径!!!
	 * @param index
	 */
	public static void update(int index) {
		vis[index] = 1;//index标记为已访问
		int len= 0;//len：从start顶点到index顶点的距离+上从index再到i顶点的距离
		//循环遍历每个邻接结点顶点，找到真正意义上的最短路径
		for (int i = 0; i < matrix[index].length; i++) {
			//记录从start顶点到index顶点的距离+上从index再到i顶点的距离
			len = dis[index] + matrix[index][i];
			//将dis[i] 即从start直接到i 的距离 与len进行比较 
			if(vis[i] == 0 && len < dis[i]) {
				dis[i] = len;//更新最短路径
				pre[i] = index;//更新前置顶点
			}
		}
	}
	/**
	 * 初始化邻接矩阵
	 * @param matrix
	 */
	public static void chushihua(int[][] matrix) {
		final int N = 9999;
		matrix[0]=new int[]{N,5,7,N,N,N,2};
		matrix[1]=new int[]{5,N,N,9,N,N,3};
		matrix[2]=new int[]{7,N,N,N,8,N,N};
		matrix[3]=new int[]{N,9,N,N,N,4,N};
		matrix[4]=new int[]{N,N,8,N,N,5,4};
		matrix[5]=new int[]{N,N,N,4,5,N,6};
		matrix[6]=new int[]{2,3,N,N,4,6,N};
	}
}