#华为机试# 5.11华为机试

#华为机试#
5.11华为机试：
1、第一行输入一个数N（1<=N<=10000)表示数组有n个元素，第二行输入为数组的元素，数组中所有值不同。输出每个数比右边大的个数。
样例输入：
4
7 2 8 9
样例输出：
1 0 0 0
样例输入：
5
7 5 9 4 3
样例输出：
3 2 2 1 0
解答：leetcode有原题（困难）......
2、找出围棋中黑子与白子的活子数。所谓活子数，就是有大于2个气的棋子。一个棋子在棋盘上，与它直线紧邻的空点是这个棋子的“气”。直线紧邻的点上如果有同色棋子存在，这些棋子就相互连接成一个不可分割的整体。直线紧邻的点上如果有异色棋子存在，此处的气便不存在。棋子如失去所有的气，就不能在棋盘上存在。
输入说明：输入只有一行，第一个字符输入的棋盘大小，后续按行列输入棋子情况，其中W为白子，B为黑子，N为空。
样例输入：
3WWWNBBBNN
样例输出：
B 3 W 0
说明：
棋盘为
W W W
N B B
B N N
因此 W白色棋子没有活子（所有子的气为1）黑色棋子有三个活子（每个棋子都有大于等于两个气）。

思路：暴力搜索代码-BFS

二重循环遍历矩阵，使棋子在同色范围内扩张，遇到同色就加入队列，遇到异色不做处理，遇到空位则气+1，气>=2即可判定矩阵的该位置上的棋子为活子。

import java.util.*;
public class HJ511 {
    static class Point{
        int x;
        int y;
         Point(int x,int y){this.x = x;this.y = y;}
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = str.charAt(0)-'0';
        char[][] chs = new char[n][n];
        int index = 1;
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                chs[i][j] = str.charAt(index++);
            }
        }
        int w=0;
        int b = 0;
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(bfs(i,j,chs,new boolean[n][n])){
                    switch (chs[i][j]){
                        case 'W':w++;break;
                        case 'B':b++;break;
                    }
                }
            }
        }
        System.out.println("B "+b+" W "+w);
    }
    public static boolean bfs(int i,int j,char[][]chs,boolean visit[][]){
        Queue<Point> que = new LinkedList<>();
        int count = 0;
        char c = chs[i][j];
        que.offer(new Point(i,j));
        while(que.size()!=0){
            Point p = que.poll();
            if(p.x+1<chs.length&&chs[p.x+1][p.y]==c&&!visit[p.x+1][p.y]){
                que.offer(new Point(p.x+1,p.y));
                visit[p.x+1][p.y] = true;
            }
            if(p.x-1>=0&&chs[p.x-1][p.y]==c&&!visit[p.x-1][p.y]){
                que.offer(new Point(p.x-1,p.y));
                visit[p.x-1][p.y] = true;
            }
            if(p.y+1<chs[0].length&&chs[p.x][p.y+1]==c&&!visit[p.x][p.y+1]){
                que.offer(new Point(p.x,p.y+1));
                visit[p.x][p.y+1] = true;
            }
            if(p.y-1>=0&&chs[p.x][p.y-1]==c&&!visit[p.x][p.y-1]){
                que.offer(new Point(p.x,p.y-1));
                visit[p.x][p.y-1] = true;
            }
            if(p.x+1<chs.length&&chs[p.x+1][p.y]=='N'&&!visit[p.x+1][p.y]){
                visit[p.x+1][p.y]= true;
                count++;
            }
            if(p.x-1>=0&&chs[p.x-1][p.y]=='N'&&!visit[p.x-1][p.y]){
                visit[p.x-1][p.y] = true;
                count++;
            }
            if(p.y+1<chs[0].length&&chs[p.x][p.y+1]=='N'&&!visit[p.x][p.y+1]){
               visit[p.x][p.y+1] = true;
                count++;
            }
            if(p.y-1>=0&&chs[p.x][p.y-1]=='N'&&!visit[p.x][p.y-1]){
                visit[p.x][p.y-1] = true;
                count++;
            }
            if(count >=2)return true;
        }
        return false;
    }
}

3.设备连线：输入两个整数n k,n代表有n个设备需要连接成一个圆环，k代表这n个设备需要从0到(2^k) - 1中取出（可以取同种类的设备）。设备连接时，相邻设备号的二进制数如果满足了同或为1会发生爆炸。求这n个设备连成圆环不发生爆炸的种数。（这道题没做，有无大佬分享思路？）

#华为机试##春招##实习##笔试题目##面经##华为##笔经##Java#