ARTS - Week 16

ARTS - Week 16

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 98 - Validate Binary Search Tree

Validate Binary Search Tree

Difficulty: Medium

Solution

这道题在之前的 ARTS - Week 3 里有一种解法,即所有节点中序排列后去重再排序进行判断。但这种方法会占用较多新申请的空间来存放 list。以下解法会更优一些。

只保留前置节点进行判断

实际上不需要把所有节点的排序都存下来,只需要每次将当前节点和前序节点比较即可,在空间复杂度上较优。

# Python

class Solution:
    def isValidBST(self, root):
        self.prev = None
        return self.helper(root)
        
    def helper(self, root):
        if root is None:
            return True
        if not self.helper(root.left):
            return False
        if self.prev and self.prev.val >= root.val:
            return False
        self.prev = root
        return self.helper(root.right)

复杂度

  • Time complexity: O(N);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 52.48 % of python3 submissions.
Memory Usage: 16.8 MB


Review

Running a Flask Application as a Service with Systemd - by Miguel Grinberg

本文介绍了如何通过 Linux 的原生组件 systemd 监控管理部署好的 Flask web application。
相比于 supervisord,使用 systemd 监控消息组件 Redis Queue 的更加的方便与实用。可以把所有的 worker 作为一个整体进行管理,也可以单独新增、关闭单一的 worker。我们不用修改配置文件就可以在通过命令行实现上面的所有操作。


Tip

pidstat 指令中, %wait 表示进程等待 CPU 的时间百分比。此时进程是运行状态
top 指令中,iowait% 则表示等待 I/O 的 CPU 时间百分比。此时进程处于不可中断睡眠态
等待 CPU 的进程已经在 CPU 的就绪队列中,处于运行状态;而等待 I/O 的进程则处于不可中断状态。


Share

子网掩码到底是什么?

# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×