Discussion:
[問題] 邏輯問題
(时间太久无法回复)
h***@ptt.cc
2007-01-31 23:46:09 UTC
Permalink
我有個問題
使用者輸入字串
如果aaa則輸出0,如果遇到aba則輸出1

ex. aababaaabaaa
result: 100

ex. aaababaaaabbababa
result: 0101

效率與簡單為重,大大們會怎麼作呢?

我想到的作法是,以兩個b以上為條件,把字串split,再去作條件測試

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.215.137.223
小安
2007-02-01 00:20:29 UTC
Permalink
※ 引述《hangting ()》之銘言:
: 我有個問題
: 使用者輸入字串
: 如果aaa則輸出0,如果遇到aba則輸出1
: ex. aababaaabaaa
: result: 100
: ex. aaababaaaabbababa
: result: 0101
: 效率與簡單為重,大大們會怎麼作呢?
: 我想到的作法是,以兩個b以上為條件,把字串split,再去作條件測試

其實我認為直接用 indexOf 去檢查就足夠了

因為在做字串比對時,只要前方的字首不同時,

就不會繼續完成目前的檢查,而是從下一個字元開始

所以與其先過濾掉部份字串,還不如直接檢查就好

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.170.216.110
骨頭
2007-02-01 03:40:05 UTC
Permalink
※ 引述《tkcn (小安)》之銘言:
: ※ 引述《hangting ()》之銘言:
: : 我有個問題
: : 使用者輸入字串
: : 如果aaa則輸出0,如果遇到aba則輸出1
: : ex. aab aba aabaaa
: : result: 100
: : ex. aaa b abaaaabbababa
: : result: 0101
: : 效率與簡單為重,大大們會怎麼作呢?
: : 我想到的作法是,以兩個b以上為條件,把字串split,再去作條件測試
: 其實我認為直接用 indexOf 去檢查就足夠了
: 因為在做字串比對時,只要前方的字首不同時,
: 就不會繼續完成目前的檢查,而是從下一個字元開始
: 所以與其先過濾掉部份字串,還不如直接檢查就好


其實我覺得原PO的這個問題的定義不清。~.~


關於這種格式在處理上應該盡量利用正則表示式來處理會比較好,
http://blog.matrix.org.cn/blueRockey/date/200605

這網頁下方有一些關於字串用正則式的替換,
透過find() 跟 appendReplacement 的處理,


再配合 "(aaa)|(aba)" 的regexp推測應該可以處理,
不過公司的電腦沒有Java環境,所以就不實做了,只提出來做參考。:P


--
 String temp="relax"; | Life just like programing
 while(buringlife) String.forgot(temp); | to be right or wrong
 while(sleeping) brain.setMemoryOut(); | need not to say
 stack.push(life.running); | the complier will
 stack.push(scouting.buck()); | answer your life
 stack.push(bowling.practice()); | Bone everything

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.218.69.114
遙遠的旅人
2007-02-01 16:39:13 UTC
Permalink
※ 引述《hangting ()》之銘言:
: 我有個問題
: 使用者輸入字串
: 如果aaa則輸出0,如果遇到aba則輸出1
: ex. aababaaabaaa
: result: 100

這個的答案是11010吧?

: ex. aaababaaaabbababa
: result: 0101

這題應該是:0110011

要不要再說清楚你的判斷邏輯呢?

: 效率與簡單為重,大大們會怎麼作呢?
: 我想到的作法是,以兩個b以上為條件,把字串split,再去作條件測試




--

JAVA 是一個靜態型別reference指定、強物件型別判定的語言。

屬於類C/C++族。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.116.116
h***@ptt.cc
2007-02-01 16:58:20 UTC
Permalink
※ 引述《zanyking (遙遠的旅人)》之銘言:
: ※ 引述《hangting ()》之銘言:
: : 我有個問題
: : 使用者輸入字串
: : 如果aaa則輸出0,如果遇到aba則輸出1
: : ex. aababaaabaaa
: : result: 100
: 這個的答案是11010吧?
: : ex. aaababaaaabbababa
: : result: 0101
: 這題應該是:0110011
: 要不要再說清楚你的判斷邏輯呢?
: : 效率與簡單為重,大大們會怎麼作呢?
: : 我想到的作法是,以兩個b以上為條件,把字串split,再去作條件測試

抱歉沒講清楚~字串依照順序判斷~由左到右
同順序中不可已有另一個順序
例如: aaaba
結果只會是:0

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.215.137.223
遙遠的旅人
2007-02-01 17:25:10 UTC
Permalink
※ 引述《hangting ()》之銘言:
: ※ 引述《zanyking (遙遠的旅人)》之銘言:
: : 這個的答案是11010吧?
: : 這題應該是:0110011
: : 要不要再說清楚你的判斷邏輯呢?
: 抱歉沒講清楚~字串依照順序判斷~由左到右
: 同順序中不可已有另一個順序
: 例如: aaaba
: 結果只會是:0

