ISBN號

ISBN號碼_牛客題霸_牛客網

算法原理

模擬，根據題意模擬就可以了，注意一下余數為10的時候要特別判斷一下是不是X就行了

代碼

import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);char[] s = scan.next().toCharArray();int sum = 0, count = 0;for(int i = 0; i < s.length - 1; i++) {if(i == 1 || i == 5 || i == 11) continue;count++;sum += (s[i] - '0') * count;}boolean flg = false;if(s[s.length - 1] == 'X') flg = (sum % 11 == 10);  //特別判斷一下為10的情況else flg = (sum % 11 == s[s.length - 1] - '0');if(flg) System.out.println("Right");else {if(sum % 11 == 10) s[s.length - 1] = 'X';else s[s.length - 1] = Character.forDigit(sum % 11, 10);StringBuffer sb = new StringBuffer();for(char x: s) sb.append(x);System.out.println(sb.toString());}}
}

kotori和迷宮

kotori和迷宮

算法原理

迷宮類最短路徑dfs問題的擴展，原理都差不多，就是最后輸出的時候單獨要多記錄一下出口數量而已

代碼

import java.util.*;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static int N = 35;public static int x1, y1;  //記錄起點位置public static int n, m;public static char[][] arr = new char[N][N];public static int[][] dist = new int[N][N];public static int[] dx = {0, 0, -1, 1};public static int[] dy = {1, -1, 0, 0};public static void bfs() {for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)dist[i][j] = -1;Queue<int[]> q = new LinkedList<>();q.add(new int[]{x1, y1});dist[x1][y1] = 0;while(!q.isEmpty()) {int[] tmp = q.poll();int a = tmp[0], b = tmp[1];for(int i = 0; i < 4; i++) {//遍歷該點的上下左右的四個點int x = a + dx[i], y = b + dy[i];//坐標是合法的，該點沒有記錄過，且不是墻if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1 && arr[x][y] != '*') {dist[x][y] = dist[a][b] + 1;if(arr[x][y] != 'e') {q.add(new int[]{x, y});}}}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);m = scan.nextInt(); n = scan.nextInt();for(int i = 0; i < m; i++) {char[] tmp = scan.next().toCharArray();for(int j = 0; j < n; j++) {arr[i][j] = tmp[j];if(arr[i][j] == 'k') {x1 = i; y1 = j;}}}bfs();int count = 0, res = 1000;    //count記錄出口個數for(int i = 0; i < m; i++)for(int j = 0; j < n; j++) {if(arr[i][j] == 'e' && dist[i][j] != -1) {    //為-1說明無法到達count++;res = Math.min(res, dist[i][j]);}}if(count == 0) System.out.println("-1");else System.out.println(count + " " + res);}
}

矩陣最長遞增路徑

矩陣最長遞增路徑_牛客題霸_牛客網

算法原理

遞歸 + 記憶搜索

代碼

import java.util.*;public class Solution {public static int m, n;public static int[] dx = {0, 0, -1, 1};public static int[] dy = {1, -1, 0, 0};public static int[][] memo = new int[1010][1010];public int dfs(int[][] matrix, int i, int j) {if (memo[i][j] != -1) return memo[i][j];int len = 1;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])len = Math.max(len, 1 + dfs(matrix, x, y));}memo[i][j] = len;return len;}public int solve (int[][] matrix) {// write code herem = matrix.length;n = matrix[0].length;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {memo[i][j] = -1;}int res = 1;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {res = Math.max(res, dfs(matrix, i, j));}return res;}
}