imlch

思路

贪心，基于取极大值和极小值会比不取这些值得到的摆动数组要长(至少也相等)的推论(画图就很直观)，对于上升(可以等于)的连续子序列，其实我们可以只取首尾；同样的下降也进行同样的操作，这样每一步都取最长摆动序列：

如[1,17,5,10,13,15,10,5,16,8]进行上述的操作：

• [1, 17]取首尾得到还是[1, 17]
• [17, 5]取首尾还是[17, 5]
• [5, 10, 13, 15]取首尾是[5, 15]
• [15, 10, 5]取首尾是[15, 5]
• 接下来依次是[5, 16]和[16, 8]
• 所以得到的序列会是[1, 17, 5, 15, 5, 16, 8]
• 观察其中的第3步，其实这里面的5是确定的前面取的，后面的10, 13, 15对于这一段来说取哪个都是上升的，但是为了后面更有可能下降，那么贪心取最大值15是最好的。

代码

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

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # c用来记录前一个差值是下降/上升的，默认0
        n, c, res = len(nums), 0, 1 
        if n < 2:
            return n
        for i in range(1, n):
            x = nums[i] - nums[i - 1]
            # 如果有差值才继续处理
            if x:
                # <0代表有上升下降的交替，=0是初始情况的判断
                if x * c <= 0:
                    res += 1
                c = x
        return res

背景

天池学习赛贷款违约预测

首次参加学习赛的过程在论坛中初识catBoost，希望能通过实践加深印象与理解

catboost 简介

###三大优点

• 自动处理类别型特征（categorical features）。首先对categorical features做一些统计，计算某个类别特征（category）出现的频率，之后加上超参数，生成新的数值型特征（numerical features）
• catboost还使用了组合类别特征，可以利用到特征之间的联系，这极大的丰富了特征维度。
• catboost的基模型采用的是对称树，同时计算leaf-value方式和传统的boosting算法也不一样，传统的boosting算法计算的是平均数，而catboost在这方面做了优化采用了其他的算法，这些改进都能防止模型过拟合。

catboost 实战

首先通过pandas读入数据。

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

import pandas as pd
import datetime
import warnings
warnings.filterwarnings('ignore')
from sklearn.model_selection import StratifiedKFold
#warnings.filterwarnings('ignore')
#%matplotlib inline
from sklearn.metrics import roc_auc_score
## 数据降维处理的
from sklearn.model_selection import train_test_split  
from catboost import CatBoostClassifier
train=pd.read_csv("train.csv")
testA=pd.read_csv("testA.csv")

数据中包含了47种不同特征，而且特征的数据类型各不一样，有数值型（creative_height），布尔型（creative_is_js)等不同类型的特征。

而在catboost中不需要预处理数据，只需要提供，哪些特征属于类别特征，它会自动处理。代码如下所示：

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

sub=testA[['id']].copy()
sub['isDefault']=0
testA=testA.drop(['id','issueDate'],axis=1)
data_x=train.drop(['isDefault','id','issueDate'],axis=1)
data_y=train[['isDefault']].copy()
x, val_x, y, val_y = train_test_split(  
    data_x,  
    data_y,  
    test_size=0.25,  
    random_state=1,  
    stratify=data_y
)  

col=['grade','subGrade','employmentTitle','homeOwnership','verificationStatus','purpose','postCode','regionCode',
     'initialListStatus','applicationType','policyCode']
for i in data_x.columns:
    if i in col:
        data_x[i] = data_x[i].astype('str')
for i in testA.columns:
    if i in col:
        testA[i] = testA[i].astype('str')
model=CatBoostClassifier(
            loss_function="Logloss",
            eval_metric="AUC",
            task_type="CPU",
            learning_rate=0.1,
            iterations=500,
            random_seed=2020,
            od_type="Iter",
            depth=7)

最后就是将数据喂给算法进行训练

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

answers = []
mean_score = 0
n_folds = 5
sk = StratifiedKFold(n_splits=n_folds, shuffle=True, random_state=2019)
for train, test in sk.split(data_x, data_y):
    x_train = data_x.iloc[train]
    y_train = data_y.iloc[train]
    x_test = data_x.iloc[test]
    y_test = data_y.iloc[test]
    clf = model.fit(x_train,y_train, eval_set=(x_test,y_test),verbose=500,cat_features=col)
    yy_pred_valid=clf.predict(x_test)
    print('cat验证的auc:{}'.format(roc_auc_score(y_test, yy_pred_valid)))
    mean_score += roc_auc_score(y_test, yy_pred_valid) / n_folds
    y_pred_valid = clf.predict(testA,prediction_type='Probability')[:,-1]
    answers.append(y_pred_valid)
