周日的比赛的时候正在外面办事，没有参加。赛后看了下题目，几道题除了表面要考的内容，还是有些能发散扩展的地方。
做题目不是最终目的，通过做题发现知识盲区，去研究学习，才能不断提高。
理论和实际是有关系的，一些题目也都有现实意义。计算机的一些模拟操作，通过数学算法，能够大大减轻代码量和算法复杂度。
第一题是机器人在坐标系上直走和转弯，通过简单的模拟就能实现。但是仔细思考发现还能通过线性代数，坐标变换的方式做，这样在实际中计算更快。甚至还可以用复数来做。
实际扫地机器人可能就用到了类似的算法。让他能够不至于始终原地打转。
第四题是典型的后缀树、后缀数组应用，找字符串最长重复子串。在搜索引擎，或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;