图

子图查找问题(阿里笔试20170825)

题目描述：若A和B是朋友，B和C是朋友，那么A和C也是间接朋友，只要是朋友关系的就被分到一组。现有一群人，他们之间的朋友关系用邻接矩阵表示。问应该被分为几组？

下面给出的解决方法，需要先将邻接矩阵转化为邻接表。

# 20180825 阿里笔试
# 求邻接表表示的无向图中子图的个数
# http://www.dannysite.com/blog/232/
def dfs(graph, node):
    """
    深度优先搜索
    graph是邻接表表示的图
    """

    # searched 用于存放已探索的节点
    # query_queue 是用来存放待探索节点的 to-do 列表，并将其模拟成 LIFO
    searched, query_queue = set(), []

    # 最初，to-do 列表中只有遍历的起点
    query_queue.append(node)

    while query_queue:
        # 总是从 to-do 列表的最后弹出一个待探索的节点
        q_node = query_queue.pop()

        if q_node in searched:
            continue

        searched.add(q_node)

        for neighbor in graph[q_node]:
            # 将邻居节点推入 to-do 列表
            query_queue.append(neighbor)

        yield q_node
from collections import deque
def bfs(graph, node):
    """
    广度优先搜索
    """

    # parents 记录所有可达节点与对应的父节点，这里是一个字典，我们将其 可达节点 作为 key，而将其 父节点 作为 value
    # query_queue 是用来存放待探索节点的 to-do 列表，这里是一个 FIFO
    parents, query_queue = {node: None}, deque([node])

    while query_queue:
        # 总是从 FIFO 的左侧弹出待探索的节点
        q_node = query_queue.popleft()

        for neighbor in graph[q_node]:
            if neighbor in parents:
                continue

            # 记录探索到的邻居节点及其父节点
            parents[neighbor] = q_node

            # 将其邻居节点推入 to-do 列表
            query_queue.append(neighbor)
        yield q_node
    # return parents
if __name__ == "__main__":
    graph = [[1,2,4],
             [0,2],
             [0,1,3,5],
             [4,5],
             [0,3],
             [3,6],
             [5],
             [8,9],
             [7],
             [7],
             [11],
             [10],
             []]

    # 子图查找
    nodes = set(range(len(graph)))
    count = 0
    while nodes:
        start = nodes.pop()
        nodes.add(start)
        searched = bfs(graph, start)
        for node in searched:
            nodes.remove(node)
        count += 1
    print(count)

二叉树

哈弗曼树

平衡二叉树

链表

反转链表

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None or pHead.next == None:
            return pHead
        pre = None #保存pHead之前节点
        while pHead:
            next = pHead.next #保存下一节点位置
            pHead.next = pre #逆转当前节点
            pre = pHead #整体向后移动一节点
            pHead = next #整体向后移动一节点
        return pre

概念知识

进程与线程

相关博客
进程与线程的一个简单解释

进程是系统资源调度的基本单位，线程是进程内部对执行任务的再细分，线程之间共享内存等资源，但是需要使用一些互斥机制来保证内存的正确共享。

联想：超线程技术

作者：大饼土博
链接：https://www.zhihu.com/question/20277695/answer/14588735
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Intel的超线程技术，目的是为了更充分地利用一个单核CPU的资源。CPU在执行一条机器指令时，并不会完全地利用所有的CPU资源，而且实际上，是有大量资源被闲置着的。超线程技术允许两个线程同时不冲突地使用CPU中的资源。比如一条整数运算指令只会用到整数运算单元，此时浮点运算单元就空闲了，若使用了超线程技术，且另一个线程刚好此时要执行一个浮点运算指令，CPU就允许属于两个不同线程的整数运算指令和浮点运算指令同时执行，这是真的并行。
我不了解其它的硬件多线程技术是怎么样的，但单就超线程技术而言，它是可以实现真正的并行的。但这也并不意味着两个线程在同一个CPU中一直都可以并行执行，只是恰好碰到两个线程当前要执行的指令不使用相同的CPU资源时才可以真正地并行执行。

