###思路

首先题目的要求是原地

  • 首先判断是否有root,如果没有则return空值
  • 接下来将root.left二叉树复制给node，然后开始判断是否有if node,有的话继续判断该节点是否有右子节点while node.right:,如果有右子节点就继续判断node=node.right。
  • 将根节点的右子节点复制到，刚刚搜索到的那个节点的右子节点node.right=root.right。
  • 将整个根节点的左子节点覆盖根节点的右子节点root.right=root.left，并将根节点的左子节点重置为None
  • 最后递归调用，参数为根节点的右子节点root.right，也就是现在root.right作为新的root根节点，之后的每次递归调用都更新根节点。

###具体代码以及注释如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """       
        if not root:
            return
        # 后序遍历
        self.flatten(root.left)
        self.flatten(root.right)
        if root.left and root.right:
            # 寻找root.left尾部用的指针
            index = root.left
            # while循环找root.left的尾部
            while index.right:
                index=index.right
            # 进行拼接工作
            index.right = root.right
            root.right=root.left
            root.left=None
            # 如果没有左节点，就不用拼接了
        elif not root.right and root.left:
            root.right=root.left
            root.left=None

1.前序遍历

前序遍历执行的是中左右的遍历原则，即先遍历中间的根节点，然后左节点，最后右节点。这样获得的遍历顺序为：1245367

1
2
3
4
5
6
7
8
9
def preorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        tree.append(node.val)
        helper(node.left)
        helper(node.right)
    helper(root)
    return tree

2.中序遍历

1
2
3
4
5
6
7
8
9
def innerorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        tree.append(node.val)
        helper(node.right)
    helper(root)
    return tree

3.后序遍历

后序遍历执行的是左右中的遍历原则，即先遍历中间的左节点，然后右节点，最后中节点。

1
2
3
4
5
6
7
8
9
def postorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        helper(node.right)
        tree.append(node.val)
    helper(root)
    return tree

4.总结规律

基于以上代码可见，二叉树的遍历基本的代码框架如下：

1
2
3
4
5
6
7
8
def Traversal(root):
    tree = []
    def helper(node):
        #判断当前节点是否为空
        #执行当前节点操作
        #执行左右子树操作
    helper(root)
    return tree

1

##二叉树基本定义

​ img

定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成

特点

1）每个结点最多有两颗子树
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树遍历

1
2
3
#判断当前节点是否为空
#执行当前节点操作
#执行左右子树操作

1.前序遍历

前序遍历执行的是中左右的遍历原则，即先遍历中间的根节点，然后左节点，最后右节点。

1
2
3
4
5
6
7
8
9
def preorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        tree.append(node.val)
        helper(node.left)
        helper(node.right)
    helper(root)
    return tree

2.中序遍历

中序遍历执行的是左中右的遍历原则，即先遍历中间的左节点，然后中间节点，最后右节点

1
2
3
4
5
6
7
8
9
def innerorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        tree.append(node.val)
        helper(node.right)
    helper(root)
    return tree

3.后序遍历

后序遍历执行的是左右中的遍历原则，即先遍历中间的左节点，然后右节点，最后中节点。

1
2
3
4
5
6
7
8
9
def postorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        helper(node.right)
        tree.append(node.val)
    helper(root)
    return tree

4.总结规律

基于以上代码可见，二叉树的遍历基本的代码框架如下：

1
2
3
4
5
6
7
8
def Traversal(root):
    tree = []
    def helper(node):
        #判断当前节点是否为空
        #执行当前节点操作
        #执行左右子树操作
    helper(root)
    return tree

Serverless架构是近年来迅速兴起的一个技术概念。基于这种架构能构建出多种应用场景，适用于各行各业。只要是对轻计算、高弹性、无状态等场景有诉求，您都可以通过本文来熟悉一些基础概念，并从相关场景中获得启发。

Serverless演进

关于Serverless架构的演进，网上比较流行用一张人类形态发展史图进行说明。从爬行猿人到蹲着的类猿人，再到直立人类，最后到使用工具的新兴人类。

人类的每一次进化都伴随着生产效率的提升。同理，整个IT计算的发展历程，也是一个逐步提高生产效率的历程，具体演进图如下所示。img

