leetcode 第 328 场算法比赛 53名

零、背景

这次比赛第二题就开始提高难度，我的机会来了，排名 53/4776。

一、数组元素和与数字和的绝对差

题意：给一个数组，求数组之和与数组中各数字各位累计和的差值。

思路：按题意循环计算即可。

二、子矩阵元素加 1

题意：给一个初始全零矩阵，k个操作，每次操作可以将指定子矩阵里面的值都加1，问最终矩阵的值。
数据范围：矩阵大小n=500*500，操作次数k=10^4。

思路：树状数组或线段树求区间和。
n*m的矩阵操作，转化为 n 个一维数组的区间操作。
复杂度：O(k * n * log(n))

PS：你是怎么做的呢？

三、统计好子数组的数目

题意：给一个数组，问有多少个子数组满足子数组内相同二元组个数大于 K。
相同二元组：如果数组内存在两个不同下标值相同，则称为一个相同二元组。

思路：暴力肯定会超时，但是分析可以发现以某个位置开始的子数组，一旦满足要求，后面的子数组都符合要求。
所以，枚举的时候，只需要找到第一个满足要求的子数组即可。

实现方法：双指针。

四、最大价值和与最小价值和的差值

题意：给一个无根树，一个根为起点的最大路径与最小路径之差称为根的开销，求所有节点为根中的最大开销。

思路：显然，根的最小开销路径就是自己，所以开销最大路径减去根节点自己。

对于枚举所有根的题型，可以预先求出一个根的答案，然后通过加加减减的方法，计算出根的儿子当做根的答案。

对于这道题，假设已经计算出0为根时，每个节点子树的最大路径。
递归的时候，可以将根的父节点不包含根时的最大路径传给当前函数。
则当前根的最大路径要么在父节点那一侧，要么是其中一个儿子的路径，求最大值即可。

五、最后

这次比赛的难度比以前难，所以我的排名比较好，4776 个人，排名 53.

后面三道题你都是怎么做的呢？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code