面向对象

Python 面向对象(初级篇)
Python 面向对象(进阶篇)

设计模式

设计模式菜鸟教程

工厂模式

接口选择问题，在不同的条件下创建不同的对象

抽象工厂模式

工厂的工厂，总是多个对象成套使用，具体的对象用工厂模式创建，但是多套对象需要多个工厂，工厂的工厂模式通过接口选择对应的工厂。

建造者模式

用于创造复杂的对象，复杂对象有多个简单对象一步步构建成

单例模式

相关博客
单例模式(Singleton)及其C++实现

单例模式，也叫单子模式，是一种常用的软件设计模式。在应用这个模式时，单例对象的类必须保证只有一个实例存在。许多时候整个系统只需要拥有一个的全局对象，这样有利于我们协调系统整体的行为。比如在某个服务器程序中，该服务器的配置信息存放在一个文件中，这些配置数据由一个单例对象统一读取，然后服务进程中的其他对象再通过这个单例对象获取这些配置信息。这种方式简化了在复杂环境下的配置管理。在多线程场景中小心使用。

// Meyers Singleton 单例模式C++实现
class Singleton  
{
    public:
        static Singleton& Instance(){
        static Singleton instance；
        return instance；
    }
    private:
        Singleton()；
        ~Singleton()；
        Singleton(const Singleton&);
        Singleton& operator=(const Singleton&);
};

MVC模式

作者：赛门喵
链接：https://www.zhihu.com/question/29138020/answer/141170242
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

每个人的主页都是相同的布局和风格，例如最上面的菜单搜索栏，颜色分割，左边显示动态等，右边是个人信息等，然后具体的内容却因人而异——每个人的头像，名字，动态都是不一样的。那么知乎是如何保证每一个人看到的都是自己的主页呢？
你可以把这个相同的布局想象成一个模板，里面有一个个空格子，当你用你的账户登陆页面时，想象你的电脑里有无数个小人根据你的账号从知乎后台的数据库里取出你的头像，动态，认证信息等等内容，然后对应着模板上规定好的位置，把对应的内容填进去。这些小人的动作实在是太快了，以至于你觉得这是在瞬间完成的。
上面所说的模板就是MVC中的V，是View的缩写，负责显示。这样做的好处在于，如果知乎有一天突然想改变一下个人主页的风格，那么只需要改变这一个模板，然后几千万注册用户的主页就相应的变化了，因为模板是公用的，是不是省了很多事情？（早期的Web开发可不是这样哟，你可能要一个个用户去改，非常麻烦。）
而这些小人除了摆放内容，它们真正负责的是业务逻辑，我们把他们叫做Controller，也就是MVC中的C。例如当你登陆的时候，这些小人要检查你的用户名是不是准确的，如果准确，它们要去数据库里取出你请求的信息等，如果用户名错误，它们要拦截住你的登陆。它们的职责还有很多，无法一一列举。在实际中，这些小人做的事情其实就是Python（或者其它脚本语言）做的事情。
最后，MVC中的Model其实就是传给View的数据，包括上面的头像，用户名，动态等因人而异的数据。这些数据在知乎服务器上是以数据库表格（table）的形式存在的，你可以把它们想象成很多不同的excel表格，不同的表格储存着不同的信息，有些记录着知乎用户的个人信息，有些记录着回答，有些记录着评论等等，而这些表格之间又彼此联系，当你在知乎的不同网页间跳转的时候，上面说的那些小人就根据你的要求，组合对应的表格取出对应的数据，然后把他们放到模板对应的空格里，发送给浏览器。然后浏览器根据你写的CSS，用不同的颜色，大小等等，将数据很漂亮的显示出来。
这样做的好处是什么呢？虽然你最终在浏览器里看到的是一个完整的页面，但是在后端逻辑上它们都是区分开的——模型（M），视图（V）和控制器（C）的区分就保证了较高的可维护性——我可以随时修改主页的显示并看到效果，同样我可以随时加入一些业务逻辑。