前两天看到有人在发Google实习生招聘题,自己手痒也实现了一个。
原帖地址:http://www.blogjava.net/andyelvis/archive/2009/04/14/265496.html
原题:
要求:写一个函数void count(char* input,int len),此函数的功能是计算出一个字符串中每个字符的个数,不区分大小写,输出结果时按字符在字符串中出现的先后顺序。使用程序语言不限。
例如:input="abCc*b",输出结果是a:1 b:2 c:2 *:1
1
import
static
java.lang.System.out;
2
import
org.junit.Test;
3
4
/**
5
* 一道Google2009夏季实习生招聘笔试程序设计题
6
* 要求:写一个函数void count(char* input,int len),此函数的功能是计算出一个字符串中每个字符的个数,不区分大小写,输出结果时按字符在字符串中出现的先后顺序。使用程序语言不限。
7
* 例如:input="abCc*b",输出结果是a:1 b:2 c:2 *:1
8
*
@author
Johny Huang
9
* @date 2009-4-14
10
*/
11
public
class
TestCountChar {
12
13
public
static
class
BNode{
14
private
BNode left;
15
private
BNode right;
16
private
int
count;
17
private
char
character;
18
19
public
BNode(
char
c,
int
count){
20
this
.character
=
c;
21
this
.count
=
count;
22
}
23
public
char
getCharacter() {
24
return
character;
25
}
26
public
void
setCharacter(
char
character) {
27
this
.character
=
character;
28
}
29
public
BNode getLeft() {
30
return
left;
31
}
32
public
void
setLeft(BNode left) {
33
this
.left
=
left;
34
}
35
public
BNode getRight() {
36
return
right;
37
}
38
public
void
setRight(BNode right) {
39
this
.right
=
right;
40
}
41
42
public
int
getCount() {
43
return
count;
44
}
45
public
void
setCount(
int
count) {
46
this
.count
=
count;
47
}
48
public
void
addOne(){
49
this
.count
++
;
50
}
51
}
52
53
@Test
54
public
void
test(){
55
char
[] input
=
"
fbagcdagaddddgFBAGCDAGADDDDG
"
.toCharArray();
56
count(input,input.length);
57
}
58
59
/**
60
*
61
*
@param
input 传入的字符数组
62
*
@param
len 需要处理的长度
63
*/
64
public
void
count(
char
[] input,
int
len){
65
/*
66
* 主要思想是用一个二叉树来存储字符,这样可以减少字符对比的次数(至少减少一半),
67
* 另外再用一个数组(或链表)来保存字符的顺序。
68
*/
69
70
//
校验参数
71
if
(input
==
null
){
72
return
;
73
}
74
if
(len
<
1
||
input.length
<
1
){
75
return
;
76
}
77
78
int
length
=
len;
79
if
(len
>
input.length){
80
length
=
input.length;
81
}
82
//
拷贝一个小写的字符数组
83
char
[] inputCopy
=
new
char
[length];
84
for
(
int
i
=
0
;i
<
length;i
++
){
85
inputCopy[i]
=
Character.toLowerCase(input[i]);
86
}
87
88
//
取第一个字符作为根节点
89
BNode root
=
new
BNode(inputCopy[
0
],
1
);
90
//
将当前节点设为根节点
91
BNode current
=
root,temp;
92
93
//
申请一个节点数组来保存字符顺序,当然也可以用List来保存
94
BNode[] charSeq
=
new
BNode[length];
95
charSeq[
0
]
=
root;
96
//
charSeq数组的下标(索引)
97
int
charSeqIndex
=
1
;
98
char
curChar;
99
100
//
从第二个字符开始遍历字符数组
101
for
(
int
i
=
1
;i
<
length;i
++
){
102
curChar
=
inputCopy[i];
103
while
(
true
){
104
//
如果字符与当前节点字符相同,则累加1
105
if
(curChar
==
current.getCharacter()){
106
current.addOne();
107
break
;
108
}
else
{
109
if
(curChar
<
current.getCharacter()){
110
//
如果字符小于当前节点字符,则转向左子节点对比
111
if
(current.getLeft()
==
null
){
112
//
左子节点为空,则加入新的节点
113
temp
=
new
BNode(curChar,
1
);
114
current.setLeft(temp);
115
//
将节点引用保存到数组
116
charSeq[charSeqIndex]
=
temp;
117
charSeqIndex
++
;
118
break
;
119
}
120
current
=
current.getLeft();
121
}
else
{
122
//
如果字符大于当前节点字符,则转向右子节点对比
123
if
(current.getRight()
==
null
){
124
temp
=
new
BNode(curChar,
1
);
125
current.setRight(temp);
126
charSeq[charSeqIndex]
=
temp;
127
charSeqIndex
++
;
128
break
;
129
}
130
current
=
current.getRight();
131
}
132
}
133
}
134
//
将当前节点指向根节点
135
current
=
root;
136
}
137
138
for
(BNode node:charSeq){
139
out.print(node.getCharacter()
+
"
:
"
+
String.valueOf(node.getCount())
+
"
"
);
140
}
141
}
142
143
}
主要是通过二叉树来保存字符,从而减少对比的次数来达到优化。因为想到很多面试题目都不给用泛型,所以这里都用数组实现了。
分享到:
相关推荐
腾讯2013实习生招聘笔试试题,2013年4月13日刚刚出炉的,相比2012年简单一些。
2014年广东移动领先100实习生招聘笔试题目,高清拍摄照片
2011百度暑期实习生招聘笔试题-web前端开发,有部分答案
腾讯历年实习生招聘笔试真题,大部分有答案。
百度2012年实习生招聘笔试试题 -技术类 2012年5月6日
此文档为阿里巴巴-2011届实习生招聘笔试题目。
2013阿里巴巴实习生招聘笔试题目,图像清晰,题目完整,获得阿里offer必备!
百度2012年实习生招聘笔试试题 -技术类 2012年5月6日
京东2016实习生招聘笔试真题-技术岗位选择题
2012年腾讯实习生技术运营试题
京东2016实习生招聘笔试真题-技术岗位选择题
百度2012实习生校园招聘机器学习数据挖掘笔试试题,花了很多时间才找到的
腾讯校园实习生笔试题,有答案,大家好好看吧
(完整版)检验科实习生出科考试题(三).pdf
2014年3月29日晚6:30-8:30,阿里巴巴集团2014实习生统一笔试题,试题很灵活,开放性很大。
2015年趋势科技实习生招聘笔试题。希望对找实习的人有用
抽象类 A. 至少含有一个纯虚函数 B. 至少含有一个静态函数 C. 其派生类必须提供纯虚函数的实现代码 D. 可以定义抽象类的对象,也可以由派生类生成新类
全国计算机等级考试二级笔试试卷Java语言程序设计试题
2013腾讯实习生招聘笔试题目
2012腾讯广州实习生招聘试题,试题齐全。为手打版