劍指Offer——迅雷筆試題+知識點總結

劍指Offer——迅雷筆試題+知識點總結

情景回顧

時間:2016.9.19 19：00-21：00

地點:山東省網絡環境智能計算技術重點實驗室

事件:迅雷筆試

總體來說，迅雷筆試內容體量不算多，主要分為30道選擇題，2道編程題，半小時將選擇題做完，1個半小時兩道編程題一道29%，一道超時。關鍵是第二道編程題直接輸出錯誤語句居然通過17%！也是醉了，絕對的判題系統BUG。

知識點回憶

希爾排序

給定一數組元素{50，40，95，20，15，70，60，45}，經過一趟希爾排序(參考博文《劍指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棧由棧幀元素組成。棧幀由三部分組成：局部變量區、操作數棧、幀數據區。

堆(Heap)

Java堆是被所有線程共享的一塊內存區域，在虛擬機啟動時創建；

Java虛擬機規范描述:所有的對象實例及數組都要在堆上分配；

Java堆可以處于物理上不連續的內存空間，只要邏輯上連續即可;

棧(Stack)

存放基本類型的數據和對象的引用，即存放變量;

如果存放的是基本類型數據（非靜態變量），則直接將變量名和值存入stack中的內存中；

如果是引用類型，則將變量名存入棧，然后指向它new出的對象（存放在堆中）;

有關堆與棧的區別，詳情參見博文《劍指Offer——簡述堆和棧的區別》。

編程題

1.LRUCache(29%)

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）get(key)：如果key在cache中，則返回對應的value值，否則返回-1。

2）set(key,value):如果key不在cache中，則將該(key,value)插入cache中（注意，如果cache已滿，則必須把最近最久未使用的元素從cache中刪除）；

如果key在cache中，則重置value的值。

3）key,value為int型數據。

輸入

第一行為capacity(capacity>0)， 后面輸入的每行數據，有兩種情況:

一種有key和value（key，value以空格分隔），這種情況為set數據，一種只有一個key值，這種為get數據。

輸出

根據給定的capacity和多組測試數據，輸出指定key值對應value值，如果該key值不存在，返回-1。

樣例輸入

3

100 100

200 200

300 300

100 100

400 400

100

200

300

500

樣例輸出

100

-1

300

-1

*/

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> map = new HashMap>();

Map 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 m = new HashMap();

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("-1");

}

}

}

}

注

其中，有關map類型m的創建位置，自己再次犯了錯誤。new的m為引用類型，存放在棧中。應保證m在循環體內創建，這樣結果才不會出現map累加的現象。類似錯誤同樣出現在博文《Android進階(四)一個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://"下載協議。現給定一個網頁的內容文本，需要從中找出所有的雷專用鏈并輸出結果，重復的迅雷專用鏈只輸出一個，在網頁的內容文本字符串中的位置排前的迅雷專用鏈先輸出。

已知迅雷專用鏈組成：

“thunder://” + 對正常http下載鏈接進行處理后Base64編碼的字符串

(Base64編碼后的字符串由數字、大小寫字母、加號’+’、斜杠’/’、等號”=”組成)

如: thunder://QUFodHRwOi8vZGwueHVubGVpLmNvbS9aWg==

輸入

網頁內容的文本字符串,可能是多行。

輸出

如果沒有找到，則輸出 no。

如果找到結果：

第一行輸出一個整數，即找到的迅雷專用鏈個數n

接下的n行每行輸出一個迅雷專用鏈，重復的迅雷專用鏈只輸出一次，在輸入字符串中的位置排前的迅雷專用鏈先輸出。

樣例輸入

This ia a thunder url

樣例輸出

１

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());

}

}

絕對的坑，用正則直接提示超時！

感觸

做編程題之前，首先要畫出流程圖，使編程邏輯更加清晰。編程完成后，要設計測試用例，分為功能性測試和特殊測試。尤其要特別注意邊界值的測試。

美文美圖

Java 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。