笔试训练2

牛客.单词搜索 

刚开始我就想是搜索，但是不清楚bfs还是dfs更好，我尝试了bfs但是队列存东西，没有我想象的那么好写，所以我决定试试dfs 

import java.util.*;public class Solution {static int m = 0;static  int n = 0;static int []dx = {1, -1, 0, 0};static int []dy = {0, 0, 1, -1};static boolean [][]vis;static char[]word;/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param board string字符串一维数组* @param word string字符串* @return bool布尔型*/public static boolean exist (String[] board, String _word) {m = board.length;n = board[0].length();word = _word.toCharArray();char[][]a = new char[m][n];vis = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i].charAt(j) == word[0]) {vis[i][j] = true;    //标记if (dfs(board, i, j, 0) == true) {return true;};vis[i][j]=false;   //回溯}}}return false;}private static boolean dfs(String[] board, int i, int j, int pos) {if (pos == word.length - 1) {return true;}for (int ii = 0; ii < 4; ii++) {int x = i + dx[ii];int y = j + dy[ii];
//注意这里是pos+1传递的是第几个下标if (x >= 0 && x < m && y >= 0 && y < n && board[x].charAt(y) == word[pos + 1] &&vis[x][y] == false) {vis[x][y] = true;     //标记if ( dfs(board, x, y, pos + 1) == true) {return true;};vis[x][y] = false;    //回溯}}return false;}
}

牛客.杨辉三角

还想起来我第一次处理这个的时候，怎么想也不知道怎么写，那时候我是大一下学期刚学数据结构，然后到了今天，虽然我不是特别厉害，但是还是有所进步的，这个问题的想法，由于它是由上一行的这个和上一行的左边这个加一起，我的想法瞬间就想起来了dp，于是使用了dp处理这个问题

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int a = scanner.nextInt();int[][]b = new int[a + 1][a + 1];for (int i = 0; i <= a; i++)b[i][0] = 1;for (int i = 1; i <= a; i++) {for (int j = 1; j <= i; j++) {b[i][j] = b[i - 1][j - 1] + b[i - 1][j];}}for (int i = 0; i < a; i++) {for (int j = 0; j <= i; j++) {if (b[i][j] != 0) {StringBuffer ret = new StringBuffer();int len = Integer.toString(b[i][j]).length();for (int k = 0; k < 5 - len; k++)ret.append(" ");System.out.print(ret.toString() + b[i][j]);}}if (i + 1 != a)System.out.println();}}
}

牛客.游游的you

输入输出是因为我想熟悉一下模版，这道题，不用也可以。就是看连续的o就-1,先找对应的you，再去找oo 

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.BufferedWriter;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static void main(String[] args)throws  IOException {Read scanner = new Read();int a1 = scanner.nextInt();int[][] a = new int[a1][3];int[] dp = new int[a1];int[] count = new int[a1];for (int i = 0; i < a1; i++) {int min = Integer.MAX_VALUE;for (int j = 0; j < 3; j++) {a[i][j] = scanner.nextInt();min = Math.min(a[i][j], min);}count[i] = a[i][1];dp[i] = min;}int sum = 0;for (int i = 0; i < a1; i++) {if (count[i] - dp[i] - 1 <= 0)sum = dp[i] * 2;else sum = dp[i] * 2 + (count[i] - dp[i] - 1) ;System.out.println(sum);}// 注意 hasNext 和 hasNextLine 的区别}
}
class Read {StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next()throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}String nextLine()throws IOException {return bf.readLine();}int nextInt() throws IOException {return Integer.parseInt(next());}long nextLong()throws IOException {return Long.parseLong(next());}double nextDouble()throws IOException {return Double.parseDouble(next());}
}

牛客.腐烂的苹果

常规的bfs,使用vis来标记，然后就直接宽度搜索，用一个队列，放循环里面，然后，分两块往下面遍历(因为这是1s，所以把它放到sz出去，因为这个sz的作用是用来，统计一个烂苹果能感染多少组好苹果，然后把这些好苹果放到里面) 

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param grid int整型ArrayList<ArrayList<>>* @return int整型*/static  int []dx = {0, 0, 1, -1};static  int []dy = {1, -1, 0, 0};public static int rotApple (ArrayList<ArrayList<Integer>> grid) {int m = grid.size();int n = grid.get(0).size();int ret = 0;boolean[][]vis = new boolean[m][n];Queue<int[]>q = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid.get(i).get(j) == 2) {q.add(new int[] {i, j});vis[i][j] = true;}}}while (!q.isEmpty()) {int sz = q.size();while (sz > 0) {int []k = q.poll();sz--;for (int i = 0; i < 4; i++) {int x = dx[i] + k[0];int y = dy[i] + k[1];if (x >= 0 && x < m && y >= 0 && y < n && grid.get(x).get(y) == 1 &&vis[x][y] == false) {q.add(new int[] {x, y});vis[x][y] = true;}}}ret++;}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid.get(i).get(j) == 1 && vis[i][j] == false) {return -1;}}}return ret - 1;}// write code her
}