Yahoo奇摩知識+ 將於 2021 年 5 月 4 日 (美國東部時間) 終止服務。自 2021 年 4 月 20 日 (美國東部時間) 起，Yahoo奇摩知識+ 網站將會轉為唯讀模式。其他 Yahoo奇摩產品與服務或您的 Yahoo奇摩帳號都不會受影響。如需關於 Yahoo奇摩知識+ 停止服務以及下載您個人資料的資訊，請參閱說明網頁。

王
王 發問時間： 電腦與網際網路程式設計 · 9 年前

C++ 字串題目問題

網路上題目

題目:字串變變變

內容 ：

每一組輸入都有兩行不含空白且 ASCII 碼介於 33~126 之間的字串，請告訴我，經過適當的順序調整後，兩個字串會變得一模一樣嗎？

例如，e83k 可以調整順序成 38ek 或 e3k8 等等共 15 種其他排列方式。

輸入說明 ：

輸入如題目描述，當讀到「STOP!!」時結束。

字串長度最長為 1000000 個字元。

輸出說明 ：

如果兩個字串可以變得一樣，輸出 yes，否則輸出 no。

範例輸入 ：

e83k

38ek

asdfghjkl;'

';lkjhgfdsa

1234

4521

_01=1

_=110

SToP!!

stop!!

STOP!!

範例輸出 ：

yes

yes

no

yes

no

我的程式:

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

while(1)

{

char s1[1000001]={0},s2[1000001]={0},s3[7]="STOP!!";

char temp;

cin.getline(s1,1000001);

if(strcmp(s1,s3)==0)

return 0;

cin.getline(s2,1000001);

if(strcmp(s2,s3)==0)

return 0;

int a=strlen(s1),b=strlen(s2);

for(int i=0;i<a;i++)

{

for(int j=i+1;j<a;j++)

{

if(s1[i]>s1[j])

{

temp=s1[i];

s1[i]=s1[j];

s1[j]=temp;

}

}

}

for(int i=0;i<b;i++)

{

for(int j=i+1;j<b;j++)

{

if(s2[i]>s2[j])

{

temp=s2[i];

s2[i]=s2[j];

s2[j]=temp;

}

}

}

if(strcmp(s1,s2) || a!=b)

cout<<"no"<<endl;

else if(strcmp(s1,s2)==0 && a==b)

cout<<"yes"<<endl;

}

}

我的想法是先經過ASCII排列 再比對兩字串

不過上傳後 有2個測資TLE(應該是逾時)

請問有比較快的方法嗎??

盡量不要用太艱深的方法 謝謝

已更新項目:

TO:我最好不要說

"讀第一個字串時紀錄每個 char 的個數"

ex:我輸入e83k 他記錄字元個數為4

然後輸入e83字元個數為3

4!=3 直接輸出NO 接著不用排序直接輸入第二組

是這樣嗎??

我在排序前加入

if(a!=b)

