ARTS 第 51 周

每周完成一个 ARTS：

Algorithm: 每周至少做一个 LeetCode 的算法题

Review: 阅读并点评至少一篇英文技术文章

Tips: 学习至少一个技术技巧

Share: 分享一篇有观点和思考的技术文章



题图：Photo by Nico Benedickt

Contents



• Algorithm: 104. Maximum Depth of Binary Tree

• Review: STL: A Seasonal-Trend Decomposition Procedure Based on Loess

• Tips: 在 MarginNote 中使用 DeepL 作为字典与翻译工具

• Share: 慢碳水饮食中几个重要的原则



Algorithm

104. Maximum Depth of Binary Tree



题目：104. Maximum Depth of Binary Tree



难度：Easy



题意：Given a binary tree, find its maximum depth.



The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.



Note: A leaf is a node with no children.



示例：



Given binary tree [3,9,20,null,null,15,7],



    3
   / \
  9  20
    /  \
   15   7



return its depth = 3.



解法：



这道题的解法也是递归，首先如果这棵树不为空，我们才可进行进一步的计算，如果这棵树不为空，那么我们选择其左右节点中较大的那棵子树，再加上根节点本身长度为 1，作为结果返回，对于子树的长度计算，套用这个思路本身，将子树的根节点传入函数即可。代码如下。



代码：



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root:
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
        return 0



Review

STL: A Seasonal-Trend Decomposition Procedure Based on Loess



本周阅读了目前为止读的最长的一篇论文，但也是读得最细致的一篇，来自 Robert Cleveland 和 William Cleveland 的经典时序分解算法，《STL: A Seasonal-Trend Decomposition Procedure Based on Loess》。



该算法基于 Loess 将时间序列$Y_v$分解为趋势分量$T_v$、季节分量$S_v$和余项$R_v$：

STL 有内循环和外循环两个部分。内循环主要是趋势项的拟合和季节项的计算，而外循环则主要用于为算法增加鲁棒性，如果原序列中没有异常值（outliers），那么不需要进行外循环。



每一轮内循环都由一个更新季节分量的季节平滑过程和一个更新趋势分量的趋势平滑过程组成，分为 6 个步骤：

1. Detrending，即「去趋势」，用时间序列减去上一轮结果的趋势分量，$Y_v-T_v^{(k)}$，第一轮 $T_v^{(0)}=0$；

2. Cycle-Subseries smoothing，即「周期子序列平滑」，用 Loess 对每个周期相同位置的样本点即周期子序列做平滑，且前后各延展一个周期$n_{(p)}$，结果记为$C_v^{(k+1)},v=-n_{(p)}+1\text{ to }N+n_{(p)}$，这里 Loess 的参数选为$q=n_{(s)},d=1$；

3. Low-Pass Filtering of Smoothed Cycle-Subseries，即对平滑过的周期子序列进行低通滤波，这个过程由两个长度为$n_{(p)}$的移动平均和一个长度为 3 的移动平均、以及一个$(d=1,q=n_{(l)})$的 Loess 组成，结果记为$L_v^{(k+1)},v=1\text{ to }N$，这一步相当于提取周期子序列的低通量；

4. Detrending of Smoothed Cycle-Subseries，即去除平滑周期子序列的趋势，得到最终的季节分量，$S_v^{(k+1)}=C_v^{(k+1)}-L_v^{(k+1)}$；

5. Deseasonalizing，即去季节，减去季节分量，$Y_v-S_v^{(k+1)}$；

6. Trend Smoothing，即趋势平滑，对于去除周期之后的序列做 Loess 平滑，得到这一步的趋势分量$T_v^{(k+1)}$，这里 Loess 的两个参数$(q=n_{(t)},d=1)$。



而外循环增加鲁棒性是这么实现的：



1. 考虑余项$R_v=Y_v-T_v-S_v$，数据中的异常值会造成比较大的$|R_v|$，那么我们首先定义$h=6\text{ median}(|R_v|)$；

2. 鲁棒性权重定义为${\rho }_v=B(|Rv|/h)$，其中$B$为 bisquare 函数，定义如下：

1. 在每一次内循环的第 2 步和第 6 步中，Loess 的 邻域权重（Neighborhood Weight）需要乘以鲁棒性权重${\rho }_v$，这样可以减少异常值对 Loess 的影响。



一共进行$n_{(i)}$次内循环，$n_{(o)}$次外循环。



这样，STL 一共有 6 个参数：



1. $n_{(i)}$内循环层数；

2. $n_{(o)}$外循环层数；

3. $n_{(p)}$一个周期的样本数；

4. $n_{(s)}$内循环第 2 步中的 Loess 平滑参数；

5. $n_{(l)}$内循环第 3 步中的 Loess 平滑参数；

6. $n_{(t)}$内循环第 6 步中的 Loess 平滑参数。



这几个参数的选择比较啰嗦，涉及到特征值分析和内循环低通滤波器的频率响应函数的分析，在这里就简单的介绍一下参数选择的几个原则：



1. $n_{(p)}$就是时间序列的频率，非常明显；

2. $n(l)=[n(p){]}_{odd}$，就是$n_{(p)}$的下一个奇数；

3. $n_{(s)}$一般是大于 7 的奇数，需要根据时间序列的特性和分析目标来选择；

4. $n_{(t)}=[1.5n_{(p)}/(1-1.5/n_{(s)}){]}_{odd}$；

5. 如果未检测到异常值，那么$n_{(i)}=2,n_{(o)}=0$，否则$n_{(i)}=1,n_{(o)}=5\text{ or }10$。



