周赛笔记207


第一题: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 个神仙

记录一下报错:

  1. 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
# 不懂
# 二分图: 不含奇数条边的环的一种图

离内推最近的一次


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录