不要用Split,太慢。

1.String轉char[] arr

2.跑迴圈
for(int i=0;i<=arr.length-3;i++)
{
if(arr[i]=='a'&& arr[i+2]=='a')
{
if(arr[i+1]=='a')print(0);
else if(arr[i+1]=='b')print(1);
else countinue;
i+=2;
}
}

直接在BBS上寫,沒有想太多,所以可能有錯,就大家找個碴吧。


--

JAVA 是一個靜態型別reference指定、強物件型別判定的語言。

屬於類C/C++族。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.116.116
阿嘎
2007-02-06 02:06:39 UTC
Permalink
※ 引述《hangting ()》之銘言:
: 我有個問題
: 使用者輸入字串
: 如果aaa則輸出0,如果遇到aba則輸出1
: ex. aababaaabaaa
: result: 100
: ex. aaababaaaabbababa
: result: 0101
: 效率與簡單為重,大大們會怎麼作呢?
: 我想到的作法是,以兩個b以上為條件,把字串split,再去作條件測試


給你的建議是STACK

有好的資料結構可以用為什麼不用呢?
{
1.先PUSH三個資料

2.CHECK 是否為aba

2.1 是==>print "1" 並pop三個出去 在push 3個資料進來 goto 2
2.2 不是==>pop一個出去 並再push一個進來 goto 2
}
至於結束條件自己想吧

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.114.0.228
失意男
2007-02-07 03:20:25 UTC
Permalink
※ 引述《zanyking (遙遠的旅人)》之銘言:
: ※ 引述《hangting ()》之銘言:
: : 抱歉沒講清楚~字串依照順序判斷~由左到右
: : 同順序中不可已有另一個順序
: : 例如: aaaba
: : 結果只會是:0
: 不要用Split,太慢。
: 1.String轉char[] arr
: 2.跑迴圈
: for(int i=0;i<=arr.length-3;i++)
: {
: if(arr[i]=='a'&& arr[i+2]=='a')
: {
: if(arr[i+1]=='a')print(0);
: else if(arr[i+1]=='b')print(1);
: else countinue;
: i+=2;
: }
: }
: 直接在BBS上寫,沒有想太多,所以可能有錯,就大家找個碴吧。
http://rafb.net/p/dmswEV84.html
剛剛本著好奇心寫寫看
本來想用regex 但是這題目好像不太適合
用了上面大大的方法寫出來了(不愧是在BBS上打的 問題不少...)
順便一提
http://rafb.net/paste/
這裡拿來貼程式碼很好用
比直接打在BBS上好得多
--
從C++版偷來的網址...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.113.77.95
阿嘎
2007-02-10 10:32:27 UTC
Permalink
�o�D��indexOf�O���Z���IJv���@�ؤ��k�F


�p�G��indexOf�Ӽg�٥����`�N�@�U�����p



�{���X�p�U:



import java.lang.*;
public class Code
{
public static void main(String args[])
{
String str1="aaababaaaabbababa"; //���l�r�����C
String str2=""; //�ťաA�o��result�A�@�}�l����
int index1=0; //�Ψө����l�r�ꤤ"aba"�����m
int index2=0; //****************"aaa"�����m
while(true)
{
index1 = str1.indexOf("aba"); //step.1�@�}�l���o���r
index2 = str1.indexOf("aaa"); //�ꪺ���m

if(index1==-1)
index1=999;
if(index2==-1)
index2=999;
if((index1==999)&&(index2==999))
break;
if(index1<index2) //step.2�������r�ꪺ
{ if(index1==-1) //�����A�����r��index�p
continue;
str2=str2+"1";
str1 = str1.substring(0,index1)+"***"+
str1.substring(index1+3);
}

else
{ if(index2==-1)
continue;
str2=str2+"0";
str1 = str1.substring(0,index2)+"***"+str1.substring(index2+3);
}
}
System.out.println(str2); //step.3�L�X���G
}
}


note:***�O�N���ΨӴ�����w���쪺�l�r���A�ϰj�饿�`�B�@

999 �O�ۤv�]�w���@�Ӥj�ơA�]��index�b�䤣���l�r�ꪺ�ɫ��|�Ǧ^-1
�Y�S���]�w���ơA�hif�|�~�P






