先說個(gè)重點(diǎn)：興業(yè)銀行筆試給了我python2.7和3.9的環(huán)境做題轨香，而我簡(jiǎn)歷明明寫的java...投的也是java相關(guān)的崗位...無(wú)語(yǔ)至極玩般。我在python的環(huán)境里寫了一會(huì)java代碼，寫不下去了挡鞍，選擇放棄起暮。這里復(fù)盤一下，這在IDEA環(huán)境里寫的朝刊。
- 筆試題：給定一個(gè)文本，里面包含字符蜈缤，數(shù)字拾氓，空格，標(biāo)點(diǎn)符號(hào)底哥，小數(shù)點(diǎn)咙鞍。單詞： 以空格為間隔的字符串為單詞，不包括單詞頭尾的引號(hào)和小數(shù)點(diǎn)趾徽。數(shù)字與字母組成的也是單詞续滋，比如1st，3rd孵奶。
- 輸出：將單詞出現(xiàn)的次數(shù)按從多到少輸出疲酌，輸出格式為：word,count。若次數(shù)相同了袁，按字典序的正序輸出（a朗恳，b，c...）载绿。
這里給出我的思路和解法
我的第一反應(yīng)粥诫，HashMap+雙向鏈表+自定義節(jié)點(diǎn)。map存儲(chǔ)word和count崭庸，雙向鏈表維護(hù)自定義節(jié)點(diǎn)Node怀浆，按次數(shù)和字典序排列。這里我沒用API怕享，而是自定義節(jié)點(diǎn)Node和頭尾節(jié)點(diǎn)执赡。
Node節(jié)點(diǎn)
/** 內(nèi)部類,定義了每個(gè)節(jié)點(diǎn) */
static class Node {
String val;
Node pre;
Node next;
int count;
public Node(String val) {
this.val = val;
this.count = 1;
}
}
- 將讀取到的當(dāng)前行字符串轉(zhuǎn)換成單詞，同時(shí)統(tǒng)計(jì)次數(shù)熬粗，放入map中搀玖。這里還沒有構(gòu)建雙向鏈表余境，因?yàn)槿绻婚_始就構(gòu)建鏈表驻呐，那單詞的count每次改變灌诅，都要調(diào)整位置。
/** 將當(dāng)前行字符串轉(zhuǎn)化成單詞,并納入map */
public void convertStringToNode(String s) {
int length = s.length();
int ind = 0, left = 0;
while (ind < length) {
char c = s.charAt(ind);
if (isNumOrLetter(c)) {
ind++;
} else {
// skip: . " ' '; 如果此時(shí)前面一個(gè)是數(shù)字或字母,說明[left,ind)是單詞
if (isNumOrLetter(s.charAt(ind - 1))) {
// find next letter
String sTmp = s.substring(left, ind);
// put it into map
if (!map.containsKey(sTmp)) {
// 不包含該sTmp,創(chuàng)建一個(gè)并插入
map.put(sTmp, new Node(sTmp));
} else {
// 否則計(jì)數(shù)+1
map.get(sTmp).count++;
}
left = ++ind;
} else {
// 若前面一個(gè)不是數(shù)字字母,說明遇到了連續(xù)空格,或者空格+引號(hào)等情況
left = ++ind;
}
}
}
}
- map添加結(jié)束后含末，就需要構(gòu)建雙向鏈表了猜拾，構(gòu)建insert方法。compareString來比較次數(shù)和字典序佣盒。
/** 比較兩個(gè)不同字符串大小,s1大則返回1,s2大返回-1 */
private int compareString(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
// 都轉(zhuǎn)成小寫再比較
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int ind = 0;
while (ind < len1 && ind < len2) {
// 字符對(duì)應(yīng)的ASCII越大,說明越靠后,在字典序中反而越小
if (s1.charAt(ind) > s2.charAt(ind)) {
return -1;
} else if (s1.charAt(ind) < s2.charAt(ind)) {
return 1;
} else {
ind++;
}
}
if (len1 == len2) {
return 0; // 應(yīng)該用不到,因?yàn)楸容^的是兩個(gè)不相同的字符串
}
return ind == len1 ? -1 : 1;
}
/** 向Node鏈表中插入一個(gè)Node */
public void insertNodeIntoList(Node node) {
if (head == null) {
head = tail = node;
} else {
// head和tail非空
Node index = tail;
// 先按出現(xiàn)次數(shù)排序
while (index != null && node.count > index.count) {
index = index.pre;
}
// count相同比較字符串
while (index != null && index.count == node.count && compareString(node.val, index.val) > 0) {
index = index.pre;
}
/* 插在index下面 */
if (index == null) {
// 插在開頭
node.next = head;
head.pre = node;
head = node;
} else if (index == tail) {
// 插在結(jié)尾
index.next = node;
node.pre = index;
tail = node;
} else {
// 插在中間
node.next = index.next;
index.next.pre = node;
index.next = node;
node.pre = index;
}
}
}
/** 調(diào)用 insertNodeIntoList 方法 */
public void callInsertNode() {
for (Map.Entry<String, Node> ele : map.entrySet()) {
insertNodeIntoList(ele.getValue());
}
}
完整代碼如下:
Node head; // head節(jié)點(diǎn)最靠前
Node tail; // tail節(jié)點(diǎn)最靠后
Map<String, Node> map = new HashMap<>();
/** 判斷字符是不是數(shù)字或者字母 */
private boolean isNumOrLetter(char c) {
return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || ('0' <= c && c <= '9');
}
/** 比較兩個(gè)不同字符串大小,s1大則返回1,s2大返回-1 */
private int compareString(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
// 都轉(zhuǎn)成小寫再比較
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int ind = 0;
while (ind < len1 && ind < len2) {
// 字符對(duì)應(yīng)的ASCII越大,說明越靠后,在字典序中反而越小
if (s1.charAt(ind) > s2.charAt(ind)) {
return -1;
} else if (s1.charAt(ind) < s2.charAt(ind)) {
return 1;
} else {
ind++;
}
}
if (len1 == len2) {
return 0; // 應(yīng)該用不到,因?yàn)楸容^的是兩個(gè)不相同的字符串
}
return ind == len1 ? -1 : 1;
}
/** 調(diào)用 insertNodeIntoList 方法 */
public void callInsertNode() {
for (Map.Entry<String, Node> ele : map.entrySet()) {
insertNodeIntoList(ele.getValue());
}
}
/** 向Node鏈表中插入一個(gè)Node */
public void insertNodeIntoList(Node node) {
if (head == null) {
head = tail = node;
} else {
// head和tail非空
Node index = tail;
// 先按出現(xiàn)次數(shù)排序
while (index != null && node.count > index.count) {
index = index.pre;
}
// count相同比較字符串
while (index != null && index.count == node.count && compareString(node.val, index.val) > 0) {
index = index.pre;
}
/* 插在index下面 */
if (index == null) {
// 插在開頭
node.next = head;
head.pre = node;
head = node;
} else if (index == tail) {
// 插在結(jié)尾
index.next = node;
node.pre = index;
tail = node;
} else {
// 插在中間
node.next = index.next;
index.next.pre = node;
index.next = node;
node.pre = index;
}
}
}
/** 將當(dāng)前行字符串轉(zhuǎn)化成單詞,并納入map */
public void convertStringToNode(String s) {
int length = s.length();
int ind = 0, left = 0;
while (ind < length) {
char c = s.charAt(ind);
if (isNumOrLetter(c)) {
ind++;
} else {
// skip: . " ' '; 如果此時(shí)前面一個(gè)是數(shù)字或字母,說明[left,ind)是單詞
if (isNumOrLetter(s.charAt(ind - 1))) {
// find next letter
String sTmp = s.substring(left, ind);
// put it into map
if (!map.containsKey(sTmp)) {
// 不包含該sTmp,創(chuàng)建一個(gè)并插入
map.put(sTmp, new Node(sTmp));
} else {
// 否則計(jì)數(shù)+1
map.get(sTmp).count++;
}
left = ++ind;
} else {
// 若前面一個(gè)不是數(shù)字字母,說明遇到了連續(xù)空格,或者空格+引號(hào)等情況
left = ++ind;
}
}
}
}
/** 內(nèi)部類,定義了每個(gè)節(jié)點(diǎn) */
static class Node {
String val;
Node pre;
Node next;
int count;
public Node(String val) {
this.val = val;
this.count = 1;
}
}
public static void main(String[] args) {
Main main = new Main();
try {
File file = new File("D:/Users/JackTheRipper/Desktop/test.txt");
InputStreamReader reader = new InputStreamReader(new FileInputStream(file));
BufferedReader buffReader = new BufferedReader(reader);
String strTmp;
while ((strTmp = buffReader.readLine()) != null) {
System.out.println(strTmp);
// 將該行轉(zhuǎn)成單詞并納入map
main.convertStringToNode(strTmp);
}
buffReader.close();
// 將map的內(nèi)容納入鏈表
main.callInsertNode();
} catch (IOException e) {
e.printStackTrace();
}
// 輸出結(jié)果
Node cur = main.head;
while (cur != null) {
System.out.println(cur.val + "," + cur.count);
cur = cur.next;
}
}
輸出結(jié)果：
I am "Derrick Rose", Nicknamed "Wind City Rose".
I like basketball, I am very strong.
I do not like singing and rap, I am very week.
Forever Bull No1
I,5
am,3
like,2
Rose,2
very,2
and,1
basketball,1
Bull,1
City,1
Derrick,1
do,1
Forever,1
Nicknamed,1
not,1
rap,1
singing,1
strong,1
week,1
Wind,1
