这周比赛的题目很有特点。几道题都需要找到一定的技巧才能巧妙解决,和以往靠数据结构的题目不太一样。
就是如果懂原理,代码会很简单,如果暴力做,也能做出来,但是十分容易出错。
第四题还挺难想的,想了好久才想明白。这次先讲第四题,然后再讲其他的题目。
下面是详细的题解和思考。
比赛的地址 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/叉积
代码:
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/
题意:
思路:
选定凸多边形的一条边为底(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);
}
};