--
�� �o�H��: ���������~�{(ptt.cc)
�� From: 59.114.0.228
遙遠的旅人
2007-02-17 04:20:40 UTC
Permalink
※ 引述《DavyBlue (失意男)》之銘言:
: : 直接在BBS上寫,沒有想太多,所以可能有錯,就大家找個碴吧。
: http://rafb.net/p/dmswEV84.html
: 剛剛本著好奇心寫寫看
: 本來想用regex 但是這題目好像不太適合
: 用了上面大大的方法寫出來了(不愧是在BBS上打的 問題不少...)
: 順便一提
: http://rafb.net/paste/
: 這裡拿來貼程式碼很好用
: 比直接打在BBS上好得多

DeBUG完的結果也順便PO一下吧,這樣可以讓討論串更加完整。

剛剛重看這個討論串的時候突然想到一個問題。

String to char Array的效率到底如何啊?所以就開了eclipse去看看原始碼。

public char[] toCharArray() {
char result[] = new char[count];
getChars(0, count, result, 0);
return result;
}

所以它new了一個新的char[]來當ans回傳,至於getChars如何運作呢?

public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
if (srcBegin < 0) {
throw new StringIndexOutOfBoundsException(srcBegin);
}
if (srcEnd > count) {
throw new StringIndexOutOfBoundsException(srcEnd);
}
if (srcBegin > srcEnd) {
throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
}
System.arraycopy(value, offset + srcBegin, dst, dstBegin,
srcEnd - srcBegin);
}

所以顯然的,他是透過System.arraycopy()來實做的,雖然不知道底層實做
的手段,但至少確定了在JAVA的世界裡,toCharArray()方法效率應該不錯。




--

JAVA 是一個靜態型別reference指定、強物件型別判定的語言。

屬於類C/C++族。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.242.79
ArssertionError
2007-02-17 07:16:47 UTC
Permalink
※ 引述《zanyking (遙遠的旅人)》之銘言:
: ※ 引述《DavyBlue (失意男)》之銘言:
: DeBUG完的結果也順便PO一下吧,這樣可以讓討論串更加完整。
托你的福 又重寫了一次
之前那個貼CODE的網站 連結過沒幾天就爆了
好像只能暫時放
下面是可以work的完整程式碼
import java.util.*;
public class ToArrayTest{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
System.out.print("Please Input a String with a and b:");
char arr[] = sc.next().toCharArray();//將輸入字串放入char陣列
for(int i=0;i<=arr.length-2;i++){//這裡長度應該是-2
if(arr[i] == 'a' && arr[i+2] == 'a'){
if(arr[i+1]=='a'){
System.out.print("0");
i+=2;//這裡也要累加
}
else if(arr[i+1]=='b'){
System.out.print("1");
i+=2;//這裡也要累加
}
}//這邊不用在else做任何動作
}
System.out.println();//最後做個換行比較好閱讀結果
}
}

如果有人想要結合ArrayList和regex的解法的話我再mail給他
寫起來麻煩又長...
Pattern跟Matcher的應用

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.121.240.218
※ 編輯: DavyBlue 來自: 203.121.240.218 (02/17 15:16)
骨頭
2007-02-17 12:19:52 UTC
Permalink
※ 引述《DavyBlue (ArssertionError)》之銘言:
: ※ 引述《zanyking (遙遠的旅人)》之銘言:
: : DeBUG完的結果也順便PO一下吧,這樣可以讓討論串更加完整。
: 托你的福 又重寫了一次
: 之前那個貼CODE的網站 連結過沒幾天就爆了
: 好像只能暫時放
: 下面是可以work的完整程式碼
: 如果有人想要結合ArrayList和regex的解法的話我再mail給他
: 寫起來麻煩又長...
: Pattern跟Matcher的應用

真是又麻煩又長...(煙)

──────解決問題用─────────────────────

//import java.util.regex.*;

String word="aaababaaaabbababa"; //Scanner不是重點,不另寫.

Pattern p1 = Pattern.compile("(aaa)|(aba)");
Matcher m1 = p1.matcher(word);

while(m1.find()){
if(m1.group().matches("aaa")){
System.out.print("0");
}else{
System.out.print("1");
}
}

System.out.println();


──彈性較大版───since 1.5.0──────────────

//import java.util.regex.*;
//import java.util.*;

String word="aaababaaaabbababa";
//同上 Scanner(或BufferedReader)不另寫


HashMap<String,String> HM=new HashMap<String,String>();

/*在這裡設立規則*/
HM.put("aaa","0");
HM.put("aba","1");

/*以下不需變動*/

Iterator<String> ir=HM.keySet().iterator();

StringBuffer pattern=new StringBuffer("");
while(ir.hasNext()){
pattern.append(String.format("(%s)",ir.next()));
if(ir.hasNext()) pattern.append("|");
}

Matcher m1 = Pattern.compile(pattern.toString()).matcher(word);

while(m1.find()){
System.out.print(HM.get((m1.group())));
}

System.out.println();

--
黑貓白貓 能抓的到老鼠的就是好貓 ;p

--
 String temp="relax"; | Life just like programing
 while(buringlife) String.forgot(temp); | to be right or wrong
 while(sleeping) brain.setMemoryOut(); | need not to say
 stack.push(life.running); | the complier will
 stack.push(scouting.buck()); | answer your life
 stack.push(bowling.practice()); | Bone everything

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.171.121.11
※ 編輯: TonyQ 來自: 218.171.121.11 (02/17 20:14)
※ 編輯: TonyQ 來自: 218.171.121.11 (02/17 20:19)
Loading...