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