前言

比赛链接：url，这是我第二次参加这个比赛，第一次做了一个题，第二个题没做出来。这一次终于看见第三个题，下次就能看见第四个题了。争取每次比赛都能总结，并从中学习。

总结

第一题

名字很高大上，三个点不在一条线上，就解决了，因此利用斜率就可以。

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        return (points[2][1]-points[1][1])*(points[1][0]-points[0][0])!=(points[2][0]-points[1][0])*(points[1][1]-points[0][1])

第二题

这个题，就是树的遍历，先遍历右节点，在根节点，最后左节点。并维护一个全局变量，表示节点的数字和。

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        global res
        res = 0
        
        def search(node):
            global res
            if node==None:
                return 
            search(node.right)
            res += node.val
            node.val = res
            search(node.left)
            
        search(root)
        return root

第三题

尝试了很久，没做出来。参考大佬的代码，学到了很多。大佬们的代码基本都是这个思路，动态规划。 1. 创建一个二维列表，dp，存储i到j三角剖分后可以得到的最低分。 2. 从2到n，遍历step 3. 从1到n，遍历i 4. 从i到j遍历，p 5. 求解从i到j，三角剖分后可以得到的最低分。

class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        n = len(A)
        dp = [[0 for i in range(n)] for j in range(n)]
        
        for step in range(2,n):
            for i in range(n):
                j = (i+step)%n
                dp[i][j]=float('inf')
                for p in range(i+1, i+step):
                    k = p%n
                    tmp = dp[i][k] + dp[k][j] + A[i]*A[j]*A[k]
                    if tmp < dp[i][j]:
                        dp[i][j] = tmp
                        
        ans = float("inf")                
        for i in range(n):
            j = (i+n-1)%n
            if ans>dp[i][j]:
                ans = dp[i][j]
                
        return ans        

第四题

看了一遍，一个大佬的代码，自己做了一遍，没做出来，靠。下面解释，大佬简介的代码。 先来理解一下题目，就是移动石头，使石头连续，求解最大最小移动次数，此外，有一个限制条件，移动一个端点石头之后，该石头不能还是端点，这一点限制，后续会提到。

• 最大移动次数：倒数第一个数与第二个数的差和倒数第二个数与第一个数差最大值，减去n-1个数的最小距离。
• 最小移动次数：遍历i，选取一个j，使得i和j之间的差刚好小于n，将i与j之外的石头移动到，i和j之内，每个石头移动一次，就是最小的。此外要注意，特殊情况，也就是题目中的限制，用一个判断来解决，这一点很巧妙。

  class Solution:
    def numMovesStones rt()
        n = len(stones)
        high = max(stones[-1] - stones[1], stones[-2] - stones[0]) - (n-2)
        low = float("inf")
          
        for i in range(n):
            j = i
            while(j+1 < n and stones[j+1]-stones[i] < n):
                j += 1
            now = n - (j-i+1)
            if stones[j]-stones[i]==j-i and j-i==n-2:
                now += 1
            low = min(low, now)
              
        return [low, high]