print('mean valAuc:{}'.format(mean_score))
cat_pre=sum(answers)/n_folds
sub['isDefault']=cat_pre
sub.to_csv('D:/projects/python/test/jupyter/金融预测.csv',index=False)

结语

catboot简单易用且功能强大，减弱了对特征工程的依赖，如果面对需要特别多的前期数据处理和特征数值化的任务，可以很高效锋发挥作用。

​

问题描述

原生的白色主题不适合在晚上长时间使用，尝试更换整个主题或者自定义透明背景等细节

原生的字体也比较小，尝试修改字体类型及大小

解决方案

• 通过修改本地路径的css文件，修改网页样式的原理来完成主题修改
• 不熟悉原生CSS文件架构，可选择使用jupyter thems 这个包来直接安装主题

*可选择主题plotting style*

markdown/equations

pandas dataframes

command palette

grade3 syntax

具体过程

1

pip install jupyterthemes

• 参数说明

  -t 设置主题， -f 设置代码的字体， -nf 设置notebook的字体，具体参数说明
  

• 更换主题

  1	jt -t chesterish

• 恢复默认主题：

  1

  jt -r

• 查看可用主题：

  1

  jt -l

问题描述

在 Hexo 搭建的博客中对文章进行编写，经常会用到一些特殊字符需要转译，比如 -、.、空格、制表符等等，在正常情况下可以使用 \ 进行转译，但是有一些字符无法转译，使用后在执行 hexo server 命令的时候会报错。

报错信息：

Unhandled rejection Template render error: (unknown path) [Line 7, Column 23]
Error: Unable to call worldcount, which is undefined or falsey……

解决方案

报错的原因是，Hexo 编译时发生错误，可能是文章中存在特殊字符，如：{ [ ( ) ] } 等等。如下面这段代码：

在页面中：

1
2

{{ worldcount(post.content) }}
1

在 Markdown 中：

1
2

{{ worldcount(post.content) }}
1

在 Markdown 中使用 \ 无法转译的字符需要使用字符的命名实体或十进制编码，如上面代码中。

注意：需要转义的字符只是文本中的特殊字符，代码块中的特殊字符无需转译或使用转译字符。

常见特殊字符

常用特殊字符转译字符对照表：

常用数学转译字符对照表：

常用希腊字母转译字符对照表：

一、引言

212. 单词搜索 II

难度困难278

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
10

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

Trie树应用广泛， NLP 中一般会用其存储大量的字典字符以用于文本的快速分词；除此之外，典型应用场景还包括大批量文本的：词频统计、字符串查询和模糊匹配（比如关键词的模糊匹配）、字符串排序等任务；（还比如搜索引擎）。由于 Trie 大幅降低了无谓的字符串比较，因此在执行上述任务时，其效率非常的高。

二、Trie 树的简介

Trie 树中文名叫字典树、前缀树等等。这些名字暗示其与字符的处理有关，事实也确实如此，它主要用途就是将字符串（当然也可以不限于字符串）整合成树形。

这个树里面每一个方块代表一个节点，其中 ”Root” 表示根节点，不代表任何字符；紫色代表分支节点；绿色代表叶子节点。除根节点外每一个节点都只包含一个字符。从根节点到叶子节点，路径上经过的字符连接起来，构成一个词。而叶子节点内的数字代表该词在字典树中所处的链路（字典中有多少个词就有多少条链路），具有共同前缀的链路称为串。除此之外， 还需特别强调 Trie 树的以下几个特点：

1. 具有相同前缀的词必须位于同一个串内；例如“清华”、“清新”两个词都有“清”这个前缀，那么在 Trie 树上只需构建一个“清”节点，“华”和“新”节点共用一个父节点即可，如此两个词便只需三个节点便可存储，这在一定程度上减少了字典的存储空间。

