owenzhang的博客

Leetcode 第136场周赛解题报告

字数统计: 2.3k阅读时长: 10 min
2019/04/21
loading

周日的比赛的时候正在外面办事，没有参加。赛后看了下题目，几道题除了表面要考的内容，还是有些能发散扩展的地方。

做题目不是最终目的，通过做题发现知识盲区，去研究学习，才能不断提高。

理论和实际是有关系的，一些题目也都有现实意义。计算机的一些模拟操作，通过数学算法，能够大大减轻代码量和算法复杂度。

第一题是机器人在坐标系上直走和转弯，通过简单的模拟就能实现。但是仔细思考发现还能通过线性代数，坐标变换的方式做，这样在实际中计算更快。甚至还可以用复数来做。

实际扫地机器人可能就用到了类似的算法。让他能够不至于始终原地打转。

第四题是典型的后缀树、后缀数组应用，找字符串最长重复子串。在搜索引擎，或DNA检测中，都是有实际使用场景的。在70年代就已经有应用了，是一个很经典的算法。而且在90年代至今，一直有科学家提升创建后缀树和后缀数组的时间复杂度。这个算法也是在不断发展的。而且在2016年中国的李志泽，李建和霍红卫三位科学家提出了线性时间复杂度，常数空间的最优构造算法。是中国人对算法的贡献。

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

比赛的地址 Weekly Contest 136

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

困于环中的机器人

题目：

困于环中的机器人(Robot Bounded In Circle)

地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/robot-bounded-in-circle/

题意：

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。机器人可以接受下列三条指令之一：

“G”：直走 1 个单位
“L”：左转 90 度
“R”：右转 90 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

思路：

假设机器人重复走N次指令后，面朝北：

此时如果坐标在原点，则N次循环后就会重复从前的路径。

如果坐标不在原点，此时把当前位置当作原点，就会每N次移动远离一段和当前原点的距离。距离最初的（0，0）位置越来越远。就不存在循环会最原始原点的问题。

其实至多经过四次，机器人就会面朝北。

经过一次指令后，机器人面朝西或东，相当于逆时针或顺时针转了90度，则再经过三次，就面朝北了。

经过一次指令后，朝南则转了180度，共移动两次指令后朝北。

数学方法：

还可以把指令集先计算一遍，得出经过一个指令集后的相对移动位置和方向转角。用矩阵计算，就不用每次都运行一大堆指令模拟，加快运算速度；

还可以用复数来运算，复数对于转90度有简单的运算方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0;
        int y = 0;
        int i = 0;
        int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        do
        {
            for(auto ch : instructions)
            {
            if(ch=='G')
            {
                x+=dir[i][0];
                y+=dir[i][1];
            }
            else if(ch=='R')
            {
                ++i;
                i%=4;
            }
            else
            {
                i+=4;
                i--;
                i%=4;
            }
            }   
        }while(i!=0);
        if(x==0&&y==0)
            return true;   
        return false;
    }
};

不邻接植花

题目：

不邻接植花(Flower Planting With No Adjacent)

地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/flower-planting-with-no-adjacent/

题意：

在一个无向图中，每个点的出度都不超过3。有四种颜色，给每个点着色，要求有边相连的点颜色不同。

给出着色方案。

思路：

由于每个点出度不超过3，四个颜色，肯定可以有解。暴力枚举即可。由于图的点很多，边少。在寻找和点相连的点时，不要按点遍历，要按边遍历，否则会超时。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    map<int, map<int, int>> mr;
    vector<int> res;
    int dfs(int index, int N)
    {
        if(index > N)
            return 0;
        for(int color=1;color<=4;++color)
        {
            res[index-1] = color;
            map<int, int> & tmp = mr[index];
            bool flag = false;
            for(auto it=tmp.begin();it!=tmp.end();++it)
            {
                if(res[it->first-1]==color)
                {
                    flag = true;
                    break;
                }
            }
            if(flag == true)
                continue;
            int ret = dfs(index+1, N);
            if(ret == 0)
                return 0;
        }
        return -1;
    }
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        res.resize(N, 0);
        for(int i=0; i<paths.size(); ++i)
        {
            int x = paths[i][0];
            int y = paths[i][1];
            mr[x][y] = 1;
            mr[y][x] = 1;
        }
        dfs(1, N);
        return res;
    }
};

