Huli's Blog

Learning by sharing

Lidemy 鋰學院是一個為初學者而生的線上程式課程平台,希望能以淺顯易懂的教學,帶領初學者更快速地入門程式設計。你可以直接到網站註冊,或者是追蹤 Lidemy 的粉絲專頁,就能搶先得知課程的最新消息

[心得] 北京清華數據結構 W1

| Comments

最近修了 edx 上的這門課:Data Structures and Algorithm Design Part I 数据结构与算法设计(上)
是由北京清華大學所開設的課程

邊修邊記一下心得

第一章主要在講一些基礎
像是時間複雜度的算法,遞迴、迴圈、DP(動態規劃)還有D&C
舉的實例是 LCS,最長共同子序列

比較有趣的是作業,一共有三題
第一題給你 n 個點(一維)以及區間 [a,b] 以及 m 次查詢,求落在區間內的點的數目
0 ≤ n, m ≤ 5×10^5
0 <= a,b <= 10^7

滿喜歡清華的 judge system 有分數制,可以先求有再求好
寫一個最直接的解法,複雜度是 O(mn),可以過一半的測資拿 50 分
要再精進就是先 sort 然後做二分搜,降到O(mlogn)

這題有兩個點要注意,第一個是我二分搜寫完以後居然還是超時...
結果是因為我用了cincout,改成scanfprintf就過了
輸出入果然還是佔了大多數時間...

第二個點是這題的二分搜不太一樣
以前寫過的都是「找出某個數」,但這題你要寫的是「找出<=某個數」
所以在程式碼上要改一下,不然會找不到;改錯的話可能會找錯或是無窮迴圈

第二題叫做 zuma,就是那個吐珠子的遊戲
給你一個初始序列,假設是 ABCDB 好了
再給你 n 個操作,每一個都是插入一顆珠子到某個 index
求每個操作結束之後的序列長怎樣

我後來上網搜尋這題相關資料的時候,才發現好像是要用雙向 linked list
但我那時候根本沒想到這個東西,只當成是一般模擬題
就用 string 做了,一樣 AC

第三題是大魔王
題目包裝的很漂亮!我很喜歡這題,要特地記錄一下
海上有很多燈塔,每個燈塔都對應到一個二維座標(x,y);燈塔的探照燈會照自己的右上角跟左下角
求有多少對燈塔可以互相照到

互相照到的數學定義其實就是一對燈塔(x1, y1) 跟 (x2, y2) 滿足 x2>x1 && y2>y2

會說這題包裝的很漂亮,是因為假設你把燈塔按照 x 排序以後
答案其實就是「順序數對」的總數,也就是全部數目減掉逆序數對
例如說 1 4 5 3 2
逆序數對是:(4,3), (4,2), (5,3), (5,2), (3,4)
順序數對是:(1,4), (1,5), (1,3), (1,2), (4,5)

因為這數對有先對 x 排序,所以順序數對很顯然就是題目所求的燈塔對的數目
這經典算法的解法是 merge sort 的最後一個步驟
在這邊稍微講一下

例如到合併時,左半邊是:7 4 2;右半邊是:8 3 1(由大到小排)
當你第一個數拿右半邊的8的時候,就知道左半的 3 個數(7, 4, 2)一定都比8
以此類推,就可以算出到底有多少組「順序數對」
要求逆序數對的話其實也差不多啦,稍微改一下而已

這題之所以是大魔王是因為,做完之後還是只拿到 95 分
上完搜了一下,要拿滿分好像要搭配輸入優化
我懶得做了,所以就算了...

參考資料:
被清华《数据结构》第一题困扰了一整天
MOOC-THU之数据结构PA1

Comments

comments powered by Disqus