4.29广联达笔试4题及答案
题目一：
Leetcode 1356 根据数字二进制下 1 的数目排序
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 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答案：
输出：[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;
}
}
