Algorithm
本周选择的算法题是：Contains Duplicate III
规则如下：
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolutedifference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
Solution
我实现的方案：
解法一：
先用了暴力解法：
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
for i in range(len(nums) - 1):
for j in range(i + 1, min(len(nums), i + k + 1)):
if abs(nums[i] - nums[j]) <= t:
return True
return False
果然还是超时了 - -
解法二：
用到了桶的思想，同时为了减少内存占用，运行时动态删除桶中超过 k 个索引的元素：
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if t < 0: return False
buckets = {}
for i in range(len(nums)):
bucket = nums[i] // (t + 1)
if bucket in buckets:
return True
if bucket - 1 in buckets:
if nums[i] - buckets[bucket - 1] <= t:
return True
if bucket + 1 in buckets:
if buckets[bucket + 1] - nums[i] <= t:
return True
buckets[bucket] = nums[i]
if i >= k:
del buckets[nums[i - k] // (t + 1)]
return False
Runtime：72 ms，快过 52.6%。
Memory：16 MB，低于 33.33%。
Review
Modularize an iOS application
关于模块化的文章，观点没有太多新颖之处，总结下常见的两种模块类型：
- 功能性模块（Feature modules）
- 非功能性模块（Kit modules）
从依赖关系上看：
- 功能性模块能依赖一个或多个非功能性模块
- 非功能性模块不能依赖任何功能性模块
- 功能性模块不能依赖其他功能性模块
那么，模块化的过程中容易碰到的问题有哪些呢？一般来说是如下几个部分：
- 模块之间横向依赖
- 模块之间相互依赖
- 如果一个新功能会横跨几个模块，那这个功能放在哪个模块中
- 资源不共享，每个模块都有自己的 bundle
- 将已经紧密耦合的功能梳理到不同的模块
还在继续思考我上周的模块化思路，传送门，希望新的一周能尝试落地
Tip
终端
sudo !!-!!将执行最后一条语句，但是前面会加上sudo前缀；可以任意前缀tig- git 的反序，这是一个文本模式的 GUI 工具，几乎支持所有的 git 功能，地址
Share
如何写出干净的代码？
重视命名
任何变量、方法、对象的名字都要回答三个问题：
- 它为什么存在
- 它做什么
- 它干什么用的
方法只做一件事
好的方法有两条黄金准则：
- 它们很小
- 它们只做一件事，而且这件事干得很好
注释不能弥补坏的代码
注释是一把双刃剑。合适的位置出现合适的注释，这对开发者来讲帮助很大；同时，注释也能产生混乱和谎言，特别是当注释和代码不匹配时。
干净、自解释的代码，再配上少许注释就够了，这比大量注释+复杂代码更有用，与其将时间花在解释你的恶心代码，不如把时间用来改善你的代码。
格式化代码总是很重要的
代码是面向沟通的，它是一个与程序员沟通的窗口，虽然人们不会记得哪些程序员的代码风格很好，但是风格不好的程序员往往会被记住。代码的风格应该是所有团队成员能理解的简单规则的约束，它影响着可读性，也影响着代码可维护性。
先写 “try-catch-finally” 语句
入参可能不正常，硬件也有可能出问题，作为程序员，我们需要确保程序在做我们期望它做的事。这其中重要的地方不在于错误有没有被处理，而在于错误被如何处理，是不是以一种干净、可读的方式来处理。
代码应该是干净、易读且健壮的，它同时还可以优雅地处理错误，这是一位伟大的软件工匠的标志。