wordpress删除管理站点链接,wordpress网站首页,企业网站功能报价,专业免费建站文章目录1. 比赛结果2. 题目1. LeetCode 5491. 矩阵对角线元素的和 easy2. LeetCode 5492. 分割字符串的方案数 medium3. LeetCode 5493. 删除最短的子数组使剩余数组有序 medium4. LeetCode 5494. 统计所有可行路径 hard1. 比赛结果
做出来3题#xff0c;最后一题动态规划最后一题动态规划好难不会。继续加油
全国排名 385 / 284213.5%全球排名 1149 / 1014011.3% 2. 题目
1. LeetCode 5491. 矩阵对角线元素的和 easy
题目链接
给你一个正方形矩阵 mat请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
示例 1
输入mat [[1,2,3],[4,5,6],[7,8,9]]
输出25
解释对角线的和为1 5 9 3 7 25
请注意元素 mat[1][1] 5 只会被计算一次。示例 2
输入mat [[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]
输出8示例 3:
输入mat [[5]]
输出5提示
n mat.length mat[i].length
1 n 100
1 mat[i][j] 100解题
一次遍历即可
class Solution {
public:int diagonalSum(vectorvectorint mat) {int n mat.size(), sum 0;for(int i 0; i n; i) {sum mat[i][i]mat[n-1-i][i];}if(n1)sum - mat[n/2][n/2];//奇数时中间重复了一次return sum;}
};32 ms 11.5 MB
2. LeetCode 5492. 分割字符串的方案数 medium
题目链接
给你一个二进制串 s 一个只包含 0 和 1 的字符串我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 s1 s2 s3 s。
请你返回分割 s 的方案数满足 s1s2 和 s3 中字符 ‘1’ 的数目相同。
由于答案可能很大请将它对 10^9 7 取余后返回。
示例 1
输入s 10101
输出4
解释总共有 4 种方法将 s 分割成含有 1 数目相同的三个子字符串。
1|010|1
1|01|01
10|10|1
10|1|01示例 2
输入s 1001
输出0示例 3
输入s 0000
输出3
解释总共有 3 种分割 s 的方法。
0|0|00
0|00|0
00|0|0示例 4
输入s 100100010100110
输出12提示
s[i] 0 或者 s[i] 1
3 s.length 10^5解题
先检查1的个数能不能被3整除然后1的个数为0那么可以有 Cn−12C_{n-1}^2Cn−12 种可能最后就是2个分界处的 0 的个数1再相乘
class Solution {
public:int numWays(string s) {long long n s.size(), one 0;for(char c : s)if(c 1)one;if(one%3)return 0;long long o1 0, o2 0;long long n1 0, n2 0, n30;for(char c : s){if(c 1){if(n1 one/3)n1;else if(n1 one/3 n2 one/3)n2;else if(n1 one/3 n2 one/3)n3;}else{if(n1 one/3 n2 0)o1;else if(n1 one/3 n2 one/3 n3 0)o2;}}if(one 0)return ((n-1)*(n-2)/2)%(int)(1e97);return (o11)*(o21)%(int)(1e97);}
};116 ms 13.6 MB
3. LeetCode 5493. 删除最短的子数组使剩余数组有序 medium
题目链接
给你一个整数数组 arr 请你删除一个子数组可以为空使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
示例 1
输入arr [1,2,3,10,4,2,3,5]
输出3
解释我们需要删除的最短子数组是 [10,4,2] 长度为 3 。
剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。示例 2
输入arr [5,4,3,2,1]
输出4
解释由于数组是严格递减的我们只能保留一个元素。
所以我们需要删除长度为 4 的子数组
要么删除 [5,4,3,2]要么删除 [4,3,2,1]。示例 3
输入arr [1,2,3]
输出0
解释数组已经是非递减的了我们不需要删除任何元素。示例 4
输入arr [1]
输出0提示
1 arr.length 10^5
0 arr[i] 10^9解题
找到首尾不满足的地方l, r可以分三种情况删除l右侧所有的或者删除r左侧所有的或者 删除中间的
class Solution {
public:int findLengthOfShortestSubarray(vectorint arr) {int n arr.size(), i, j, l -1, r -1;for(i 1; i n; i) {if(arr[i-1] arr[i]){l i-1;break;}}if(l -1)return 0;for(i n-2; i 0; --i){if(arr[i] arr[i1]){r i1;break;}}int ans min(n-l-1, r);//删除右侧的、或者删除左侧的i 0, j r;while(i l j n)//或者 处理中间部分{if(arr[i] arr[j]){ans min(ans, j-i-1);i;}elsej;}return ans;}
};296 ms 66.8 MB
4. LeetCode 5494. 统计所有可行路径 hard
题目链接
给你一个 互不相同 的整数数组其中 locations[i] 表示第 i 个城市的位置。 同时给你 startfinish 和 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 取余后返回。
示例 1
输入locations [2,3,6,8,4], start 1, finish 3, fuel 5
输出4
解释以下为所有可能路径每一条都用了 5 单位的汽油
1 - 3
1 - 2 - 3
1 - 4 - 3
1 - 4 - 2 - 3示例 2
输入locations [4,3,1], start 1, finish 0, fuel 6
输出5
解释以下为所有可能的路径
1 - 0使用汽油量为 fuel 1
1 - 2 - 0使用汽油量为 fuel 5
1 - 2 - 1 - 0使用汽油量为 fuel 5
1 - 0 - 1 - 0使用汽油量为 fuel 3
1 - 0 - 1 - 0 - 1 - 0使用汽油量为 fuel 5示例 3
输入locations [5,2,1], start 0, finish 2, fuel 3
输出0
解释没有办法只用 3 单位的汽油从 0 到达 2 。
因为最短路径需要 4 单位的汽油。示例 4
输入locations [2,1,5], start 0, finish 0, fuel 3
输出2
解释总共有两条可行路径0 和 0 - 1 - 0 。示例 5
输入locations [1,2,3], start 0, finish 2, fuel 40
输出615088286
解释路径总数为 2615088300 。
将结果对 10^9 7 取余得到 615088286 。提示
2 locations.length 100
1 locations[i] 10^9
所有 locations 中的整数 互不相同 。
0 start, finish locations.length
1 fuel 200解题
学习了大佬的题解
dp[city][f] 表示到达city时花费了 f燃料的方案数
class Solution {
public:int countRoutes(vectorint locations, int start, int finish, int fuel) {int n locations.size(), i, j, f, mod 1e97;vectorvectorint dp(n, vectorint(fuel1, 0));dp[start][0] 1; // 到达 i 城市花了 f 油的方案数for(f 0; f fuel; f)//遍历燃料{for(i 0; i n; i)//前一个城市{for(j 0; j n; j)//转移到的城市{if(i j)continue;if(dp[i][f] ! 0 fabs(locations[i]-locations[j]) fuel){ //前一个状态存在且可以到达下一个状态dp[j][fabs(locations[i]-locations[j])] dp[i][f];dp[j][fabs(locations[i]-locations[j])] % mod;}}}}int ans 0;for(f 0; f fuel; f)ans (ansdp[finish][f])%mod;//所有燃料情况下到达终点的方案之和return ans;}
};440 ms 12.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