在这个发展历程中有以下几个渐进的里程碑事件：

  1. 通过虚拟化技术将大型物理机虚拟成单个的VM资源。
  2. 将虚拟化集群搬到云计算平台上，只做简单运维。
  3. 把每一个VM按照运行空间最小化的原则切分成更细的Docker容器。
  4. 基于Docker容器构建不用管理任何运行环境、仅需编写核心代码的Serverless架构。

因此，这个发展历程也是一场IT架构的演进，期间经历了一系列代际的技术变革，把资源切分得更细，让运行效率更高，让硬件软件维护更简单。IT架构的演进主要有以下几个特点：

  • 硬件资源使用颗粒度变小
  • 资源利用率越来越高
  • 运维工作逐步减少
  • 业务更聚焦在代码层面

Serverless架构主要有以下特点：

  • 实现了细粒度的计算资源分配。
  • 不需要预先分配资源。
  • 具备真正意义上的高度扩容和弹性。
  • 按需使用，按需计费。

根据Serverless的这些通用特点，归纳出下面几种典型使用场景，供大家参考。

Serverless的典型应用有哪些？

事件请求场景

  • 定制图片

    网店店家进行商品图片维护时，需要根据商品陈列位置，将图片动态切割成不同尺寸，或者打上不同水印。当店家把图片上传到对象存储 OSS上，会通过函数计算上定制的trigger来触发函数计算。根据计算规则，生成不同尺寸的图片，满足在线商品陈列需求，整个过程无需再搭建额外服务器，也无需网站美工干预。

  • 物联网中的低频请求

    物联网行业中，物联网设备传输数据量小，且往往是以固定时间间隔进行数据传输，因此经常涉及低频请求场景。例如：物联网应用程序每分钟仅运行一次，每次运行 50ms，这意味着CPU的使用率仅为 0.1%/小时，或者说有 1000 个相同的应用可以共享计算资源。而Serverless架构下，用户可以购买每分钟 100ms 的资源来满足计算需求，既能有效解决效率问题，也能降低使用成本。

  • 定制事件

    用户注册时发邮件验证邮箱地址，同样可以通过定制的事件来触发后续的注册流程，而无需再配置额外的应用无服务器来处理后续的请求。

  • 固定时间触发

    事件触发固定时间触发，例如在夜间或者服务空闲时间来处理繁忙时候的交易数据，或者运行批量数据，来生成数据报表，通过Serverless方式，不用再额外购买利用率并不高的处理资源。

流量突发场景

  • 弹性扩展应对突发流量

    移动互联网应用经常会面对突发流量场景。例如：移动应用的通常流量情况是 QPS 20，但每隔 5 分钟会有一个持续 10s 的 QPS 200 流量（10 倍于通常流量）。传统架构下，企业必须扩展 QPS 200 的硬件能力来应对业务高峰，即使高峰时间仅占整个运行时间的4%。

    在Serverless架构下，您可以利用弹性扩展特性，快速构建新的计算能力来满足当前需求，当业务高峰后，资源能够自动释放，有效节省成本。

  • 转码和流量扩容

    视频直播某次专场活动，由于无法预估会有多少点播的观众视频接入，把转码和流量扩容这部分内容通过Function来处理，无需考虑并发和流量扩容。

处理大数据场景

由于安全审计问题，您需要从OSS（多个地域）过去一年的数据（1 个小时一个文件）中找出特定关键字访问的日志，同时做聚合运算（计算出总值）。如果使用阿里云函数计算，您将高峰期每 2 小时的访问日志，或者低谷期每 4 小时的访问日志交给一个计算函数处理，并将处理结果存到RDS中。使用一个函数分派数据给另一个函数，使其执行成千上万个相同的实例。

这样会同时运行近千个计算函数（24 x 365 / 10），在不到一分钟的时间内完成整个工作。同样的事情交给ECS+计算脚本来做计算，单单为这些instance配置网络就让人头疼（不同地域无法走内网下载OSS文件）：instance的数量可能已经超出了子网中剩余IP地址的数量（比如，您的VPC使用了24位掩码）。

下面结合阿里云的函数计算产品来讲解各个应用场景中地架构以及如何解决场景中的痛点。阿里云的函数计算是基于Serverless这种架构实现的一个全托管产品，用户只需要上传核心代码到函数计算，就可以通过事件源或者SDK&API来运行代码。函数计算会准备好运行环境，并根据请求峰值来动态扩容运行环境。函数计算是按照执行时间来计费，请求处理完成后，计费停止，对于有业务请求有明显高峰和低谷的应用来说，相对节省成本。