Rob Hyndman 的 forecast R 包中封装了 STL 的 Fortran 实现，感兴趣的朋友可以一试。



Tips

在 MarginNote 中使用 DeepL 作为字典与翻译工具



我一直使用 MarginNote 这个软件来阅读论文，因为它除了支持常规的标注功能之外，还有两个杀手锏功能：一是可以根据标注内容自动生成思维导图和记忆卡片，方便回顾；二是 MarginNote 中集成了字典、文本、学术、问题、图片搜索和翻译等一整套常用的文献阅读时的高频操作，配合上使用 ABBYY 引擎的 OCR 功能，说是科研利器完全不为过。



DeepL 则是最近比较火爆的一款 NLP（自然语言处理）工具，提供了相当准确的翻译功能，有网友评测其翻译效果好于谷歌。我亲身体验了一下，DeepL 的翻译质量确实较谷歌翻译更为自然。于是我萌生了将 DeepL 作为 MarginNote 的内置字典和翻译工具的念头。





打开 MarginNote 的设置，选择「研究」，我们可以看到在「字典搜索」这一栏中有一个「自定义 URL」的选项，点击，就会出现自定义 URL 的填写框，我们将这个 URL 填入：https://www.deepl.com/translator#en/zh/{keyword}，接下来就可以使用 DeepL 提供的翻译功能了。



有的朋友就要问了：「为什么不更改翻译的选项呢？」



那是因为你没得选。。（现在我想做个好人🙃此处有一个老梗）





Share

慢碳水饮食中几个重要的原则



慢碳水饮食只适合于希望减脂和控制体脂率的人群，对于健康或无此需求的人群，请谨慎采用。



本教程不构成任何医学指导，请谨慎采用。



本周我们来介绍慢碳水饮食以及其中的几个重要的原则。



首先，没听过的朋友肯定想问，到底什么是「慢碳水饮食」？



根据 Tim Ferriss 在《The 4-hour Body》（中文版《每周健身四小时》）中的解释：



This diet claims to help weight loss by increasing the breakdown of fats and boosting feelings of fullness.（这是一种以分解脂肪和延长饱腹感来减轻体重的饮食方式。）



「慢碳水饮食」全称「慢碳水化合物饮食」，英文 Slow-carb diet，它和我们上周讲的血糖生成指数有着莫大的关系，实际上，所谓的「慢」，就是指的尽量去摄取低 GI 值的食物，减少摄取那些能够迅速被转换为脂肪的食物，延长饱腹感，进而使身体尽可能地使用脂肪来供能，达到减脂的效果。



我们来看数据。根据 Lift 的一项为期 4 周的研究试验：



84% of people who stuck to the program lost weight and the average weight loss was 8.6 pounds.



参与实验的人员中，有 84% 的人成功减轻了体重，平均减轻 8.6 磅，约合 4 公斤。（当然这项实验还包括了其它内容，包括洗冷水浴、起床 30 分钟之内吃掉 30 克蛋白质等等略显奇葩的方式。）



此外，全球还有数不清的人使用慢碳水饮食法成功减脂，这其中也包括我自己。



慢碳水饮食的一项优点就是，它非常简单，你只有五条原则需要去遵守：



原则一：不粘所有「白色」的碳水化合物



这一点至关重要。两个重要的点，一是「白色」，二是「碳水化合物」，这指的所有白色的、有可能成为白色的、或者曾经是白色但经过加工已经不是白色的碳水化合物。比如面包、米饭（紫米黑米也算）、各种谷物、土豆、面食、薯片等等。



不吃白色食物是保证你不再长胖的第一要义。



原则二：重复吃固定的食物搭配



超市里的食物千千万，但让你不发胖的则没多少。这里是三类「安全」的食物，可以自行搭配，然后重要的是，你可以想吃多少吃多少。



蛋白质：鸡蛋、牛肉、鸡胸或去皮鸡腿、瘦猪肉

豆类：小扁豆（lentil）、黑豆、红豆、黄豆

蔬菜：菠菜、十字花科蔬菜（花菜、西蓝花）、芦笋、韩国泡菜



对于我来说，这种吃法实际上就是简单地用豆类替代了米饭，该如何炒菜如何煲汤，还是和以往做简单的中餐没有太大的区别，但效果却很明显。



原则四：不吃水果



这一点看起来挺吓人的对不？但实际上从营养学的角度来看，不吃水果的原因挺简单的，水果中的葡萄糖和果糖相比较比其他任何碳水化合物，都更容易转化为甘油磷酸酯，进而通过肝脏转化为甘油三酯（没错这就是高血脂的一项指标），然后储存为脂肪。果汁就更不要喝了。



不用担心维生素缺乏，你在正餐吃的那些豆类、蔬菜和肉类已经完全能够补充你需要的维生素了，实在担心缺乏某些元素的话，可以适当补充一些镁钾钙，因为慢碳水饮食会让你相对更容易缺水，电解质的流失是必然的。



原则五：每周休息一天（Cheat Day）



每周你都可以休息一天，去吃任何你想吃的东西，薯片、蛋糕、肥宅水，并且想吃多少吃多少。这是为了补充一周内你因为使用慢碳水饮食造成的能量缺口，但放心，这一天你不管吃多少，它们不会全部都被身体消化吸收，这样做更多的是对身体的一种欺骗，让你的身体不再对垃圾食品那么地渴望。你可能会发现在 Cheat Day 的第二天体重增加了不少，但实际上是前一天吃下去的水分，24 小时之内就会被代谢掉。



以上就是慢碳水饮食的五点重要的原则，不信的话，试试就知道咯！



之后我会讲讲关于慢碳水饮食的一些常见问题，下周见！