科大讯飞8.20笔试编程题
第一题
第一个数字是1/2，第二个数字是2/3，每个数的分子是前一个数的分母，分母是前一个数的分子+分母，求前n个的累加和
/*
* 查找1900-2021有多少个2
* */
public class ToFindNumberK {
public static void main(String[] args) {
System.out.println(toFindNumberK(2));
}
// 暴力破解法
public static int toFindNumberK(int k){
// 计数
int count = 0;
//遍历1900-2021所有的数
for (int i = 1900; i <=2021 ; i++) {
int x = i;
while (x!=0){
// 取到各个位上的数
int res = x % 10;
if (res==2){
count++;
}
x /= 10;
}
}
return count;
}
}
第二题
判断字符串合法性 key - value间不能存在空格 =左边只能是小写字母，右边可以是字母、数组、空格，但收割字符不能是空格
public class StringValidity {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
// 字符串转换字符数组方便操作
char[] ch = str.toCharArray();
// 如果前三个位置出现不合法直接返回
if (ch[0] < 'a' || ch[0] > 'z' || ch[1] != '=' || ch[2] == ' '){
System.out.println(false);
return;
}
// 遍历等号右边的字符是否合法
for (int i = 3; i < ch.length; i++) {
if (ch[i] == ' ' || ch[i] >= 'a' && ch[i] <= 'z' || Character.isDigit(ch[i]))continue;
// 说明等号右边存在出了小写字母、数组、空格外的字符直接返回false
System.out.println(false);
return;
}
System.out.println(true);
}
} 第三题
迷宫找礼物，求找到礼物的最短路径
给定一个4x4的二维数组，0代表能走，1代表不能走，8代表宝藏的位置，入口是二维数组的边界位置的任一个不为0的位置，求从人口到宝藏位置的最短路径，并输出路径
public class MazeShortestPath {
public static void main(String[] args) {
int[][] maze = {
{0,1,1,1},
{0,0,0,1},
{1,0,8,1},
{1,0,1,1}
};
// 记录迷宫的长宽
int row = maze.length;
int column = maze[0].length;
// 遍历数组，找到迷宫中的礼物位置
int i = 0,j = 0;
look :for (i = 0; i < row; i++) {
for (j = 0; j < column; j++) {
if (maze[i][j] == 8){
break look;
}
}
}
// 用两个队列，一个队列是保存当前到达的点，另个保存路径
Deque<int[]> queue = new ArrayDeque<>();
Deque<ArrayList<Point>> paths = new ArrayDeque<>();
// 初始化起始点
queue.addLast(new int[]{i,j});
// 初始化路径点集合
ArrayList<Point> points = new ArrayList<>();
points.add(new Point(i,j));
paths.addLast(points);
// 用一个数组扩展四个方向
int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};
while (!queue.isEmpty()){
// 抛出当前到达的点和路径集合
int[] pop = queue.remove();
ArrayList<Point> remove = paths.remove();
// 如果最先到达举证边沿就是出去了，第一个路径自然就是最短路径
if (pop[0] == 0 || pop[0] == row-1 || pop[1] == 0 || pop[1] == column-1){
// 直接返回路径集合
System.out.println(remove);
return;
}
// 遍历四个方向，向四个方向扩展
for (int[] dir : direction) {
// 计算新坐标
int x = pop[0] + dir[0];
int y = pop[1] + dir[1];
// 判断是否越界
if (x >= 0 && x < row && y >= 0 && y < column && maze[x][y] == 0){
// 将扩展点放入队列
queue.addLast(new int[]{x,y});
// 生成新的路径集合
ArrayList<Point> newPoints = new ArrayList<>(remove);
// 将点放入列表中，向前插入，因为这里是要返回入口到礼物的路径
newPoints.add(0,new Point(x,y));
paths.addLast(newPoints);
// 将走过的点做标记
maze[x][y] = -1;
}
}
}
// 没有直接返回礼物点，说明礼物 就在迷宫边线上
System.out.println(points);
}
}
// 点类。记录路径上的各个点的坐标
class Point{
int x;
int y;
public Point(int x,int y){
this.x = x;
this.y = y;
}
} 
