Leetcode 第134场周赛解题报告

字数统计: 3.2k阅读时长: 13 min

 2019/04/21 

因为上周日上班，这场比赛没有参加。赛后做了下比赛的题目，前三道题比较常规，第四道题有点特殊，要利用题目给的提示。

第三题在后来思考时，感觉有点「眼熟」，原来是最长公共子序列的变种。学习知识要触类旁通，多思考。很多问题的本质底层都是一个模型。

通过第四题发散想一下，还是能够发现很多有意思的结论，在题解中会详细分析。

思考到最后，甚至想到了极限，量变引起质变。烧脑，头疼，感觉数学知识好匮乏，我要去学习了。

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

今天比赛的地址 Weekly Contest 134

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

1. 动石子直到连续

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

题号：

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

题意：

三枚石子放置在数轴上，所在位置必须是整数。位置分别为 a，b，c。
每一回合，假设三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z > 且 k != y。
当这些石子的位置连续时，游戏结束。

要使游戏结束，可以执行的最小和最大移动次数分别是多少？

思路：
每次只能移动最左侧，或者最右侧的石子往中间移动。所以z-x的值是逐渐收敛的。

最大次数就是一步一步往中间挪，所需的步数是z-x-2。因为z和x之间能移动的空间是z-x-1，还要去掉一个y占的位置，所以最终移动的最多步数是z-x-2。

最小步数呢？

最小值为0：如果x,y,z三个值本身就挨着，那么不用移动就游戏结束了。

最小值为1：如果x和y之间只有一个位置，那么z移动到这个空位，只移动1次也就结束了。

最小值为2：除了上面两种情况，每次都把x移动到y-1或把z移动到y+1，那么只要两步就结束了。

代码

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        if(a>b)
            swap(a,b);
        if(a>c)
            swap(a,c);
        if(b>c)
            swap(b,c);
        int mx = c-b-1+b-a-1;
        int mi = 0;
        if(abs(c-b)==1)
            mi+=0;
        else
            mi+=1;
        if(abs(b-a)==1)
            mi+=0;
        else
            mi+=1;
        if(b-a==2||c-b==2)
            mi=1;
        return vector<int>{mi,mx};
    }
};

2. 边框着色

题目：边框着色（Coloring A Border）

题号：

https://leetcode-cn.com/contest/weekly-contest-134/problems/coloring-a-border/

题意：给一个二维网格，网格被分成几种区域，每个区域都被涂上了不同的颜色。然后给定一个点（x,y）和一种颜色值c。要求把这个点所在的区域边缘涂上颜色c,最后返回新的网格图。

思路：

先根据点找到整个区域的点的集合，然后判断哪些点是边缘，如果是边缘，给边缘涂色。

找到区域点集合可以用深度优先搜索或广度优先搜索。判定边缘，就看和二位网格的边界是否相连，还有是否上下左右有其他颜色。

为了方便判断，减少干扰。可以再建两个网格，一个网格标识哪些点被搜索过，一个网格标识最终涂色的网格。

代码

class Solution {
public:
    int m,n;
    bool isEdge(int i, int j, vector<vector<int>>& grid, int ocolor)
    {
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        for(int k=0; k<4; ++k)
        {
            int x = dx[k]+i;
            int y = dy[k]+j;
            if(x<0||x>=m||y<0||y>=n)
                return true;
            else
            {
                if(grid[x][y]!=ocolor)
                {
                    return true;
                }
            }
        }
        return false;
    }
    void dfs(vector<vector<int>>& grid, vector<vector<int>>& visited,vector<vector<int>>& res, int i, int j, int pcolor, int ocolor)
    {
        if(isEdge(i,j,grid,ocolor))
        {
            res[i][j]=pcolor;
        }
        visited[i][j]=1;
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        for(int k=0; k<4; ++k)
        {
            int x = dx[k]+i;
            int y = dy[k]+j;
            if(x>=0&&x<m&&y>=0&&y<n)
            {
                if(grid[x][y]==ocolor&&!visited[x][y])
                    dfs(grid,visited,res,x,y,pcolor,ocolor);
            }
        }
        return ;
    }
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
        m=grid.size();
        n=grid[0].size();
        vector<vector<int>> visited(m,vector<int>(n,0));
        vector<vector<int>> res(grid);
        dfs(grid,visited,res,r0,c0,color,grid[r0][c0]);
        return res;
    }
};

