劍指Offer——迅雷筆試題+知識點總結
來源：程序員人生 發布時間：2016-11-14 09:34:48 閱讀次數：2547次
劍指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());
}
}
絕對的坑，用正則直接提示超時！
感觸
做編程題之前，首先要畫出流程圖，使編程邏輯更加清晰。編程完成后，要設計測試用例，分為功能性測試和特殊測試。特別要特別注意邊界值的測試。
美文美圖
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