2. Trie 树中的词只可共用前缀，不可共用词的其他部分；例如“中华”、“华人”这两个词虽然前一个词的后缀是后一个词的前缀，但在树形上必须是独立的两条链路，而不可以通过首尾交接构建这两个词，这也说明 Trie 树仅能依靠公共前缀压缩字典的存储空间，并不能共享词中的所有相同的字符；

3. Trie 树中任何一个完整的词，都必须是从根节点开始至叶子节点结束，这意味着对一个词进行检索也必须从根节点开始，至叶子节点才算结束。

4. Trie树特性：

   1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。

   2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

   3）每个节点的所有子节点包含的字符都不相同。

   4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。

   5）插入查找的复杂度为O(n)，n为字符串长度。

三、Trie 树的时间复杂度

在 Trie 树中搜索一个字符串，会从根节点出发，沿着某条链路向下逐字比对字符串的每个字符，直到抵达底部的叶子节点才能确认字符串为该词，这种检索方式具有以下两个优点：

基本思想（以字母树为例）：

• 1、插入过程
  对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
• 2、查询过程
  同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

这两个优点相结合可以最大限度地减少无谓的字符比较，使得搜索的时间复杂度理论上仅与检索词的长度有关：O(K)，其中 K 为检索词的长度。

四、Trie 树的缺点

综上可知， Trie 树主要是利用词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历，从而达到高效检索的目的。这一思想有赖于字符在词中的前后位置能够得到表达，因此其设计哲学是典型的“以信息换时间”，当然，这种优势同样是需要付出代价的：

1. 由于结构需要记录更多的信息，因此 Trie 树的实现稍显复杂。好在这点在大多数情况下并非不可接受。
2. Trie 型词典不仅需要记录词，还需要记录字符之间、词之间的相关信息，因此字典构建时必须对每个词和字逐一进行处理，而这无疑会减慢词典的构建速度。对于强调实时更新的词典而言，这点可能是致命的，尤其是采用双数组实现的 Trie 树，更新词典很大概率会造成词典的全部重构，词典构建过程中还需处理各种冲突，因此重构的时间非常长

五、Trie 树的几种实现

5.1、Array Trie 树

很多文章里将这种实现称为“标准 Trie 树”，但其实它只是 Trie 众多实现中的一种而已，由于这种实现结构简单，检索效率很好，作为讲解示例很不错，因此特地改称其为“经典 Trie 树”，这里引用一下别人家的示例图[2]：

abc、d、da、dda 四个字符串构成的 Trie 树，如果是字符串会在节点的尾部进行标记。没有后续字符的 branch 分支指向NULL

如上图，这种实现的特点是：每个节点都由指针数组存储，每个节点的所有子节点都位于一个数组之中，每个数组都是完全一样的。对于英文而言，每个数组有27个指针，其中一个作为词的终结符，另外 26 个依次代表字母表中的一个字母，对应指针指向下一个状态，若没有后续字符则指向NULL。由于数组取词的复杂度为O(1)

5.2、List Trie 树

由于数组的长度是不可变，因此经典 Trie 树存在着明显的空间浪费。但是如果将每一层都换成可变数组（不同语言对这种数据结构称呼不同，比如在 Python 中为List，C# 称为 LinkedList）来存储节点（见下图[3]），每层可以根据节点的数量动态调整数组的长度，就可以避免大量的空间浪费。下图就是这种实现的图例[3]：

5.3、Hash Trie 树

可变数组取词速度太慢，用一组键值对字典类型代替可变数组：其中每个节点包含一组 Key-Value，每个 Key 对应该节点下的一个子节点字符，value 则指向相应的后一个状态。这种方式可以有效的减少空间浪费，同时由于键值对本质上就是一个哈希实现，因此理论上其查词效率也很高（理想状态下取词复杂度为O(1)

5.4、Double-array Trie 树

双数组 Trie 树是目前 Trie 树各种实现中性能和存储空间均达到很好效果的实现

Pwn是一个黑客语法的俚语词 ，是指攻破设备或者系统 。发音类似“砰”，对黑客而言，这就是成功实施黑客攻击的声音——砰的一声，被“黑”的电脑或手机就被你操纵。以上是从百度百科上面抄的简介，而我个人理解的话，应该就是向目标发送特定的数据，使得其执行本来不会执行的代码，前段时间爆发的永恒之蓝等病毒其实也算得上是pwn的一种。

