[LEETCODE] Weekly Contest 135

https://leetcode.com/contest/weekly-contest-135/problems/valid-boomerang/

第一題很簡單,問三點共線,原本很無腦的直接算斜率

後來遇到什麼分母等於零阿、有兩點共點之類龜毛的問題

就直接懶了,用向量直接算面積,如果面積算出來是零就是共線,有面積就是非三點共線

 

https://leetcode.com/contest/weekly-contest-135/problems/binary-search-tree-to-greater-sum-tree/

這題要比原來的BST sum還要大

inoder traversal,用一個global variable存起來當下的sum,並更新自己的value

第三題

https://leetcode.com/contest/weekly-contest-135/problems/minimum-score-triangulation-of-polygon/

這題就是DP題目….當年第一次學還被前女友嫌我很笨,慘

切割成子問題找出局部最佳解

比如說邊界是[I,J]=[2,3],這時候根本無法形成三角形,那就是0

比如說邊界是[I,J]=[2,4],這時候只有一個三角形[I,J,K]=[2,3,4],就直接算乘積是多少

比如說一個子四邊形dp[2][5] {2,3,4,5},邊界是[I,J]=[2,5],中間點k可以選擇3,4,這時候就看3,4哪個會使sub answer最少

接著以此往下類推

第四題太晚加入,時間已經結束就放棄了XDDD