JAVA算法练习day4
一、ISBN号码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int res = 0,start = 1;;
for (int i = 0; i < str.length()-1; i++) {
if(str.charAt(i)=='-') continue;
res += Integer.parseInt(Character.toString(str.charAt(i)))*start;
start++;
}
res %= 11;
String result = new StringBuilder(str).deleteCharAt(str.length()-1).toString();
if(res == 10){
result = result + "X";
}else {
result = result + res ;
}
if(result.equals(str)){
System.out.println("Right");
}else {
System.out.println(result);
}
}
}思路：
1.从控制台读取一个字符串 str（例如 "0-306-40615-7"）。
2.计算该字符串中除最后一个字符外所有数字（跳过连字符 -）的加权和，权重从 1 开始依次递增。
3.用加权和对 11 取模，得到一个新的校验码（10 用 X 表示）。将原字符串去掉最后一个字符，再拼接新校验码，形成新字符串。
4.比较新字符串与原字符串，若相同输出 "Right"，否则输出新字符串（即修正后的结果）。
1.从控制台读取一个字符串 str
Scanner sc = new Scanner(System.in);
String str = sc.next(); // 读取一行输入，遇空格或换行结束
int res = 0, start = 1; // res: 加权和, start: 当前权重2.计算该字符串中除最后一个字符外所有数字（跳过连字符 -）的加权和，权重从 1 开始依次递增。
方法一：
遍历字符串前length-1个字符，排除最后一个校验位
for (int i = 0; i < str.length()-1; i++) {
if(str.charAt(i)=='-') continue; // 跳过连字符
res += Integer.parseInt(Character.toString(str.charAt(i))) * start;
start++;
}遇到连接符‘-’时用continue跳过
str.char(i) -->从字符串中取出索引 i 处的字符
Integer.parseInt(Character.toString(str.charAt(i)))先把字符串中取出来的字符转化为String类型，用Character.toString( )
再把String类型转化为Int类型，取到整数，用Interger.parseInt( )
Interger.parseInt( )是把字符串转化为int类型整数的静态方法
方法二：
int num = str.charAt(i) - '0';
res += num * start;这个方法可以直接把字符串变成整数，比上面的方法更简洁清晰
3.用加权和对 11 取模，得到一个新的校验码（10 用 X 表示）。
res %= 11; // 模 11 得到新校验码数值
String result = new StringBuilder(str).deleteCharAt(str.length()-1).toString();
// 去掉原字符串最后一个字符（原校验位）
if(res == 10){
result = result + "X";
} else {
result = result + res;
}String result = new StringBuilder(str).deleteCharAt(str.length()-1).toString();
（1）由于需要修改字符串，所以借用StringBuilder方法
new StringBuiler(str)，创建一个StringBuilder类型的对象，用原字符串str初始化其内容。
（2）然后调用 StringBuilder 的 deleteCharAt (int index)方法，删掉最后一个字符
（3）把修改后StringBuiler对象转换回不可变的String对象，赋值给 result
将原字符串去掉最后一个字符，再拼接新校验码，形成新字符串。
4.比较新字符串与原字符串，若相同输出 "Right"，否则输出新字符串（即修正后的结果）。
if(result.equals(str)){
System.out.println("Right");
} else {
System.out.println(result);
}二、kotori和迷宫
考点：深度优先搜索
import java.util.*;
public class Main {
static class Pair {
int x, y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读取迷宫大小
int n = in.nextInt();
int m = in.nextInt();
char[][] a = new char[n + 1][m + 1];
int beginx = 0, beginy = 0;
for (int i = 1; i <= n; i++) {
String line = in.next();
for (int j = 1; j <= m; j++) {
a[i][j] = line.charAt(j - 1);
if (a[i][j] == 'k') {
beginx = i;
beginy = j;
}
}
}
// BFS
int[][] dist = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(dist[i], 1, m + 1, -1);
}
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0, 1, 0};
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(beginx, beginy));
dist[beginx][beginy] = 0;
while (!q.isEmpty()) {
Pair cur = q.poll();
int x1 = cur.x, y1 = cur.y;
for (int i = 0; i < 4; i++) {
int x2 = x1 + dx[i];
int y2 = y1 + dy[i];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m &&
a[x2][y2] != '*' && dist[x2][y2] == -1) {
dist[x2][y2] = dist[x1][y1] + 1;
if (a[x2][y2] == 'e') {
continue; // 出口不加入队列，不继续扩展
}
q.offer(new Pair(x2, y2));
}
}
}
// 统计出口
int cnt = 0;
int minDist = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 'e' && dist[i][j] != -1) {
cnt++;
if (dist[i][j] < minDist) {
minDist = dist[i][j];
}
}
}
}
if (cnt == 0) {
System.out.println(-1);
} else {
System.out.println(cnt + " " + minDist);
}
}
}1.输入处理
int n = in.nextInt();
int m = in.nextInt();
char[][] a = new char[n + 1][m + 1];
int beginx = 0, beginy = 0;
for (int i = 1; i <= n; i++) {
String line = in.next();
for (int j = 1; j <= m; j++) {
a[i][j] = line.charAt(j - 1);
if (a[i][j] == 'k') {
beginx = i;
beginy = j;
}
}
}char[n + 1][m + 1]为什么要n+1和m+1? 用空间代替清晰性。为了使用 1‑based 索引（行号和列号从 1 开始计数），而不是默认的 0‑based。
String line = in.next();读取当前按行的字符串。先按字符串读取，再用charAt（int index）方法读取每一个数
if (a[i][j] == 'k') {
beginx = i;
beginy = j;
}读取格子的起点并标记
二、BFS最短路径搜素
int[][] dist = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(dist[i], 1, m + 1, -1);
}
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0, 1, 0};
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(beginx, beginy));
dist[beginx][beginy] = 0;-
dist数组记录每个格子从起点出发的最短步数，初始化为-1表示未访问。 -
Arrays.fill(dist[i], 1, m+1, -1)填充索引[1, m]范围内的元素（起始索引包含，结束索引不包含）。 -
方向数组
dx, dy对应左、下、右、上四个方向（顺序无关紧要）。 -
使用队列进行 BFS，起点入队，距离设为 0。
核心 BFS 循环
while (!q.isEmpty()) {
Pair cur = q.poll();
int x1 = cur.x, y1 = cur.y;
for (int i = 0; i < 4; i++) {
int x2 = x1 + dx[i];
int y2 = y1 + dy[i];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m &&
a[x2][y2] != '*' && dist[x2][y2] == -1) {
dist[x2][y2] = dist[x1][y1] + 1;
if (a[x2][y2] == 'e') {
continue; // 出口不加入队列，不继续扩展
}
q.offer(new Pair(x2, y2));
}
}
}-
每次弹出队首节点
(x1, y1)，遍历四个相邻格子。 -
如果相邻格子合法（在边界内）、不是墙
'*'、且未访问过（dist == -1），则：-
更新其距离为当前距离 +1。
-
关键：若该格子是出口
'e'，则不将其加入队列（通过continue跳过入队操作）。
原因：出口是目标点，不需要再从出口继续向外扩展，这能提高效率，且避免无意义的搜索。 -
否则，将格子入队以便继续 BFS。
-
-
BFS 的特点保证第一次到达某个格子时，
dist记录的就是最短步数。
四、统计结果
int cnt = 0;
int minDist = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 'e' && dist[i][j] != -1) {
cnt++;
if (dist[i][j] < minDist) {
minDist = dist[i][j];
}
}
}
}-
遍历整个迷宫，找出所有出口（
a[i][j] == 'e'）且dist不为 -1（即可达）的格子。 -
累加可达出口数量
cnt，并更新最小距离minDist。
五、输出
if (cnt == 0) {
System.out.println(-1);
} else {
System.out.println(cnt + " " + minDist);
}-
若无出口可达，输出
-1。 -
否则输出
cnt和minDist，中间用空格分隔。
六、代码优点
-
BFS 正确性：对于无权图，BFS 保证第一次访问即最短路径。
-
边界处理简洁：数组下标从 1 开始，避免了多处
-1判断。 -
出口不入队优化：减少不必要的扩展，尤其当出口较多时能提升效率。
-
距离与访问标记合一：
dist数组既记录距离，又充当visited标记。 -
输入鲁棒：使用
in.next()逐行读取字符串，正确处理换行。
更多推荐
11
0- 0
已为社区贡献6条内容
所有评论(0)