双周赛34


第一题:https://leetcode-cn.com/problems/matrix-diagonal-sum/
第二题:https://leetcode-cn.com/problems/number-of-ways-to-split-a-string/
第三题:https://leetcode-cn.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/
第四题:https://leetcode-cn.com/problems/count-all-possible-routes/

(1)矩阵对角线元素的和

给你一个正方形矩阵 mat,请你返回矩阵对角线元素的和。

输入:mat = [[1,2,3],[4,5,6],[7,8,9]]
输出:25

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        l=len(mat)
        prim=sum([mat[i][i] for i in range(l)])
        seco=sum([mat[i][l-i-1] for i in range(l)])
        if l%2==0: 
            return prim+seco
        else: 
            return prim+seco-mat[l//2][l//2]

(2)分割字符串的方案数

给你一个二进制串 s (一个只包含 0 和 1 的字符串),我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 (s1 + s2 + s3 = s)。

请你返回分割 s 的方案数,满足 s1,s2 和 s3 中字符 ‘1’ 的数目相同。

由于答案可能很大,请将它对 10^9 + 7 取余后返回。

class Solution:
    def numWays(self, s: str) -> int:     
        mod=10**9 + 7
        len_s=len(s)
        helper=[0]
        for i in range(len_s):
            helper.append(helper[i]+(s[i]=='1'))

        cnt=helper[len_s]
        if cnt%3 : return 0
        if not cnt: return (len_s-1)*(len_s-2)//2%mod

        return helper.count(cnt//3)*helper.count(cnt//3*2)%mod

# helper就很灵性

(3)删除最短的子数组使剩余数组有序

给你一个整数数组 arr ,请你删除一个子数组(可以为空),使得 arr 中剩下的元素是 非递减 的。

一个子数组指的是原数组中连续的一个子序列。

请你返回满足题目要求的最短子数组的长度。

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        len_arr=len(arr)

        # k 用于计算非递减的个数
        k=len_arr-1
        while k>0 and arr[k-1]<=arr[k]: k-=1
        if k==0: return 0

        r=k
        j=0
        while j<len_arr-1: # j 从0到倒数第二个元素
            ci=bisect_left(arr[k:],arr[j])
            t=len_arr-((len_arr-k-ci)+j+1)
            if r>t: r=t
            if arr[j]>arr[j+1]: break
            j+=1
        return r

# 不懂

(4)统计所有可行路径

给你一个 互不相同 的整数数组,其中 locations[i] 表示第 i 个城市的位置。同时给你 startfinishfuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量

每一步中,如果你在城市 i ,你可以选择任意一个城市 j ,满足 j != i0 <= j < locations.length ,并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]||x| 表示 x 的绝对值。

请注意, fuel 任何时刻都 不能 为负,且你 可以 经过任意城市超过一次(包括 start 和 finish )。

请你返回从 startfinish 所有可能路径的数目。

由于答案可能很大, 请将它对 10^9 + 7 取余后返回。

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        dp = {}
        n = len(locations)
        mod = 10**9+7

        def dfs(c, s):
            if c==0 and s==finish: return 1
            k = (c, s)
            if k in dp: return dp[k]
            if s==finish:
                r=1
            else:
                r=0

            i = 0
            while i<n:
                if i!=s:
                    d = locations[i]-locations[s]
                    if d<0: d=-d
                    if c>=d:
                        r += dfs(c-d, i)
                        r %= mod
                i+=1
            dp[k] = r
            return r

        return dfs(fuel, start)

#不懂

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