[LeetCode] Weekly Contest 135

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

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

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

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

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

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最少

接著以此往下類推

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