题目描述

给你一个01字符串，定义答案=该串中最长的连续1的长度，现在你有至多K次机会，每次机会可以将串中的某个0改成1，现在问最大的可能答案

输入描述:

1
2
3
4
5
6

输入第一行两个整数N,K，表示字符串长度和机会次数

第二行输入N个整数，表示该字符串的元素

( 1 <= N <= 300000
, 0 <= K <= N )

输出描述:

1

输出一行表示答案

输入例子1:

1
2

10 2 
1 0 0 1 0 1 0 1 0 1

输出例子1:

1

5

解题思路

​ 首先应该分几种情况进行分类讨论：

1.当K>N时，输出应该直接为K

2.当K<N，如果K等于0，结果直接为最长连续1子串长度

​ 如果K不等于0，那么需要进行动态滑动窗口实验

滑动窗口实验思路为：

​ 1.首先计算不进行替换时，最长连续1子串长度，即为max

​ 2.设置初始值

​ 滑动窗口大小初始值 slide = max+K

​ 滑动窗口最大和初始值 slide_sum = max

​ 3.使用当前滑动窗口大小进行扫描数据，看是都存在一个滑动窗口内的和超过当前滑动窗口最大和

​ 如果有，那么说明存在更大的连续子串，因此将silde和silde_sum都加1(在初始值时已经设置了相当于K个空位，如果值大于silde_sum,说明空格还没用完，如果等于说明空格用完了，但是还可能存在更大的连续1，因此只有当值小于silde_sum才能保证是最大的连续1串）

​ 如果没有，那么说明silde-1为最大窗口，也就是最长全1串

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

# 10 2
# 1 0 0 1 0 1 0 1 0 1


n,k = map(int,input().split())

nums = list(map(int,input().split()))

#判断新的滑动窗口是不是存在和大于等于原来的最大和
def get_maxsum(silde,nums,max_sum):

    end = silde
    start = 0
    while end<len(nums):
        new_max_sum = sum(nums[start:end])
        if new_max_sum>=max_sum:
            return True

        start += 1
        end+=1

    return False


if k>n:
    print(n)
else:
    max_len = 0
    i =0
    tmp_len = 0
    while i<n:
        if nums[i]==1:
            tmp_len +=1
        else:
            tmp_len = 0


        max_len = max(max_len,tmp_len)
        i+=1

    if max_len+k>=n:
        print(n)
    else:
        flag = True
        silde = max_len + k
        max_sum = max_len
        while flag:
            if get_maxsum(silde,nums,max_sum):
                silde += 1
                max_sum+=1
            else:
                flag = False
    print(silde-1)

​ 常见的降维技术只要分为PCA、LDA和t-sne三种，下面我们将具体介绍这三种降维技术以及适用范围

1.PCA

2.LDA

3.t-sne

​ t-sne是在NLP词切入可视化降维的最佳选择，因为它具有保存向量之间相对距离的特性，能有效地保存线性子结构和关系，可以很好的表达不同的单词的在当前训练的词向量上是否相似。

​ 核心特性: 会保存向量之间的相对距离

wordcloud是一种NLP中常用的可视化工具，主要用途是可视化展示文本中各个词出现的频率多少，将出现频率多的使用更大的字体进行展示。

基本用法

1
2
3
4
5
6
7

import wordcloud
with open("./type1.txt","r") as f:
    type1 = f.read()
  
w = wordcloud.WordCloud()
w.generate(type1)
w.to_file("type1.png")

wordcloud内部处理流程：

​ 1 、分隔：以空格分隔单词

​ 2、统计 ：单词出现的次数并过滤

​ 3、字体：根据统计搭配相应的字号

​ 4 、布局

常用参数

​

1.清洗

​ 主要包括清除掉无关内容和区分出各个部分。

段落的首尾单独区分：这里比较常见的一种却分时将段落的首尾单独区分出来，因为首尾句一般都是更加具有代表性的句子

2.标准化

​ 主要包含了字母小写化和标点符号替换两个步骤

1
2
3
4
5
6

#字母小写化
str.lower()

#标点符号替换为空格
import re
text = re.sub(r"a-zA-Z0-9"," ")

3.标记化(分词)

​ 标记化是指将目标切分成无法再分符号，一般主要指分词，一般的处理中都会将句子按照” “进行分词。

1
2
3
4
5
6
7
8

#自写原始分词，进行前面的标准化以后进行
words = text.split()

#使用nltk进行分词,分词会比上面的更加准确，根据标点符号的不同位置进行不同种处理，例如Dr. 中的.不会被处理掉
from nltk.tokenize import word_tokenize
sentence = word_tokenize(text)
words = word_tokenize(sentence)
#nltk提供了多种token方式，包括正则表达式等，按需选择

4.删除停用词

​ 删除停用词是指删除掉哪些去掉哪些和当前任务判断关系不大的词，对于设计到的语料没有具体领域时，可以使用英文常用停用词，其中包括800多个英文的常见停用词。

​ 英文常见停用词标准表

在特定领域时，最好使用专门针对于该领域的停用词表，因为在一个问题中的停用词可能会在另一个问题中肯能就是关键词

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

#去除停用词
def get_stopword(path):
  """
      获取停用词表
      return list
  """
  with open(path) as f:
    stopword = f.read()
  stopword_list = stopword.splitlines()

  return stopword_list

stopwords = get_stopword(path)
words = [word for word in words if word not in stopwords]

5.词性标注

​ 用于标注句子中各个单词分别属于什么词性，更加有助于理解句子的含义，另一方面，词性标注更加有利于后续处理。

常见的一种利用词性标注的后续处理步骤就是直接去掉非名词的部分，因为在一个句子中，名词在很大程度就可以表现两个句子的相似度。

1
2
3
4

#使用nltk进行词性标注
from nltk import pos_tag
sentence = word_tokenize("this is a dog")   #分词
pos = pos_tag(sentence)   #标注

6.命名实体识别

​ 命名实体识别指的是识别

​ 条件：命名实体识别首先要完成词性标注

​ 应用：对新闻文章进行简历索引和搜索

实践性能并不是一直都很好，但对大型语料库进行实验确实有效

1
2
3
4

from nltk import pos_tag,ne_chunk
from nltk.tokenize import word_tokenize

ne_chunk(pos_tag(word_tokenize("I live in Beijing University")))

7.词干化和词型还原

​ 词干提取是指将词还原成词干或词根的过程

​ 方式：利用简单的搜索和替换样式规则，例如去除结尾的s、ing，将结尾的ies变为y等规则

​ 作用：有助于降低复杂度，同时保留次所含的意义本质

还原的词干不一定非常准确，但是只要这个词的所有形式全部都转化成同一个词干就可以了，因为他们都有共同的含义

1
2

from nltk.stem.porter import PorterStemmer
stemmed = [PoeterStemmer().stem(w) for w in words]

​ 词型还原是将词还原成标准化形式的另一种技术，利用字典的方式将一个词的不同形式映射到其词根

​ 方式：字典

​ 优点:可以将较大的词型变化很大的正确还原到词根

1
2
3

from nltk.stem.wordnet import WordNetLemmater

lemmed = [WordNetLemmater.lemmative(w) for w in words]

​ 这里我们发现只有ones被还原成了one，其他词并没有找到词的原型，这是因为词型转化是针对词型进行的，只会转化指定词型的词，默认只转换名词，因此上面只有ones被转换了，下面我们来指定转换动词：

1
2
3

from nltk.stem.wordnet import WordNetLemmater

lemmed = [WordNetLemmater.lemmative(w) for w in words]

8.向量化

​ 向量化是将提取好的token转化成向量表示，准备输入到模型中。常见的方式包括词袋模型、tf-idf、Word2vec、doc2vec等

9. 分类模型或聚类模型

​ 根据实际情况选用合适的分类模型，聚类模型。

注意:上面的处理流程并不是全部都一定要进行,可以根据实际情况进行选择,例如在下一篇文章情感分类中,只是使用了标准化、去停用词、词干提取、向量化、分类等步骤

简介

​ GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，在传统机器学习算法中，GBDT算的上TOP3的算法。想要理解GBDT的真正意义，那就必须理解GBDT中的Gradient Boosting 和Decision Tree分别是什么？

分类树和回归树

1.分类树

​ 分类树使用信息增益或增益比率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。

​ 以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1)，按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

