|
华为机试一共三道题，分值分别是100，100，200，满分400分，限时2.5小时。我抽到的这三题相对来说比较简单，满分通过，这里做个总结：
第一题：数据分类
■?题目描述
- 对一个数据a进行分类，分类方法为：此数据a（四个字节大小）的四个字节相加对一个给定的值b取模，如果得到的结果小于一个给定的值c，则数据a为有效类型，其类型为取模的值；如果得到的结果大于或者等于c，则数据a为无效类型。
- 比如一个数据a=0x01010101，b=3，按照分类方法计算（0x01+0x01+0x01+0x01）%3 = 1，所以如果c=2，则此a为有效类型，其类型为1，如果c=1，则此a为无效类型；
- 又如一个数据a=0x01010103，b=3，按照分类方法计算（0x01+0x01+0x01+0x03）%3 = 0，所以如果c=2，则此a为有效类型，其类型为0，如果c=0，则此a为无效类型。
- 输入12个数据，第一个数据为c，第二个数据为b，剩余10个数据为需要分类的数据，请找到有效类型中包含数据最多的类型，并输出该类型含有多少个数据。
输入描述
- 输入12个数据，用空格分隔，第一个数据为c，第二个数据为b，剩余10个数据为需要分类的数据。
输出描述
示例1?输入输出示例仅供调试，后台判题数据一般不包含示例
输入
3 4 256 257 258 259 260 261 262 263 264 265
输出
3
说明
10个数据4个字节相加后的结果分别为1 2 3 4 5 6 7 8 9 10，故对4取模的结果为1 2 3 0 1 2 3 0 1 2，c为3，所以0 1 2都是有效类型，类型为1和2的有3个数据，类型为0的只有2个数据，故输出3。
示例2?输入输出示例仅供调试，后台判题数据一般不包含示例
输入
1 4 256 257 258 259 260 261 262 263 264 265
输出
2
说明
10个数据4个字节相加后的结果分别为1 2 3 4 5 6 7 8 9 10，故对4取模的结果为1 2 3 0 1 2 3 0 1 2，c为1，所以只有0是有效类型，类型为0的有2个数据，故输出2。
解析： 本题的任务说的十分清晰了，就是将一个int型（4字节，32位）的数字拆分成四个8位的数字再相加，一般的同学可能会通过模拟的方式将数字转化为2进制或者其他进制来做，然后再每8位或其它位又将其转换回10进制后再相加，这种方案当然是可以的，但是作为一个程序员，我们要对位运算十分敏感。本题其实考察的就是位运算，对于4字节的数字x，x & 11111111（或0xff）就可以取出低8位的数字，要取第二个8位的数字只需要将x右移8位后再做与运算即可：（x >> 8）& 0xff，第三个8位数字第四个8位数字以此类推。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int c = in.nextInt(), b = in.nextInt();
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<10;++i) {
int num = in.nextInt();
int sum = 0;
while(num>0) {
sum += num & 0xff;
num >>= 8;
}
int res = sum%b;
if(res<c) {
if(!map.containsKey(res)) {
map.put(res, 1);
}else {
map.replace(res, map.get(res)+1);
}
}
}
int max = 0;
for(int value : map.values()) {
max = Math.max(max, value);
}
System.out.println(max);
}
}
第二题：查找众数及中位数
■?题目描述
- 众数是指一组数据中出现次数量多的那个数，众数可以是多个。
- 中位数是指把一组数据从小到大排列，最中间的那个数，如果这组数据的个数是奇数，那最中间那个就是中位数，如果这组数据的个数为偶数，那就把中间的两个数之和除以2，所得的结果就是中位数。
- 查找整型数组中元素的众数并组成一个新的数组，求新数组的中位数。
输入描述
- 输入一个一维整型数组，数组大小取值范围 0<N<1000，数组中每个元素取值范围 0<E<1000
输出描述
示例1?输入输出示例仅供调试，后台判题数据一般不包含示例
输入
10 11 21 19 21 17 21 16 21 18 15
输出
21
示例2?输入输出示例仅供调试，后台判题数据一般不包含示例
输入
2 1 5 4 3 3 9 2 7 4 6 2 15 4 2 4
输出
3
示例3?输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5 1 5 3 5 2 5 5 7 6 7 3 7 11 7 55 7 9 98 9 17 9 15 9 9 1 39
输出
7
解析：这个分为两个任务，第一个任务求众数，可以用哈希表做，哈希表记录每个数字的出现次数，最后遍历哈希表，出现次数最多的就是众数。第二个任务求众数组成的新数组的中位数，若众数只有一种就非常简单了，这时不管它的个数是奇是偶，中位数都等于它本身，如示例1的众数是21：21 21?21?21，中位数为（21+21）/ 2 = 21。但若众数并非只有一种时，如示例2的众数就是2和4：2 2 2 2 4 4 4 4，其中位数为（2+4）/ 2 =?3，示例三的众数是5 7 9：5 5 5 5 5 7 7 7 7 7 9 9 9 9 9，中位数为7，就需要先排序，然后根据个数是奇是偶来计算中位数。当然，如果进一步分析这些由众数组成的新数组，我们能发现它具有一些典型的特点：数组中大小不同的数字其个数是相同的（因为它们都是原数组的众数）；当众数的种类为偶数时，其组成的新数组中位数为排好序后位于中间的两个众数的平均值，当众数的种类为奇数时，其组成的新数组中位数为好序后位于中间的那个众数（为什么不是众数的个数而是众数的种类的奇偶呢，因为它的反例太容易找到了，只要把示例三每种众数的个数都+1得到新数组：5 5 5 5 5 5 7 7 7 7 7 7 9 9 9 9 9 9，它的元素个数为16是偶数，但中位数依然是中间的7）。根据这些特点，我们是否可以大胆假设：众数组成的新数组的中位数与其个数无关而只与其种类相关？其实这个假设是可以证明的：对于偶数种类的众数序列，如：1 2 4 5，目前其中位数为（2+4）/ 2 = 6，现在增加每种众数的个数，1 1 2 2 4 4 5 5，注意红色部分，你是否发现了？在2 4的左边增加了2个数，右边就会增加两个数，它们是对称增长的！而对称增长是不会影响中位数的值的；再来看奇数种类的众数序列，如 1 2 3 4 5，目前其中位数为3，用同样的方法分析，但此时我们每次增加众数的个数都+2，1 1 1 2 2 2 3 3 3 4 4 4 5 5 5?，发现了吧，仍然是对称增长的，那个数+1是什么情况呢？我们来看 1 1 2 2 3 3 4 4 5 5 ，这种情况下，对称增长的趋势好像被破坏了，那为什么中位数还是保持不变呢？因为这个破坏是由中位数自己引起的，在刚刚的例子中，把中位数3的所有数字去掉，1 1 2 2 4 4 5 5 ，这个序列无论个数+1还是+2都是对称增长的，而中位数3，当个数+1时 3 3，其非对称增长，但这个非对称增长是由自身引起的，中位数的值仍然不改变，个数+2时 3 3 3，对称增长，中位数不变。把上述分析中举例的序列换成任意序列，把举例时的+1、+2换成加奇数个、加偶数个，结论仍然成立！所以在编写代码的过程中我们就不用把所有众数都保存起来了，不同的众数只用保留一个即可。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] s = in.nextLine().split(" ");
ArrayList<Integer> num = new ArrayList<>();
for(int i=0;i<s.length;++i)
num.add(Integer.valueOf(s[i]));
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<num.size();++i) {
int key = num.get(i);
if(!map.containsKey(key)) {
map.put(key, 1);
}else {
map.replace(key, map.get(key)+1);
}
}
int max = 0;
for(int value : map.values()) {
max = Math.max(max, value);
}
num.clear();
for(int key : map.keySet()) {
if(map.get(key)==max) {
num.add(key);
}
}
num.sort(null);
int n = num.size();
if((n&1)==0) {
System.out.println((num.get(n/2)+num.get(n/2-1))/2);
}else {
System.out.println(num.get(n/2));
}
}
}
第三题：
■?题目描述
- 某通信网络中有N个网络结点，用1到N进行标识。
- 网络中的结点互联互通，且结点之间的消息传递有时延，相连结点的时延均为一个时间单位。
- 现给定网络结点的连接关系link[i]={u，v}，其中u和v表示网络结点。
- 当指定一个结点向其他结点进行广播，所有被广播结点收到消息后都会在原路径上回复一条响应消息，请计算发送结点至少需要等待几个时间单位才能收到所有被广播结点的响应消息。
注：
- N的取值范围为[1，100];
- 连接关系link的长度不超过3000，且1 <= u,v <= N;
- 网络中任意结点间均是可达的;
输入描述：
- 输入的第一行为两个正整数，分别表示网络结点的个数N，以及时延列表的长度T；
- 接下来的T行输入，表示结点间的连接关系列表；
- 最后一行的输入为一个正整数，表示指定的广播结点序号；
输出描述：
- 输出一个整数，表示发送结点接收到所有响应消息至少需要等待的时长。
示例1?输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5 7
1 2
1 4
2 3
2 4
3 4
3 5
4 5
2
输出
4
说明
结点2到5的最小时延为2，到剩余结点的最小时延均为1，所以至少要等待2*2=4s。
解析：单源最短路问题，至少要等待的时间即为最大的最短路径*2（因为有一个来回），直接使用dijkstra算法就可以了。200分的题抽到这个属于是很幸运了。这题的边权均为1，似乎也可以直接用BFS写，但我没试过，感兴趣的读者可以试试。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
ArrayList<Edge>[] head = new ArrayList[n+1];
int[] dis = new int[n+1];
boolean[] vit = new boolean[n+1];
for(int i=1;i<=n;++i){
dis[i]=1000;
vit[i]=false;
head[i]=new ArrayList<Edge>();
}
for(int i=0;i<m;++i){
int from = in.nextInt(), to = in.nextInt();
addEdge(from, to, head);
addEdge(to, from, head);
}
int start = in.nextInt();
dis[start] = 0;
PriorityQueue<Node> q = new PriorityQueue<>((a,b)->(a.value-b.value));
q.add(new Node(start,dis[start]));
while(!q.isEmpty()){
int i = q.poll().key;
if(vit[i]) continue;
vit[i]=true;
for(int j=0;j<head[i].size();++j){
Edge edge = head[i].get(j);
int x = edge.to;
if(dis[i]+edge.dis<dis[x]){
dis[x]=dis[i]+edge.dis;
q.add(new Node(x,dis[x]));
}
}
}
int max = 0;
for(int i=1;i<=n;++i){
max = Math.max(max, dis[i]);
}
System.out.println(max*2);
}
public static void addEdge(int from, int to, ArrayList<Edge>[] head){
Edge edge = new Edge(to);
head[from].add(edge);
}
}
class Edge{
int to;
int dis=1;
public Edge(int to){
this.to = to;
}
}
class Node{
int key;
int value;
public Node(int key, int value){
this.key = key;
this.value = value;
}
}
|