ARTS - Week 15

ARTS - Week 15

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

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

Algorithm

LeetCode Problems 18 - 4Sum

4Sum

Difficulty: Medium

Solution

第一种解法:暴力解法

嵌套 4 层循环去寻找符合的解法。
这种方法的时间复杂度为 O(N4),由于逻辑比较简单,代码就不列出了。

第二种解法:使用 Set 结构

使用哈希表,以减少一层循环的复杂度。选择 Set 是因为可以更好的达到去重的目的。

# Python

class Solution(object):
    def fourSum(self, nums, target):
        result = set()
        nums.sort()
        for i in range(0, (len(nums) - 3)):
            if i >= 1 and nums[i] == nums[i - 1]:
                continue

            for j in range(i + 1, (len(nums) - 2)):
                d = {}
                for k in range(j + 1, len(nums)):
                    if nums[k] not in d:
                        d[target - nums[i] - nums[j] - nums[k]] = 1
                    else:
                        result.add((nums[i], nums[j], target - nums[i] - nums[j] - nums[k], nums[k]))

        return result

复杂度

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

运行结果

Python:
Runtime: 1112 ms.
Your runtime beats 12.36 % of python3 submissions.
Memory Usage: 11.9 MB
Your memory usage beats 11.01 % of python submissions.

第三种解法:双向收缩

此方法和 ARTS - Week 3 中的 3sum的解题思路一致。
先将给定 nums 排序;
两层循环进行遍历,根据剩余元素最小值和最大值的情况进行循环,不断进行双向收缩。
要注意代码中关于去重的部分。

# Python

class Solution(object):
    def fourSum(self, nums, target):
        result = set()
        nums.sort()
        for i in range(0, (len(nums) - 3)):
            if i >= 1 and nums[i] == nums[i - 1]:
                continue

            for j in range(i + 1, (len(nums) - 2)):
                l, r = j+1, len(nums)-1
                while l < r:
                    s = nums[i] + nums[j] + nums[l] + nums[r]
                    if s > target: r -= 1
                    elif s < target: l += 1
                    else:
                        result.add((nums[i], nums[j], nums[l], nums[r]))
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        while l < r and nums[r] == nums[r-1]:
                            r -= 1
                        l += 1; r -= 1

        return result

复杂度

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

运行结果

Python:
Runtime: 844 ms.
Your runtime beats 26.69 % of python3 submissions.
Memory Usage: 12 MB
Your memory usage beats 11.01 % of python submissions.


Review

Setting Up a Flask Application in PyCharm - by Miguel Grinberg

本文通过文章和视频,作者介绍了在 Pycharm 中,如何设置启动一个 Flask 应用;如何设置 Debug 模式并进行常规的调试;如何设置单元测试模式。
最后,介绍了如何让 Pycharm 的 Debugger 去捕捉程序跑出的各种 errors,以更有效率的进行调试。


Tip

Linux 将中断处理过程分为了两个阶段 - 上半部和下半部

  • 上半部用来直接处理硬件请求,也就是我们常说的硬中断。它在中断禁止模式下运行,主要处理跟硬件紧密相关或时间敏感的工作。特点是快速执行;
  • 下半部则是由内核触发,也就是我们常说的软中断。用来异步延迟处理上半部未完成的工作,通常以内核线程的方式运行。特点是延迟执行。

可以通过 proc 文件系统来查看系统中断的运行情况:

  • /proc/softirqs 提供了软中断的运行情况
  • /proc/interrupts 提供了硬中断的运行情况

总结了一些涉及中断性能问题的工具和指令:

  1. ps aux | grep softirq 可以查看软中断内核线程的运行状况;
  2. hping3 是一个可以构造 TCP/IP 协议数据包的工具,可以对系统进行安全审计、防火墙测试等;
  3. sar 是一个系统活动报告工具。可以用来查看系统的网络收发情况,还可以观察网络收发的 PPS,即每秒收发的网络帧数。

# ARTS 

评论

Your browser is out-of-date!

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

×