作者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/cn.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/cn.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