第一题：https://leetcode-cn.com/contest/weekly-contest-207/problems/rearrange-spaces-between-words/
第二题：https://leetcode-cn.com/contest/weekly-contest-207/problems/split-a-string-into-the-max-number-of-unique-substrings/
第三题：https://leetcode-cn.com/contest/weekly-contest-207/problems/maximum-non-negative-product-in-a-matrix/
第四题：https://leetcode-cn.com/contest/weekly-contest-207/problems/minimum-cost-to-connect-two-groups-of-points/
一、重新排列单词间的空格
给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词 。
请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。如果不能重新平均分配所有空格，请 将多余的空格放置在字符串末尾 ，这也意味着返回的字符串应当与原 text 字符串的长度相等。
返回 重新排列空格后的字符串 。
class Solution:
def reorderSpaces(self, text: str) -> str:
n=text.count(" ")
t=text.split()
len_t=len(t)-1
if len_t==0: return "".join(t)+n*" "
return (" "*(n//len_t)).join(t)+" "*(n%len_t)
二、拆分字符串使唯一子字符串的数目最大
给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
class Solution:
def maxUniqueSplit(self, s: str) -> int:
self.ans=1
def bk(l,r,path):
if l==r:
#print(path[:])
self.ans=max(self.ans,len(path))
for i in range(l,r):
tmp=s[l:i+1]
if tmp not in path:
path.append(tmp)
bk(i+1,r,path)
path.pop()
bk(0,len(s),[])
return self.ans
# hhh,最近写多了回溯，
# 这题写着写着拐进了dfs,又回溯了，回溯神奇啊
#看着的时候挺抽象的，
#回溯出来也就这样了
#回溯应对拆分，专长了
三、矩阵的最大非负积
给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 10**9 + 7 取余 的结果。如果最大积为负数，则返回 -1 。
注意，取余是在得到最大积之后执行的。
class Solution:
def maxProductPath(self, grid: List[List[int]]) -> int:
mod=10**9+7
rows,cols=len(grid),len(grid[0])
self.ans=-1
@lru_cache(None)
def dfs(x,y,tmp):
if 0<=x<rows and 0<=y<cols:
tmp=tmp*grid[x][y]
if x==rows-1 and y==cols-1:
self.ans=max(self.ans,tmp)
return
dfs(x+1,y,tmp)
dfs(x,y+1,tmp)
dfs(0,0,1)
return -1 if self.ans==-1 else self.ans%mod
#lru_cache 个神仙
记录一下报错:
- ans 不加self在这里会
error：referenced before assignment
还有一种改法：把ans弄成列表，子函数中用ans[0]更改
四、连通两组点的最小成本
给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。
任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。
返回连通两组点所需的最小成本。
class Solution:
def connectTwoGroups(self, cost: List[List[int]]) -> int:
self.ans=float('inf')
rows,cols=len(cost),len(cost[0])
def argmin(a):
mini,minv=-1,float('inf')
for i,v in enumerate(a):
if v<minv:
mini,minv,=i,v
return mini
mina=[argmin(x) for x in cost] #横排最小值索引表
minb=[argmin(x) for x in [[cost[r][c] for r in range(rows)] for c in range(cols)]]
#竖列最小值的索引表
def dfs(index,vis,pre):
if index >=rows:
if len(vis)==cols:
self.ans=min(self.ans,pre)
else:
for i in range(cols):
if i not in vis:
j=minb[i]
pre+=cost[j][i]
self.ans=min(self.ans,pre)
return
if pre>self.ans: return
x=[(cost[index][i],i) for i in range(cols)]
x.sort() # sort()不能直接写在上面，机制不懂
for c,i in x:
dfs(index+1,vis|{i},pre+c) # 集合中 | 表示或运算
dfs(0,set(),0)
return self.ans
# from copy
# km
# 不懂
# 二分图： 不含奇数条边的环的一种图
