第一题：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 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量
每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
请你返回从 start 到 finish 所有可能路径的数目。
由于答案可能很大， 请将它对 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)
#不懂
