内容简介：周日的比赛的时候正在外面办事，没有参加。赛后看了下题目，几道题除了表面要考的内容，还是有些能发散扩展的地方。做题目不是最终目的，通过做题发现知识盲区，去研究学习，才能不断提高。理论和实际是有关系的，一些题目也都有现实意义。计算机的一些模拟操作，通过数学算法，能够大大减轻代码量和算法复杂度。
周日的比赛的时候正在外面办事，没有参加。赛后看了下题目，几道题除了表面要考的内容，还是有些能发散扩展的地方。
做题目不是最终目的，通过做题发现知识盲区，去研究学习，才能不断提高。
理论和实际是有关系的，一些题目也都有现实意义。计算机的一些模拟操作，通过数学算法，能够大大减轻代码量和算法复杂度。
第一题是机器人在坐标系上直走和转弯，通过简单的模拟就能实现。但是仔细思考发现还能通过线性代数，坐标变换的方式做，这样在实际中计算更快。甚至还可以用复数来做。
实际扫地机器人可能就用到了类似的算法。让他能够不至于始终原地打转。
第四题是典型的后缀树、后缀数组应用，找字符串最长重复子串。在搜索引擎，或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度有简单的运算方法。
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，四个颜色，肯定可以有解。暴力枚举即可。由于图的点很多，边少。在寻找和点相连的点时，不要按点遍历，要按边遍历，否则会超时。
代码：
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),实际没有这个元素，初始化零计算即可。
代码：
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的最大值能够找到那两个后缀，然后提取公共前缀就找到答案。
代码：
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);
}
};
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- Leetcode 第133场周赛解题报告
- Leetcode 第135场周赛解题报告
- Codeforces Round #530 (Div. 2) 解题报告
- Codeforces Round #538 (Div. 2) 解题报告
- The Cryptopals Crypto Challenges 解题报告（1）
- The Cryptopals Crypto Challenges 解题报告（2）
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
