89Trillion 春招 java 笔试

开着腾讯会议，写两道leetcode的题 :

1 LC547 . 省份数量

class Solution {
public:
    int ans = 0  , n ;
    vector<vector<int>> g ;
    vector<bool> st ;
    void bfs(int i){
        st[i] = true ;
        for(int j : g[i]){
            if(st[j]==false){
                st[j] = true ;
                bfs(j) ;
            }
        }
    }
    int findCircleNum(vector<vector<int>>& nt) {
        n = nt.size() ;// 200
        g.resize(n+1) ;
        st.resize(n+1) ;
        for(int i=0;i<n;i++){// 建图
            st[i+1] = false ;// 没访问过
            // i->j ;
            for(int j=0;j<n&&j!=i;j++){
                if(nt[i][j]==1){
                    g[i+1].push_back(j+1) ;
                    g[j+1].push_back(i+1) ;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(st[i]==false){
                bfs(i) ;
                ans ++ ;
            }
        }
        return ans ;
    }
};

当场写的，有时间限制 ， 属于是想到什么写什么了 , 一个简单的bfs ,当然dfs也可以

2 . 529 扫雷游戏

看了很久题目才看懂 :

int xx[] = {-1,0,1,-1,1,-1,0,1} ;
int yy[] = {-1,-1,-1,0,0,1,1,1} ;

class Solution {
public:

    int n , m ;
    vector<vector<char>> ans ;
    void fs(int x ,int y){
        if(ans[x][y]=='M'){
            ans[x][y] = 'X' ;
        }else if(ans[x][y]=='E'){
            // 有无相邻地雷
            int cnt = 0 ;
            for(int j=0;j<8;j++){// 求相邻的地雷数
                int nx = x+xx[j] , ny = y+yy[j] ;
                if(nx<0||nx>=m||ny<0||ny>=n) continue ;
                if(ans[nx][ny]=='M'||ans[nx][ny]=='X') cnt ++ ;
            }
            if(cnt>0) ans[x][y] = (char)(cnt+'0') ;
            else {// 没有xl
                ans[x][y] = 'B' ;
                for(int j=0;j<8;j++){
                    int nx = x+xx[j] , ny = y+yy[j] ;
                    if(nx<0||nx>=m||ny<0||ny>=n) continue ;
                    fs(nx,ny) ;
                }
            }
        }else {
            return ;
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& a, vector<int>& ck) {
        ans = a ;
        m = ans.size() ; n = ans[0].size() ;
        int x = ck[0] , y = ck[1] ;
        fs(x,y) ;
        return ans ;
    }
};