先说个重点：兴业银行笔试给了我python2.7和3.9的环境做题，而我简历明明写的java...投的也是java相关的岗位...无语至极。我在python的环境里写了一会java代码，写不下去了，选择放弃。这里复盘一下，这在IDEA环境里写的。
- 笔试题：给定一个文本，里面包含字符，数字，空格，标点符号，小数点。单词： 以空格为间隔的字符串为单词，不包括单词头尾的引号和小数点。数字与字母组成的也是单词，比如1st，3rd。
- 输出：将单词出现的次数按从多到少输出，输出格式为：word,count。若次数相同，按字典序的正序输出（a，b，c...）。
这里给出我的思路和解法
我的第一反应，HashMap+双向链表+自定义节点。map存储word和count，双向链表维护自定义节点Node，按次数和字典序排列。这里我没用API，而是自定义节点Node和头尾节点。
Node节点
/** 内部类,定义了每个节点 */
static class Node {
String val;
Node pre;
Node next;
int count;
public Node(String val) {
this.val = val;
this.count = 1;
}
}
- 将读取到的当前行字符串转换成单词，同时统计次数，放入map中。这里还没有构建双向链表，因为如果一开始就构建链表，那单词的count每次改变，都要调整位置。
/** 将当前行字符串转化成单词,并纳入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: . " ' '; 如果此时前面一个是数字或字母,说明[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,创建一个并插入
map.put(sTmp, new Node(sTmp));
} else {
// 否则计数+1
map.get(sTmp).count++;
}
left = ++ind;
} else {
// 若前面一个不是数字字母,说明遇到了连续空格,或者空格+引号等情况
left = ++ind;
}
}
}
}
- map添加结束后，就需要构建双向链表了，构建insert方法。compareString来比较次数和字典序。
/** 比较两个不同字符串大小,s1大则返回1,s2大返回-1 */
private int compareString(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
// 都转成小写再比较
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int ind = 0;
while (ind < len1 && ind < len2) {
// 字符对应的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; // 应该用不到,因为比较的是两个不相同的字符串
}
return ind == len1 ? -1 : 1;
}
/** 向Node链表中插入一个Node */
public void insertNodeIntoList(Node node) {
if (head == null) {
head = tail = node;
} else {
// head和tail非空
Node index = tail;
// 先按出现次数排序
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) {
// 插在结尾
index.next = node;
node.pre = index;
tail = node;
} else {
// 插在中间
node.next = index.next;
index.next.pre = node;
index.next = node;
node.pre = index;
}
}
}
/** 调用 insertNodeIntoList 方法 */
public void callInsertNode() {
for (Map.Entry<String, Node> ele : map.entrySet()) {
insertNodeIntoList(ele.getValue());
}
}
完整代码如下:
Node head; // head节点最靠前
Node tail; // tail节点最靠后
Map<String, Node> map = new HashMap<>();
/** 判断字符是不是数字或者字母 */
private boolean isNumOrLetter(char c) {
return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || ('0' <= c && c <= '9');
}
/** 比较两个不同字符串大小,s1大则返回1,s2大返回-1 */
private int compareString(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
// 都转成小写再比较
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int ind = 0;
while (ind < len1 && ind < len2) {
// 字符对应的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; // 应该用不到,因为比较的是两个不相同的字符串
}
return ind == len1 ? -1 : 1;
}
/** 调用 insertNodeIntoList 方法 */
public void callInsertNode() {
for (Map.Entry<String, Node> ele : map.entrySet()) {
insertNodeIntoList(ele.getValue());
}
}
/** 向Node链表中插入一个Node */
public void insertNodeIntoList(Node node) {
if (head == null) {
head = tail = node;
} else {
// head和tail非空
Node index = tail;
// 先按出现次数排序
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) {
// 插在结尾
index.next = node;
node.pre = index;
tail = node;
} else {
// 插在中间
node.next = index.next;
index.next.pre = node;
index.next = node;
node.pre = index;
}
}
}
/** 将当前行字符串转化成单词,并纳入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: . " ' '; 如果此时前面一个是数字或字母,说明[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,创建一个并插入
map.put(sTmp, new Node(sTmp));
} else {
// 否则计数+1
map.get(sTmp).count++;
}
left = ++ind;
} else {
// 若前面一个不是数字字母,说明遇到了连续空格,或者空格+引号等情况
left = ++ind;
}
}
}
}
/** 内部类,定义了每个节点 */
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);
// 将该行转成单词并纳入map
main.convertStringToNode(strTmp);
}
buffReader.close();
// 将map的内容纳入链表
main.callInsertNode();
} catch (IOException e) {
e.printStackTrace();
}
// 输出结果
Node cur = main.head;
while (cur != null) {
System.out.println(cur.val + "," + cur.count);
cur = cur.next;
}
}
输出结果：
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