下图是函数计算的一个开发者试用操作流程：img

  1. 开发者编写代码，目前支持的语言Java、NodeJS、Python等语言。
  2. 把代码上传到函数计算上，上传的方式有通过API或者SDK上传，也可以通过控制台页面上传上传，还可以通过命令行工具Fcli上传。
  3. 通过API&SDK来触发函数计算执行，同样也可以通过云产品的事件源来触发函数计算执行。
  4. 函数计算在执行过程中，会根据用户请请求量动态扩容函数计算来保证请求峰值的执行，这个过程对用户是透明无感知的。
  5. 函数执行结束后，可以通过账单来查看执行费用，根据函数的实际执行时间按量计费，收费粒度精确到100ms。

讲解完上面的流程后，下面会详细讲解3个Serverless的应用场景，通过案例分享能让您对Serverless这种架构有更清晰的认识。

场景一：事件触发计算能力

img

场景描述

用户通过手机终端、Web应用、或者PC工具把各种文件包括图片、视频以及文本等上传到OSS（对象存储，下同）后，利用OSS的PutObject事件可以触发函数计算对上传后的文件进行处理。

典型场景

当用户把视频文件上传到OSS后，触发函数计算把对象的Meta信息获取并传输给核心算法库，核心算法库根据算法把相应的视频文件推送CDN源站，达到特定视频热加载的处理。另外一个场景，视频文件上传到OSS后也同时触发函数计算同步做多转码率的处理，并把处理后的视频文件存储到OSS中，完成轻量的数据处理。

在多媒体的处理场景中，经常会碰到海量文件上传到OSS后，还需要对文件进行进一步的加工，例如加水印、转码率、获取文件属性等操作，这个场景中，用户在处理的时候会遇到以下需要解决的技术难点：

  • 如何接收文件上传后的动作事件，通常的做法是定制消息通道来接收OSS事件通知，搭建一个运行环境，并编写相关的代码来处理事件通知。
  • 如何高效的处理完海量上传的文件。
  • 如何无缝的把多个云产品连接起来。

通过函数计算能比较方便解决以上几个技术难点：

  • 函数计算可以设置OSS的触发器来接收事件通知，在函数计算中编写业务代码来处理文件，并通过内网把文件传输到OSS中，整个流程简单易用可扩展。
  • 可以把核心代码部署到函数计算中，通过函数计算来并发处理事件通知。
  • 函数计算目前打通了多款产品的内部交互，通过控制台简单配置就可以高效的解决产品间连接问题。

事件触发场景常规做法：

  • 设置消息通道接收事件，并编写业务代码。
  • 购买服务器资源做后端数据处理。
  • 设计一套多并发框架完成业务上传文件峰值的处理。
  • 开通多个产品，并调用SDK代码来完成业务交互。

函数计算解法：

  • 在控制台上配置事件源通知，编写业务代码。
  • 代码写到函数计算里，不需要管理软硬件环境。
  • 业务高峰期函数计算会动态伸缩，无需管理。
  • 内置打通多款产品，简单配置就可以无缝对接。

场景二：利用弹性扩容（视频直播多人连麦场景）

img

场景描述

直播间的客户端把主播和连麦观众的音视频采集发送给函数计算做混流服务，函数计算把数据汇集后交给混流服务进行合成，并把合成画面视频流推送给CDN，终端观众实时拉取直播流，能实时看到混流合成画面。

视频直播应用场景中，有一种场景视频直播的多人连麦，主播可以同时和多个工作进行连麦，把多个观众或者好友画面接入，并把画面合成到一个场景中，供给更多观看直播的观众观看。这个场景中，有几个技术难度需要关注：

  • 连麦的观众不固定，需要考虑适度的并发和弹性。
  • 直播不可能 24 小时在线，有较为明显的业务访问高峰期和低谷期。
  • 直播是事件或者公众点爆的场景，更新速度较快，版本迭代较快，需要快速完成对新热点的技术升级。

综合以上几个特点，可以通过Serverless这种架构来完美地解决以上痛点。

函数计算作为连麦观众和主播接入的实时音频和视频转发集群，当并发量过来时，函数计算自动扩容多个执行环境来处理实时数据流；当业务高峰期过去后，会适度缩减资源使用。代码管理部署在云端，代码迭代可以随时进行修改和维护，无需再多管理一套软件运行环境。

