4.29广联达笔试4题及答案

题目一：

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
举例：

输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
AC答案：

class Solution {
   /**
     * 直接调用快排，改写一下排序的规则
     * @param arr
     * @return */
    public int[] sortByBits(int[] arr) {
                // 特殊情况
        if (arr==null || arr.length==0) return new int[0];
                // 构建Integer数组，因为Arrays.sort方法的比较器使用到了泛型，必须是int的包装类型
        Integer[] tmp = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            tmp[i] = arr[i];
        }
                // 对比，根据含有1的数量，如果相同，比较数值本身大小
        Arrays.sort(tmp, new Comparator() { @Override public int compare(Object o1, Object o2) {
                int diff = numOf1((Integer) o1) - numOf1((Integer) o2);
                if (diff == 0) return (Integer) o1 - (Integer) o2;
                return diff;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            arr[i] = tmp[i];
        }
        return arr;
    }
        // 一个数含有1的大小的计算方法
    public int numOf1(int n){
        int count =0;
        while (n!=0){
            n &=n-1; // 按位与，只有两个数字的同一个位值都为1时，才为1； 减1后 最右边的位置不同了。
            count++; // 因此，每次减少一；
        }
        return count;
    }
}

题目二：
给定N个（N>3）囚犯，开始在标号为N的牢房

重新排序的时候要求囚犯不能和之前的相邻的囚犯再次相邻，

求所有的排序方法。

举例：

N=4;

return [2,1,4,3],[3,4,1,2].

因为2不能和1，3相邻； 3不能和2，4相邻。

思路：回溯。

参考答案：

import java.util.ArrayList;
import java.util.List;

/**
 * 思路： 回溯。
 */
public class Main {
    // List中每一个String是一种答案。
    List<String> ans = new ArrayList<>();
    int N; //作为全局变量，不需要每次递归传递
    public List<String> premute(int N){
        this.N = N;
        backtrack(new String());
        return ans;
    }

    void backtrack(String path){
        // 退出条件
        if (path.length()==N){
            ans.add(path);
            return;
        }
        // 选择当前符合条件的情况
        for (int i=1;i<=N;i++){
            if (!check(path,i))continue;
            String cur = path+i;
            backtrack(cur);
        }
    }
    private boolean check(String path, int i) {
        if (path.length()==0) return true;
        if (path.contains(""+(char)(i+'0')))return false;
        char right = path.charAt(path.length()-1);
        if ((i+'0'-1)==right ||(i+'0'+1) == right || (i+'0')==right)
            return false;
        return true;
    }

}

题目三：

Leetcode 406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
思路：

先对people数组按身高从高到低排序，如果相同，按k从低到高排序；

然后调用arraylst.add根据k的位置插入；

public class Main { public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
                int diff = o2[0] - o1[0]; //身高由高到低
                if (diff==0) return o1[1] - o2[1];
                return diff;
            }
        });
        ArrayList<int[]> q = new ArrayList();
        for (int[] p:people){
            q.add(p[1], p);
        }
        int[][] ans = q.toArray(new int[people.length][2]);
        return ans;
    } }

题目四：

Leetcode473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入: [1,1,2,2,2]
输出: true
思路：

1. 判断nums和是否为4的整数倍

2. 回溯法分割成四分，判断最后每份的和是否为1/4. 但是效率较低

public class Main {
    
    int[] part4 = new int[4];
    int len;
    int[] nums;
    public boolean makesquare(int[] nums) {
        len = nums.length;
        if (nums==null || nums.length<4) return false;
        int sum =0;
        for (int i: nums) sum += i;
        if (sum %4 != 0) return false;
        sum /=4;
        System.out.println(sum);
        this.nums = nums;
        return backtrack(0, sum);
    }

    boolean backtrack(int n, int sum){
        if (n==len){
            for (int i: part4)
                if(i!=sum) return false;
            return true;
        }
        for (int i=0;i<4;i++){
            part4[i] += nums[n];
            if (backtrack(n+1,sum))
                return true;
            part4[i] -= nums[n];
        }
        return false;
    }
}

#广联达暑期实习内推2021##笔试题目##广联达#