不会飞的章鱼

第3集剧情简介

周末跟完了《工作细胞 BLACK》的最新剧集，第三集的剧情给我留下了非常深刻的印象，因为它触碰到了我上小学和中学的知识禁区——性行为。

第3集的大致剧情是一群红细胞收到了比运输氧气更重要的任务，就是这具身体因生殖行为而进行兴奋状态，需要红细胞使阴茎中的海绵组织（海绵体）勃起，完成射精！

但结果非常不顺：刚开始红细胞排成一队进入海绵体，把螺旋动脉张开，血液进去，进入勃起状态，看似一切顺利

搜索-遍历

• 每个节点都要访问一次
• 每个节点仅仅要访问一次（不做无用功）
• 对于节点的访问顺序不限：dfs / bfs

示例代码

DFS算法模板

1
2
3
4
5
6
7
8
9
10
11
12

def dfs(node):
    if node in visited:
        # already visited
        return
    
    visited.add(node)

    # process current node
    # ... logic here

    dfs(node.left)
    dfs(node.right)

分治的思想

本质就是找重复性和分解问题，以及最后组合每个子问题的结果。

例如：

它是如何工作的？

在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

LC二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
 

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

哈希表（Hash Table）

工程实践：电话号码簿、用户信息表、缓存（LRU Cache）、键值对存储（Redis）。

原理

哈希函数：

题目

LeetCode
LeetCode-cn

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

复习

树

• 前序(Pre-order)：根-左-右
• 中序(In-order)：左-根-右
• 后序(Post-order)：左-右-根

记忆方法：前序->根在最前面，中序->根在中间，后序->根在最后，左永远在右的前面。

动态规划-Dynamic Programming

1，wiki定义
2，in a recursive manner
3，Divide & Conquer + Optimal substructure——分治+最优子结构

关键点

• 动态规划和递归或者分治没有根本区别（关键看有无最优的子结构）
• 共性：找到重复子问题
• 差异性：最优子结构、中途可以淘汰次优解

顺推模板

栈

想象成一个先入后出的容器：

队列

像排队，先来先出：