剑指Offer——顺丰笔试题+知识点总结
情景回顾
- 时间:2016.10.16 19：00-20：40
- 地点:山东省网络环境智能计算技术重点实验室
- 事件:顺丰笔试
知识点总结
快排
霍尔排序(快排)
快速排序是由安东尼·霍尔所发明的一种排序算法，又名霍尔排序。
哈夫曼树带权路径长度
赫夫曼树又称最优二叉树，是带权路径长度WPL最小的二叉树。
- WPL定义:树中所有叶子节点的带权路径长度之和。
构建赫夫曼树的步骤:
- 1.构造森林全是根；
- 2.选用两小造新树；
- 3.删除两小添新人；
- 4.重复(2)(3)剩单根。
vector，map，set用什么数据结构存储
- 1.TreeSet采用红黑树的数据结构来存储集合元素；
- 2.EnumSet在内部以位向量的形式存储，这种存储形式非常紧凑、高效，因此Enum对象占用内存很小，运行效率很高；
- 3.HashSet、TreeSet、EnumSet都不是线程安全的。可用Collections工具类的synchronizedSortedSet方法封装；
- 4.ArrayList和Vector类都是基于数组实现的List类，两者均封装了一个动态、允许再分配的Object[]数组；Vector是线程安全的，而ArrayList不是。
- 5.LinkedList与ArrayList、ArrayDeque的实现机制完全不同，ArrayList、ArrayDeque内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；而LinkedList内部以链表的形式来保存集合中的元素，因此随即访问集合元素时性能较差，但在删除、添加元素时性能非常出色(只需改变指针所指的地址即可)。需要指出的是，虽然Vector也是以数组的形式在存储集合元素的，但因为实现了线程同步功能，所以各方面性能都有所下降。
- 6.对于所有的内部基于数组的集合实现，例如ArrayList、ArrayDeque等，使用随机访问的性能比使用Iterator迭代访问的性能要好，因为随机访问会被映射成对数组元素的访问(因为数组以一块连续内存区来保存所有的数组元素)；
- 7.Map采用关联数组形式存储；
- 8.HashMap和HashTable都是Map接口的典型实现类。HashTable线程安全，HashMap不安全；HashTable不允许null作为key和value，否则会报NullPointerException异常，HashMap可以使用null作为key或value。
- 9.Properties类是HashTable类的子类，在处理属性文件时特别方便。
码上示例
package cn.edu.ujn.demo;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Properties;
/**
*
*
* @author SHQ
* @since 2016/10/16
*/
public class PropertiesDemo {
/**
* @param args
*/
public static void main(String[] args) {
final String ADDR = "C:\\Users\\SHQ\\Desktop\\temp.xml";
// 书写properties文件
Properties properties = new Properties();
// 建议使用
properties.setProperty("ONE", "1");
properties.put("TWO", "2");
properties.put("中文", "看看中文怎么样");
properties.put("日本語", "日本語はどう？");
properties.put("한국어", "한국어");
properties.put("Thảo luận tiếng Việt", "Thảo luận tiếng Việt");
OutputStream stream = null;
try {
stream = new FileOutputStream(ADDR);
properties.storeToXML(stream, "Temporary Properties");
}
catch (IOException ex) {
ex.printStackTrace();
}finally{
try{
stream.close();
}catch(Exception e){
}
}
// 读取properties文件
Properties properties2 = new Properties();
InputStream is = null ;
try{
is = new FileInputStream(ADDR);
properties2.loadFromXML(is);
System.out.println(properties2);
}catch (IOException e) {
e.printStackTrace();
}finally{
try{
is.close();
}catch (Exception e) {
}
}
}
}
树是一种线性表存储结构吗？
数据结构按逻辑结构可以分为集合、线性结构、非线性结构；按存储结构可以划分为顺序、链式、索引、散列存储结构。
简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：
- 1．集合中必存在唯一的一个”第一个元素”；
- 2．集合中必存在唯一的一个”最后的元素”；
- 3．除最后元素之外，其它数据元素均有唯一的”后继”；
4．除第一元素之外，其它数据元素均有唯一的”前扑”。
数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。所以树不是线性表存储结构。
Hashtable实现栈的操作
编程题
/**
*
* @author SHQ
*编程题 | 30分 1/2
*题目描述：
小A是一个城市中救援机构的负责人，他手头上有一张特殊的地图，记载了本省各个城市中救援队伍的数量和城市之间的道路连接情况。
他的任务相当重要，除负责本市紧急情况救援外，他还需要在某个其他城市发生紧急情况时，第一时间带领他的队伍参与救援，
同时调动路过城市的救援机构参与救援。
输入
多组输入数据，第一行是一个正整数T(T<=10)，表示测试数据的组数，接下来包含T组测试数据。
每组测试数据的第一行包含四个整数n(1<n<=1000)，m(0<=m<=n*(n-1)/2)，s 和 t(1<=s<=n, 1<=t<=n)，分别表示城市的数量、道路的数量、
小A所在的城市和目标城市。
第二行包含n个整数，表示每个城市中救援机构的数量。
接下来的M行中，每行包含三个整数u, v, w, (0 <= u <= n-1, 0 <= v <= n-1, u不等于v, 0 <= w <= 1)
表示结点u和结点v之间存在一条长度为w(1<=w<=10000的道路(保证没有重复)。
不保证城市之间有道路可以通行。
输出
对于每一组测试数据，输出一行"Case t: x y"，其中 t表示第t组数据，t从1开始递增。x从小A所在城市到救援城市之间可以通行的路径数
，y为所能召集的最大救援队伍数。若无法达到救援目标城市，则输出"No answer"，详见给定样例。
样例输入
2
4 5 0 3
1 1 1 1
0 1 1
0 2 3
1 2 2
1 3 3
2 3 1
5 4 0 4
1 1 1 1 1
0 1 1
1 2 3
0 2 2
3 4 3
样例输出
Case 1: 3 4
Case 2: No answer
*
*//**
* 编程题 | 30分 2/2
分割游戏
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
小C负责设计一种新的益智数字游戏。游戏分A、B两方，规则如下：
1.A方在一个纸片上写一个不超过6位的数值N，同时给出一个目标数M；
2.B方对写有数值N的纸片进行分割，分割成的每个纸片上有一个数，所有纸片上数的和不能大于目标数M，但需要尽可能与M接近。
3.若N与M相同，则不进行分割。
4.若无论如何分割，所得的碎纸片上数之和都大于目标数M，则表示错误。
5.若有多种不同的分割方式可以得到相同的最优结果。则拒绝分割。
游戏开发之前，小A计划先编写一个模拟程序。给定两个数，第一个是目标数M，第二个是写在纸片上的数N，输出分割的方式。
输入
输入包括多组数据，每一组数据为一行，包括两个正整数M和N，保证两个数都不会以0开头，而且两个数最多只包含6个数字。
输入的最后一行包括由空格分隔两个0，表示输入的结束。
输出
对每组输入数据，给出相应的输出。可能有三种不同的输出结果：
sum part1 part2 ...
rejected
error
上述结果表示如下：
sum为碎纸片上数之和，即：sum = part1 + part2 +...。partj为碎纸片上数，顺序与待碎纸片上原始数中数字出现的次序一致。
若无论如何分割，所得碎纸片上数的和都大于目标数，则输出“error”。
若有多种不同的分割方式可得到相同的最优结果，则输出“rejected”。
样例输入
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
样例输出
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
*/
package cn.edu.ujn.practice;
import java.util.Scanner;
public class SF_2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
String[] strs = sc.nextLine().split(" ");
int m = Integer.valueOf(strs[0]);
String n = strs[1];
if (m == 0)
break;
int optionSum = Integer.MAX_VALUE;
int optionSplit = Integer.MAX_VALUE;
int sameCount = 0;
int z = 1 << (n.length() - 1);
for (int i=0; i<z; i++) {
char[] chars = Integer.toBinaryString(i).toCharArray();
int sum = 0;
int lastIndex = 0;
for (int j=0; j<chars.length; j++) {
if (chars[j] == '0')
continue;
int curIndex = n.length() - (chars.length - j);
sum += Integer.valueOf(n.substring(lastIndex, curIndex));
lastIndex = curIndex;
}
sum += Integer.valueOf(n.substring(lastIndex, n.length()));
if (sum <= m && sum == optionSum) {
sameCount++;
} else if (sum <= m && Math.abs(sum-m) < Math.abs(optionSum-m)) {
optionSum = sum;
optionSplit = i;
sameCount = 1;
}
}
if (optionSum > m)
System.out.println("error");
else if (sameCount > 1)
System.out.println("rejected");
else {
System.out.print(optionSum + " ");
int lastIndex = 0;
char[] chars = Integer.toBinaryString(optionSplit).toCharArray();
for (int j=0; j<chars.length; j++) {
if (chars[j] == '0')
continue;
int curIndex = n.length() - (chars.length - j);
System.out.print(n.substring(lastIndex, curIndex) + " ");
lastIndex = curIndex;
}
System.out.println(n.substring(lastIndex, n.length()));
}
}
}
}
注 数据精度
package cn.edu.ujn.practice;
public class YouKuTuDou {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(resolution(10));
}
private static int resolution(int k){
int fm = 1;
double sum = 0;
while(sum <= k){
// 注意不要丢失精度
sum += 1/(double)fm;
fm++;
}
return fm-1;
}
}
