https://leetcode.com/contest/weekly-contest-135/problems/valid-boomerang/
第一題很簡單，問三點共線，原本很無腦的直接算斜率
後來遇到什麼分母等於零阿、有兩點共點之類龜毛的問題
就直接懶了，用向量直接算面積，如果面積算出來是零就是共線，有面積就是非三點共線
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: bool isBoomerang(vector<vector<int>>& points) { vector<vector<int>> vec(2, vector<int> (2, 0)); ///vector ab vec[0][0] = points[1][0] - points[0][0]; vec[0][1] = points[1][1] - points[0][1]; ///vector ac vec[1][0] = points[2][0] - points[0][0]; vec[1][1] = points[2][1] - points[0][1]; if((vec[0][0]*vec[1][1] - vec[0][1]*vec[1][0]) != 0) return true; else return false; } }; |
https://leetcode.com/contest/weekly-contest-135/problems/binary-search-tree-to-greater-sum-tree/
這題要比原來的BST sum還要大
inoder traversal，用一個global variable存起來當下的sum，並更新自己的value
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int sum = 0; TreeNode* bstToGst(TreeNode* root) { return copy(root); } TreeNode *copy(TreeNode *root) { TreeNode *new_root; if(root != NULL) { new_root = new TreeNode(0); new_root->right = copy(root->right); new_root->val = root->val + sum; sum = new_root->val; new_root->left = copy(root->left); } else return NULL; return new_root; } }; |
第三題
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最少
接著以此往下類推
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { public: int dp[101][101] = {0}; int minScoreTriangulation(vector<int>& a) { int n = a.size()-1; for(int i = n; i >= 0;i--) { for(int j = i+1; j <= n; j++) { if(j-i == 1) dp[i][j] = 0; else if( j-i == 2) { dp[i][j] = a[i]*a[i+1]*a[i+2]; } else for(int k = i+1; k <= j-1; k++) { if(dp[i][j] == 0) dp[i][j] = dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]; else dp[i][j] = min(dp[i][j], (dp[i][k]+dp[k][j]+a[i]*a[j]*a[k])); } } } return dp[0][n]; } }; |
第四題太晚加入，時間已經結束就放棄了XDDD
