Leetcode第418周赛

第一题

连接二进制表示可形成的最大数值

因为数组的个数有限，直接将数字转为二进制字符串，通过数组的自定义排序方法进行排序（根据题意是拼接而不是二进制相加），最后将排序后的结果依次拼接，转为10进制。

class Solution {
    public int maxGoodNumber(int[] nums) {
        String[] binaryReprs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            binaryReprs[i] = Integer.toBinaryString(nums[i]);
        }

      
        Arrays.sort(binaryReprs, (a, b) -> (b + a).compareTo(a + b));

 
        StringBuilder largestBinary = new StringBuilder();
        for (String binary : binaryReprs) {
            largestBinary.append(binary);
        }

      
        return Integer.parseInt(largestBinary.toString(), 2);
    }
}

第二题

3310. 移除可疑的方法

认真读题，就是先将点边顺序存储起来，然后根据以bug点出发做深度搜索，全部标记为异常，做好之后，再判断剩余点是否存在到异常点的情况，如果存在就返回全部，否则返回剩余点。

class Solution {
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<List<Integer>> graph = new ArrayList<>();
        List<Integer> reT = new ArrayList<>();
        for(int i = 0 ;i<n;i++){
            reT.add(i);
            graph.add(new ArrayList<>());
        }
        for(int[] invocation : invocations){
            
            graph.get(invocation[0]).add(invocation[1]);

        }

        boolean[] sus = new boolean[n];
        dfs(k, graph, sus);

        for(int i=0;i<n;i++){
            if(!sus[i]){
                for(int  next: graph.get(i)){
                    if(sus[next]){
                        return reT;
                    }
                }
            }
        }

        List<Integer> re = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(!sus[i]){
                re.add(i);
            }
        }
        return re;
    }

    void dfs(int k,  List<List<Integer>> graph, boolean[] sus){
        sus[k] = true;
        for(int next: graph.get(k)){
            if(!sus[next]){
                dfs(next, graph, sus);
            }
        }
    }
}

第三题

3311. 构造符合图结构的二维矩阵

这个题，没看到样例二想当然认为矩阵是根n*根n，最后没时间修改。我的思路是，先将点边信息存储起来，得到所有点的相临点个数。根据相邻点个数能确定矩阵的形状，进行矩阵初始化。从相邻点个数最低的点开始做dfs，直到遍历所有的点。在做dfs的过程中要用到回溯。

class Solution {
        int[][] nums;
    // 用于打印邻接表的方法
    private static void printGraph(List<List<Integer>> graph) {
        for (int i = 0; i < graph.size(); i++) {
            System.out.println("节点 " + i + " 的邻接节点: " + graph.get(i));
        }
    }
    private int[] findBestDimensions(int n) {
        int r = 1, c = n; // 从最坏的 1 x n 尝试开始
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                // i 是 n 的约数，i 和 n/i 可以组成合法矩阵
                r = i;
                c = n / i;
            }
        }
        return new int[] { r, c }; // 返回行列组合
    }


    public int[][] constructGridLayout(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int[] edge: edges){
            int to  = edge[0];
            int from  = edge[1];
            graph.get(to).add(from);
            graph.get(from).add(to);
        }


        int start = 0;
        int max = graph.get(0).size();
        int min = graph.get(0).size();
        for(int i=1;i<graph.size();i++){
            if(graph.get(i).size() < graph.get(start).size()) {
                start = i;
                min = graph.get(i).size();
            }
            max = Math.max(max, graph.get(i).size());
            min = Math.min(min, graph.get(i).size());
        }



        boolean[] user = new boolean[n];


        if(min==1){
            nums = new int[1][n];
        }else if(max==3){
            nums = new int[n/2][2];
        }else {
            int[] dims = findBestDimensions(n); // 找到最优的 (rows, cols) 组合
            int rows = dims[0];
            int cols = dims[1];
            nums = new int[rows][cols];
        }

//        nums = new int[(int)Math.sqrt(n)][(int)Math.sqrt(n)];





        for (int[] row : nums) Arrays.fill(row, -1);
        int[][] nums_nodes = new int[(int)Math.sqrt(n)][(int)Math.sqrt(n)];
        for(int i=0;i<nums_nodes.length;i++){
            for(int j=0;j<nums_nodes[i].length;j++){
                // 如果是角落（四个）
                if ((i == 0 && j == 0) ||               // 左上角
                        (i == 0 && j == nums_nodes.length - 1) ||        // 右上角
                        (i == nums_nodes.length - 1 && j == 0) ||        // 左下角
                        (i == nums_nodes.length - 1 && j == nums_nodes.length - 1)) { // 右下角
                    nums_nodes[i][j] = 2; // 角落有2个邻居
                }

                // 如果是边界但不是角落
                else if (i == 0 || i == nums_nodes.length - 1 || j == 0 || j == nums_nodes.length - 1) {
                    nums_nodes[i][j] = 3; // 边界上有3个邻居
                }

                // 如果是中间的非边界区域
                else {
                    nums_nodes[i][j] = 4; // 中间有4个邻居
                }
            }
        }


        dfs(start, user, graph,nums_nodes, 0, 0);
        return nums;
    }

    boolean dfs(int node, boolean[] user,List<List<Integer>> graph ,int[][] nums_nodes, int i, int j){

        if(i < 0 || i >= nums.length || j < 0 || j >= nums[0].length || nums[i][j] != -1 || graph.get(node).size() != nums_nodes[i][j] || user[node] ) return false;

        nums[i][j]=node;
        user[node] = true;
        boolean success = true;
        for(int next: graph.get(node)){
            if (!user[next]) {
                // 尝试从 (i, j) 的四个方向进行 DFS 遍历
                if (!dfs(next, user, graph, nums_nodes, i+1, j) &&  // 向下
                        !dfs(next, user, graph,nums_nodes, i-1, j)&&  // 向上
                        !dfs(next, user, graph, nums_nodes, i, j-1) &&  // 向右
                        !dfs(next, user, graph, nums_nodes, i, j+1)) {  // 向左
                    // 如果没有可行的方向，回溯：撤销当前状态
                    success = false;
                    break;
                }
            }
        }
        if (!success) {
            nums[i][j] = -1;
            user[node] = false;
        }
        return success;
    }
}

第四题

哈哈，三题选手从来不考虑四题的事