LEETCODE 第17场双周赛

这次周赛写的都比较丑陋,排名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即可。

第二题:矩阵区域和

  给你一个 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]

第三题:祖父节点值为偶数的节点和

  给你一棵二叉树,请你返回满足以下条件的所有节点的值之和:
  
  该节点的祖父节点的值为偶数。(一个节点的祖父节点是指该节点的父节点的父节点。)
  如果不存在祖父节点值为偶数的节点,那么返回 0 。
    
  示例:
    
  输入:root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
  输出:18
  解释:图中红色节点的祖父节点的值为偶数,蓝色节点为这些红色节点的祖父节点。

  思路:偷懒的方法,dfs遍历一遍,然后对每个值为偶数的结点求子节点的子节点。

第四题:不同的循环子字符串

  给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目:这些子字符串可以写成某个字符串与其自身的串联。
  
  示例 1:
  
  输入:text = “abcabcabc”
  输出:3
  解释:3 个子字符串分别为 “abcabc” , “bcabca” 和 “cabcab” 。
  示例 2:
  
  输入:text = “leetcodeleetcode”
  输出:2
  解释:2 个子字符串为 “ee” 和 “leetcodeleetcode” 。

  思路:意思就是找text有几个不重复的子串,满足AA的形式。python遍历一遍,8000ms居然也过了😰。