3. 不相交的线

题目：不相交的线（Uncrossed Lines）

题号：

https://leetcode-cn.com/contest/weekly-contest-134/problems/uncrossed-lines/

题意：

在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

思路：

我们设函数f(x,y)标识A的前x个数字和B的前y个数字，能绘制出的最大连接数。假设A、B都是从下标1开始。

则f(0,y)=0,f(x,0)=0;

情况1：

如果A[x]!=B[y]，那么f(x,y)=max(f(x-1,y),f(x,y-1));

情况2：

如果A[x]==B[y]，那么f(x,y)=f(x-1,y-1)+1;

可以看出，是一个标准的递推公式，利用两层循环就能得出答案，最后求f(A.size(),B.size())就是答案。

公式的推导如下：

如果两个长度为0的整数串连线，最大值肯定为0。

如果出现情况1，在合法的解答中，不可能出现A[x],B[y]都参与连线的情况。如果他们两个点都被别的点连线了，那么一定会出现直线相交。因为与B[y]连线的点一定小于A[x]，与A[x]连线的点的位置也一定小于B[y]。

如果出现情况2, 那么一定A[x]和B[y]连是最优解，其他没有比这个情况更大的解。否则A[x]和B[y]一定只有一个点参与连线（看情况1中的说明，否则会有相交）。

例如只有B[y]参与了连接，连了A[z]，那么A[z]一定小于A[x]，所以f(z,y)=f(x,y)，和A[x]连B[y]的情况值一样。所以把这两个点去除得到f(x-1,y-1)再加上这两个点连上的情况，就是f(x,y)的值了。

看这个公式也有点眼熟原来是最长公共子序列（Longest Common Subsequences)。就是求两个字符串公共子序列的长度。例如ABCED和AXYCD的最长公共子序列就是ACD，和上面的递推是一样的。因为子序列能够保证他们的连线不相交。

代码

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int m=A.size();
        int n=B.size();
        int v[501][501]={0};
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(A[i-1]==B[j-1])
                {
                    v[i][j]=v[i-1][j-1]+1;
                }
                else
                    v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        }
        return v[m][n];
    }
};

4. 逃离大迷宫

题号：

https://leetcode-cn.com/contest/weekly-contest-134/problems/escape-a-large-maze/

题目：逃离大迷宫（Escape a Large Maze）

题意：
在一个10^6 乘 10^6的二维网格上，标识两个点S和T，还有最多200个障碍点。问S和T是否连通。
连通的定义为，从S出发，只通过上下左右移动，且障碍点是不能移动到的，最终能够移动到T。

思路：
如果网格很小比较简单，就和第二题一样，通过深搜或广搜，看是否能到达终点T即可。但是网格空间太大了。直接搜肯定超时。

可以从最多200个点来思考。到不了的情况就是S或T被这200个点给围住了。只要能判断是否被围住就可以了。

原题200个点是在最下面数据范围里写的，很隐藏，很难注意到。

怎么判断S或T被障碍点围住呢？

找到200个点能够围住的最大范围包括的点数Total，从S广搜，如果已经搜到Total个空白点，还有路可走，那么这200个点肯定包围不了S点。

同理再判断下是否有包围住T点，两个都没被包围，则一定能走到。

当然，也可能两个点都被包围了，那么在搜的时候判断能直达，直接返回true就可以了。

200个点能够包围的最大空白部分是多少？答案是19900=(200-1)*200/2。

为什么是这个值呢？
如果要200个障碍点得到充分利用，包围最多的范围，那么一定要借助网格自身的边界。

