ARTS-Week 1

最近报名了极客时间的数据结构与算法之美，打算一点点巩固算法知识，每周都进步一些。

Algorithm

Leetcode 70

爬楼梯

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

首先想到的就是递归啦，不过估计八成过不了，会超时并且占用内存过大。

from functools import lru_cache

class Solution:

    @lru_cache()
    def climbStairs(self, n: int) -> int:
        if n == 2:
            return 2
        elif n == 1:
            return 1
        return self.climbStairs1(n-1) + self.climbStairs1(n-2)

不过不死心，想来一个记忆递归，就这样查到了python的一个语法糖：lru_cache 这个钩子函数加到函数上会将结果存储起来，实现了类似于备忘的功能，在重复调用的时候就不用重新计算了，并且缓存也不会无限增加，在一段时间没有使用的时候就会丢掉，加上这个函数就过了。

之后想到的就是动态规划啦。

class Solution:

    def climbStairs(self, n: int) -> int:
        arr_list = [1, 2]
        for i in range(2, n):
            arr_list.append(arr_list[i-1] + arr_list[i-2])
        return arr_list[n-1]

这个直接 AC，不过这种方式在 n 的增加的时候，占用的内存就会无限增加，其实因为只要求的最后的结果，并且求的是最大的值，那之前的值也就没有必要保存。

class Solution:

    def climbStairs(self, n: int) -> int:
        temp = 1
        if n == 2:
            return 2
        elif n == 1:
            return 1
        a, b = 1, 2
        for i in range(2, n):
            temp = a + b
            a = b
            b = temp
        return temp

当阶梯数量为1的时候，最大要有1种方案，2的时候有两种方案（1，1或2），3步的时候有三种（1，1，1或1，2或2，1），与此类推，会发现，这实际上就是斐波那契额数列。

Review

Understanding kubernetes networking: pods

是关于 K8S 中 Pods 的讲解，算是整个 K8S 最重要的部分。pods 是 k8s 中最小的一个基本单位和 volumes 类似。可以包含多个容器，有自己的命名空间。

Tip

Green Tea Press

publisher of Think Python, Think Bayes, and other books by Allen Downey.

里面提供了多本书集的在线阅读和下载PDF的方式，全部都是英文的书集，按作者的话来说就是也希望通过这种方式来帮助开发者，下面截取网站的一句话：

All of our books are available under free licenses that allow readers to copy and distribute the text; they are also free to modify it, which allows them to adapt the book to different needs, and to help develop new material.

lru_cache

Python中的一个很神奇的装饰器，实现了备忘功能的一种优化技术，在迫不得已要写递归的时候可以把这个加上，而且省去了写记忆递归的时间，算是一种原生的缓存机制。

Share

整洁代码之道—重构

之前需要重构代码的时候查阅到这篇文章，作者从为什么重构，到重构的技巧等讲解了很多方面，主要围绕 Java 语言的重构，不过总的思想值得学习，总的来说重构是贯穿在整个开发过程中的，需要不断持续的改进，不要想着现在随便写到时候再改，这滚雪球效应会越来越难偿还。

Note

最近在学习数据结构与算法之美。