牛客.单词搜索
刚开始我就想是搜索，但是不清楚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 }
