作者Gway (我愛的你 也愛我 好嗎?)
看板C_and_CPP
標題Re: [問題] 詢問 C 程式設計的問題
時間Fri Aug 10 16:36:48 2018
Status Update:
原先的code是我想的字元加總拿來當index是有問題(感謝指正)
後來我的解法是:
不使用array改成使用binary tree儲存每筆資料
這樣做的好處是 輸入完後 可以不用sort
直接binary search。
有興趣的人可以看一下我的解法。
分享一下程式碼:
https://goo.gl/kF8bJs
感謝大家的討論，看到有人用Link-List，我才想到要用tree，
果然大家腦力激盪比較能有好解法，感謝板上的大家。
※ 引述《Gway (我愛的你 也愛我 好嗎?)》之銘言：
參加了一個簡單的線上30天刷題(每天一題)，遇到第8天的題目寫完後，
還是都只能過 基礎 testcase0 其它的 testcase 1~5 全部fail...
想上來跟大家討論一下 是否有神人可以解惑
題目網址如下:
https://goo.gl/3PG61f
程式碼如下:
https://gist.github.com/ablueway/47d9b94d19e83fdfa4b3c64579b3515d
補充說明(Supplement)：
我想知道用C寫如何解決此題，其他語言的方法暫時不考慮，
程式碼最上方配合題意定義了基礎資料結構(name/number/idx)，
之前使用strcmp的時候想不出來如何與quicksort做結合
所以資料結構多了idx欄位，是將輸入的string的每個char加總得到的值，
拿來為了後面排序使用。
針對輸入內容用quick sort排序+查找時使用binary search，
但還是過不了測資.... Orz
寫得有點暴力 ...請各位多多包涵
有啥好想法 大家可以討論看看
謝謝歐
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.177.221
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1533718198.A.A29.html
※ 編輯: Gway (125.227.177.221), 08/08/2018 16:51:20
※ 編輯: Gway (125.227.177.221), 08/08/2018 16:56:17
1F：推 b0920075: 你可以去找找他的題目意義和相關的資料結構 08/08 16:54
2F：→ b0920075: 喔喔我沒看到前面的內容，當我沒說 08/08 17:02
3F：→ sarafciel: 你怎麼會覺得char value加起來可以定序呢XD 08/08 17:48
4F：推 bibo9901: 其實stdlib.h就有qsort()和bsearch() 08/08 17:56
5F：推 s06i06: 他都跟你說要用hash了 08/08 19:05
6F：推 moebear: 我偷看解答 跟你作法一樣的過了 直接用字串來排序 08/08 19:25
7F：→ moebear: strcmp()<0 08/08 19:26
8F：→ moebear: <= 08/08 19:26
10F：→ stimim: quick_sort 排完之後把東西印出來，看有沒有照你想的排 08/08 20:50
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.177.221
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1533890210.A.E2C.html
11F：→ oToToT: why not hashtable? 理論上效率會比較好吧XD 08/12 01:19
12F：→ Gway: 願聞hash的做法 請大大明示之？ 08/12 10:05
13F：→ Gway: 可否提供hash fun的實作想法呢？hash是查找快O(1)但如果hash 08/12 10:09
14F：→ Gway: fun不好 很多碰撞 不也是要串在list上，最後查找也是O(n)? 08/12 10:09
15F：→ Gway: BST O(Lon n)會比較差嗎？謝謝 08/12 10:09
16F：→ cphe: hash之後也可以再用tree串起來，這應該都是worst case才會這 08/12 14:29
17F：→ cphe: 樣，其實刷code用C真的是很麻煩，以前也刷過一陣子 08/12 14:29
18F：→ cphe: 可考慮用c++或其他語言，基本的資料結構有支援寫code很快的 08/12 14:30