视频直播场景常规做法：

  • 购买负载均衡应付并发。
  • 购买计算资源做数据处理。
  • 业务低谷期需要想办法释放硬件资源来节省成本。
  • 多版本要维护多套运行环境。

函数计算解法：

  • 把负载分发程序写到函数里。
  • 多版本迭代无需更换运行环境，仅仅替换代码版本即可。
  • 业务访问按需付费，业务低谷期无费用。

场景三：物联网数据处理场景

img

整个架构图分成 2 部分内容：

  • Web应用：模拟一个社交内容更新和数据处理的流程，Web用户通过API网关把请求转发到函数计算进行处理，函数计算把处理后的内容更新到数据库中，并更新索引，另外一个函数计算把索引更新推送的搜索引擎供给外部客户进行检索，完成整个数据闭环处理。
  • 智能设备：通过IoT网关把设备状态推送到函数计算处理，函数计算通过API接口把消息通过移动推送服务，推送给移动端进行状态确认和管理。

在智能设备状态处理的场景中，同样也会碰到几个核心技术问题要解决。当海量设备把状态发送到IoT平台后，如何设计一套高效非轮询的技术框架来处理设备状态数据；如何把处理后的数据高效透传其他产品，例如写数据库或者推送给移动端。

IoT设备状态场景常规做法：

  • 设置消息通道接收事件，并编写业务代码。
  • 购买服务器资源做后端数据处理。
  • 开通多个产品，并调用SDK代码来完成业务交互。
  • 维护相关硬件软件环境。

函数计算解法：

  • 定制IoT平台的事件通知，直接把业务代码写到函数计算中。
  • 不需要维护运行环境，用完即可释放。
  • 控制台配置，就可以把信息透传给相关产品。

通过 2 种方式的对比，能看出函数计算的解法更具备通用性，可以大量减少维护工作。

场景四：共享派单系统详解

客户通过派单平台选择某种商家提供的服务，可能是餐饮、商品、或者服务。派单平台通知最近的骑手到最近的商家拿到服务并派送到客户手里。一个简单的流程图如下：img

流程详解：

  1. 客户通知派单平台下单某商品。
  2. 派单平台通知最新骑手。
  3. 派单平台同时通知商家商品售卖出去。
  4. 骑手到指定的商家获取商品。
  5. 骑手配送到客户所在地。

这个派单场景中，要解决几个棘手的技术：

  • 整合多种资源，计算资源会涉及到，骑手位置信息、最优路径规划、车况情况、调度系统等。
  • 低延迟：派单系统对订单的响应要求很高，从接单到商家在到客户，整个闭环都需要在段时间内完成。
  • 海量数据：涉及到三方面的数据，客户数据、商家数据、平台骑手数据、位置信息、商品信息等。
  • 请求明显波峰波谷：派单系统在一天中的资源使用非常不均衡，波峰期，例如外卖，在中午和晚饭达到高峰，平时空闲。

通过技术选型转化成阿里云产品的解决方案后，函数计算结合其他产品比较完美地解决上述问题，解决方案如下图所示：

img

流程详解：

  1. 客户APP把订单请求通过API网关透传给函数计算。

  2. 函数计算把处理后的数据传输给表格存储。

  3. 表格存储存放了骑行数据、商家信息、位置信息等。

    说明 其中骑行日志会存放到日志服务里，便于后续做报表分析。骑行过程中骑手头像、随手拍街景会存放到OSS中，骑手位置可以通过函数计算去拉取第三方地图信息，例如高德地图等。

这个方案中，函数计算可以完成动态扩容问题，API网关可以解决鉴权和安全访问问题，函数计算打通了多款产品，可以无缝使用其他资源和内容。所有处理后的数据可以存放到表格存储数据库中，所有日志都可以直接加载到日志服务为后续数据报表服务。

共享派单系统常规做法：

  • 购买多台服务器来支持高峰期的访问，访问波谷期自行设置释放原则。
  • 通过编程方式完成多个产品的交互。
  • 为了保证负载均衡，需要购买相关的产品来支撑。
  • 维护相关硬件软件环境。

