2022/08/21字节后端笔试
只会做2，3题...（代码写的烂，仅供参考吧）
第二题是走迷宫，找不能到达的位置个数，主要思路是BFS，从出口开始逆向查找所有可以到达的点，标记为可以访问
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
cin.nextLine();
int startI = 0, startJ = 0;
char[][] grid = new char[n][];
for (int i = 0; i < n; i++) {
String line = cin.nextLine();
grid[i] = line.toCharArray();
for (int j = 0; j < m; j++) {
if (grid[i][j] == 'O') {
startI = i; startJ = j;
}
}
}
System.out.println(countLeft(grid, n, m, startI, startJ));
}
public static int countLeft(char[][] grid, int n, int m, int i, int j) {
Queue<int[]> q = new ArrayDeque<>();
boolean[][] visited = new boolean[n][m];
q.offer(new int[]{i,j});
visited[i][j] = true;
while (!q.isEmpty()) {
int[] currPoint = q.poll();
int x = currPoint[0], y = currPoint[1];
// 上，上一个字母必须是D或者.
if (x - 1 >= 0 && !visited[x - 1][y]) {
int newX = x - 1, newY = y;
if (grid[newX][newY] == '.' || grid[newX][newY] == 'D') {
q.offer(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
// 下，上一个字母必须是U或者.
if (x + 1 < n && !visited[x + 1][y]) {
int newX = x + 1, newY = y;
if (grid[newX][newY] == '.' || grid[newX][newY] == 'U') {
q.offer(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
// 左，上一个字母必须是R或者.
if (y - 1 >= 0 && !visited[x][y - 1]) {
int newX = x, newY = y - 1;
if (grid[newX][newY] == '.' || grid[newX][newY] == 'R') {
q.offer(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
// 右，上一个字母必须是L或者.
if (y + 1 < m && !visited[x][y + 1]) {
int newX = x, newY = y + 1;
if (grid[newX][newY] == '.' || grid[newX][newY] == 'L') {
q.offer(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
}
int cannotReach = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
if (!visited[r][c])
cannotReach++;
}
}
return cannotReach;
}
}
第三题是创意广告，判断是否匹配，题目描述虽然看起来复杂，但本质是通配符匹配问题，参见LeetCode的通配符匹配
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
cin.nextLine();
String pattern = cin.nextLine();
StringBuilder sb = new StringBuilder();
int idx = 0, len = pattern.length();
while (idx < len) {
char ch = pattern.charAt(idx);
if (ch == '{') {
while (idx < len && pattern.charAt(idx) != '}')
idx++;
idx++;
sb.append('*');
if (idx < len)
sb.append(pattern.charAt(idx));
idx++;
continue;
}
sb.append(ch);
idx++;
}
String p = sb.toString();
for (int i = 0; i < n; i++) {
String s = cin.nextLine();
if (match(s, p))
System.out.println("True");
else
System.out.println("False");
}
}
public static boolean match(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*')
dp[0][j] = true;
else
break;
}
for (int i = 1; i <= m; i++) {
char a = s.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char b = p.charAt(j - 1);
if (b == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else if (a == b) {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[m][n];
}
}
