很久没有时间写总结，拖到七月份才写，实在是懒。
1041. 困于环中的机器人
在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。机器人可以接受下列三条指令之一：
“G”：直走 1 个单位 “L”：左转 90 度 “R”：右转 90 度 机器人按顺序执行指令 instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。
示例 1：
输入："GGLLGG"
输出：true
解释：
机器人从 (0,0) 移动到 (0,2)，转 180 度，然后回到 (0,0)。
重复这些指令，机器人将保持在以原点为中心，2 为半径的环中进行移动。
示例 2：
输入："GG"
输出：false
解释：
机器人无限向北移动。
示例 3：
输入："GL"
输出：true
解释：
机器人按 (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ... 进行移动。
idea: 题目意思是机器人反复执行指令，判断它是否困在环中。题目中只有左转和右转，假设一次指令只有一个转向，那么要回到初始状态，要执行四次指令(360=904)。因此，我们对原始指令4，如果能回到初始状态，那么就困在环中，不是就没有困在环中。
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
# 重复多次能回到起点
instruct = instructions*4
d = 0
point = [0,0]
for i in instruct:
if i=='G':
if d==0:
point[1]+=1
elif d==1:
point[0]-=1
elif d==2:
point[1]-=1
elif d==3:
point[0]+=1
elif i=='L':
d = (d+1)%4
elif i=='R':
d = (d-1)%4
if point==[0,0]:
return True
else:
return False
1042. 不邻接植花
有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外，没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。
示例 1：
输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
示例 2：
输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]
示例 3：
输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]
提示：
- 1 <= N <= 10000
- 0 <= paths.size <= 20000
- 不存在花园有 4 条或者更多路径可以进入或离开。
- 保证存在答案。
idea： 这个题比较简单，因为题目中已经说明，不存在四条或者更多路径可以进入或离开，只需要提供一个可行的方案，不用求总共有多少种方案。
- 首先，将paths转化为字典，key是花园的序号，value是花园的路径。
- 遍历每一个花园，查看该花园的序号是否在字典中：
- 不在字典中，说明该花园没有路径通向其它花园，就任意种花。
- 在字典中，遍历该花园的路径，排除已经种植的花，种上未种植的花。
class Solution:
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
if paths==[]:
ans = [1 for i in range(N)]
return ans
ans = [0 for i in range(N)]
d = {}
for path in paths:
if path[0] not in d:
d[path[0]] = []
d[path[0]].append(path[1])
if path[1] not in d:
d[path[1]] = []
d[path[1]].append(path[0])
del paths
for i in range(N):
tmp = [1,2,3,4]
if i+1 not in d:
ans[i] = 1
continue
for p in d[i+1]:
if ans[p-1]!=0 and ans[p-1] in tmp:
tmp.remove(ans[p-1])
ans[i] = tmp[0]
return ans
1043. 分隔数组以得到最大和
给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。
返回给定数组完成分隔后的最大和。
示例：
输入：A = [1,15,7,9,2,5,10], K = 3
输出：84
解释：A 变为 [15,15,15,9,10,10,10]
提示：
- 1 <= K <= A.length <= 500
- 0 <= A[i] <= 10^6
idea: 这个题，就动态规划来解决。对于dp[0]，最大的就是A[0]，对于dp[1]，最大的是max(A[0].A[1])2…对于dp[i]，我们已经知道i之前数组完成分割后的最大和，考虑第i个元素独立，求dp[i-1]+A[i]，然后再考虑第i-1和i元素一组，求dp[i-2]+max(A[i],A[i-1])2，直到第K个元素。将其中的最大值赋给dp[i]。
动态规划问题，要弄清楚最优解和最优子结构，这个题的最优子结构，就是dp[i-k]是最优的。
class Solution:
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
n = len(A)
if n<=K:
return max(A)*n
dp = [0]*n
for i in range(K):
dp[i] = max(A[:i+1])*(i+1)
for i in range(K, n):
temp = float('-inf')
for j in range(K):
temp = dp[i-j-1] + max(A[i-j:i+1])*(j+1)
dp[i] = max(temp, dp[i])
return dp[-1]
1044. 最长重复子串
给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ““。）
示例 1：
输入："banana"
输出："ana"
示例 2：
输入："abcd"
输出：""
提示：
- 2 <= S.length <= 10^5
- S 由小写英文字母组成。
idea: 这题超出我理解了。我只有一个暴力解法，先两层循环，产生可能重复的字符串，然后将这个字符串去匹配，返回匹配成功的次数，这种方法，复杂度O(n^4)，所以不可取。参看JOHNKRAM
class Solution {
public:
typedef long long ll;
int P=998244353,P1=1000000007,base=233,base1=666;
int h[100005],h1[100005],p[100005],p1[100005];
set<pair<int,int>> s;
string longestDupSubstring(string S) {
int n=S.size(),i,j,k,l,r,mid;
pair<int,int> o;
for(i=h[0]=0;i<n;i++)h[i+1]=((ll)h[i]*base+S[i])%P;
for(i=h1[0]=0;i<n;i++)h1[i+1]=((ll)h1[i]*base1+S[i])%P1;
for(i=p[0]=1;i<=n;i++)p[i]=(ll)p[i-1]*base%P;
for(i=p1[0]=1;i<=n;i++)p1[i]=(ll)p1[i-1]*base1%P1;
l=0;
r=n;
while(l+1<r)
{
mid=l+r>>1;
s.clear();
for(i=mid;i<=n;i++)
{
j=(h[i]+(ll)(P-h[i-mid])*p[mid])%P;
k=(h1[i]+(ll)(P1-h1[i-mid])*p1[mid])%P1;
o=make_pair(j,k);
if(s.find(o)==s.end())s.insert(o);
else break;
}
if(i>n)r=mid;
else l=mid;
}
s.clear();
for(i=l;i<=n;i++)
{
j=(h[i]+(ll)(P-h[i-l])*p[l])%P;
k=(h1[i]+(ll)(P1-h1[i-l])*p1[l])%P1;
o=make_pair(j,k);
if(s.find(o)==s.end())s.insert(o);
else break;
}
string ans="";
for(j=i-l;j<i;j++)ans+=S[j];
return ans;
}
};
更多解答，参看rank。