函数计算解法：

  • 定制IoT平台的事件通知，直接把业务代码写到函数计算中。
  • 不需要维护运行环境，用完即可释放。
  • 控制台配置，就可以把信息透传给相关产品。
  • 2种解法都能达到目标，从资源利用率和可维护性来看，使用Serverless架构的方式会更优。

总结

通过上面几个场景的详解，大致可以得出这样的结论：通过事件触发场景；有业务访问高峰和低谷的场景，迭代次数较多，需要快速打通多款产品场景；通过函数计算能完美地解决成本、效率、联通等问题。

函数计算 自建计算环境
维护性 内置打通API网关，OSS，Table Store、IoThub、Log Service、Message Service、Datahub等产品，只需要简单配置。沙箱执行环境，无需配置。自动伸缩和负载均衡。触发条件简单，入口多。 多款产品链接需要自己编写代码来实现，有技术门槛。自建物理环境，需要配置运行环境，消耗人力物力。需要自行搭建伸缩机制和负载均衡，耗时较多。
可靠性 代码和配置存放在OSS中，自动多重冗余备份。 受限于硬件可靠性，易出问题，一旦出现运行环境或者数据损坏，容易出现不可逆转的数据丢失。人工数据恢复困难、耗时、耗力。
成本 按执行付费，在业务请求波谷期费用低廉。上行流量免费无需运维人员和托管费用阿里云产品内部传输无费用同比计算能力，成本节省1/3 业务请求的波峰需要资源扩容，波谷的时候资源浪费。需要专人维护运行环境和硬件资源，人力成本较高。产品之间联通如果走公网，需要额外支付流量费用。
安全 沙箱运行在阿里云企业级别安全环境里。多用户运行是服务器级别隔离机制。提供多种服务授权和子主账号。 需要另外购买清洗和黑洞设备需要单独实现安全访问机制。

函数计算虽然适用于很多场景，但也不是覆盖全部应用场景的万金油。例如某些业务在一天中没有明显的请求波峰波谷，请求相对平缓，那么使用函数计算成本不见得会节省多少。

Serverless框架作为新兴的技术，目前相应的支持开发工具较少，整体框架还在探索中。另外，函数计算的执行环境是不记录状态的，有些耦合性较强的应用也不太适合用Serverless这种框架。受限于资源大小分配，一些大型的应用程序也不太容易能拆分搬上来。

Xpath

xpath如何取包含多个class属性

但是如果html是

1
div class="test demo"></div><div class="demo test"></div><div class="test demo2"></div>

如果目标 class 不一定是第一个，那么：

//div[contains(concat(‘ ‘, @class, ‘ ‘), ‘demo’)] ##只想选出有demo这个class的对象

取多个class属性值的元素

1
<div class='a b'>test</div>

可以用如下的表达式：

