欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

百度算法题

程序员文章站 2023-12-28 09:35:34
...

百度题目

记录一下自己秋招时候的脑残算法日常吧

9.14号百度第一题

小明小红下围棋,小明执黑棋(1),小红执白棋(0),当局面是

1011
1101
1101
1111

时候,0被1给吃掉,即局面变为

1011
1111
1111
1111

输入:
第一行输出N
接下来输入N*N的矩阵
即:

4
1011
1101
1101
1111

输出:

1011
1111
1111
1111

(如果我题目没有说清楚的话,大家可以去看leetcode130题,这两道题是一样的)

题解:
1.输入问题
百度这道题的输入很有意思,一般在给输入二维矩阵的时候,每个数字之间会有个空格,即是

1 0 1 1
1 1 0 1
1 1 0 1
1 1 1 1

这种格式,这个时候只需要用split(" ")就可以将二维数组中的各个数字进行遍历保存

但是百度给的输入是没有空格的,所以在将每一行保存成字符串之后,直接使用substring或者charAt将每一个字符读出,之后再转换成int存入二维数组。

		Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());


        int[][] arr = new int[n][n];
        String[] strArr = new String[n];

        for (int i = 0;i < n;i++){
            strArr[i] = sc.nextLine();
        }




        for (int i = 0;i < n;i++){
            String numbers = strArr[i];
            System.out.println(numbers);
            for (int j = 0;j < n;j++){
                arr[i][j] = Integer.parseInt(String.valueOf(numbers.charAt(j)));
                System.out.println(arr[i][j]);
            }
        }

或者:

		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();


        int[][] arr = new int[n][n];
        String[] strArr = new String[n];

        for (int i = 0;i < n;i++){
            strArr[i] = sc.next();
        }




        for (int i = 0;i < n;i++){
            String numbers = strArr[i];
            System.out.println(numbers);
            for (int j = 0;j < n;j++){
                arr[i][j] = Integer.parseInt(String.valueOf(numbers.charAt(j)));
                System.out.println(arr[i][j]);
            }
        }

这里要注意,如果在读完第一行的N之后使用nextLine去读取之后的二维数组,一定也要使用nextLine读取第一行的N,因为如果先使用nextInt读取第一行的N,此时光标还是停留在N后面,之后当第一次使用nextLine进行读取时,依然读取的是第一行,即此时读取的是一个空字符串。

解决方法就是第二个代码块里写的,当使用nextInt读取完N之后,可使用next读取接下来的一行,读取时会自动换行。

2.暴力dfs问题
我的第一思路就是,遍历这个二维数组中的每一个数字,对每一个数字的周围的数字进行判断,如果有一个方向上的数字和当前数字相同,就继续往这个方向递归,直到找到不同数字(被包围)或者到达边界(不被包围)
代码为(用时过长):

package baidu;

import java.util.ArrayList;
import java.util.Scanner;

public class problem1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();


        int[][] arr = new int[n][n];
        String[] strArr = new String[n];

        for (int i = 0;i < n;i++){
//            strArr[i] = sc.nextLine();
            strArr[i] = sc.next();
        }




        for (int i = 0;i < n;i++){
            String numbers = strArr[i];
            for (int j = 0;j < n;j++){
                arr[i][j] = Integer.parseInt(String.valueOf(numbers.charAt(j)));
            }
        }

        demo1 d1 = new demo1();
        
        for (int i = 0;i < n;i++){
            for (int j = 0;j < n; j++){
                boolean results = d1.qipan(arr,i,j,arr[i][j],n);
                if (results == true){
                    if (arr[i][j] == 1){
                        arr[i][j] = 0;
                    }else {
                        arr[i][j] = 1;
                    }
            }
                System.out.print(arr[i][j]);
        }
            System.out.print("\n");
            
        }
    }
}

class demo1{
    int[][] turns = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    public boolean qipan(int[][] arr,int x,int y,int num,int n){
        int count = 0;
        for (int i = 0;i < turns.length;i++){
            int x_t = turns[i][0];
            int y_t = turns[i][1];
            int x_temp = x + x_t;
            int y_temp = y + y_t;
            if (x_temp < 0 || x_temp >= n || y_temp < 0 || y_temp >= n){
                return false;
            }
            if (arr[x_temp][y_temp] != num){
                count++;
            }
            if (arr[x_temp][y_temp] == num){
                boolean re = rearch(arr,x_t,y_t,x_temp,y_temp,num,n);
                if (re == true){
                    count++;
                }
            }
        }
        return count==4;
    }

    public boolean rearch(int[][] arr,int x_t,int y_t,int x_temp,int y_temp,int num,int n){
        int t_x = x_temp+x_t;
        int t_y = y_temp+y_t;
        if (t_x < 0 || t_x >= n || t_y < 0 || t_y >= n){
            return false;
        }
        if (arr[t_x][t_y] != num){
            return true;
        }else {
            rearch(arr,x_t,y_t,t_x,t_y,num,n);
        }

        return false;
    }
}

3.正确方法:
先处理边界,举个例子,如果边界上的1能直接或者间接达到的1一定不会被围起来。

package baidu;

import java.util.Scanner;

public class problem1_new {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
        int n = Integer.parseInt(sc.nextLine());


        int[][] arr = new int[n][n];
        String[] strArr = new String[n];

        for (int i = 0;i < n;i++){
            strArr[i] = sc.nextLine();
//            strArr[i] = sc.next();
        }




        for (int i = 0;i < n;i++){
            String numbers = strArr[i];
            for (int j = 0;j < n;j++){
                arr[i][j] = Integer.parseInt(String.valueOf(numbers.charAt(j)));
            }
        }

        
        boolean[][] results = new boolean[n][n];
        demo1_new dn = new demo1_new();
        dn.find(arr,n,results);

        for (int i = 0;i < n; i++){
            for (int j = 0;j < n;j++){
                if (results[i][j] == false){
                    int temp_num = arr[i][j];
                    if (temp_num == 1){
                        arr[i][j] = 0;
                    }else {
                        arr[i][j] = 1;
                    }
                }
                System.out.print(arr[i][j]);
            }
            System.out.print("\n");
        }
    }
}
class demo1_new{
    public void find(int[][] arr,int n,boolean[][] results){

        for (int i = 0;i < n;i++){
            int temp_num1 = arr[0][i];
            int temp_num2 = arr[i][n-1];
            find_same(temp_num1,0,i,n,arr,results);
            find_same(temp_num2,i,n-1,n,arr,results);
        }

        for (int i = 1;i < n-1;i++){
            int temp_num3 = arr[i][0];
            int temp_num4 = arr[n-1][i];
            find_same(temp_num3,i,0,n,arr,results);
            find_same(temp_num4,n-1,i,n,arr,results);
        }

        }

    public void find_same(int temp_num,int x,int y,int n,int[][] arr,boolean[][] results){
        if (x >= n || x < 0 || y >= n || y < 0 || arr[x][y] != temp_num){
            return;
        }
        if (results[x][y] == true){
            return;
        }else {
            results[x][y] = true;

            find_same(temp_num,x+1,y,n,arr,results);
            find_same(temp_num,x-1,y,n,arr,results);
            find_same(temp_num,x,y+1,n,arr,results);
            find_same(temp_num,x,y-1,n,arr,results);
        }
}
}

上一篇:

下一篇: