参考 Lee215215
1.困于环中的机器人
题目描述：无限的平面上，机器人最初位于 (0,0)点，面朝北，重复执行给定的一组指令，问机器人能否离开平面。
思路：因为机器人是重复执行给定的指令，所以只有当一组指令执行完后，机器人相对于原点有位移且仍面向北方，才能离开平面。不难理解，当执行完一组后若机器人回到原点，那么机器人无法离开平面；若执行完一组操作后机器人面向其他方向，那么因为是重复执行，在执行若干次后机器人必将回到原点。
因此可以执行一组操作，并判断机器人相对于原点有位位移且仍面向北方。
2.不邻接种花
题目描述：在 N 个花园中种 4 种类型的花，要求在给定的相通的路径 paths 连通的花园不能种相同种类的花。给出一种方案即可。
思路：在决定第 i 个花园种哪种花时，只需判断与 i 连通的花园种了哪些花即可。首先，可以构造一个图：
G = [[] for _ in range(N+1)]
for x, y in paths:
G[x].append(y)
G[y].append(x)
然后，从第一个花园开始种花：
for i in range(1, N+1):
res[i-1] = ({1, 2, 3, 4} - {res[j-1] for j in G[i]}).pop()
使用 set 的差集操作很优雅，是我学习的一个点。
3.分割数组已得到最大和
题目描述：给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。返回给定数组完成分隔后的最大和。
思路：利用 动态规划 的思路，dp[i] 表示以 i 为结尾的分割数组得到的最大和，返回 dp[-1] 。对于第 i 个数字，将其作为个数为 1~K 连续数组的最后一位，用 k 来遍历。那么可得状态转移方程：
dp[i] = max(dp[i], dp[i-k] + k * curMax) 。
详细代码：
for i, num in enumerate(A):
curMax = 0
for k in range(1, K+1):
if i-k+1 >= 0:
curMax = max(curMax, A[i-k+1])
dp[i] = max(dp[i], (dp[i-k] if i-k >=0 else 0) + curMax*k)
4.最长重复子串
题目描述：给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。返回任何具有最长可能长度的重复子串。
思路：后缀数组排序，然后比较相邻的元素即可。因为相邻的元素才可能有最长的公共前缀。时间复杂度为O(N^2 * logN)。