2.回归树

​ 回归树使用最大均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。

​ 回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即(每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

Decision Tree：CART回归树

​ GBDT使用的决策树都是CART数回归树，无论是处理回归问题还是二分类以及多分类。

为什么不用CART分类树呢？

​ 因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。

​ CART回归树的评价指标：平方误差

为什么CART回归时的评价指标不再使用Gini、熵等不纯度指标？

​ 对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

Graident Boosting:梯度提升树

​ 梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树

提升树 Boosting Tree

​ 提升树就是通过不断建立树来不断拟合前一个问题的残差来不断接近目标。

​ 先来个通俗理解：假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。

​ 当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，Friedman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。

Graident Boosting:梯度提升树

​ 核心：利用损失函数的负梯度作为提升树算法中的残差的近似值。

下面我们来看一下负梯度具体的样子，第t轮的第i个样本的损失函数的负梯度为：

那么对于分类问题呢？二分类和多分类的损失函数都是logloss，下面以回归问题为例对GBDT算法进行讲解。

GBDT

常见问题：

1.GBDT和Xgboost的区别？

1.损失函数上 在GBDT的损失函数上XGboost加入了正则化项

2.优化方法上 GBDT在优化上只使用一阶导数的信息，而XGBoost则对代价函数进行了二阶的展开。

3.基分类器的支持上 GBDT只支持CART数作为基分类器，XGBoost在其基础上加入了线性分类器

4.Xgboost加入了shrinkage策略。在完成一次迭代后会将叶子节点的权值乘以该系数削弱了每棵树的影响，使后面的数拥有更大的学习空间

5.列抽样 借鉴了随机森林的做法，支持列抽样，不仅能防止过拟合还能减少计算

6.缺失值自动处理 对于有缺失值的样本，XGBoost可以自动学习出分裂方向

7.计算特征增益时并行 预先对特征值进行排序，保存成block结构，后面的迭代重复使用这个结构

2.lightgbm和Xgboost的区别在哪里？

​ lightgbm基本原理和Xgboost一样，在框架上做了一些优化

1.xgboost采用的level-wise的分裂策略，而lightgbm采用的是leaf-wise的策略，区别是xgboost对每一层节点做无差别的分裂，可能有些节点的信息增益非常小，对结果影响不大，但是依然进行分裂；leaf-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂。明显leaf-wise更容易过拟合，陷入高度较高的深度中，因此lightgbm更应该注意对深度进行限制

2.lightgbm使用histgram的决策树算法，而xgboost使用exact算法，hostgram算法在内存和计算代价上都有不小的优势

3.lightgbm采用直方图加速计算

4.并行化。

​ a.特征并行化

​ 一般的特征并行化都并行化都采用将数据进行垂直切分，然后分割后的数据分散到各个worker，各个worker计算器拥有的数据上计算 best split point，然后汇总得到最优切点。这种方式在数据量很大的时候效率提升有限

​ lightgbm采用直接将全量数据分散到每个worker，然因此最优的特征分裂结果不需要传输到其他worker中，只需要将最优特征以及分裂点告诉其他worker，worker随后本地自己进行处理。

​ b.数据并行化

​ 传统的数据并行算法，首先水平切分数据集，每个worker基于数据集构建局部特征直方图（Histogram），归并所有局部的特征直方图，得到全局直方图，找到最优分裂信息，进行数据分裂。

​ LightGBM算法使用Reduce Scatter并行算子归并来自不同worker的不同特征子集的直方图，然后在局部归并的直方图中找到最优局部分裂信息，最终同步找到最优的分裂信息。

​ 除此之外，LightGBM使用直方图减法加快训练速度。我们只需要对其中一个子节点进行数据传输，另一个子节点可以通过histogram subtraction得到。

参考文献：https://blog.csdn.net/zpalyq110/article/details/79527653

​

​ 思路：这道题讲道理如果起点终点没有那么大就很简单了，直接使用字典进行存储，然后选择value最大的那个值即可。而这道题目中明显直接使用上面的思路是行不通了，因此这题使用了一种比较巧的方式，

​ 先将各个列车的起点终点分别编码为(站点,编号)，起点编号为-1，终点编号为0，然后从小到大对元组进行排序，然后便利元组列表，如果是终点，那么将维护数+1，如果是起点，那么代表到这里已经有一辆车不再需要维护了，同时记录最大的维护值，便利完全部列表最大的维护值即为结果

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

n = int(input())
train = []
t = 0
ans = 0


for i in range(n):
	l = list(map(int,input().split()))
  train.append((l[0],1))
  train.append((l[1],-1))

train.sort()   #这里是关键点，sort函数将对元组进行排序

for i in train:
  if i[1]==0:
    t+=1
  else:
    t-=1
    ans = max(ans,t)
pritn(ans)

上式中的sort函数对元素为元祖的列表来进行排序，默认规则是先使用元组的第一个元素进行排序，当第一个元素值相同时再使用第二个元素进行排序，下面是一个例子：

1
2
3
4
5

l = [[1,1],[2,1],[2,-1],[1,-1]]
l.sort()

output:
	[[1, -1], [1, 1], [2, -1], [2, 1]]

在这个问题中使用sort进行排序后，表示由于同一个车站的负值被排在前面，每次先减去1，也就是前一个车一这里为起点，不需要再使用维护。

之前还遇到过好多类似的问题，其实都可以采用这种类似的思路来减少内存占用，比如之前360笔试中遇到过的找

执行顺序：类中同时出现new()和init()时，先调用new()，再调用init()

python中__new_和\_init__的区别

1.用法不同：

​ __new__()用于创建实例，所以该方法是在实例创建之前被调用，它是类级别的方法，是个静态方法；

​ __init__() 用于初始化实例，所以该方法是在实例对象创建后被调用，它是实例级别的方法，用于设置对象属性的一些初始值

​ 注：由此可知，__new__()在__init__() 之前被调用。如果__new__() 创建的是当前类的实例，会自动调用__init__()函数，通过return调用的__new__()的参数cls来保证是当前类实例，如果是其他类的类名，那么创建返回的是其他类实例，就不会调用当前类的__init__()函数

2.传入参数不同：

​ __new__()至少有一个参数cls，代表当前类，此参数在实例化时由Python解释器自动识别；

​ __init__()至少有一个参数self，就是这个__new__()返回的实例，__init__()在__new__()的基础上完成一些初始化的操作。

3.返回值不同：

​ __new__()必须有返回值，返回实例对象；

　__init__()不需要返回值。

__new__的两种常见用法

1.继承不可变的类

​ __new__()方法主要用于继承一些不可变的class，比如int, str, tuple， 提供一个自定义这些类的实例化过程的途径，一般通过重载__new__()方法来实现

1
2
3
4
5
6
7
8

class PostiveInterger(int):
	def __new__(cls,value):
    return super(PostiveInterger,cls).__new__(cls,abs(value))
a = PostiveInterger(-10)
print(a)

output:
  10

2.实现单例模式

​ 可以用来实现单例模式，也就是使每次实例化时只返回同一个实例对象。

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

class Singleobject(object):
  def __new__(cls):
    if not cls.instance:
      cls.instance = super(Singleobject,cls).new(cls)
    return cls.instance

object1 = Singleobject()
object2 = Singleobject()

object1.attr = 'value1'

print(object1.attr,object2.attr)
print(object1 is object2)

output:
  value1,value1
  True

​ 最近在做各大场笔试题的过程中，发现排列组合在笔试中是一个经常出现的内容，由于读研后就在没有接触过，忘得已经差不多了，大的都不是很好，因此决定写一篇博客来重新复习一下相关知识，下面开始进行总结。

排列组合

1.排列

​ n个元素中取m个元素按照一定的书序排成一排，用$A_n^m$表示。

计算公式：

​ $A_n^m = n(n-1)(n-2)…(n-m+1)​$

2.组合

​ n个元素中取m个不同的元素(不关心顺序)

计算公式：

​ $C_n^m = A_n^m/A_m^m = \frac{n(n-1)(n-2)…(n-m+1)}{m(m-1)(m-2)…1}$

常用技巧

1.捆绑法

​ 要求几个元素相邻时，可以将它们作为一个整体在进行排列

2.差空法

​ 要求元素不相邻时，如ABCDEF排成一排，要求AB不相邻，则可以把CDEF先排好，把AB插进CDEF产生的5个空中就好

3.插板法

​ 要求n个元素分成m个组，每个组必须要有一个元素时，可以在n个元素中产生的n-1个空中插m-1个板子

4.留一法

​ 排列问题中，有元素的顺序已定，如alibaba全排列产生多少个字符串，7个元素中a重复3次，b重复两次，则结果为元素全排除以重复元素的全排

常见问题

环形排列问题：

堆相关知识

​ 堆是一种特殊的完全二叉树，其父节点的值都比子节点的大(大根堆)，

注意：堆的孩子节点左右无大小关系

相关知识：

完全二叉树

​ 性质：1.完全二叉树的深度为logn

​ 2.最后一个非叶子节点为n//2

​ 3.一个编号为x的节点父节点的编号为x//2

​ 4.一个编号为x的左孩子节点为2*x

​ 完全二叉树一般都存储在数组中，但是由于二叉树节点的序号是从1开始的，数组索引是从0开始的，所以需要将恰其全部向后移动一位，将索引为0的位空出来，从1开始计数，但是在python中数组因为没有appendleft方法，因此一般采用colllections中的deque链表类来进行存储(因为其有appendleft方法，直接在首位添加空位)

1
2
3

from collections import deque
L = deque([50, 16, 30, 10, 60,  90,  2, 80, 70])
L.appendleft(0)

​

堆操作

​ 性质：1.插入新元素的时间复杂度为logn，比较次数就是完全二叉树的深度

插入元素

​ 直接将新元素插入到末尾，再根据情况判断新元素是否需要上移，直到满足堆的特性为止。如果堆的大小为N（即有N个元素），那么插入一个新元素所需要的时间也是O(logN)。

​ 下面以在小根堆中插入新节点为例：

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

heap.append(i)

def insert_heapq(i):
	flag = 0   #标志是否还需要进行向上调整
  if i==1:
    return 
  while i!=1 and flag==0:
    if heap[i]<heap[i//2]:
      heap[i],heap[i//2] = heap[i//2],heap[i]
      
   	else:
      flag = 1
   	i = i//2

建立堆

​ 建立堆最自然的思路就是从空的堆开始不断向堆中添加元素，直到所有数据都被插入堆中，此时由于插入每个元素的时间复杂度为O(logi)，所以插入全部数据的时间复杂度为O(nlogn)

​ 而真正的堆建立往往采取另外一种更加高效的时间复杂度为O(n)的方法来进行，即直接先将全部数放入完全二叉树,然后在这个棵完全二叉树中，我们从最后一个结点开始依次判断以这个结点为根的子树是否符合最小堆的特性。如果所有的子树都符合最小堆的特性，那么整棵树就是最小堆了。

​ 具体做法如下：

​ 首先我们从叶结点开始。因为叶结点没有儿子，所以所有以叶结点为根结点的子树（其实这个子树只有一个结点）都符合最小堆的特性（即父结点的值比子结点的值小）。这些叶结点压根就没有子节点，当然符合这个特性。因此所有叶结点都不需要处理，直接跳过。从第n/2个结点开始（n为完全二叉树的结点总数，这里即7号结点）处理这棵完全二叉树。（这里用到了完全二叉树的性质：最后一个非叶结点是第n/2个结点)。

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

#调整编号为n的节点符合堆结构(这里是最小堆)
def head_adjust(i,end):
  tmp = L[i]
 
  j = i*2  #j是i的左子节点索引
  while j<=end:
    if j<end and heap[j]>heap[j+1]:
      j = j+1      #这里是比较两个孩子，将比较小的索引付给j
    if heap[j]<heap[i]:     #比较该节点和孩子中比较小的，如该节点比孩子中比较小的大，那么交换两个节点
      heap[i],heap[j] = heap[j],heap[i]
      i = j
      j *= i
    else:     #如果比孩子中较小的还小，说明一符合堆特性，不必继续向下遍历
      break     #由于是自下向上的，如果该节点移到的位置已经比两个子节点都小，那么他们也一定比孩子的孩子小

#从一个列表创建一个堆
def create_heap(L):
	from collections import deque
  heap =deque(L)
	heap.appendleft(0)
  
 	length = len(heap)-1
  last_no_leaf_index = length//2
  for i in range(last_no_leaf_index):
    heap_adjust(last_no_leaf_index-i,length)

堆排序

​ 平均时间复杂度：O(nlogn)

​ 最坏时间复杂度：O(nlogn)

时间复杂度主要是由于建立好堆后输出排序时，每输出一个结果要将一个数据从头向下比较，时间为O(logn)，有n次比较，因此总的时间复杂度为O(nlogn)

​ 堆排序的核心思想如下：

• 首先将待排序的数组构造出一个小根堆
• 取出这个小根堆的堆顶节点(最小值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个小根堆
• 重复第二步，直到这个小根堆的长度为1，此时完成排序。

​ 这里第一步就是小根堆的建立过程，上面已经有了，不在赘述，下面是第二、三不断交换完成啊排序的过程：

1
2
3
4
5
6

for i in range(length-1):
  heap[i],heap[length-i] = heap[length-i],heap[i]
  heap_adjust(i,length-i)    #每次都会有一个元素相当于已经输出，从后向前依次
  result = [L[i] for i in range(1,length+1)]
  return result

​ 因此整个堆排序过程为:

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

#调整编号为n的节点符合堆结构(这里是最小堆)
def head_adjust(i,end):
  tmp = L[i]
 
  j = i*2  #j是i的左子节点索引
  while j<=end:
    if j<end and heap[j]>heap[j+1]:
      j = j+1      #这里是比较两个孩子，将比较小的索引付给j
    if heap[j]<heap[i]:     #比较该节点和孩子中比较小的，如该节点比孩子中比较小的大，那么交换两个节点
      heap[i],heap[j] = heap[j],heap[i]
      i = j
      j *= i
    else:     #如果比孩子中较小的还小，说明一符合堆特性，不必继续向下遍历
      break     #由于是自下向上的，如果该节点移到的位置已经比两个子节点都小，那么他们也一定比孩子的孩子小

#从一个列表创建一个堆
def heap_sort(L):
  #创建堆
	from collections import deque
  heap =deque(L)
	heap.appendleft(0)
  
 	length = len(heap)-1
  last_no_leaf_index = length//2
  for i in range(last_no_leaf_index):
    heap_adjust(last_no_leaf_index-i,length)

  #输出堆的各个元素
  for i in range(length-1):
    heap[i],heap[length-i] = heap[length-i],heap[i]
    heap_adjust(i,length-i)    #每次都会有一个元素相当于已经输出，从后向前依次
    result = [L[i] for i in range(1,length+1)]
  return result

python中内置的堆

​ python中只内置了小根堆，要使用大根堆的功能，可以将数转化成对应的负值进行堆操作，出堆时再取负值即为原来的最大值

python中的堆引用：

1

import heapq

常用方法：

1.heapq.heapify(list) 将一个列表、元组穿换成小根堆对象，后续可以直接用堆操作

2.heapq.heappop(heap) 将堆顶元素出堆

堆常见题目

1.前K个高频的单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

1
2
3
4

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

1
2
3
4

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

分析：本题的主要难点在出现频率相同的但此处理上

解法一：利用Counter进行排序

关键点：使用Couner进行词频统计后如何进行排序，这里的排序只能使用频率的负值和首字母进行升序排序。为什么仔细进行思考，例:[“i”, “love”, “leetcode”, “i”, “love”, “coding”]

1
2
3
4
5
6
7
8
9

def topKFrequent(self, words: List[str], k: int) -> List[str]:
        from collections  import Counter
        result = []
        word_list = list(Counter(words).most_common())
        word_list = sorted(word_list,key=lambda x:[-x[1],x[0]])  #这里的排序使用只能使用频率的负值进行排序和首字母进行升序排序
        for i in range(k):
            result.append(word_list[i][0])
        
        return result

解法二：使用headp进行堆排序

1
2
3
4
5
6
7
8

def topKFrequent(self, words: List[str], k: int) -> List[str]:
         
        import collections
        count = collections.Counter(nums)
        heap = [(-freq, word) for word, freq in count.items()]
        import heapq
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in range(k)]

​ Counter对象就是python内部的一个计数器，常用来统计列表、字符串中各个字符串出现的频次，以及找到出现频次最该以及最低的元素

​ 使用前必须先引入引用：

1

from collections import Counter

​ 下面介绍在日常使用过程中常见的用法：

1.统计列表和字符串中各个元素出现的频数

1
2
3
4
5
6
7
8

s = "acfacs"
l = [1,1,2,4,2,7]
print(Counter(s))
print(Counter(l))

output:
  Counter({'c': 2, 'a': 2, 's': 1, 'f': 1})
	Counter({1: 2, 2: 2, 4: 1, 7: 1})

2.获取最高频的N个元素及频数

​ Counter对象的most_common方法可以获取列表和字符串的前N高频的元素及频次。

most_common:

​ param n:前几个高频对象，从1开始，默认为全部，也就相当于按照频数排序

​ return list:按照出现的频数高低已经排好序的前N个列表，列表的元素是两元组，第一项代表元素，第二项代表频率

1
2
3
4
5

s = "acfacs"
print(Counter(s).most_common(1))

output:
	[('c', 2)]