4399秋招java岗笔试

切换屏幕会有提醒，但没有限制次数。

有单选题，简答题，编程题。比较简单。

相关知识点

1. vlan之间的通信；路由器，中继器，网桥的区别。
2. SQL语句
3. 场景题：高并发、高可用性的抽卡系统，如何设计架构，如何确保概率，如何实现保底机制。

编程题

第一题

有若干个包间，以及若干组客人在等候，怎样让成功进入包间的客人的组数最多。

例如，包间大小为2,3,3，客人有：1,3，3,4，则最多3组客人能进入。

import java.util.*;

public class Main2{
    public static void get (List<Integer>queue,List<Integer>dining) {
        Collections.sort(queue);
        Collections.sort(dining);
        int len_q=queue.size(),len_d=dining.size(),point=0,ans=0;
        for(int family:queue){
            while(point<len_d &&family>dining.get(point)){
                point++;
            }
            if(point>=len_d){
                break;//说明完全放不下了
            }
            ans++;point++;//指针移动是因为当前房间已经被使用了
        }
        System.out.println(ans);
    }
}

（后知后觉，如果题目换成 让进入成功进入包间的客人的人数最多，那么解法就不是这样。大致思路是下面这样

public static int maxGuests(List<Integer> queue, List<Integer> dining) {
        // 对包间大小和客人数量进行排序
        Collections.sort(dining);
        Collections.sort(queue);

        int guestCount = 0;
        int guestIndex = 0;

        // 遍历每个包间
        for (int roomSize : dining) {
            // 找到一个适合当前包间大小的客人组
            if (guestIndex < queue.size() && queue.get(guestIndex) <= roomSize) {
                guestCount += queue.get(guestIndex); // 增加该组的客人数
                guestIndex++; // 移动到下一组客人
            }
        }

        return guestCount;
    }

第二题

用数组来表示一个n*n大小的图，例如[1,0][0,1]，你可以把1个0变成1（也可以不改变），你需要让连通图的大小最大。

例如，在这个图中把1个0换成1的话，连通图的大小可以变成3

import java.util.*;

public class Main3{
    static int count=0;
    static HashSet<Integer> to_put=new HashSet();
    public static void main (String[] args) {
        int[][] array=new int[4][4];
        array[0]=new int[]{1,1,0,0};
        array[1]=new int[]{1,1,0,0};
        array[2]=new int[]{0,0,1,1};
        array[3]=new int[]{0,0,0,1};
        int n=array.length;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if(array[i][j]==1){
                    dfs(array,i,j);
                    put_cnt(array);
                    count=0;to_put.clear();
                }
            }
        int minn=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                minn=Math.min(minn,array[i][j]);
            }
        System.out.println(-minn+1);

    }
    private static void dfs(int[][] array,int row,int col){
        array[row][col]=2;//表示已经访问
        count++;
        int n=array.length;
        int[] drx=new int[]{-1,0,1,0};
        int[] dry=new int[]{0,1,0,-1};
        for(int i=0;i<4;i++){
            int n_row=row+drx[i];
            int n_col=col+dry[i];
            if(n_row>=0&&n_row<n&&n_col>=0&&n_col<n){
                if(array[n_row][n_col]==1){
                    dfs(array,n_row,n_col);
                }else  if(array[n_row][n_col]<=0){
                    to_put.add(n_row*n+n_col);
                }
            }
        }
    }
    private static void put_cnt(int[][] array){
        int n=array.length;
        for(int position:to_put){
            int i=position/n;
            int j=position%n;
            array[i][j]-=count;
        }
    }
}