Leetcode 第135场周赛解题报告

这周比赛的题目很有特点。几道题都需要找到一定的技巧才能巧妙解决，和以往靠数据结构的题目不太一样。

就是如果懂原理，代码会很简单，如果暴力做，也能做出来，但是十分容易出错。

第四题还挺难想的，想了好久才想明白。这次先讲第四题，然后再讲其他的题目。

下面是详细的题解和思考。

比赛的地址 Weekly Contest 135

https://leetcode-cn.com/contest/weekly-contest-135

移动石子直到连续 II

题目：移动石子直到连续 II(Moving Stones Until Consecutive II)

地址：

https://leetcode-cn.com/contest/weekly-contest-135/problems/moving-stones-until-consecutive-ii/

题意：

在数轴上摆放了n个石子，石子位置都是整数，并且不能重叠。游戏规则是：每个回合，将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。无法移动时游戏停止。

问最小和最大移动次数分别是多少。

思路：

题目是上周第一题的扩展，但是有点不同。

由题意可知，每进行一轮操作，石子的左右端点的距离会缩短，一轮一轮收敛。最后会石子都紧邻游戏结束。

举个例子：

初始时有8颗石子，在数轴上的有石子的刻度为：

4，6，8，9，15，16，19，20

最大值求解方法：

石子可以放置的空间，等于左右两端石子之间的未占用位置。在例子中，一共有20-4+1-8个位置。

石子覆盖的线段长度是20-4个，加上一个端点的位置即20-4+1，再减去已经占用的8个位置。

用公式表示为

s1=stones[n-1]-stones[0]+1-n 。

但是第一次移动的左端点或右端点的石子后，这个移动的石子和它相邻的那颗石子之间的空间，后面就不能被放置了，因为与他相邻的那个点变为端点，他们之间的位置不可以被放置了。

例如第一步移动了4，那么5这个位置就不可能放置石子了。所以要计算不能被访问的空间

s2=min(stones[n-1]-stones[n-2]-1, stones[1]-stones[0] -1) 。

最大值为 s1-s2 。因为在后面的步骤里，我们都可以做出策略，让每一轮左右端点的差值只减1。

最小值求解方法：

如果最后游戏结束，那么一定有n个连续坐标摆满了石子。如果我们要移动最少，必定要找一个石子序列，使得在n大小连续的坐标内，初始时有最多的石子。

设想有个尺子，上面有n个刻度点，我们用这个尺子在石子从最左边到最右边移动，每动一次都查看下在尺子范围内有m个石子，那么要使这个区间填满，就需要移动n-m次。

只要在尺子外部有石子，就有策略填满尺子内的。

这些次数中最小的就为虽少次数。

但是有一种特例：

1，2，3，4，7

这种1-4是最好的序列，但是7不能移动到端点，只能1先移动到6，然后7移动到5解决，这种情况要用2步。就是尺子内的石子都是连续的，中间没空洞，只在边上有空，要用2次。

代码：

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(),stones.end());
        int n = stones.size();
        int mx = stones[n - 1] - stones[0] + 1 - n;
        mx -= min(stones[n-1]-stones[n-2] - 1, stones[1]-stones[0] -1);
        int mi = mx;
        int i = 0;
        int j = 0;
        for(i = 0; i < n; ++i)
        {
            while(j + 1 < n && stones[j + 1] - stones[i] + 1 <= n)
                ++j;
            int cost = n - (j - i + 1);
            if(j - i + 1 == n - 1 && stones[j] - stones[i] + 1 == n - 1)
                cost = 2;
            mi = min(mi, cost);
        }
        return vector<int>{mi, mx};
    }
};

有效的回旋镖

题目：有效的回旋镖(Valid Boomerang)

地址：

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

题意：

回旋镖定义为一组三个点，这些点各不相同且不在一条直线上。

给出平面上三个点组成的列表，判断这些点是否可以构成回旋镖。

思路：

题目说是回旋镖，其实就是三角形。只要能判断三点不共线就可以。

方法一：简单的想法可以用斜率和截距的方法，判断三点共线。

缺点：要用到除法，可能有精度问题，而且要考虑和坐标轴平行的特殊情况。

方法二：利用三角形变长的性质，两边之和大于第三边。

缺点：也存在用开方的操作，可能有精度问题。

方法三：最优的方法。利用向量叉积。因为a×b=|a|.|b|sinθ。如果共线sinθ为0。

向量叉积后还是的向量，这个向量的长度是两个向量所组成平行四边形的面积。如果共线，这个值为0。

具体可以参考维基百科：

https://zh.wikipedia.org/wiki/%E5%8F%89%E7%A7%AF

代码：

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1=points[0][0],y1=points[0][1];
        int x2=points[1][0],y2=points[1][1];
        int x3=points[2][0],y3=points[2][1];

        int cross = (y3-y1)*(x2-x1) - (y2-y1)*(x3-x1);
        return cross != 0;
    }
};

从二叉搜索树到更大和树

题目：

从二叉搜索树到更大和树(Binary Search Tree to Greater Sum Tree)

地址：

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

题意：

修改树的每个节点的值，为访问的所有节点的和，包括当前节点。

访问的次序是先访问右子树，再访问根节点，再访问左子树。

思路：

代码比较简单，递归实现。

代码：

class Solution {
public:
    int ans = 0;
    TreeNode* bstToGst(TreeNode* root) {
        if(root==nullptr)
            return root;
        bstToGst(root->right);
        ans+=root->val;
        root->val=ans;
        bstToGst(root->left);
        return root;
    }
};

多边形三角剖分的最低得分

题目：多边形三角剖分的最低得分(Minimum Score Triangulation of Polygon)

地址：

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

题意：

想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

思路：

选定凸多边形的一条边为底（A[0]A[N-1]组成的线段），和A[i]为顶点，可以把凸多边形分为三部分，左侧A[0]A[1]…A[i]组成的凸多边形，右侧A[i]A[i+1]…A[N-1]组成的凸多边形，还有A[0]A[i]A[N-1]组成的三角形。

两个凸多边形还可以再递归分解，最后比较出最优解。递归算过的形状不用重复计算，可以用记忆化搜索，记录中间结果。

如果凸多边形只有两个点，那么组成不了三角形，可以直接返回权值为0。

递推公式为：

设w(i,k,j)为i,j,k三个点组成的三角形的权值。

v[i][j]=0 (当i+1==j时)

v[i][j]=v[i][k]+v[k][j]+w(i,k,j)

（当i + 1 < j时, i < k < j)

代码：

class Solution {
public:
    int memo[51][51]={0};
    inline int w(int i, int j, int k, vector<int>& A)
    {
        return A[i]*A[j]*A[k];
    }
    int dfs(int i, int j, vector<int>& A)
    {
        if(i==j-1)
            return 0;

        if(memo[i][j]!=0)
            return memo[i][j];

        memo[i][j]=INT_MAX;
        for(int k = i+1; k < j; ++k)
        {
            int ans = dfs(i, k, A) + w(i, k, j, A) + dfs(k, j, A);
            memo[i][j] = min(ans, memo[i][j]);
        }
        return memo[i][j];
    }
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();

        return dfs(0, n-1, A);

    }
};