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);

    }
};

转载请注明来源:Leetcode 第135场周赛解题报告
欢迎收听公众号

发表评论

电子邮件地址不会被公开。 必填项已用*标注