分隔数组以得到最大和

题目：

分隔数组以得到最大和(Partition Array for Maximum Sum)

地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/partition-array-for-maximum-sum/

题意：

给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。

返回给定数组完成分隔后的最大和。

思路：

该问题可以划分为子问题求解。

设数组有N个元素A[0]A[1]…A[N-1]，sum(i)表示从A[i]~A[N]求解的最大和。

则sum(i) = max( max(A[i]-A[i+m-1])*m + sum(m) ) 其中i<=m<=k;

就是每个从i开始到数组结尾的最大和，等于前m个元素单独划分，再加上剩下元素的最大和。这k中划分方案最大的，就是从i开始到数组结尾最大和最大的。

依次计算到第0个位置结束。

为了计算统一，会用到sum(n),实际没有这个元素，初始化零计算即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dp[501]={0};
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        int n = A.size();
            for(int i = n-1; i>=0; --i)
            {
                int ma = 0;
                int j;
                for(j=i;j<i+K && j < n ;++j)
                {
                    ma = max(ma, A[j]);
                    dp[i] = max(dp[i], ma*(j - i + 1) + dp[j + 1]);
                }
            }
        return dp[0];
    }
};

最长重复子串

题目：

最长重复子串(Longest Duplicate Substring)

地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/longest-duplicate-substring/

题意：

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 “”。）

思路：

后缀数组教科书般的例题。

后缀数组是后缀树的一种变种，能够节省空间。构造的方法有「倍增算法」，「DC3算法」。

主要思想：

设字符串为S(1-n)由n个字符组成。则字符串有n个相同后缀的子串。分别为s(1-n),s(2-n),…,s(n-n)。

然后构建一个SA数组，每个数组存储这些后缀的子串，存储后进行字典序排序。

最后构造出一个height数组，表示SA数组每个元素和前一个元素相同前缀的字符个数。

那么，最长重复子串的长度就是height数组的最大值。

因为最长重复子串一定是两个不同后缀的公共前缀，而且这两个不同后缀的字典序排列后一定是相连的。否则一定有比他更长的。

所以height的最大值能够找到那两个后缀，然后提取公共前缀就找到答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
namespace SA
{
bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int str[], int sa[], int rank[], int height[], int n, int m)
{
    n++;
    int i, j, p, *x = t1, *y = t2;
    for (i = 0; i < m; i++)
        c[i] = 0;
    for (i = 0; i < n; i++)
        c[x[i] = str[i]]++;
    for (i = 1; i < m; i++)
        c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--)
        sa[--c[x[i]]] = i;
    for (j = 1; j <= n; j <<= 1)
    {
        p = 0;
        for (i = n - j; i < n; i++)
            y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= j)
                y[p++] = sa[i] - j;
        for (i = 0; i < m; i++)
            c[i] = 0;
        for (i = 0; i < n; i++)
            c[x[y[i]]]++;
        for (i = 1; i < m; i++)
            c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
    int k = 0;
    n--;
    for (i = 0; i <= n; i++)
        rank[sa[i]] = i;
    for (i = 0; i < n; i++)
    {
        if (k)
            k--;
        j = sa[rank[i] - 1];
        while (str[i + k] == str[j + k])
            k++;
        height[rank[i]] = k;
    }
}
int num_rank[MAXN], height[MAXN];
int num[MAXN];
int sa[MAXN];
} // namespace SA

class Solution
{
  public:
    string longestDupSubstring(string S)
    {
        using namespace SA;
        int pos = 0;
        int len = 0;
        int n = S.length();
        for (int i = 0; i <= n; ++i)
        {
            num[i] = S[i]&0x3f;
        }
        num[n] = 0;
        da(num, sa, num_rank, height, n, 256);
        for (int i = 2; i <= n; ++i)
        {
            if (height[i] > len)
            {
                pos = sa[i];
                len = height[i];
            }
        }
        return S.substr(pos, len);
    }
};

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-Leetcode-%E7%AC%AC136%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

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 困于环中的机器人
  2. 2. 不邻接植花
  3. 3. 分隔数组以得到最大和
  4. 4. 最长重复子串
Total : 150
2024
2020
2019
2018
2017
2016
2014
2013
2012
2011
技术 读书 思考 技巧 学习 跑步