笔试训练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>
     * @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
}