作者TampaBayRays (光芒今年拿冠军)
看板Grad-ProbAsk
标题[理工] 台大资结
时间Tue Feb 6 09:56:39 2018
Height从0还是1开始啊？
我假设写在手写最後面有用吗XD
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.9.155.142
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1517882204.A.58B.html
1F：推 leoone: 1吧 02/06 09:59
2F：→ leoone: 看到连考两天均摊分析 直接笑出来 02/06 09:59
3F：推 cutearia: 猜1 02/06 10:01
4F：推 stacy62123: 1吧 02/06 10:01
5F：推 Dora5566: double function 大家算多少 02/06 10:04
6F：→ Dora5566: hash 那题 02/06 10:04
7F：推 gary70812: 後面那几题应该不用写虚拟码吧… 02/06 10:05
8F：→ gary70812: 好像到4把 02/06 10:06
9F：推 s1020824: 应该是4吧 02/06 10:06
10F：推 ghost1025: 我怎麽记得我看过这句：h是root到leaf所经的longest pa 02/06 10:06
11F：→ ghost1025: th长Q_Q 02/06 10:06
12F：推 jch660tw: 回楼上 我也看过 02/06 10:08
13F：推 sarsman: 如果今年跟去年的出题老师一样那应该不用写 02/06 10:09
14F：推 leoone: 可是height是定义最大level值吧 02/06 10:09
15F：推 yaya517: 我也看过 台大某年资结考古题 02/06 10:09
16F：→ leoone: 最後一题是DFS+topi 跟dijkstra吗？ 02/06 10:10
17F：推 gary70812: 最後一题我写bfs 和 dij 但都没有写code不知道会不会怎 02/06 10:11
18F：→ gary70812: 样 02/06 10:11
19F：推 sarsman: weight相同，BFS就好了吧 02/06 10:11
20F：推 leoone: 我是把过程写给他而已 毕竟他要分析time 没写感觉抖抖的 02/06 10:12
21F：推 s06i06: 我也是写这样 然而不觉得会有分... 02/06 10:12
22F：推 item0932: bfs就好+1 02/06 10:14
23F：推 ahahahahah: 有一题是不是多选 02/06 10:15
24F：推 kobebset105: Remove bst那题是什麽啊 02/06 10:17
26F：推 TMDTMD2487: bst我两个都选了 02/06 10:17
27F：推 leoone: 有多选@@？ 02/06 10:17
28F：推 sarsman: 我只有选砍掉最接近的数值的选项 02/06 10:19
29F：推 qaswed101: 我也BFS 快冷死了外面 02/06 10:20
30F：推 leoone: Hash search 大家算多少呢？ 3.0？ 02/06 10:20
31F：推 kai3570: 只有我从0吗... 02/06 10:23
32F：推 Dora5566: 我也从0 别吓我啊 02/06 11:21
33F：→ Dora5566: 1.BFS 2.BFS +Dij 02/06 11:22
34F：→ yolo7033: 楼上这麽早交卷喔 02/06 12:09
35F：推 Dora5566: 我会的写完就出来吃饭ㄌ 02/06 12:11
36F：推 leo0519: 我也从0 呵呵 02/06 12:11
37F：推 gary70812: 选择题也要写外面吗 02/06 12:16
38F：推 Dora5566: 剩最有把握的数学了，加油 02/06 12:17
39F：→ Dora5566: 垦得鸡真TM难吃 02/06 12:17
40F：推 MOUOREO: 我怎麽觉得是从1啊 02/06 12:24
41F：推 HungDa: 哥从1没定义清楚啊，而且出题老师又不同 02/06 12:32
42F：推 kai3570: 这种情况台大会不会都给分啊QQ 02/06 12:35
43F：推 MOUOREO: Array index都从1了 02/06 12:38
44F：推 a020304888a: 从0没选项可选吧 02/06 12:38
45F：→ gary70812: hash算3.6 qq 02/06 12:42
46F：推 kai3570: 我记得都有选项啊，还是我算错?! 02/06 12:45
47F：推 ahahahahah: 我也记得都有可以选的 02/06 12:45
48F：推 MOUOREO: hash 3.6+1 02/06 12:46
49F：推 Dora5566: array 从1吧 从0没选项 02/06 12:48
50F：推 kai3570: 喔对array是从1，可是height从0也有选项 02/06 12:49
51F：→ Dora5566: 对 02/06 12:50
52F：→ Dora5566: 好怕height 倒扣就差了10分 QQ 02/06 12:51
53F：推 gary70812: 有到扣？ 02/06 12:51
54F：推 ghost1025: 有倒扣 02/06 12:57
55F：→ HungDa: 没吧 02/06 12:58
56F：推 rondoya: 有倒扣啊== 02/06 12:59
57F：推 TS28: 有倒扣唷 考卷第一行 02/06 12:59
58F：推 sarsman: 有，倒扣当题分数 02/06 13:00
59F：推 Gogoro5566: 有说答错倒扣该题分数 02/06 13:00
60F：推 leoone: 是扣到该题0分还是整张考卷扣该题分数QQ 02/06 13:02
61F：推 ap954212: 整张 02/06 13:03
62F：推 gary70812: …连後面都倒扣喔 早知道deque那题不写了 02/06 13:05
63F：推 sarsman: 後面没有吧…？ 02/06 13:06
64F：推 ahahahahah: Dequeue写了2面....结果才6分QQ 02/06 13:10
65F：推 leo0519: 他只说一到四有倒扣吧 02/06 13:12
66F：推 HungDa: 倒扣是几分啊 02/06 13:14
67F：→ leo0519: 就该题的分数 02/06 13:18
68F：推 leoone: 痛哭 没发现那题要多选 02/06 13:18
69F：推 HungDa: 我也没多选要+365惹 02/06 13:26
70F：→ nova06091: hash 364+1 02/06 13:51
71F：推 Dora5566: 哪题多选…? 02/06 14:37
72F：推 jerry900287: 干等等啦 heap 那题是top down 喔？ 02/06 14:37
73F：→ jerry900287: 我还以爲老师那题组最後一题出错欸干 02/06 14:38
74F：推 s1020824: 是吧 不然bottom up做不出来 02/06 14:38
75F：→ jerry900287: ..............................我这一年都在打手枪 02/06 14:39
76F：推 ghost1025: 楼上QQ 02/06 14:40
77F：推 jerry900287: 不行拉 说不定 heap那题多选大家都错 02/06 14:42
78F：→ jerry900287: 欧噎 02/06 14:42
79F：→ jerry900287: 会不会到最後 不答题的才是赢家 02/06 14:43
80F：推 leoone: 整张考卷只写背後演算法好像也可以60齁 02/06 14:44
81F：推 winiel559: 我想greedy反例想超久，後面都乱写= = 02/06 14:47
82F：推 jerry900287: 母汤喔教授 给我送分喔 02/06 14:50
83F：推 leoone: 其实他给的example就是Greedy反例了 02/06 14:58
84F：推 jerry900287: 那index 3是多少 是7吗 给我说是7喔 02/06 15:00
85F：推 leoone: 6吧XD 02/06 15:06
86F：推 jerry900287: 呜呜呜呜呜呜呜 02/06 15:06
87F：推 leoone: 应该啦 有点忘惹 02/06 15:08
88F：推 jerry900287: 落下的不是我的泪 是我碎裂的心 02/06 15:10
89F：推 ghost1025: 7 02/06 15:17
90F：→ ghost1025: -1 02/06 15:17
91F：推 jerry900287: 你这个小淘气 02/06 15:19
92F：推 kai3570: 我好像也写6 XD 02/06 15:37
93F：推 starbygod: 抱歉我觉得很greedy 02/06 16:13
94F：推 jerry900287: 干 heap 那题组 最後两题分别几分啊 02/06 18:08
95F：推 can18: 7/7吧 02/06 18:23
96F：→ can18: heap第二题是O(n^2)吗 02/06 18:23
97F：推 leoone: 哪里有heap? 02/06 18:23
98F：→ can18: stack做 dequeu 说错 02/06 18:27
99F：推 leoone: 完全忘记第二题问啥XD 02/06 18:33
100F：推 can18: 是否amortized cost 为O(n) 02/06 18:54
101F：推 ahahahahah: 是吧 02/06 18:56
102F：推 can18: double end queue也是吗 02/06 18:57
103F：→ can18: 你怎麽用stack 做 double end queue的 02/06 18:57
104F：→ ahahahahah: 我两题都写O(n) 02/06 18:57
105F：→ ahahahahah: 差不多一样作法 02/06 18:58
106F：→ ahahahahah: 写了两面pseudo code 结果才6分QQ 02/06 18:58
107F：推 can18: 如果交叉push 在 head rear 也可以在O(n) ? 02/06 18:59
108F：推 ahahahahah: 做出来好像是O(n)+O(n)之类的 02/06 19:01
109F：推 can18: 你stack 怎麽实现 push 跟 pop 两个方向的 02/06 19:02
110F：推 gary70812: 插入head 就push 第二个stack 移除尾巴就pop 第一个sta 02/06 19:06
111F：→ gary70812: ck,乱掰的ㄏㄏ 02/06 19:06
112F：推 leoone: 老招吧 倒到另一个stack在pop出来 02/06 19:06
113F：→ leoone: amortize time都是O(n)没错 02/06 19:07
114F：推 HungDa: 全倒到另一个拿走再放回来 02/06 19:08
116F：推 arhtur945: 考卷上写的Multipop Cost还要再加1，应该会不太一样， 02/06 19:23
117F：→ arhtur945: 我不会写 02/06 19:23
118F：推 ahahahahah: 这不是成大的题目吗 02/06 19:24
119F：推 leoone: 成大题目是用aggregate algo解的 02/06 19:43
120F：推 arhtur945: 我道歉 我说的是成大的，考到头昏了 ，大家不要紧张 02/06 19:49
121F：推 HYH84: 推 02/07 11:11