剑指Offer——迅雷笔试题+知识点总结
栏目：综合技术时间：2016-11-14 09:34:48
剑指Offer——迅雷笔试题+知识点总结
情形回顾
时间:2016.9.19 19：00⑵1：00
地点:山东省网络环境智能计算技术重点实验室
事件:迅雷笔试
整体来讲，迅雷笔试内容体量不算多，主要分为30道选择题，2道编程题，半小时将选择题做完，1个半小时两道编程题1道29%，1道超时。关键是第2道编程题直接输出毛病语句竟然通过17%！也是醉了，绝对的判题系统BUG。
知识点回想
希尔排序
给定1数组元素{50，40，95，20，15，70，60，45}，经过1趟希尔排序(参考博文《剑指Offer--排序算法小结》)后，数组元素变成
[15 40 60 20 50 70 95 45]
public static void shellSort(int[] data) {
int j = 0;
int temp = 0;
for (int increment = data.length / 2; increment > 0; increment /= 2) {
for (int i = increment; i < data.length; i++) {
temp = data[i];
for (j = i; j >= increment; j -= increment) {
if(temp < data[j - increment]){
data[j] = data[j - increment];
}else{
break;
}
}
data[j] = temp;
}
for(int a : data)
System.out.print(a + " ");
System.out.println("");
}
}
WPL、全局变量与局部变量的区分(存储？)
Java里面“==”与equals()的区分：前者比较的是地址，后者比较的是内容。
int 是在栈里创建的，Integer是在堆里创建的。栈里创建的变量要比在堆创建的速度快很多。
根据“静态型变量是寄存在内存的数据区中的,它们在程序开始运行前就分配了固定的字节,在程序运行进程中被分配的字节大小是不改变的.只有程序运行结束后,才释放所占用的内存.” 这段话可以得知，全局变量就是所谓的静态变量，寄存在栈中。
Java栈由栈帧元素组成。栈帧由3部份组成：局部变量区、操作数栈、帧数据区。
Java里面“==”与equals()的区分：前者比较的是地址，后者比较的是内容。
int 是在栈里创建的，Integer是在堆里创建的。栈里创建的变量要比在堆创建的速度快很多。
堆(Heap)
Java堆是被所有线程同享的1块内存区域，在虚拟机启动时创建；
Java虚拟机规范描写:所有的对象实例及数组都要在堆上分配；
Java堆可以处于物理上不连续的内存空间，只要逻辑上连续便可;
栈(Stack)
寄存基本类型的数据和对象的援用，即寄存变量;
如果寄存的是基本类型数据（非静态变量），则直接将变量名和值存入stack中的内存中；
如果是援用类型，则将变量名存入栈，然后指向它new出的对象（寄存在堆中）;
有关堆与栈的区分，详情参见博文《剑指Offer——简述堆和栈的区分》。
编程题
1.LRUCache(29%)
程序流程图(set操作)
package cn.edu.ujn.practice;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Pattern;
/**
*
* @author SHQ
*
LRUCache
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描写：
为LRU Cache设计1个数据结构，它支持两个操作：
1）get(key)：如果key在cache中，则返回对应的value值，否则返回⑴。
2）set(key,value):如果key不在cache中，则将该(key,value)插入cache中（注意，如果cache已满，则必须把最近最久未使用的元素从cache中删除）；
如果key在cache中，则重置value的值。
3）key,value为int型数据。
输入
第1行动capacity(capacity>0)， 后面输入的每行数据，有两种情况:
1种有key和value（key，value以空格分隔），这类情况为set数据，1种只有1个key值，这类为get数据。
输出
根据给定的capacity和多组测试数据，输出指定key值对应value值，如果该key值不存在，返回⑴。
样例输入
3
100 100
200 200
300 300
100 100
400 400
100
200
300
500
样例输出
100
⑴
300
⑴
*/
public class XunLei_1 {
public static void main(String[] args) {
StringBuffer sb =new StringBuffer();
Scanner in = new Scanner(System.in);
// 容量
int capacity = in.nextInt();
// 用于接收换行符
in.nextLine();
while (in.hasNextLine()) {
String s = in.nextLine();
if(s == null || s.length() == 0)
break;
sb.append(s + "\r");
}
resolution(capacity, sb.toString());
}
private static void resolution(int capacity, String str){
/* System.out.println(capacity);
System.out.println(str);*/
int index = 0;
Map<Integer, HashMap<String, String>> map = new HashMap<Integer, HashMap<String, String>>();
Map<String, String> mapTmp;
Pattern pat = Pattern.compile("[ ]+");
Pattern pattern = Pattern.compile("[\r]");
String [] sr = pattern.split(str);
boolean flag = false;
for(String s : sr){
// 注意map集合m的创建位置
HashMap<String, String> m = new HashMap<String, String>();
String [] string = pat.split(s);
// set操作
if(string.length == 2){
// 如果key不在cache中，则将该(key,value)插入cache中；如果key在cache中，则重置value的值。
// 1.cache未满
if(map.size() == 0){
m.put(string[0], string[1]);
map.put(index++, m);
}else if(map.size() < capacity){
for(int key : map.keySet()){
mapTmp = map.get(key);
// 2.cache存在旧k,替换旧v
if(mapTmp.containsKey(string[0])){
m.put(string[0], string[1]);
flag = true;
break;
}
}
if(!flag){
// 3.cache不存在旧k,直接插入
m.put(string[0], string[1]);
}
map.put(index++, m);
}
// 4.cache已满
else{
for(int key : map.keySet()){
mapTmp = map.get(key);
// 5.cache存在旧k,替换旧v
if(mapTmp.containsKey(string[0])){
m.put(string[0], string[1]);
map.put(index++, m);
map.remove(key);
break;
}
else{
// 6.cache不存在旧k,使用LRU将元素从cache中删除
int min = Collections.min(map.keySet());
int max = Collections.max(map.keySet());
/* for(int i : map.keySet()){
if(i < min){
min = i;
}
if(i > max)
max = i;
}*/
// 根据LRU规则，将元素从cache中删除
map.remove(min);
// 将元素存入cache中最大位置+1处
m.put(string[0], string[1]);
map.put(max+1, m);
break;
}
}
}
}else if(string.length == 1){
flag = false;
// get操作
for(int in : map.keySet()){
mapTmp = map.get(in);
if(mapTmp.containsKey(string[0])){
flag = true;
System.out.println(mapTmp.get(string[0]));
break;
}
}
if(!flag)
System.out.println("⑴");
}
}
}
}
注
其中，有关map类型m的创建位置，自己再次犯了毛病。new的m为援用类型，寄存在栈中。应保证m在循环体内创建，这样结果才不会出现map累加的现象。类似毛病一样出现在博文《Android进阶(4)1个APP引发的思索之ArrayList的add总是添加相同的值》。
2迅雷专用链提取(正则超时)
package cn.edu.ujn.practice;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
*
* @author SHQ
迅雷专用链提取
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描写：
迅雷专用链是通过迅雷专用链技术将网站现有的HTTP、FTP等下载协议转换成迅雷的专用下载协议，从而实现与web迅雷的无缝结合。常见的软件下载使用的是http或ftp下载协议，而迅雷专用链使用的是专用的"thunder://"下载协议。现给定1个网页的内容文本，需要从中找出所有的雷专用链并输出结果，重复的迅雷专用链只输出1个，在网页的内容文本字符串中的位置排前的迅雷专用链先输出。
已知迅雷专用链组成：
“thunder://” + 对正常http下载链接进行处理后Base64编码的字符串
(Base64编码后的字符串由数字、大小写字母、加号’+’、斜杠’/’、等号”=”组成)
如: thunder://QUFodHRwOi8vZGwueHVubGVpLmNvbS9aWg==
输入
网页内容的文本字符串,多是多行。
输出
如果没有找到，则输出 no。
如果找到结果：
第1行输出1个整数，即找到的迅雷专用链个数n
接下的n行每行输出1个迅雷专用链，重复的迅雷专用链只输出1次，在输入字符串中的位置排前的迅雷专用链先输出。
样例输入
<a href="thunder://QUFodHRwOi8vZGwueHVubGVpLmNvbS9aWg==/">This ia a thunder url</a>
样例输出
１
thunder://QUFodHRwOi8vZGwueHVubGVpLmNvbS9aWg==
Hint
题目解析：
主要分析迅雷专用链的特点，通过字符串匹配查找，或通过正则表达式查找。
*/
public class XunLei_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
while (in.hasNextLine()) {
// 输入文本
String s = in.nextLine();
if(s == null || s.length() == 0)
break;
sb.append(s);
resolution(sb.toString());
// 只输出这句话就可以通过17%!也是醉了~
System.out.println("no");
}
}
private static void resolution(String str){
Pattern pattern = Pattern.compile("(thunder://){1}[\\w\\d//=+]+");
Matcher matcher = pattern.matcher(str);
StringBuffer buffer = new StringBuffer();
int cnt = 0;
while(matcher.find()){
cnt++;
buffer.append(matcher.group());
buffer.append("\r\n");
}
System.out.println(cnt);
System.out.println(buffer.toString());
}
}
绝对的坑，用正则直接提示超时！
感触
做编程题之前，首先要画出流程图，使编程逻辑更加清晰。编程完成后，要设计测试用例，分为功能性测试和特殊测试。特别要特别注意边界值的测试。
美文美图
------分隔线----------------------------
上一篇 AWT菜单：
------分隔线----------------------------