pwnable.kr

pwnable.tw

pwn介绍

CTF pwn中的目标是拿到flag，一般是在linux平台下通过二进制/系统调用等方式编写漏洞利用脚本exp来获取对方服务器的shell，然后get到flag

简介

长亭安全：https://zhuanlan.zhihu.com/p/25816426

前置技能

• 汇编语言，函数调用约定，大小端，函数栈帧
• python语言，gdb调试，IDA pro分析
• linux相关：32位与64位，各类防护机制（NX，ASLR，Canary，Relro），ELF文件格式，系统调用，shell命令
• 编译，链接，装载，执行

常见漏洞简介

• 缓冲区溢出(Buffer overflow)
• 栈溢出，堆溢出，bss溢出等
• 整数溢出(Integer overflow)
• 整数的加减乘法
• 有符号与无符号的转换
• 整数溢出一般可以转换成其它漏洞
• 格式化字符串(Format string)
• printf(s)，sprint f(s)，fprintf(s)可以修改地址也可以用来leak信息
• 使用后释放(Use-after-free)
• 释放掉的内存可能会被重新分配，释放后使用会导致重新分配的内存被旧的使用所改写
• Double free是一种特殊的UAF

工具

• IDA
• pro
• gdb
• pwntools
• zio
• peda
• readelf
• ropgadget
• string
• objdump

利用方法

• 注入代码

• • 溢出后在栈上执行代码

• 伪造函数

• • 修改.got.plt地址，替换掉正常函数
  • 布置gadget将ret地址指向libc中的其它函数

学习网站

如何开始你的CTF之旅

PWN总结

p4-team

uaf

ddaa

二进制漏洞学习

sploitfun

CTF Writeup Github

pwnable.kr

pwnable.tw

ROPemporium

学习资料

《有趣的二进制》
《深入理解计算机系统》
《程序员的自我修养》
《深入理解Linux内核》

GRID SEARCH 网格搜索（KNN算法）寻找最合适的超参数

KNN算法的超参数：

1

from sklearn.neighbors import KNeighborsClassifier

KNeighborsClassifier 的超参数：

1. n_neighbors : 表示选择距离最近的K个点来投票的数量。

1

knn_clf = KNeighborsClassifier(n_neighbors=3)

2.weights ：表示最近的K个点中，是否考虑距离的权重；

weights = uniform （默认）表示不考虑权重

weighs = distance 表示考虑距离的权重

1

knn_clf = KNeighborsClassifier(n_neighbors=3 , weights = 'distance')

3. p ：表示选择的距离类型；只有当 weights = ‘distance’ 时，p才有意义；

p = 1 表示选择曼哈顿距离

p = 2 表示选择欧拉距离（默认）

p >=3 表示选择其他距离

1

knn_clf = KNeighborsClassifier(n_neighbors=3 , weights = 'distance' , p = 1)

4. KNN算法还有其他超参数，暂时不考虑

具体可以参考：http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

GRID SEARCH 网格搜索

1. 创建KNN实例，设置需要搜寻的超参数格式，用字典的形式表示

*字典的键 表示参数的名称 ； 对应的值放在列表中，表示需要搜寻的参数值*

2. 用GridSearchCV 来网格搜索

3. fit 结束后

调用 .best_estimator_ ，可以返回最佳的分类器

调用 .best_score_ ， 可以返回最佳分类器对应的准确度

调用 .best_params_ ，可以返回最佳分类器对应的参数

4. GridsearchCV 中的准确度（score）采用的是交叉验证（Cross-validation）得来的分数；不是通过 test数据集验证；

其他超参数：N_JOBS 和 VERBOSE

n_jobs 参数，表示为计算机分配几个核来并行执行搜索 ， n_jobs = -1 表示计算机有几个核就分配几个；

verbose 参数，表示在搜索的过程中 输出过程， 参数为整数，越大表示输出的内容月详细

1
2
3
4
5
6
7
8
9
10
11

%%time

grid_search = GridSearchCV(knn_clf,param_grid,n_jobs = -1,verbose=4)


