前两天我参加了网易举办的有道难题，只做出了两道题，结果给出的提示都是运行超时（运行时间超过1000ms了）。希望大家帮我优化一下程序，如果程序中有什么不规范的也请您指出。谢谢大家了。
题目内容如下：
A:有“道”难题
描述
‘道’是中国古代哲学的重要范畴。用以说明世界的本原、本体、规律或原理。在不同的哲学体系中，其涵义有所不同。老子所写的《道德经》是关于‘道’的经典著作。
道的原始涵义指道路、坦途，以后逐渐发展为道理，用以表达事物的规律性。这一变化经历了相当长的历史过程。《易经》中有“复自道，何其咎”（《小畜》），“履道坦坦”（《履》），“反复其道，七日来复”(《复》)，都为道路之义。
《尚书•洪范》中说：“无有作好,遵王之道；无有作恶,遵王之路。无偏无党,王道荡荡;无党无偏,王道平平；无反无侧,王道正直”。这里的道，已经有正确的政令、规范和法度的意思,说明“道”的概念已向抽象化发展。
---- 节选自有道词典(http://dict.youdao.com)
Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一。它把每三个8Bit的字节转换为四个6Bit的字节（3*8
= 4*6 = 24），然后把6Bit再添两位高位0，组成四个8Bit的字节，也就是说，转换后的字符串理论上将要比原来的长1/3。
有道的工程师闲暇之余，将Base64编码改成了Base4编码，即把每个8Bit的字节转换成4个2Bit的字节，然后以4个字符来代替。编码和字符的对应方案如下：
00 ---- a
01 ---- o
10 ---- d
11 ---- 空格
这样，编码后的字符串就只会含有字符‘d','a','o'和空格。
例如字符y ,其ASCII码是121，对应的二进制串是01111001，这样分成 01 11 10 01四块后，用Base4编码后的字符串为"o do"。
有道的工程师很好奇，按照这种编码方式，编码后的字符串中含有多少个完整的dao呢？一个完整的dao由连续的‘d','a','o'三个字符组成。
输入
第一行有一个正整数n，代表接下来有n个待编码的原串。（1 <= n <= 10)
接下来有n行，每行有一个长度不超过106的原串，原串中的字符可能为ASCII码中除换行符以外的任意可见字符。
输出
共有n行，每行为一个整数k, 表示输入数据中对应的原串用Base4编码后含有多少个完整的dao。
样例输入
2
www.youdao.com
dict.youdao.com
样例输出
1
1
提示
Java时限是标准时限的3倍，而且对于每个输入文件都有100ms的额外IO时间
我写的程序如下：
import java.util.Scanner;
public class Main {
public static void main(String args[]) throws Exception {
Scanner cin = new Scanner(System.in);
// 接受输入的第一个整数。用来得到要输入的行数。
int a = cin.nextInt();
// 用来存放各个行输入的字符串
String[] inputStr = new String[a];
for(int i=0;i<a;i++){
inputStr[i] = cin.next();
}
// 输出每行字符串中道的个数
for(int j=0;j<a;j++){
System.out.println(getNum(inputStr[j]));
}
}
/**
* 用来得到"道"这个字符"100001"在整个字符串中的个数
* @param str
* @return
*/
private static int getNum(String str) {
// 道的个数
int num =0;
// 道这个字符串"100001"在该行中的位置，如果是-1表示没有字符串"100001"。
int num1 = 0;
// 查找字符串的起始位置
int num2 = 0;
String xuli = "";
// 将字符串转换成字节
byte[] ch = str.getBytes();
// 将字节转化成二进制字符串
for(int i=0;i<ch.length;i++){
xuli+=Integer.toBinaryString(ch[i]);
}
while((num1=xuli.indexOf("100001", num2))!=-1){
num2=num1+1;
num++;
}
return num;
}
}
B:有道饭团
描述
有道为每位员工提供每工作日享受中午与晚上两顿餐费报销，每顿饭额度上限为X元。为了能够用这些钱吃得更丰盛，大家纷纷组成了各种饭团，每天中午和晚上扫荡清华科技园附近各大中小饭馆。
为了使报销过程更加方便，在每个饭团吃完饭的时候，由一个人付帐拿发票，这个人在发票上写上所有饭团成员的姓名，并且拿发票回去报销。如果平均每人的消费超过了额度上限，大家会将超出部分平均补给付帐的同事。
比如，某天中午A B C D E五人到某餐厅吃饭，消费5X +
5元，由A付款，B C D E每人补给A同事1元钱，A同事拿发票可报销得5X元。若消费5X – 5 元，则其他同事无需补钱，A同事拿发票直接报销得到5X – 5元。
由于目前公司的人越来越多，行政MM每天处理这些发票事务非常的繁琐，现在需要你来写一个程序，拿着所有的发票信息，统计一下需要分别给每个人报销多少钱。
输入
输入第一行有一个正整数T，表示下面有T个数据。
对于每个数据，其格式如下
第一行是一个正整数X，表示每个人一顿饭的额度上限，
第二行是一个正整数S，表示饭团报销的发票总数量，
接下来S行分别是每张发票的细节：
对于每一行 输入格式为
n m u1 u2 u3….un ux
n是一个正整数，表示该张发票的饭团人数，m也是一个正整数，表示消费金额总数。
u1..un分别是该饭团的名单，ux为付款人的姓名，ux一定是u1..un中间的一员。
数据中可能会包含一周甚至更长时间的数据，所以，由于每个人在不同时间会参与不同的饭团，所以有些人的名字会出现在好几行内，这是正常现象。
其中0<T<=10, 0<X<=100, 0<S<=10000,
0<n<=10, 0<m<=1000，所有员工的姓名都由大写字母组成，不为空且长度不超过10。
输出
每个数据按照员工姓名字典序，输出分别应该给每个人报销多少钱，如果某人的报销钱数为0，则不需要输出。
请在每组数据结束之后输出一个空行。
样例输入
2
20
4
3 61 A
B C B
2 39 A
B A
4 88 A
B C D C
3 40 B C D B
15
4
3 61 A
B C B
2 39 A
B A
4 88 A
B C D C
3 40 B C D B
样例输出
A 39
B 100
C 80
A 30
B 85
C 60
程序如下：import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class MainB {
public static void main(String args[]) throws Exception {
Scanner cin = new Scanner(System.in);
// 接受输入值，得到要报销的组数
int sum = cin.nextInt();
// 得到每一组的每个人一顿饭的额度上限和饭团报销的发票总数量。
for(int i=0;i<sum;i++){
// 用来存放报销人和应该给报销人的钱。
HashMap map = new HashMap();
// 用来存放报销人，主要用来排序。将map输出时按照list的顺序输出
ArrayList<String> list = new ArrayList<String> ();
// 每个人一顿饭的额度上限
int sumNum = cin.nextInt();
// 饭团报销的发票总数量
int groupNum = cin.nextInt();
// 该张发票的饭团人数
int[] personNum = new int[groupNum];
// 表示消费金额总数。
int[] sumMoney = new int[groupNum];
// 付款人
String[] lastPerSon = new String[groupNum];
for(int j=0;j<groupNum;j++){
personNum[j] = cin.nextInt();
sumMoney[j] = cin.nextInt();
for(int t=0;t<personNum[j]+1;t++){
lastPerSon[j] = cin.next();
}
}
// 对每张发票进行遍历
for(int t=0;t<groupNum;t++){
// 发票的人数
int perNum = personNum[t];
// 消费金额
int sumMoneyTmp = sumMoney[t];
// 付款人
String perSon = lastPerSon[t];
// 如果付款人已经存在在map中，那么将这张发票的钱添加到这个付款人的总价钱上，如果不存在，就添加上 这个付款人，以及他付款的金额
if(map.get(perSon)!=null){
Integer Money = (Integer)map.get(perSon);
int thisMoney = 0;
// 拍到报销金额是否超出了报销总数的上限，超出就按照报销的上限给钱，没有超出，就按照报销的总数给钱
if(perNum*sumNum>sumMoneyTmp){
thisMoney = sumMoneyTmp;
}else{
thisMoney = perNum*sumNum;
}
// 将原来报销的金额加上这次报销的金额就是这个付款人报销的总金额
map.put(perSon, new Integer(thisMoney+Money.intValue()));
}else{
int thisMoney = 0;
// 拍到报销金额是否超出了报销总数的上限，超出就按照报销的上限给钱，没有超出，就按照报销的总数给钱
if(perNum*sumNum>sumMoneyTmp){
thisMoney = sumMoneyTmp;
}else{
thisMoney = perNum*sumNum;
}
map.put(perSon, new Integer(thisMoney));
list.add(perSon);
}
}
// 将报销人按照字典顺序排列
for(int m=0;m<list.size();m++){
for(int n=m;n<list.size();n++){
if(list.get(n).compareTo(list.get(m))<0){
String a = list.get(n);
String b = list.get(m);
list.set(n, b);
list.set(m, a);
}
}
}
// 输出报销人，和报销人报销的总金额
for(int m =0;m<list.size();m++){
System.out.println(list.get(m)+" "+map.get(list.get(m)));
}
}
}
}
posted on 2010-06-02 10:44
fzllcc 阅读(208)
评论(0) 编辑 收藏