这次周赛写的都比较丑陋，排名157/897
第一题：解压缩编码列表
给你一个以行程长度编码压缩的整数列表 nums 。
考虑每相邻两个元素 [a, b] = [nums[2i], nums[2i+1]] （其中 i >= 0 ），每一对都表示解压后有 a 个值为 b 的元素。
请你返回解压后的列表。
示例：
输入：nums = [1,2,3,4]
输出：[2,4,4,4]
思路：将nums分为两两一组(a, b)，每次扩展上a个b即可。
|
1 2 3 4 5 6 7 8 |
class Solution: def decompressRLElist(self, nums: List[int]) -> List[int]: ans = [] for i in range(0, len(nums),2): for j in range(nums[i]): ans.append(nums[i+1]) return ans |
第二题：矩阵区域和
给你一个 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]]
思路：用c++直接暴力算也可以，用python暴力会超时。
用 all[i][j] 记录坐标 (0, 0) 到 (i, j) 的元素之和。则坐标 (a, b) 和 (c, d) 之间的元素之和可以表示为：all[c][d] - all[a-1][d] - all[c][b-1] + all[a-1][b-1]。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class Solution: def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]: all = [[0 for i in range(len(mat[0]))] for j in range(len(mat))] ans = [[0 for i in range(len(mat[0]))] for j in range(len(mat))] def handle(i, j): try: if i == 0 and j == 0: all[i][j] = mat[i][j] elif i == 0: all[i][j] = mat[i][j] + all[i][j-1] elif j == 0: all[i][j] = mat[i][j] + all[i-1][j] else: all[i][j] = mat[i][j] + all[i][j - 1] + all[i - 1][j] - all[i - 1][j - 1] except: print(i,j) for i in range(len(all[0])): for j in range(i, len(all[0])): handle(i, j) for j in range(i+1, len(all)): handle(j, i) def get_all(i, j): if i < 0: i = 0 if j < 0: j = 0 if i > len(ans)-1: i = len(ans)-1 if j > len(ans[0])-1: j = len(ans[0])-1 return all[i][j] def get_sum(x1,y1,x2,y2): try: if x1 < 0: x1 = 0 if y1 < 0: y1 = 0 if x2 > len(ans) - 1: x2 = len(ans) - 1 if y2 > len(ans[0]) - 1: y2 = len(ans[0]) - 1 if x1 == 0 and y1 == 0: return all[x2][y2] elif x1 == 0: return all[x2][y2] -all[x2][y1-1] elif y1 == 0: return all[x2][y2] - all[x1-1][y2] else: return all[x2][y2]-all[x2][y1-1] - all[x1-1][y2]+all[x1-1][y1-1] except: print(x1,y1,x2,y2) for i in range(len(ans)): for j in range(len(ans[0])): ans[i][j] = get_sum(i-K,j-K,i+K,j+K) # print(all) return ans |
第三题：祖父节点值为偶数的节点和
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。
示例：
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出：18
解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
思路：偷懒的方法，dfs遍历一遍，然后对每个值为偶数的结点求子节点的子节点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Solution { public: vector<TreeNode*>v; void dfs(TreeNode* root){ if (!root) return; v.push_back(root); // cout<<root->val<<endl; if (root->left)dfs(root->left); if (root->right)dfs(root->right); } int sumEvenGrandparent(TreeNode* root) { int ans=0; dfs(root); TreeNode* t; for (int i=0;i<v.size();i++){ if (v[i]->val%2==0){ if(v[i]->left){ if (t=v[i]->left->left){ ans += t->val; } if (t=v[i]->left->right){ ans += t->val; } } if(v[i]->right){ if (t=v[i]->right->left){ ans += t->val; } if (t=v[i]->right->right){ ans += t->val; } } } } return ans; } }; |
第四题：不同的循环子字符串
给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目：这些子字符串可以写成某个字符串与其自身的串联。
示例 1：
输入：text = “abcabcabc”
输出：3
解释：3 个子字符串分别为 “abcabc” ， “bcabca” 和 “cabcab” 。
示例 2：
输入：text = “leetcodeleetcode”
输出：2
解释：2 个子字符串为 “ee” 和 “leetcodeleetcode” 。
思路：意思就是找text有几个不重复的子串，满足AA的形式。python遍历一遍，8000ms居然也过了😰。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution: def distinctEchoSubstrings(self, text: str) -> int: ans = set() def panduan(txt): l = len(txt) for i in range(2, 3): # 一开始以为可以AAA的形式，所以写成这样了 if l % i == 0: tt = '' r = True l1 = l // i for j in range(i): if tt == '': tt = txt[0:l1] else: if tt != txt[l1*j:l1*j+l1]: r = False break if r: return True return False for i in range(len(text)): for j in range(i, len(text)+1): txt = text[i: j] if txt and panduan(txt): ans.add(txt) return len(ans) |