{

cout<<"no"<

2 個已更新項目:

我在排序前加入

if(a!=b)

{

cout<<"no"<

3 個已更新項目:

字一直被吃..=.=

還是TLE

4 個已更新項目:

先謝謝 "我最好不要說" "【帕拉提斯】" "東邪無弓" 三位的建議

首先我學到了sort()這種簡潔的排序方法

雖然我上傳之後多了一個測資AC 不過還是有一個逾時

關於【帕拉提斯】所提到的counting sort，"我最好不要說"有貼出程式碼讓我參考

實在很感謝

不過這邊我實在不懂

for(a=0;a

5 個已更新項目:

for(a=0;a

6 個已更新項目:

c陣列是空的 x[a]是字元

所以c[x[a]]++就是把x[a]的個數+1....是這樣嗎?

這種寫法我是第一次看到

7 個已更新項目:

TO東邪無弓:

您的程式測出來:

AC (34ms, 660KB)

5 個解答

評分
  • chien
    Lv 7
    9 年前
    最佳解答

    這題你給它排序下去，當然 TLE

    開一個陣列 int c[127] = { 0 };

    讀第一個字串時紀錄每個 char 的個數，

    讀第2個字串時用減法

    如果陣列中有出現負值就不合規定

    直接輸出 no 跳下一組。

    應該會 ac

    2012-03-01 23:00:59 補充：

    我舉個例子好了

    假如 2 個字串分別是

    AABCD

    BBBCD

    你先開一個陣列 int c[127] = {0}

    讀完 AABCD 後

    c[65] = 2 c[66] = 1 c[67] = 1 c[68] = 1

    開始讀入 BBBCD

    c[66] --

    c[66] --

    c[66] -- 這時 c[66] = -1

    顯然就可輸出 no 了。

    參考看看。

    2012-03-01 23:04:06 補充：

    你是那個 v00623 嗎

    加油呀 別放棄。

    2012-03-02 00:20:00 補充：

    寫得不太好，不過剛 AC 了，雖然時間高了點，參考一下。

    #include <iostream>

    #include <stdio.h>

    #include <string.h>

    using namespace std;

    int main()

    {

    char x[1000001],y[1000001],z[7]="STOP!!";

    int a;

    while(scanf("%s",&x)!=EOF)

    {

    if(strcmp(x,z)==0) break;

    scanf("%s",&y);

    int c[127]={0};

    for(a=0;a<strlen(x);a++)

    {c[x[a]]++;c[y[a]]--;}

    for(a=0;a<127;a++)

    {if(c[a]<0){printf("no\n");goto next;}}

    printf("yes\n");continue;

    next:;

    }

    return 0;

    }

    2012-03-02 09:33:30 補充：

    樓上的大師寫的程式真是簡潔，

    可惜放上 zerojudge 還是逾時了。

    2012-03-02 10:05:38 補充：

    那題 字串長度最長為 1000000 個字元。

    用 string 好像過不了。

    2012-03-02 10:07:17 補充：

    題目在這

    http://zerojudge.tw/ShowProblem?problemid=a275

    2012-03-02 15:07:25 補充：

    那一題有排入前 20 名的都 1x ms

    我的確要 35 ms

    不過先求有，再求好，

    您說對吧。

    2012-03-02 18:47:19 補充：

    噗 大師

    http://zerojudge.tw/RealtimeStatus?problemid=a275

    最上面那 2 題是幫您測的

    1074592 35 ms

    1074593 34 ms

    2012-03-03 10:04:24 補充：

    在 zerojudge 上作題目

    11 ms 和 12 ms 根本沒啥差別

    因為這是他主機的關係

    網站管理者已做過解釋

    上面也有些討論

    有些題目我用 basic 作答都是 0 ms

    用 c++ 怎麼答都是 4 ms

    不會有人以為 basic 效能比較好吧

    2012-03-03 12:42:21 補充：

    那題 8 ms 就站在排頭了 恭喜

    2012-03-03 13:01:53 補充：

    novus

    我是不該把 strlen 放在迴圈裡，應該先指定個變數 ( 這點我常忘記 )

    謝謝您的提醒。

    那個 scanf 後來有依 東邪 的方法改為 gets 時間也大為改善 ( 12 ms )，

    其實在那網站上也常在提醒 gets scanf cin 的差別。

    我一時 ac 就 po 文上來了，

    不過我開頭就說速度不是很好。當時沒想到。

    2012-03-03 13:14:36 補充：

    http://judge.nccucs.org/

    這裡有一個類似的網站

    測資弄得超大

    我記得其中有一題

    如果不小心把 strlen 放在迴圈裡就爆掉了。

    2012-03-03 14:45:40 補充：

    能測到 8 ms ( 那是真本事 ) 的人提出的建議，

    收下了，哈。

    2012-03-03 14:47:45 補充：

    可惜不能按讚

    殘念。

  • Jacob Lee
    Lv 7
    9 年前

    這裡能有本事讓我心服的，目前為止，不超過10人。

    東邪是其中之一。

    2012-03-04 22:50:10 補充：

    忙到爆!

    226~228到你的地盤忙裡偷閒!

    現在更忙! T.T

  • novus
    Lv 6
    9 年前

    to 我最好不要說

    我是剛剛才注意到這個題目，在我還沒有看到東邪的回答、也還沒看到這串討論、甚至都還沒有理解你的流程時，就基於對模式的敏感性而認為有贅餘

    1. 在迴圈使用 strlen

    2. 索引方式 （您的方法不一定比較不好，但看到這種寫法有時候是有潛在改良空間的）

    這是一種來自經驗的敏感性，可能很不準，可能不值得花時間去分析（例如本題實驗結果並沒有顯著差異），但有助於發現關鍵，例如本題的 scanf

    2012-03-03 12:47:05 補充：

    to 【帕拉提斯】

    方便給一下 C 和 C++ 程式嗎？

  • 東邪無弓
    Lv 7
    9 年前

    想法是正確的，但做法卻未能完善的詮釋想法，有改善空間。

    2012-03-02 16:40:23 補充：

    概略的分析，應可使時間縮短約60％，即不到原來的一半。

    請試著改善看看。

    2012-03-03 01:05:20 補充：

    速度不如預期，是匆促中（趕著和狐群狗黨們哈酒）未改用IO函式所致。

    1.請把 while ( scanf("%s", &a) != EOF )

    　改用 while ( gets(a) != NULL)

    2.再把 scanf("%s", &b);

    　改成 gets(b);

    小改一下，12 ms 等你驗收。

    2012-03-03 01:07:40 補充：

    解題編號：1075042 ＆1075043 (guest) 12ms

    2012-03-03 02:44:13 補充：

    這句： 『想法是正確的，但做法卻未能完善的詮釋想法，有改善空間。』

    是事實的陳述。

    你的程式在處理上，的確有贅餘之舉，難道你還未看出？

    既有贅餘，不亦存在改善空間！

    請你平心靜氣的看看程式碼，便可看出差異在哪裡！

    俺對於效率提升比率60％的說法，因IO之故，未盡客觀，應予修正為10％。

    但效率絕對有提升，是無庸置疑的。

    （能馬上看出 IO 耗時的差異，看似沒啥，卻是經驗！）

    俺後來的幾次測試，都是 11ms。

    2012-03-03 11:32:15 補充：

    11ms 和12 ms，的確有可能是誤差，

    但若多次是11ms，便大大降低了誤差的可能性。

    2012-03-03 12:20:14 補充：

    俺剛又小修了一下，上傳重測。

    解題編號：1075228 guest 8ms

    為免除無謂的紛爭，俺刪答啦！

    2012-03-03 13:49:37 補充：

    俺已刪答，較有立場提出修改意見：

    1.scanf 改用 gets，printf 改用 puts。

    2.C字串已有 Sentinel，用結尾零的偵測取代 strlen。

    3.後置＋＋（－－）改用前置。

    4.陣列索引改用指標。

    祝你再創佳績。

    2012-03-03 14:35:30 補充：

    漏寫了一點：

    if(c[a]<0) ......

    改成

    if(c[a] != 0) ......

    略佳一點點。

    2012-03-04 11:23:13 補充：

    Jacob 大，好久不見了，是否逍遙到澳洲去享受 「Jacob 紅酒」？

    謝謝您的美言，您的程式才真的令人讚嘆！

  • 您覺得這個回答如何？您可以登入為回答投票。
  • ?
    Lv 7
    9 年前

    你的排序用 bubble sort 當然會 TLE......

    紀錄每個字元出現幾次的方法叫做「counting sort」。

    想用排序的方法，可以用 C++ 的 std::sort()。

    2012-03-02 09:09:26 補充：

    程式可以很短：

    http://pastebin.com/ufdYx5N0

    2012-03-03 08:16:23 補充：

    奇怪，我這邊一份 C 一份 C++，在 Local 測時間大概差 1.5~2 倍左右（C++ 比較慢）。

    丟去 server 上以後時間差了近十倍...

    這個比較可能是 compiler 的關係還是 flag 的關係？

還有問題？馬上發問，尋求解答。