前兩天我參加了網(wǎng)易舉辦的有道難題，只做出了兩道題，結(jié)果給出的提示都是運(yùn)行超時(shí)（運(yùn)行時(shí)間超過(guò)1000ms了）。希望大家?guī)臀覂?yōu)化一下程序，如果程序中有什么不規(guī)范的也請(qǐng)您指出。謝謝大家了。
題目?jī)?nèi)容如下：
A:有“道”難題
描述
‘道’是中國(guó)古代哲學(xué)的重要范疇。用以說(shuō)明世界的本原、本體、規(guī)律或原理。在不同的哲學(xué)體系中，其涵義有所不同。老子所寫的《道德經(jīng)》是關(guān)于‘道’的經(jīng)典著作。
道的原始涵義指道路、坦途，以后逐漸發(fā)展為道理，用以表達(dá)事物的規(guī)律性。這一變化經(jīng)歷了相當(dāng)長(zhǎng)的歷史過(guò)程。《易經(jīng)》中有“復(fù)自道，何其咎”（《小畜》），“履道坦坦”（《履》），“反復(fù)其道，七日來(lái)復(fù)”(《復(fù)》)，都為道路之義。
《尚書•洪范》中說(shuō)：“無(wú)有作好,遵王之道；無(wú)有作惡,遵王之路。無(wú)偏無(wú)黨,王道蕩蕩;無(wú)黨無(wú)偏,王道平平；無(wú)反無(wú)側(cè),王道正直”。這里的道，已經(jīng)有正確的政令、規(guī)范和法度的意思,說(shuō)明“道”的概念已向抽象化發(fā)展。
---- 節(jié)選自有道詞典(http://dict.youdao.com)
Base64是網(wǎng)絡(luò)上最常見(jiàn)的用于傳輸8Bit字節(jié)代碼的編碼方式之一。它把每三個(gè)8Bit的字節(jié)轉(zhuǎn)換為四個(gè)6Bit的字節(jié)（3*8
= 4*6 = 24），然后把6Bit再添兩位高位0，組成四個(gè)8Bit的字節(jié)，也就是說(shuō)，轉(zhuǎn)換后的字符串理論上將要比原來(lái)的長(zhǎng)1/3。
有道的工程師閑暇之余，將Base64編碼改成了Base4編碼，即把每個(gè)8Bit的字節(jié)轉(zhuǎn)換成4個(gè)2Bit的字節(jié)，然后以4個(gè)字符來(lái)代替。編碼和字符的對(duì)應(yīng)方案如下：
00 ---- a
01 ---- o
10 ---- d
11 ---- 空格
這樣，編碼后的字符串就只會(huì)含有字符‘d','a','o'和空格。
例如字符y ,其ASCII碼是121，對(duì)應(yīng)的二進(jìn)制串是01111001，這樣分成 01 11 10 01四塊后，用Base4編碼后的字符串為"o do"。
有道的工程師很好奇，按照這種編碼方式，編碼后的字符串中含有多少個(gè)完整的dao呢？一個(gè)完整的dao由連續(xù)的‘d','a','o'三個(gè)字符組成。
輸入
第一行有一個(gè)正整數(shù)n，代表接下來(lái)有n個(gè)待編碼的原串。（1 <= n <= 10)
接下來(lái)有n行，每行有一個(gè)長(zhǎng)度不超過(guò)106的原串，原串中的字符可能為ASCII碼中除換行符以外的任意可見(jiàn)字符。
輸出
共有n行，每行為一個(gè)整數(shù)k, 表示輸入數(shù)據(jù)中對(duì)應(yīng)的原串用Base4編碼后含有多少個(gè)完整的dao。
樣例輸入
2
www.youdao.com
dict.youdao.com
樣例輸出
1
1
提示
Java時(shí)限是標(biāo)準(zhǔn)時(shí)限的3倍，而且對(duì)于每個(gè)輸入文件都有100ms的額外IO時(shí)間
我寫的程序如下：
import java.util.Scanner;
public class Main {
public static void main(String args[]) throws Exception {
Scanner cin = new Scanner(System.in);
// 接受輸入的第一個(gè)整數(shù)。用來(lái)得到要輸入的行數(shù)。
int a = cin.nextInt();
// 用來(lái)存放各個(gè)行輸入的字符串
String[] inputStr = new String[a];
for(int i=0;i<a;i++){
inputStr[i] = cin.next();
}
// 輸出每行字符串中道的個(gè)數(shù)
for(int j=0;j<a;j++){
System.out.println(getNum(inputStr[j]));
}
}
/**
* 用來(lái)得到"道"這個(gè)字符"100001"在整個(gè)字符串中的個(gè)數(shù)
* @param str
* @return
*/
private static int getNum(String str) {
// 道的個(gè)數(shù)
int num =0;
// 道這個(gè)字符串"100001"在該行中的位置，如果是-1表示沒(méi)有字符串"100001"。
int num1 = 0;
// 查找字符串的起始位置
int num2 = 0;
String xuli = "";
// 將字符串轉(zhuǎn)換成字節(jié)
byte[] ch = str.getBytes();
// 將字節(jié)轉(zhuǎn)化成二進(jìn)制字符串
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:有道飯團(tuán)
描述
有道為每位員工提供每工作日享受中午與晚上兩頓餐費(fèi)報(bào)銷，每頓飯額度上限為X元。為了能夠用這些錢吃得更豐盛，大家紛紛組成了各種飯團(tuán)，每天中午和晚上掃蕩清華科技園附近各大中小飯館。
為了使報(bào)銷過(guò)程更加方便，在每個(gè)飯團(tuán)吃完飯的時(shí)候，由一個(gè)人付帳拿發(fā)票，這個(gè)人在發(fā)票上寫上所有飯團(tuán)成員的姓名，并且拿發(fā)票回去報(bào)銷。如果平均每人的消費(fèi)超過(guò)了額度上限，大家會(huì)將超出部分平均補(bǔ)給付帳的同事。
比如，某天中午A B C D E五人到某餐廳吃飯，消費(fèi)5X +
5元，由A付款，B C D E每人補(bǔ)給A同事1元錢，A同事拿發(fā)票可報(bào)銷得5X元。若消費(fèi)5X – 5 元，則其他同事無(wú)需補(bǔ)錢，A同事拿發(fā)票直接報(bào)銷得到5X – 5元。
由于目前公司的人越來(lái)越多，行政MM每天處理這些發(fā)票事務(wù)非常的繁瑣，現(xiàn)在需要你來(lái)寫一個(gè)程序，拿著所有的發(fā)票信息，統(tǒng)計(jì)一下需要分別給每個(gè)人報(bào)銷多少錢。
輸入
輸入第一行有一個(gè)正整數(shù)T，表示下面有T個(gè)數(shù)據(jù)。
對(duì)于每個(gè)數(shù)據(jù)，其格式如下
第一行是一個(gè)正整數(shù)X，表示每個(gè)人一頓飯的額度上限，
第二行是一個(gè)正整數(shù)S，表示飯團(tuán)報(bào)銷的發(fā)票總數(shù)量，
接下來(lái)S行分別是每張發(fā)票的細(xì)節(jié)：
對(duì)于每一行 輸入格式為
n m u1 u2 u3….un ux
n是一個(gè)正整數(shù)，表示該張發(fā)票的飯團(tuán)人數(shù)，m也是一個(gè)正整數(shù)，表示消費(fèi)金額總數(shù)。
u1..un分別是該飯團(tuán)的名單，ux為付款人的姓名，ux一定是u1..un中間的一員。
數(shù)據(jù)中可能會(huì)包含一周甚至更長(zhǎng)時(shí)間的數(shù)據(jù)，所以，由于每個(gè)人在不同時(shí)間會(huì)參與不同的飯團(tuán)，所以有些人的名字會(huì)出現(xiàn)在好幾行內(nèi)，這是正常現(xiàn)象。
其中0<T<=10, 0<X<=100, 0<S<=10000,
0<n<=10, 0<m<=1000，所有員工的姓名都由大寫字母組成，不為空且長(zhǎng)度不超過(guò)10。
輸出
每個(gè)數(shù)據(jù)按照員工姓名字典序，輸出分別應(yīng)該給每個(gè)人報(bào)銷多少錢，如果某人的報(bào)銷錢數(shù)為0，則不需要輸出。
請(qǐng)?jiān)诿拷M數(shù)據(jù)結(jié)束之后輸出一個(gè)空行。
樣例輸入
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);
// 接受輸入值，得到要報(bào)銷的組數(shù)
int sum = cin.nextInt();
// 得到每一組的每個(gè)人一頓飯的額度上限和飯團(tuán)報(bào)銷的發(fā)票總數(shù)量。
for(int i=0;i<sum;i++){
// 用來(lái)存放報(bào)銷人和應(yīng)該給報(bào)銷人的錢。
HashMap map = new HashMap();
// 用來(lái)存放報(bào)銷人，主要用來(lái)排序。將map輸出時(shí)按照l(shuí)ist的順序輸出
ArrayList<String> list = new ArrayList<String> ();
// 每個(gè)人一頓飯的額度上限
int sumNum = cin.nextInt();
// 飯團(tuán)報(bào)銷的發(fā)票總數(shù)量
int groupNum = cin.nextInt();
// 該張發(fā)票的飯團(tuán)人數(shù)
int[] personNum = new int[groupNum];
// 表示消費(fèi)金額總數(shù)。
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();
}
}
// 對(duì)每張發(fā)票進(jìn)行遍歷
for(int t=0;t<groupNum;t++){
// 發(fā)票的人數(shù)
int perNum = personNum[t];
// 消費(fèi)金額
int sumMoneyTmp = sumMoney[t];
// 付款人
String perSon = lastPerSon[t];
// 如果付款人已經(jīng)存在在map中，那么將這張發(fā)票的錢添加到這個(gè)付款人的總價(jià)錢上，如果不存在，就添加上 這個(gè)付款人，以及他付款的金額
if(map.get(perSon)!=null){
Integer Money = (Integer)map.get(perSon);
int thisMoney = 0;
// 拍到報(bào)銷金額是否超出了報(bào)銷總數(shù)的上限，超出就按照?qǐng)?bào)銷的上限給錢，沒(méi)有超出，就按照?qǐng)?bào)銷的總數(shù)給錢
if(perNum*sumNum>sumMoneyTmp){
thisMoney = sumMoneyTmp;
}else{
thisMoney = perNum*sumNum;
}
// 將原來(lái)報(bào)銷的金額加上這次報(bào)銷的金額就是這個(gè)付款人報(bào)銷的總金額
map.put(perSon, new Integer(thisMoney+Money.intValue()));
}else{
int thisMoney = 0;
// 拍到報(bào)銷金額是否超出了報(bào)銷總數(shù)的上限，超出就按照?qǐng)?bào)銷的上限給錢，沒(méi)有超出，就按照?qǐng)?bào)銷的總數(shù)給錢
if(perNum*sumNum>sumMoneyTmp){
thisMoney = sumMoneyTmp;
}else{
thisMoney = perNum*sumNum;
}
map.put(perSon, new Integer(thisMoney));
list.add(perSon);
}
}
// 將報(bào)銷人按照字典順序排列
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);
}
}
}
// 輸出報(bào)銷人，和報(bào)銷人報(bào)銷的總金額
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 閱讀(225)
評(píng)論(0) 編輯 收藏