网站运营与规划,凡科网免费建站,网站建设德尔普,手机wap网站开发与设计文章目录1. 比赛结果2. 题目LeetCode 5143. 解压缩编码列表 easyLeetCode 5144. 矩阵区域和 mediumLeetCode 5145. 祖父节点值为偶数的节点和 mediumLeetCode 5146. 不同的循环子字符串 hard1. 比赛结果
做出来了1, 3两题#xff0c;第2题在比赛结束后10分钟提交通过。
2.…
文章目录1. 比赛结果2. 题目LeetCode 5143. 解压缩编码列表 easyLeetCode 5144. 矩阵区域和 mediumLeetCode 5145. 祖父节点值为偶数的节点和 mediumLeetCode 5146. 不同的循环子字符串 hard1. 比赛结果
做出来了1, 3两题第2题在比赛结束后10分钟提交通过。
2. 题目
LeetCode 5143. 解压缩编码列表 easy
题目链接 给你一个以行程长度编码压缩的整数列表 nums 。 考虑每相邻两个元素 [a, b] [nums[2*i], nums[2*i1]] 其中 i 0 每一对都表示解压后有 a 个值为 b 的元素。
请你返回解压后的列表。
示例
输入nums [1,2,3,4]
输出[2,4,4,4]提示
2 nums.length 100
nums.length % 2 0
1 nums[i] 100解答语文题读懂题目即可一开始没读懂出错一次。
class Solution {
public:vectorint decompressRLElist(vectorint nums) {vectorint ans;int count, val;for(int i 0; i nums.size()/2; i){count nums[2*i];val nums[2*i1];while(count--)ans.push_back(val);}return ans;}
};LeetCode 5144. 矩阵区域和 medium
题目链接 给你一个 m * n 的矩阵 mat 和一个整数 K 请你返回一个矩阵 answer 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和
i - K r i K, j - K c j K 且 (r, c) 在矩阵内。示例 1
输入mat [[1,2,3],[4,5,6],[7,8,9]], K 1
输出[[12,21,16],[27,45,33],[24,39,28]]
示例 2
输入mat [[1,2,3],[4,5,6],[7,8,9]], K 2
输出[[45,45,45],[45,45,45],[45,45,45]]提示
m mat.length
n mat[i].length
1 m, n, K 100
1 mat[i][j] 100解题
按行动态规划ans[i][j] ans[i][j-1]vs(mat,jK,i-K,iK)-vs(mat,j-K-1,i-K,iK)后面的和 左边的和 新增加的列 - 出去的列
class Solution {int m, n, sum, x, y;
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int K) {m mat.size();n mat[0].size();vectorvectorint ans(m, vectorint(n));int i, j;for(i 0; i m; i){ans[i][0] sqsum(mat,i,0,K);for(j 1; j n; j)ans[i][j] ans[i][j-1]vs(mat,jK,i-K,iK)-vs(mat,j-K-1,i-K,iK);}return ans;}int vs(vectorvectorint mat, int j, int i0, int i1){for(sum0 ; i0 i1; i0){if(inside(i0,j))sum mat[i0][j];}return sum;}int sqsum(vectorvectorint mat, int i, int j, int K){sum 0;for(xi-K; x iK; x)for(y j-K; y jK; y){if(inside(x,y))sum mat[x][y];}return sum;}bool inside(int x, int y){return (x0 xm y0 yn);}
};LeetCode 5145. 祖父节点值为偶数的节点和 medium
题目链接
给你一棵二叉树请你返回满足以下条件的所有节点的值之和
该节点的祖父节点的值为偶数。一个节点的祖父节点是指该节点的父节点的父节点。
如果不存在祖父节点值为偶数的节点那么返回 0 。
示例
输入root [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出18
解释图中红色节点的祖父节点的值为偶数蓝色节点为这些红色节点的祖父节点。
提示
树中节点的数目在 1 到 10^4 之间。
每个节点的值在 1 到 100 之间。解题常规操作递归
class Solution {
public:int sumEvenGrandparent(TreeNode* root) {int ans 0;dfs(ans, root);return ans;}void dfs(int ans, TreeNode* root){if(!root) return;if(root-val%2 0){if(root-left){if(root-left-left)ans root-left-left-val;if(root-left-right)ans root-left-right-val;}if(root-right){if(root-right-left)ans root-right-left-val;if(root-right-right)ans root-right-right-val;}}dfs(ans, root-left);dfs(ans, root-right);}
};LeetCode 5146. 不同的循环子字符串 hard
题目链接
给你一个字符串 text 请你返回满足下述条件的 不同 非空子字符串的数目这些子字符串可以写成某个字符串与其自身的串联。
示例 1
输入text abcabcabc
输出3
解释3 个子字符串分别为 abcabc bcabca 和 cabcab 。示例 2
输入text leetcodeleetcode
输出2
解释2 个子字符串为 ee 和 leetcodeleetcode 。提示
1 text.length 2000
text 只包含小写英文字母。解题
想着暴力能够破解想多了hard题目不能暴力解。 超时代码
class Solution {
public:int distinctEchoSubstrings(string text) {int i, len, n text.size();string s, doubS;setstring set;for(len 1; len n/21; len){for(i 0; i n-len; i){s text.substr(i, len);doubS ss;if(text.find(doubS) ! text.npos)set.insert(doubS);}}return set.size();}
};class Solution {
public:int distinctEchoSubstrings(string text) {int i, len, n text.size(), count 0;string s, doubS;for(len 1; len n/21; len){setstring set;for(i 0; i n-2*len; i){s text.substr(i, len);doubS text.substr(i,2*len);if(ss doubS)set.insert(doubS);}count set.size();}return count;}
};用c17 的 string_view 可以避免复制可以节省内存
class Solution {
public:int distinctEchoSubstrings(string text) {int i, len, n text.size(), count 0;string_view t(text);for(len 1; len n/21; len){setstring_view set;for(i 0; i n-2*len; i){if(t.substr(i,len) t.substr(ilen,len))set.insert(t.substr(i,len));}count set.size();}return count;}
};