如果是直线，相同周长，面积最大的是圆，所以围成个1/4圆可能是答案。但是网格上的点是离散的，围成个三角形，200个点做斜边，是围成区域最大的。为什么不是圆呢，因为两个正方形，只有斜着连接，在二维表围的面积才最大。如图

如上图，最开始是黄色的布局障碍。此时有1、3、5三个点是在统一垂直方向，这时让1移动到2会更好，多围一个点，把3移动到4也会多一个点。同理5->6,4->7,2->8最终形成一个斜线，达到蓝色部分。就能围住的点最多了。那点有多少个呢？设斜边的长度为n个方块。则围住的总面积块数等于1+2+3+…+n-n=n*(n-1)/2。

有两个问题：

1. 为什么连续区间周长最大的是圆，而在二位方块中最大的是三角形？

因为对于每个小方块，能够贡献的长度只有自己的边长和内部的斜对角线长度，没有圆的弧线。这样斜对角线就是获取最长长度的最优解。

2. 一个3×3方块围成的图形，面积是9，周长是12。但是周长上的边的方块一共有多少个？

这个问题的第一反应是3×3=9，但实际围成外围的方块数是2×4=8。就像题目中说的200个点，如果围个正方形，那么肯定不是边长为50的，而是51。因为四个角的方块是两个边公用的，如果在连续空间中，只是一个点，但是在离散中，这个点就是个面积了。

上面说的这些有什么用呢？

生活中，家里铺地砖，不理解会算错。

工作中，做计算机图形展示程序，或者做显示器上的运算，都是离散像素点，理解好会有有助于实现。

又衍生了几个问题需要研究：

现实世界中有绝对的圆吗?世界是离散的还是连续的?微分到一定的量就出现了无理数π。这个值是怎么得出来的，他和自然有什么关系，在宇宙中是什么存在？有没有的时空，或者什么情况下又出现新的无理数替代掉π？？？

代码

class Solution {
public:
    unordered_map<int,unordered_map<int, int>> position;
    const int kBlock = 1;
    const int kSource = 2;
    const int kTarget = 3;
    const int kMaxPosNum = (1+200)*200/2-200;
    int R=1e6;
    int C=1e6;
    bool bfs(int sx, int sy, int sourceFlag, int targetFlag)
    {
        queue<pair<int, int>> q;
        q.push({sx,sy});
        int total = 0;
        while(!q.empty())
        {
            pair<int,int> p = q.front();
            q.pop();
            int i = p.first;
            int j = p.second;
            if(position[i][j]==targetFlag)
            {
                return true;
            }
            total++;
            if(total>kMaxPosNum)
            {
                return true;
            }
            int dx[]={-1,1,0,0};
            int dy[]={0,0,-1,1};
            for(int k=0;k<4;++k)
            {
                int x = dx[k]+i;
                int y = dy[k]+j;
                if(x>=0&&x<R&&y>=0&&y<C&&position[x][y]!=sourceFlag&&position[x][y]!=kBlock)
                {
                    position[x][y] = sourceFlag;
                    q.push({x,y});
                }
            }
        }
        return false;
    }
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        for(int i=0;i<blocked.size();++i)
        {
            position[blocked[i][0]][blocked[i][1]]=kBlock;
        }
        position[source[0]][source[1]]=kSource;
        position[target[0]][target[1]]=kTarget;
        return bfs(source[0], source[1], kSource, kTarget)
            && bfs(target[0], target[1], kTarget, kSource);
    }
};

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-Leetcode-%E7%AC%AC134%E5%9C%BA%E5%91%A8%E8%B5%9B%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

发表日期：April 21st 2019, 10:00:03 am

更新日期：April 21st 2019, 10:00:03 am

Next Post

Leetcode 第133场周赛解题报告
Previous Post

Leetcode 第135场周赛解题报告

CATALOG

1. 1. 动石子直到连续
2. 2. 边框着色
3. 3. 不相交的线
4. 4. 逃离大迷宫