grid_search.fit(X_train,y_train)
Fitting 3 folds for each of 60 candidates, totalling 180 fits
[Parallel(n_jobs=-1)]: Done  17 tasks      | elapsed:   10.8s
[Parallel(n_jobs=-1)]: Done  90 tasks      | elapsed:   35.6s
Wall time: 1min 14s
[Parallel(n_jobs=-1)]: Done 180 out of 180 | elapsed:  1.2min finished

P/NP/NP_complete/NP_hard问题

机器学习面临的问题通常是NP-hard甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意味着我们构造性地证明了“P=NP”，因此，只要相信“P≠NP”，过拟合就不可避免。

###定义问题

P问题、NP问题、NPC问题和NP hard问题，其中P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系：P=NP?

• NP类问题，就是不知道这个问题是不是存在多项式时间内的算法，所以叫non-deterministic非确定性，但是我们可以在多项式时间内验证并得出这个问题的一个正确解（TSP问题）

• P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内得到验证

• NP-complete问题是如果所有NP问题可在多项式时间内归约成某个NP问题，则该NP问题称为NP完全问题。

  同时满足两个条件：（1）该问题是一个NP问题；（2）所有NP问题可以归约为该问题。所以NPC问题既是NP问题的子集，又是NP hard问题的子集，因此NPC问题是NP问题和NP hard问题的交集。

  可满足性问题、哈密顿圈问题、巡回售货员问题、最长路径问题都是NPC问题。 装箱(bin packing)问题、背包(knapsack)问题、图的着色(graph coloring)问题以及团(clique)的问题都是著名的NPC问题。

• NP_Hard指问题S，满足任何NP问题都可以在多项式级时间复杂度内被归约为S（归约：即被归约的NP问题与S的答案相同，当解决了S时，就同时解决了所有的NP问题）。可以理解为，这是一个比所有NP问题都难的问题。

  （NP hard问题不一定是NP问题，有可能是不可判定问题。这时候说明原问题也是不可判定的）

###相互关系

NP hard问题和NPC问题都要求能够在多项式时间内规约成另外一个问题。这里规约的意思是将一个特殊问题一般化，即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题，这个问题具有最高的计算复杂度，如果这个最一般的问题也能有多项式时间求解算法，那么那些特殊的原问题也能有多项式时间求解算法。

• 假设 N P = P 猜想不成立，那么计算复杂度的相对关系为（按照由低到高）：P < N P < N P C < NPhard
• 假设 N P = P 猜想成立，那么说明所有存在多项式时间验证算法的问题都存在多项式时间求解算法，而NPC本身属于NP问题，因此NPC也存在多项式时间求解算法，所以NPC = P，所以 P = N P = NPC ，属于NP hard问题的一个子集。

正是NPC问题的存在，使人们相信P≠NP
NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决

###其他理解

• 计算机处理的输入常常不是几十个或几千个，而是几百万个的时候，时间复杂度为O ( n 2 ) O(n^2)O(n2)和O ( e n ) O(e^n)O(e**n)的算法，所需的运行次数简直是天壤之别，O ( e n ) O(e^n)O(e**n)指数级的可能运行好几天都没法完成任务，所以才要研究一个问题是否存在多项式时间算法。
• 而我们也只在乎一个问题是否存在多项式算法，因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的

• 最开始的时候，大家不知道NP的定义是存在所谓 最难的 这么一个东西的，各类问题没有固定的比较标准。直到一个叫Cook的数学家做了点CS的工作，他证明了任何一个NP形式的问题都可以转换成 3SAT （某个NP问题）。3SAT 就是说有n个variable，m个clause，每个clause都是某三个variable 或（|） 在一起， 最后再把所有的clause 和（&） 在一起， 问题是：“有没有一种对于这n个variable的取值可以让整个boolean formula的值为true？” 3SAT 这个问题的优点在于它非常的直观清晰。最开始这篇文章没得到什么重视，直到一个非常出名的计算机科学家Levin看到了这篇文章，突然意识到如果这么多问题都等价于 3SAT 问题，那这就很好地揭示了为什么之前那么多算法问题都找不到快速的（多项式级）算法，因为都和3SAT一样难嘛；另外可以用 3SAT 作为对各种计算问题的分界线，那以后只要发现是NP-complete的问题，大家就不用对于每个问题找解法了。由此衍生了很多对于complexity class的研究，而cook-levin这种把NP问题化为3SAT的思想一次又一次起到了至关重要的作用。

