[理工] [ALGO] 101 中央資工

看板Grad-ProbAsk作者 (Up2u)時間12年前 (2012/02/13 17:31), 編輯推噓7(7推 0噓 19→)
留言26則, 10人參與, 最新討論串1/1
1. 兩個array X , Y ， 求 |Xi - Yj| is minimun time 要比 O(n^2)好 2. 一個array 和 key k 用 time = O(n) , space = O(1) 讓K擺在適當位置，K左邊 < K , K右邊 > K himt:quick sort 這題我有點不懂，題目好像沒說array中有沒有包含K K有沒有重複 -- When we toss a coin , we obtain either head or tail. Now we toss a coin 5 times. There are 2^5 possible outcomes. How many of them contain no two consecutive heads? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.105.81.17 ※ 編輯: bjk 來自: 59.105.81.17 (02/13 17:33)
→
02/13 17:35, , 1F
第一個我覺得可以把一個array sorting好(eg:X array)
02/13 17:35, 1F
→
02/13 17:36, , 2F
然後對Ｙ array的每個數值用binary search找出跟他最近的
02/13 17:36, 2F
→
02/13 17:37, , 3F
值 然後再去比較每個pair的最小值就應該可以了
02/13 17:37, 3F
→
02/13 17:38, , 4F
第二題的意思應該就是quick sort的partition吧
02/13 17:38, 4F
→
02/13 17:51, , 5F
題目沒說K擺在哪裡
02/13 17:51, 5F
→
02/13 17:52, , 6F
且直接代的話好像沒辦法解決K要擺哪裡
02/13 17:52, 6F
推
02/13 18:00, , 7F
一樓一定是大神!
02/13 18:00, 7F
推
02/13 18:55, , 8F
第二題就每個元素跟K比大小 小的放K前大的放K後 O(n)就好了吧
02/13 18:55, 8F
→
02/13 18:56, , 9F
想要看array裏面K放在哪也只要O(n)就好啦
02/13 18:56, 9F
推
02/13 19:06, , 10F
第二題我想是從頭、尾各取一個跟k比較，分三種情況
02/13 19:06, 10F
→
02/13 19:07, , 11F
一大一小，則小的放左邊那個位置，大的放右邊那個位置
02/13 19:07, 11F
→
02/13 19:08, , 12F
然後取從左算來跟從右算來第二個，換下一輪
02/13 19:08, 12F
→
02/13 19:09, , 13F
兩小，則原來在左邊的不動，大的跟左邊算來第二個交換
02/13 19:09, 13F
→
02/13 19:09, , 14F
跟右邊算來第二個，一起換下一輪。兩小則反過來
02/13 19:09, 14F
→
02/13 19:11, , 15F
大致上的想法是這樣啦 雖然是交卷後才想到的...QQ
02/13 19:11, 15F
推
02/13 19:29, , 16F
聽說演算法有三題 有人記得第三題嗎@@ 想知道
02/13 19:29, 16F
推
02/13 22:47, , 17F
第三題好像是圖論的
02/13 22:47, 17F
推
02/14 00:13, , 18F
第三題很像是MST
02/14 00:13, 18F
推
02/14 00:40, , 19F
第三題有三個小題
02/14 00:40, 19F
→
02/14 00:41, , 20F
1.寫出任意一個MST的演算法及其時間複雜度
02/14 00:41, 20F
→
02/14 00:41, , 21F
2.在一Graph中，若減少不在MST中的edge之weight值，請寫
02/14 00:41, 21F
→
02/14 00:42, , 22F
出一個O(|V|)的演算法來決定新的MST
02/14 00:42, 22F
→
02/14 00:43, , 23F
3.在一Graph中，若加入一個vertex與edge，要花多久時間
02/14 00:43, 23F
→
02/14 00:43, , 24F
才能決定新的MST
02/14 00:43, 24F
→
02/14 00:44, , 25F
題目大概是這樣，有記錯或漏掉的條件再請各位補齊吧@@
02/14 00:44, 25F
→
09/11 14:55, , 26F
第二題我想是從頭、尾各 https://daxiv.com
09/11 14:55, 26F
‣ 更多 bjk 的文章
文章代碼(AID): #1FEDXxXz (Grad-ProbAsk)