day04笔试练习

1.Fibonacci数列

题目链接：Fibonacci数列_牛客题霸_牛客网

题目思路：

定义 a b c 三个变量 使 c 一直加到比 n  大的最近的斐波那契数 此时比较 c 和 b 哪个数离得最近就好

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = 0,b = 1, c = 1;
        while( c <= n){
            a = b;
            b = c;
            c = a + b;
        }
        System.out.println(Math.min(c-n,n-b));
    }

2.单词搜索

题目链接：单词搜索_牛客题霸_牛客网

    static int m;
    static int n;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static boolean[][] vis;
    static char[] word;

    public static boolean exist (String[] board,String _word){
        m = board.length;
        n = board[0].length();
        vis = new boolean[m][n];
        word = _word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i].charAt(j) == word[0]){
                    if(dfs(board,i,j,0) == true) return true;
                }
            }
        }
        return false;
    }
    public static boolean dfs(String[] board,int i,int j,int pos){
        if(pos == word.length - 1){
            return true;
        }
        vis[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k],y = j + dy[k];
            //board[x].charAt(y) == word[pos + 1] 判断下一个位置是否单词相同
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x].charAt(y) == word[pos + 1]){
                if(dfs(board,x,y,pos+1))
                    return true;
            }
        }
        vis[i][j] = false;
        return false;
    }

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] board = new String[12];
        for (int i = 0; i < 3; i++) {

            for (int j = 0; j < 4; j++) {
                String  x = sc.next();
            }

        }
       exist(board,"XDEE");
    }

3.杨辉三角

题目链接：杨辉三角_牛客题霸_牛客网

解题思路：

   public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] dp = new int[n+1][n+1];
        dp[1][1] = 1;
        for (int i = 2; i <= n ; i++) { //表示行 第一行已经定义为 1了所以从第二行开始初始化
            for (int j = 1; j <= i; j++) {  // j表示行  在第几行就有几列
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= i ; j++) {
              StringBuffer ret = new StringBuffer();
              int len = Integer.toString(dp[i][j]).length();
                for (int k = 0; k < 5 - len ; k++) {
                    ret.append(" ");
                }
                System.out.print(ret.toString() + dp[i][j]);
            }
            System.out.println();
        }
    }