xpath(‘//div[contains(@class,”a”)]’) #它会取得所有class为a的元素

xpath(‘//div[contains(@class,”a”) and contains(@class,”b”)]’) #它会取class同时有a和b的元素

##应对反爬虫措施解决方案

user_agent 伪装和轮换

不同浏览器的不同版本都有不同的user_agent，是浏览器类型的详细信息，也是浏览器提交Http请求的重要头部信息。我们可以在每次请求的时候提供不同的user_agent，绕过网站检测客户端的反爬虫机制。比如说，可以把很多的user_agent放在一个列表中，每次随机选一个用于提交访问请求。有一个提供各种user_agent的网站：

http://www.useragentstring.com/

最近又看到一个专门提供伪装浏览器身份的开源库，名字取得很直白：

fake-useragent

使用代理IP和轮换

检查ip的访问情况是网站的反爬机制最喜欢也最喜欢用的方式。这种时候就可以更换不同的ip地址来爬取内容。当然，你有很多有公网ip地址的主机或者vps是更好的选择，如果没有的话就可以考虑使用代理，让代理服务器去帮你获得网页内容，然后再转发回你的电脑。代理按透明度可以分为透明代理、匿名代理和高度匿名代理:

  • 透明代理：目标网站知道你使用了代理并且知道你的源IP地址，这种代理显然不符合我们这里使用代理的初衷
  • 匿名代理：匿名程度比较低，也就是网站知道你使用了代理，但是并不知道你的源IP地址
  • 高匿代理：这是最保险的方式，目标网站既不知道你使用的代理更不知道你的源IP
    代理的获取方式可以去购买，当然也可以去自己爬取免费的，这里有一个提供免费代理的网站，可以爬下来使用，但是免费的代理通常不够稳定。

设置访问时间间隔

很多网站的反爬虫机制都设置了访问间隔时间，一个IP如果短时间内超过了指定的次数就会进入“冷却CD”，所以除了轮换IP和user_agent
可以设置访问的时间间间隔长一点，比如没抓取一个页面休眠一个随机时间：

1
2
import time，random
time.sleep(random.random()*3)

对称二叉树

image-20200514180949390.png

###思路—分治法

如果满足条件的对称二叉树

其左子树的前序遍历 && 右子树的后序遍历

得到的列表必然完全相反

左子树进行前序遍历: pre_order = [2,3,5,6,4,7,8] 后序遍历：post_order = [8,7,4,6,5,3,2]

pre==post.reverse

###代码

  • 按照总结的二叉树遍历模板
1
2
3
4
5
6
7
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}
  • 分别定义前序和后序遍历的函数
1
2
3
4
5
6
7
def pre_order(self,root,li):    # 二叉树的前序遍历
    if root:
        li.append(root.val)
        self.pre_order(root.left,li)
        self.pre_order(root.right,li)
    elif root == None:
        li.append(None)
1
2
3
4
5
6
7
def post_order(self,root,li):   # 二叉树的后序遍历
    if root:
        self.post_order(root.left,li)
        self.post_order(root.right,li)
        li.append(root.val)
    elif root == None:
        li.append(None)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        pre = []     # 用来存左子树的前序遍历
        post = []     # 用来存右子树的后序遍历
        if root == None:   # 无根节点
            return True
        if root and root.left == None and root.right == None:  # 只有根节点
            return True

        if root and root.left and root.right:
            self.pre_order(root.left, pre)
            self.post_order(root.right, post)
            post.reverse()            # 将后序遍历的列表倒序
            if pre == post:
                return True
            else:
                return False

关键字yield

首先直观上等价于return，其次可看作生成器的一部分，（带有yield的函数，会被解释器视为一个迭代器，返回iterable对象）

实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Fab(object):

    def __init__(self, max):
        self.max = max
        self.n, self.a, self.b = 0, 0, 1

    def __iter__(self):
        return self

    def next(self):
        if self.n < self.max:
            r = self.b
            self.a, self.b = self.b, self.a + self.b
            self.n = self.n + 1
            return r
        raise StopIteration()
  • 判断函数是否为特殊的 generator 函数—isgeneratorfunction

sort()和sorted()

区别介绍

  • sort 是应用在 list 上的方法，针对原list排序无返回值

  • sorted 是内建函数，可对所有可迭代的对象进行排序操作，会返回新的list

内部实现探究

  1. （知乎）python sort 函数采用的排序算法 ：其中一个回答提到了 python 中的 sorted 排序内部实现是 timsort，并没有说 sort 。

  2. （GitHub）python的sorted排序分析 ： 同样只提到了 python 中的 sorted 排序内部实现是 timsort，并没有说 sort （知乎回答的一个链接）。

  3. （CSDN）C++，java,Python的内部实现sort怎么实现的 ：内容提到 python内部的sort采用的是混合（hybrid）排序，规模小的时候采用 binary insertion，规模大的时候采用 sample sort 。

###结论：实现机制—Timsort 时间复杂度O(nlogn) 空间复杂度O（n）

Timsort

Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）的排序算法，由Tim Peters在2002年设计了该算法并在Python中使用（TimSort 是 Python 中 list.sort 的默认实现）。Pyhton自从2.3版以来一直采用Timsort算法排序，现在Java SE7和Android也采用Timsort算法

基本流程

基本工作过程是：

  • 扫描数组，确定其中的单调上升段和严格单调下降段，将严格下降段反转。我们将这样的段称之为run。
  • 定义最小run长度，短于此的run通过插入排序合并为长度高于最小run长度；
  • 反复归并一些相邻run，过程中需要避免归并长度相差很大的run，直至整个排序完成；
  • 如何避免归并长度相差很大run呢， 依次将run压入栈中，若栈顶run X，run Y，run Z 的长度违反了X>Y+Z 或 Y>Z 则Y run与较小长度的run合并，并再次放入栈中。 依据这个法则，能够尽量使得大小相同的run合并，以提高性能。注意Timsort是稳定排序故只有相邻的run才能归并。
  • Merge操作还可以辅之以galloping模型（记录归并时run的界值，如runA完全小于或大于runB直接合并，提升归并效率

总结

timsort是工业级算法，其混用插入排序与归并排序，二分搜索等算法

充分利用待排序数据可能部分有序的事实，并且依据待排序数据内容动态改变排序策略——选择性进行归并以及galloping

Timsort是稳定的算法，当待排序的数组中已经有排序好的数，它的时间复杂度会小于n logn。Timesrot稳定（最坏和平均时间一致），时间复杂度是O（n log n）。在最坏情况下，Timsort算法需要的临时空间是n/2，在最好情况下，它只需要一个很小的临时存储空间

TimSort–python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import time
import random
"""
二分搜索用于插入排序寻找插入位置
"""
def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
插入排序用于生成mini run
"""
def insertion_sort(the_array):
   
    l = len(the_array)
    
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array[pos+1:index+1] = the_array[pos:index]
        the_array[pos] = value
   
    return the_array
"""
归并，将两个有序的list合并成新的有序list
"""
def merge(left, right):
    
    if not left:
        return right
    if not right:
        return left
    l_len = len(left)
    r_len = len(right)
    result = [None]*(l_len+r_len)
    i, j, k= 0,0,0
    while i < l_len and j< r_len:
        if left[i] <= right[j]:
            result[k] = left[i]
            i+=1
        else:
            result[k] = right[j]
            j+=1
        k+=1
    while i<l_len:
        result[k]=left[i];
        k+=1
        i+=1
    while j<r_len:
        result[k]=right[j]
        k+=1
        j+=1
   
    return result
     
    

def timsort(the_array):
    runs = []
    length = len(the_array)
    new_run = [the_array[0]]
    new_run_reverse = False
    # 将the_array拆分成多了(递增或严格递减)list并将严格递减的list反转后存入runs。
    for i in range(1, length):
       
        if len(new_run) == 1:
            if the_array[i] < the_array[i-1]:
                new_run_reverse = True
            else:
                new_run_reverse = False
            new_run.append(the_array[i])
                
        elif new_run_reverse:
            if the_array[i] < the_array[i-1]:
                new_run.append(the_array[i])
            else:
                new_run.reverse()
                runs.append(new_run)
                #print(new_run)
                new_run=[]
                new_run.append(the_array[i])
        else:
            if the_array[i] >= the_array[i-1]:
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                #print(new_run)
                new_run=[]
                new_run.append(the_array[i])
       
        if i == length - 1:
            runs.append(new_run)
            #print(new_run)

    mini_run = 32
    sorted_runs=[]
    cur_run=[]
    # 对runs中的每一项list长度不足mini_run用插入排序进行扩充，存入sorted_runs
    for item in runs:
        if len(cur_run) > mini_run:
            sorted_runs.append(insertion_sort(cur_run))
            cur_run = item
        else:
            cur_run.extend(item)
      
    sorted_runs.append(insertion_sort(cur_run))
    
   
    # 依次将run压入栈中，若栈顶run X，Y，Z。
    # 违反了X>Y+Z 或 Y>Z 则Y与较小长度的run合并，并再次放入栈中。
    # 依据这个法则，能够尽量使得大小相同的run合并，以提高性能。
    # Timsort是稳定排序故只有相邻的run才能归并。
    run_stack = []
    sorted_array = []
    
    for run in sorted_runs:
        run_stack.append(run)
        stop = False
        while len(run_stack) >= 3 and not stop:
            
            X = run_stack[len(run_stack)-1]
            Y = run_stack[len(run_stack)-2]
            Z = run_stack[len(run_stack)-3]
            if (not len(X)>len(Y)+len(Z)) or (not len(Y)>len(Z)):
                run_stack.pop()
                run_stack.pop()
                run_stack.pop()
                if len(X) < len(Z):
                    YX = merge(Y,X)
                    run_stack.append(Z)
                    run_stack.append(YX)
                else:
                    ZY = merge(Z,Y)
                    run_stack.append(ZY)
                    run_stack.append(X)
            else:
                stop =True
            
        
        
    #将栈中剩余的run归并
    for run in run_stack:
        sorted_array = merge(sorted_array, run)
        

    #print(sorted_array)

data = []
for x in range(0,100):
    data.append(random.randint(0,10000))

start = time.process_time()
timsort(data)
end = time.process_time()
print(end-start)

##思路

  • res List[str]：记录当前已被分隔的字符串，初始值为 [s]，未做分隔

  • for 循环 3 次，每次给 res 中所有字符串加一个 ‘.’，多分隔出一个整数，例如 [“2552551135”] 一次循环之后，变成 [“2.552551135”, “25.52551135”, “255.2551135”]，分隔出了一个合法整数

  • 然后在最后面的那串又加 ‘.’，继续分隔，维护好加 ‘.’ 分隔的位置

  • 添加三个 ‘.’ 后，分隔出的前三个整数都已满足条件，只需检验一下分隔出的最后一个整数即可，若满足条件，则四个整数都满足条件

##代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def validInt(self, s):
        if s and int(s) < 256:
            if s[0] != '0' or s == '0':
                return True
        return False
def restoreIpAddresses(self, s: str):
    res = [s]
    for _ in range(3):
        res_now = []
        for si in res:
            last = si.split('.')[-1]
            idx = len(si) - len(last)
            for i in range(len(last)):
                if i > 2:
                    break
                if int(last[:i + 1]) < 256:
                    si_now = si[: idx + i + 1] + '.' + si[idx + i + 1 :]
                    res_now.append(si_now)
                if last[0] == '0':
                    break
        res = res_now

    res_now = []
    for si in res:
        last = si.split('.')[-1]
        if self.validInt(last):
            res_now.append(si)

    return res_now

##方法一：显式中序遍历

###思路与算法

对于二叉搜索树进行中序遍历，得到的值序列是递增有序的；对于两个错误的节点等价于在这个值序列中交换了两个值，破坏了值序列的递增性。那么序列中就会出现两个位置不满足或者一个位置不满足递增的两种情况

###解决方案

  • 中序递归遍历整个树，当 pre 节点值大于当前节点，记录这两个节点。
  • 判断逆序对节点数是2个还是4个，如果是2两个，交换即可，如果是4个，则交换第1个和第4个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def _inorder(root):
            if not root: return
            # 遍历左子树
            _inorder(root.left)
            
            nonlocal pre, nodes
            if pre and pre.val > root.val:  # 记录当前的逆序对
                nodes.append(pre)
                nodes.append(root)
            pre = root
            # 遍历右子树
            _inorder(root.right)

        pre = None
        nodes = []
        _inorder(root)
        if len(nodes) == 2:
            i, j = 0, 1
        elif len(nodes) == 4:
            i, j = 0, 3
        else:
            return
        nodes[i].val, nodes[j].val = nodes[j].val, nodes[i].val
        return

##整体思路

  • 两个树相同，中根遍历肯定相同；中根遍历相同，两个树就一定相同？不一定，比如这种情况，中根遍历都是 [1,2]
1
2
3
输入:      1          1
          /           \
         2             2

  • 如果中根遍历，先根遍历，后根遍历均相同，那肯定是相同的树。但遍历 3 遍，时间复杂度太高。这道题是简单，显然不会这么复杂

  • 中根遍历只记录非空「值」，如果将没有空节点也记录，可以通过判断遍历结果（[1,2,null], [1,null,2]）是否相同来判断两个树是否相同。解法一：通过遍历结果是否相同来判断。

  • 解法二：通过两个数组是否完全相同来判断，其实也是依次判断每一个元素是否相同，如果都相同，则最终结果相同。依次判断每一个节点是否相同，相同为 true，不同为 false，存在 false，则最后结果为 false。

###解法一：通过判断遍历结果是否相同
时间复杂度：O(N)，递归栈的深度为节点的数量（N）
空间复杂度：O(N)，需要一个额外长度为 N 的数组（不考虑叶子节点为 null 的情况）

###代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        arrp,arrq = [],[]
        self.traversal(p,arrp)
        self.traversal(q,arrq)
        return arrp == arrq
def traversal(self, root: TreeNode, arr: List[int]):
    if root == None:
        return
    arr.append(root.val)
    if root.left != None:
        self.traversal(root.left,arr)
    else:
        arr.append(None)
    if root.right != None:
        self.traversal(root.right,arr)
    else:
        arr.append(None)

###解法二：依次判断每一个节点是否相同
时间复杂度：O(N)，递归栈的深度为节点的数量（N）
空间复杂度：O(1)，不需要额外的空间

###代码

1
2
3
4
5
6
7
8
9
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
,