PS : 时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

##LeetCode485

方法一：一次遍历

算法：

用一个计数器 count 记录 1 的数量，另一个计数器 maxCount 记录当前最大的 1 的数量。
遇到 1 时，count 加一。遇到 0 时：将 count 与 maxCount 比较，maxCoiunt 记录较大值。
将 count 设为 0。 返回 max（Count，maxcount)。

PS :当然也可以在遇到1时候就进行maxcount比较，（从测试用例耗时来看）和前面相比耗时会多一些 ，考虑原因可能是题目是找最大连续1的个数，用例中1比0多的用例占多数，遇到0时再max比较，比较次数会少一些

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

def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
       res=0
       count=0
       for i in range(len(nums)):
           if nums[i]:
               count+=1
               #res=max(res,count)
           else:
               count=0
               res=max(res,count)
       #return res
   	retuen max(res,count)

复杂度分析

时间复杂度：O(N) N是数组的长度。
空间复杂度：O(1) count 和 maxCount。
方法二：
使用 splits 函数在 0 处分割将数组转换成字符串。在获取子串的最大长度就是最大连续 1 的长度。

1

return max(map(len, ''.join(map(str, nums)).split('0'))

方法三：

看到评论区有其他语言的双指针法，改写python

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

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        count =0
        start = 0
        for i in range(len(nums)):
            if nums[i]==1:
                start =i
                break
        curstart = start 
        maxcount = 0
        count =0
        for i in range(start, len(nums)):
            if nums[i]==1:
                count+=1
                if count>maxcount:
                    maxcount = count
            else:
                curstart=i+1
                count = 0
        return maxcount

如果使用普通的快排划分，虽然时间复杂度是O(n)，空间复杂度是O(1)。

但是仍然不是最优解。因为普通的快排划分需要对数组进行两次扫描(第一次以2为中心划分，第二次以1为中心划分)。

题目要求的最优是对数组进行一次扫描。

怎么做呢？

设置两个变量r1,r2，含义是r1,左边(包含r1)的变量值都小于1，r2左边(包含r2)的变量值都小于2。

那么初始时他俩都是-1(实际上是左边界-1)，代表他俩所包裹的范围是空。

假设现在有数组nums = [0,0,1,1,2,0,0],r1 = 1,r2 = 3。下一个数组索引i是5，也就是要处理0，这个数是小于2的。

因此r2+1，代表区间扩大，把nums[i]和nums[r2]交换。此时维持了r2左侧的数都是小于2的这个性质。

交换完之后，这个小于2的数存放在了nums[r2]，但是这个nums[r2]仍然有可能小于1，若是小于1，那么

应该把r1+1，代表区间扩大，然后把nums[r1]和nums[r2]交换，这样才能维持r1左侧的数小于1的这个性质。

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

def sortColors(self, nums: List[int]) -> None:
        def swap(nums,i,j):
            temp=nums[i]
            nums[i]=nums[j]
            nums[j]=temp
        r1,r2=-1,-1
        for i in range (len(nums)):
            if nums[i]<2:
                r2+=1
                swap(nums,i,r2)
                if nums[r2]<1:
                    r1+=1
                    swap(nums,r1,r2)

思路

1
2

[9,3,15,20,7]
[9,15,7,20,3]

• 1.用L表示左子树，P代表根，R代表右子树
• 2.中序序列可表示为 LPR, 后序序列可表示为 LRP
• 3.后序序列的最后一个元素是二叉树的根，如3
• 4.根据根的值可以把中序序列分为两部分[9]和[3,15,20, 7]
• 5.中序两部分元素个数分别为1，4
• 6.根据中序元素个数把后续分为两部分[9]和[15, 7, 20, 3]
• 7.用中序和后序对应的部分分别创建树的左子树和右子树

代码

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

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        
        def helper(il, ir, pl, pr):
            if (il == ir or pl == pr):
                return None
        
            root = TreeNode(postorder[pr-1])
            inRootPos = inorder.index(root.val, il, ir)
            rightSize = ir - inRootPos
            
            root.right = helper(inRootPos + 1, ir, pr - rightSize, pr - 1)
            root.left = helper(il, inRootPos, pl, pr - rightSize)
            return root
            
        return helper(0, len(inorder), 0, len(postorder))