前两天看到有人在发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
}
主要是通过二叉树来保存字符,从而减少对比的次数来达到优化。因为想到很多面试题目都不给用泛型,所以这里都用数组实现了。
分享到:
相关推荐
《永磁无刷直流电机控制系统与软件综合研究——集成电机计算软件、电机控制器及电磁设计软件的创新设计与实践》,永磁无刷直流电机计算与控制软件:高效电机控制器与电磁设计工具,永磁无刷直流电机计算软件,电机控制器,无刷电机设计软件,电机电磁设计软件 ,永磁无刷直流电机计算软件; 电机控制器; 无刷电机设计软件; 电机电磁设计软件,无刷电机设计专家:永磁无刷直流电机计算与控制器设计软件
新能源汽车VCU开发模型及策略详解:从控制策略到软件设计全面解析,新能源汽车VCU开发模型及策略详解:从控制策略到软件设计全面解析,新能源汽车VCU开发模型及控制策略,MBD电控开发 新能源汽车大势所向,紧缺VCU电控开发工程师,特别是涉及新能源三电系统,工资仅仅低于无人驾驶、智能驾驶岗位。 ——含控制策略模型 整车控制策略详细文档 通讯协议文档 接口定义 软件设计说明文档 等(超详细,看懂VCU电控策略开发就通了) 内容如下: 新能源汽车整车控制器VCU学习模型,适用于初学者。 1、模型包含高压上下电,行驶模式管理,能量回馈,充电模式管理,附件管理,远程控制,诊断辅助功能。 2、软件说明书(控制策略说明书) 3、模型有部分中文注释 对想着手或刚开始学习整车控制器自动代码生成或刚接触整车控制器有很大帮助。 ,新能源汽车VCU开发模型; 控制策略; MBD电控开发; 模型学习; 代码生成; 整车控制器; 能量回馈; 诊断辅助功能,新能源汽车电控开发详解:VCU控制策略模型及学习手册
内容概要:本文详细介绍了两种利用 Python 读取 Excel 文件的不同方法,分别是基于 pandas 和 openpyxl。对于想要利用Python 处理 Excel 数据的读者来说,文中不仅提供了简洁明了的具体代码片段以及执行效果展示,还针对每个库的应用特性进行了深度解析。此外,文档提到了一些进阶应用技巧如只读特定的工作薄、过滤某些列等,同时强调了需要注意的地方(像是路径设置、engine 参数调整之类),让读者可以在面对实际项目需求时做出更加明智的选择和技术选型。 适合人群:对 Python 有基本掌握并希望提升数据读取能力的开发人员。 使用场景及目标:适用于任何涉及到批量数据导入或是与 Excel 进行交互的业务流程。无论是做初步的数据探索还是深入挖掘隐藏于电子表格背后的故事,亦或是仅为了简化日常办公自动化任务都可以从中受益。最终目标帮助使用者熟悉两大主流 Excel 解决方案的技术特性和最佳实践。 阅读建议:本文既是一份详尽的学习指南也是一份方便随时查阅的手册。因此初学者应当认真研究所提供的示例,而有一定经验者也可以快速定位到感兴趣的部分查看关键要点。
# 医护人员排班系统 ## 1. 项目介绍 本系统是一个基于SpringBoot框架开发的医护人员排班管理系统,用于医院管理医护人员的排班、调班等工作。系统提供了完整的排班管理功能,包括科室管理、人员管理、排班规则配置、自动排班等功能。 ## 2. 系统功能模块 ### 2.1 基础信息管理 - 科室信息管理:维护医院各科室基本信息 - 医护人员管理:管理医生、护士等医护人员信息 - 排班类型管理:配置不同的排班类型(如:早班、中班、晚班等) ### 2.2 排班管理 - 排班规则配置:设置各科室排班规则 - 自动排班:根据规则自动生成排班计划 - 排班调整:手动调整排班计划 - 排班查询:查看各科室排班情况 ### 2.3 系统管理 - 用户管理:管理系统用户 - 角色权限:配置不同角色的操作权限 - 系统设置:管理系统基础配置 ## 3. 技术架构 ### 3.1 开发环境 - JDK 1.8 - Maven 3.6 - MySQL 5.7 - SpringBoot 2.2.2 ### 3.2 技术栈 - 后端框架:SpringBoot - 持久层:MyBatis-Plus - 数据库:MySQL - 前端框架:Vue.js - 权限管理:Spring Security ## 4. 数据库设计 主要数据表: - 科室信息表(keshixinxi) - 医护人员表(yihurengyuan) - 排班类型表(paibanleixing) - 排班信息表(paibanxinxi) - 用户表(user) ## 5. 部署说明 ### 5.1 环境要求 - JDK 1.8+ - MySQL 5.7+ - Maven 3.6+ ### 5.2 部署步骤 1. 创建数据库并导入SQL脚本 2. 修改application.yml中的数据库配置 3. 执行maven打包命令:mvn clean package 4. 运行jar包:java -jar xxx.jar ## 6. 使用说明 ### 6.1 系统登录 - 管理员账号:admin - 初始密码:admin ### 6.2 基本操作流程 1. 维护基础信息(科室、人员等) 2. 配置排班规则 3. 生成排班计划 4. 查看和调整排班 ## 7. 注意事项 1. 首次使用请及时修改管理员密码 2. 定期备份数据库 3. 建议定期检查和优化排班规则
MATLAB仿真的夫琅禾费衍射强度图:圆孔、圆环、矩形孔定制研究,MATLAB仿真:夫琅禾费衍射强度图的可定制性——以圆孔、圆环及矩形孔为例的研究分析,MATLAB夫琅禾费衍射强度图仿真 圆孔,圆环,矩形孔可定制。 ,MATLAB; 夫琅禾费衍射; 强度图仿真; 圆孔; 圆环; 矩形孔; 可定制。,MATLAB仿真夫琅禾费衍射强度图:定制孔型(圆孔/圆环/矩形)
详细介绍及样例数据:https://blog.csdn.net/samLi0620/article/details/145652300
基于Dugoff轮胎模型与B08_01基础建模的七自由度车辆动力学模型验证:利用MATLAB 2018及以上版本与CarSim 2020.0软件的仿真对比研究,基于Dugoff轮胎模型与B08_01框架的七自由度车辆动力学模型验证——使用MATLAB 2018及以上版本与CarSim 2020.0软件进行仿真对比研究,七自由度车辆动力学模型验证(Dugoff轮胎模型,B08_01基础上建模) 1.软件: MATLAB 2018以上;CarSim 2020.0 2.介绍: 基于Dugoff轮胎模型和车身动力学公式,搭建7DOF车辆动力学Simulink模型,对相关变量(质心侧偏角,横摆角速度,纵、横向速度及加速度)进行CarSim对比验证。 ,核心关键词:七自由度车辆动力学模型验证; Dugoff轮胎模型; B08_01建模基础; MATLAB 2018以上; CarSim 2020.0; Simulink模型; 变量对比验证。,基于Dugoff轮胎模型的七自由度车辆动力学模型验证与CarSim对比
【毕业设计】基于Java+servlet+jsp+css+js+mysql实现“转赚”二手交易平台_pgj
微猫恋爱聊妹术小程序源码介绍: 微猫恋爱聊妹术小程序源码是一款全新升级的聊天工具,它采用全新主题和UI,完美支持分享朋友圈功能。同时,它的独立后台也进行了大规模更新,让操作更加简单。其中,课堂页面、搜索页面和子话术列表页面等,均增加了流量主展示,具有超多的功能。 安装教程: 您可以先加入微猫恋爱聊妹术小程序源码的赞助群,然后在群内找到魔方安装说明。根据源码编号找到相应的安装说明,非常详细,让您轻松完成安装。
电气安装工程安全技术规程_蒋凯,杨华甫,马仲范,王清禄译;孙照森校;鞍钢工程技术编委会编
基于Copula函数的风光空间相关性联合场景生成与K-means聚类削减MATLAB研究,基于Copula函数的风光空间相关性联合场景生成与K-means聚类削减算法研究,基于copula的风光联合场景生成?K-means聚类并削减 MATLAB 由于目前大多数研究的是不计风光出力之间的相关性影响,但是地理位置相近的风电机组和光伏机组具有极大的相关性。 因此,采用 Copula 函数作为风电、光伏联合概率分布,生成风、光考虑空间相关性联合出力场景,在此基础上,基于Kmeans算法,分别对风光场景进行聚类,从而实现大规模场景的削减,削减到5个场景,最后得出每个场景的概率与每个对应场景相乘求和得到不确定性出力 ,基于Copula的风光联合场景生成; K-means聚类削减; 空间相关性; 概率分布; 场景削减,基于Copula与K-means的风光联合场景生成与削减研究
模块化多电平变流器MMC的VSG控制技术研究:基于MATLAB-Simulink的仿真分析与定制实现——支持三相与任意电平数,构网型模块化多电平变流器MMC的VSG控制策略与仿真模型:三相负荷变动下的虚拟同步发电机控制研究,构网型 模块化多电平变流器 MMC 的VSG控制 同步发电机控制 MATLAB–Simulink仿真模型,可按需求定制 10电平.14电平,任意电平可做。 三相MMC,采用VSG控制。 设置负荷变动,调整有功无功,保持电网电压和频率 ,构网型模块化多电平变流器; MMC的VSG控制; 虚拟同步发电机控制; MATLAB–Simulink仿真模型; 任意电平可做; 三相MMC; 负荷变动; 有功无功调整; 电网电压和频率保持。,基于VSG控制的模块化多电平变流器(MMC)的构网型仿真模型
暗通道算法DCP-Python实现
南师大实验室安全准入知识供学习
纯openMV寻迹小车.zip
【毕业设计】基于Java mvc架构开发的完整购物网站
以下是针对初学者的 **51单片机入门教程**,内容涵盖基础概念、开发环境搭建、编程实践及常见应用示例,帮助你快速上手。
springboot医院信管系统--
springboot私人健身与教练预约管理系统--
yolov8-0的资源