​ 这些都是一个星期面的，感觉头皮发麻。。。

叭咔科技

​ 先写在这里，因为是交叉在里面的

​ 一次性面了两面+hr面，整体上技术面比较水，但是有一道题目挺有意思的，记录一下。让你通过什么方法去近似求一下圆形的面积，当时我一脸蒙b，后来面试官提示说可以从概率的角度，用随机数什么的，才想出了用变长为2r的正方形去处理

​ 这里涉及到一个列表和链表在增删时处理冲突的问题，列表可能会出现寻址问题

​ 其中还有一个尴尬的问题是python中random.random生成的随机数是均匀分布还是正态分布？答案是均匀分布

58同城

一面

​ 这一面面试官人很nice而且感觉专业水平很强，从我说项目开始一直问的模型问题都很深，问题面也边角广，而且注重细节，还会问一些具体模型实现上的事情，比如说transformer中的muti-self attention在编码上是如何实现的？word2vec输入一个词时是只更新一个词还是会更新全部的词？整体上感觉答的还可以就进了二面。然后让写了一道算法题，再两个无序数组中找出全部和为定值的组合，这个题我直接和他说了暴力枚举，他说你这个时间是多少？还能不能再优化一下？我说是O(n2)，他说能不能优化到O(n)？我说那就可以将第一数组先转成字典，这样可以降到O(n)

二面

​ 二面整体来说比一面要简单一些，主要就是问项目上事情，特征、数据处理、模型效果等等，涉及到模型具体实现细节上的东西没有深问，本来以为一定会深问transformer的，然而并没有提。。。

三面

​ 刚面完，热乎的三面，主要问的问题还是比较简单了，没有一面的难，感觉也是个技术人员，但是没有问的很深，遇到了一个和一面一样的问题，pytorch和tensorflow的区别在哪里，其他的基本上和一面一样了，讲项目、word2vec的原理、优化，正则化原理、公式，auc、roc含义是怎么来的，有一个问题没有答出来，kmeans是否一定会收敛，为什么？

good luck！

顺利通过，在端午回家的前一天顺利上岸，happy！

微软亚洲研究院

一面

​ 项目介绍+算法题，去除数组中重复元素去重，写完了又加了一条，删除数组中有重复元素的数

一面面完已经过了4、5天了，还没约面试时间，一面感觉还不错，不知道为什么就凉了。。。

深信服

HR说面试时间已经约了，他说下周，但是下周已经过了三天，还会没消息 希望过完端午回去可以有机会

什么是BERT？

​ BERT(Bidirectional Encoder Representations from Transformer)源自论文Google2018年的论文”Pre-training of Deep bidirectional Transformers for Language Understanding“，其前身是Google在2017年推出的transormfer模型。

​ 核心点为：

1.预训练

2.双向的编码表征

3.深度的Transformer

4.以语言模型为训练目标

BERT的两个任务

​ 1.语言模型，根据词的上下文预测这个词是什么

​ 2.下一句话预测（NSP）模型接收成对的句子作为输入，并学习预测该对中的第二个句子是否是原始文档中的后续句子

双向attention

​ 在之前常见的attention结构都是单向的attention，顺序的从左到右，而借鉴Bi_LSTM和LSTM的关系，如果能将attention改为双向不是更好吗？

​ 将attention改为双向遇到的最大问题就是深度的增加导致信息泄露问题，如下图：

解决该问题主要的解决方案有两种：

1.多层单向RNN，独立建模(ELMo)。前项后项信息不公用，分别为两个网络

2.Mask ML(BERT采用)

​ 解决的问题：多层的self-attention信息泄漏问题

​ 随机mask语料中15%的token，然后将masked token 位置输出的最终隐层向量送入softmax，来预测masked token。

​ 在训练过程中作者随机mask 15%的token，而不是把像cbow一样把每个词都预测一遍。最终的损失函数只计算被mask掉那个token。

​ Mask如何做也是有技巧的，如果一直用标记[MASK]代替（在实际预测时是碰不到这个标记的）会影响模型，所以随机mask的时候10%的单词会被替代成其他单词，10%的单词不替换，剩下80%才被替换为[MASK]。]

BERT整体结构

Input representation

​ 输入表征主要由下面三部分加和而成：

​ 1.词的向量化编码

就是常用的词向量化，例如Word2vec等或者直接embedding

​ 2.段编码

使用[CLS]、[SEP]做标记区分段，每个段用于其各自的向量Ei，属于A段的每个词都要加EA，属于B段的每个词都要加EB…

主要是为了下句话预测任务

​ 3.位置编码

和transormer不同的是，这里的position embedding是可训练的，不再是适用固定的公式计算

Transformer Encoder

​ 这里还会沿用Transformer的Encoder网络，首先是一个Multi-head self-attention，然后接一个Position-wise前馈网络，并且每个结构上都有残差连接.

Losses

​ Losses就是两部分，一部分是语言模型的任务的损失，一部分是上下文是否连续的损失。

​ 语言模型的任务的损失

​ 对于Mask ML随机选择进行mask的15%的词，是否正确做损失函数(一般为交叉熵损失函数)

​ 上下文是否连续损失

​ 二分类的损失函数，连续/不连续

常见问题

1.Bert的mask ml相对Cbow有什么相同和不同？

​ 相同点：两种方式都采用了使用一个词周围词去预测其自身的模式。

​ 不同点：1.mask ml是应用在多层的bert中，用来防止 transformer 的全局双向 self-attention所造成的信息泄露的问题；而Cbow时使用在单层的word2vec中，虽然也是双向，但并不存在该问题

​ 2.cbow会将语料库中的每个词都预测一遍，而mask ml只会预测其中的15%的被mask掉的词

2.Bert针对以往的模型存在哪些改进？

​ 1.创造性的提出了mask-ml来解决多层双向 self-attention所出现的信息泄露问题

​ 2.position embedding采用了可训练的网络取到了余弦函数公式

3.Bert的双向体现在那里？

​ Bert的双向并不是说他和transformer相比，模型结构进行了什么更改，而是transformer原始的Encoder部分在使用到语言模型时就是一种双向的结构，而本身transformer之所以不是双向的是因为他并不是每个单词的语言建模，而是一种整体的表征，因此不存在单向双向一说

4.对输入的单词序列，随机地掩盖15%的单词，然后对掩盖的单词做预测任务，预训练阶段随机用符号[MASK]替换掩盖的单词，而下游任务微调阶段并没有Mask操作，会造成预训练跟微调阶段的不匹配，如何金额绝？

​ 15%随机掩盖的单词并不是都用符号[MASK]替换，掩盖单词操作进行了以下改进：

​ 80%用符号[MASK]替换：my dog is hairy -> my dog is [MASK]

​ 10%用其他单词替换：my dog is hairy -> my dog is apple

​ 10%不做替换操作：my dog is hairy -> my dog is hairy

5.手写muti-attention

>
>
>

6、 elmo、GPT、bert三者之间有什么区别？（elmo vs GPT vs bert）

（1）特征提取器：elmo采用LSTM进行提取，GPT和bert则采用Transformer进行提取。很多任务表明Transformer特征提取能力强于LSTM，elmo采用1层静态向量+2层LSTM，多层提取能力有限，而GPT和bert中的Transformer可采用多层，并行计算能力强。

（2）单/双向语言模型：

• GPT采用单向语言模型，elmo和bert采用双向语言模型。但是elmo实际上是两个单向语言模型（方向相反）的拼接，这种融合特征的能力比bert一体化融合特征方式弱。
• GPT和bert都采用Transformer，Transformer是encoder-decoder结构，GPT的单向语言模型采用decoder部分，decoder的部分见到的都是不完整的句子；bert的双向语言模型则采用encoder部分，采用了完整句子。

为什么RNN会造成梯度消失和梯度爆炸，而LSTM可以防止梯度消失？

对于RNN：

而对于LSTM：

旋转数组的最小数字

​ 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。

1

例如:数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0

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 minNumberInRotateArray(self, rotateArray):
        # write code here
        
        if len(rotateArray) == 0:
            return 0
        left = 0
        right = len(rotateArray) - 1


        def find_rotate_index(arr, left, right):
            if right-left <= 1:
                return right
            mid = (left + right) >> 1

            # 当左半边有序
            if arr[left] <= arr[mid]:
                return find_rotate_index(arr,mid,right)
            else:
                return find_rotate_index(arr,left,mid)


        min_index = find_rotate_index(rotateArray, left, right)
        return rotateArray[min_index]

首先要找到目标数值，然后看该节点的左右子树情况，

​ 1.没有左子树，返回其右子树

​ 2.没有右子树，返回其左子树

​ 3.左右子树都有，查找到其右子树的最小值的节点，替换掉被删除的节点，并删除找到的最小节点

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

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root: return None
        if root.val == key:
            if not root.right:
                left = root.left
                return left
            else:
                right = root.right
                while right.left:
                    right = right.left
                root.val, right.val = right.val, root.val
        root.left = self.deleteNode(root.left, key)
        root.right = self.deleteNode(root.right, key)
        return root

1.三次握手过程以及四次挥手过程

2.进程和线程的区别

3.操作系统的页式存储是怎么样的？有什么优缺点

Time_wait和close_wait是什么。拥塞控制和流量控制。

快排

Spark调优核心参数设置

num-executors 该参数一定被设置， 为当前Application生产指定个数的Executors 实际生产环境分配80个左右的Executors
executor-memory 与JVM OOM(内存溢出)紧密相关，很多时候甚至决定了spark运行的性能 实际生产环境下建议8GB左右 若运行在yarn上，内存占用量不超过yarn的内存资源的50%
excutor-cores 决定了在Executor中能够并行执行的Task的个数 实际生产环境建议2~3个

driver-memory 作为驱动，默认是1GB 生产环境一般设置4GB

spark.default.parallelism 建议至少设置100个，官方推荐是num-executors*excutor-cores的2~3倍
spark.storage.memoryFraction 用于存储的比例默认占用60%，如果计算比较依赖于历史数据，则可以适当调高该参数，如果计算严重依赖于shuffle，则需要降低该比例
spark.shuffle.memoryFraction 用于shuffle的内存比例，默认占用20% 如果计算严重依赖于shuffle,则需要提高该比例

spark生态的主要组件：

spark core，任务调度，内存管理，错误恢复
spark sql，结构化数据处理
spark streaming，流式计算
spark MLlib，机器学习库
GraphX,图计算

spark运行模式：

1. local模式
2. standalone模式，构建master+slave集群
3. Spark on Yarn模式
4. Spark on Mesos模式

宽窄依赖

1.窄依赖是1对1或1对多，宽依赖是多对1

2.窄依赖前一步map没有完全完成也可以进行下一步，在一个线程里完成不划分stage;宽依赖下一步需要依赖前一步的结果，划分stage

4.在传输上，窄依赖之间在一个stage内只需要做pipline，每个父RDD的分区只会传入到一个子RDD分区中，通常可以在一个节点内完成转换；宽依赖在stage做shuffle，需要在运行过程中将同一个父RDD的分区传入到不同的子RDD分区中，中间可能涉及多个节点之间的数据传输

3.容错上，窄依赖只需要重新计算子分区对应的负分区的RDD即可；宽依赖，在极端情况下所有负分区的RDD都要被计算

map­reduce中数据倾斜的原因?应该如何处理?

如何处理spark中的数据倾斜?

原因：在物理执行期间，RDD会被分为一系列的分区，每个分区都是整个数据集的子集。当spark调度并运行任务的时候，Spark会为每一个分区中的数据创建一个任务。大部分的任务处理的数据量差不多，但是有少部分的任务处理的数据量很大，因而Spark作业会看起来运行的十分的慢，从而产生数据倾斜

处理方式：

1.使用需要进行shuffle人工指定参数并行度

2.进行数据的清洗,把发生倾斜的刨除,用单独的程序去算倾斜的key

3.join的时候使用小数据join大数据时，换用map join

1. 尽量减少shuffle的次数

Spark分区数设置

1、分区数越多越好吗？

不是的，分区数太多意味着任务数太多（一个partion对应一个任务），每次调度任务也是很耗时的，所以分区数太多会导致总体耗时增多。

2、分区数太少会有什么影响？

分区数太少的话，会导致一些结点没有分配到任务；另一方面，分区数少则每个分区要处理的数据量就会增大，从而对每个结点的内存要求就会提高；还有分区数不合理，会导致数据倾斜问题。

3、合理的分区数是多少？如何设置？

总核数=executor-cores * num-executor

一般合理的分区数设置为总核数的2~3倍

Worker、Master、Executor、Driver 4大组件

1.master和worker节点

搭建spark集群的时候我们就已经设置好了master节点和worker节点，一个集群有一个master节点和多个worker节点。

master节点常驻master守护进程，负责管理worker节点，我们从master节点提交应用。

worker节点常驻worker守护进程，与master节点通信，并且管理executor进程。

2.driver和executor进程

driver进程就是应用的main()函数并且构建sparkContext对象，当我们提交了应用之后，便会启动一个对应的driver进程，driver本身会根据我们设置的参数占有一定的资源（主要指cpu core和memory）。下面说一说driver和executor会做哪些事。

driver可以运行在master上，也可以运行worker上（根据部署模式的不同）。driver首先会向集群管理者（standalone、yarn，mesos）申请spark应用所需的资源，也就是executor，然后集群管理者会根据spark应用所设置的参数在各个worker上分配一定数量的executor，每个executor都占用一定数量的cpu和memory。在申请到应用所需的资源以后，driver就开始调度和执行我们编写的应用代码了。driver进程会将我们编写的spark应用代码拆分成多个stage，每个stage执行一部分代码片段，并为每个stage创建一批tasks，然后将这些tasks分配到各个executor中执行。

executor进程宿主在worker节点上，一个worker可以有多个executor。每个executor持有一个线程池，每个线程可以执行一个task，executor执行完task以后将结果返回给driver，每个executor执行的task都属于同一个应用。此外executor还有一个功能就是为应用程序中要求缓存的 RDD 提供内存式存储，RDD 是直接缓存在executor进程内的，因此任务可以在运行时充分利用缓存数据加速运算。

driver进程会将我们编写的spark应用代码拆分成多个stage，每个stage执行一部分代码片段，并为每个stage创建一批tasks，然后将这些tasks分配到各个executor中执行。

Spark是如何进行资源管理的？

1）资源的管理和分配

资源的管理和分配，由Master和Worker来完成。

Master给Worker分配资源， Master时刻知道Worker的资源状况。

客户端向服务器提交作业，实际是提交给Master。

2）资源的使用

资源的使用，由Driver和Executor。程序运行时候，向Master请求资源。

Spark和mapreduce点的区别

优点：

1.最大的区别在于.spark把用到的中间数据放入内存，而mapreduce需要通过HDFS从磁盘中取数据。

2.spark算子多，mapreduce只有map和reduce两种操作

缺点：

​ spark过度依赖内存计算，如果参数设置不当，内存不够时就会因频繁GC导致线程等待

什么是RDD

RDD是一个只读的分布式弹性数据集，是spark的基本抽象

主要特性：

​ 1.分布式。由多个partition组成，可能分布于多台机器，可并行计算

​ 2.高效的容错（弹性）。通过RDD之间的依赖关系重新计算丢失的分区

​ 3.只读。不可变

RDD在spark中的运行流程？

1. 创建RDD对象
2. sparkContext负责计算RDD之间的依赖关系，构建DAG
3. DAGScheduler负责把DAG分解成多个stage(shuffle stage和final stage)，每个stage中包含多个task，每个task会被TAskScheduler分发给WORKER上的Executor执行

spark任务执行流程：

1. Driver端提交任务，向Master申请资源
2. Master与Worker进行RPC通信，让Work启动Executor
3. Executor启动反向注册Driver，通过Driver—Master—Worker—Executor得到Driver在哪里
4. Driver产生Task，提交给Executor中启动Task去真正的做计算

spark是如何容错的？

主要采用Lineage(血统)机制来进行容错，但在某些情况下也需要使用RDD的checkpoint

1. 对于窄依赖，只计算父RDD相关数据即可，窄依赖开销较小

2. 对于宽依赖，需计算所有依赖的父RDD相关数据，会产生冗余计算，宽依赖开销较大。

在两种情况下，RDD需要加checkpoint

1.DAG中的Lineage过长，如果重算，开销太大

2.在宽依赖上Cheakpoint的收益更大

一个RDD的task数量是又什么决定？一个job能并行多少个任务是由什么决定的？

task由分区决定，读取时候其实调用的是hadoop的split函数，根据HDFS的block来决定
每个job的并行度由core决定

cache与checkpoint的区别

cache 和 checkpoint 之间有一个重大的区别，cache 将 RDD 以及 RDD 的血统(记录了这个RDD如何产生)缓存到内存中，当缓存的 RDD 失效的时候(如内存损坏)，
它们可以通过血统重新计算来进行恢复。但是 checkpoint 将 RDD 缓存到了 HDFS 中，同时忽略了它的血统(也就是RDD之前的那些依赖)。为什么要丢掉依赖？因为可以利用 HDFS 多副本特性保证容错！

reduceByKey和groupByKey的区别?

如果能用reduceByKey,那就用reduceByKey.因为它会在map端,先进行本地combine,可以大大减少要传输到reduce端的数据量,减小网络传输的开销。

groupByKey的性能,相对来说要差很多,因为它不会在本地进行聚合,而是原封不动,把ShuffleMapTask的输出,拉取到ResultTask的内存中,所以这样的话,就会导致,所有的数据,都要进行网络传输从而导致网络传输性能开销非常大!

map和mapPartition的区别？

1.map是对rdd中的每一个元素进行操作；mapPartitions则是对rdd中的每个分区的迭代器进行操作
如果是普通的map，比如一个partition中有1万条数据。ok，那么你的function要执行和计算1万次。使用MapPartitions操作之后，一个task仅仅会执行一次function，function一次接收所有的partition数据。只要执行一次就可以了，性能比较高。

2.如果在map过程中需要频繁创建额外的对象(例如将rdd中的数据通过jdbc写入数据库,map需要为每个元素
创建一个链接而mapPartition为每个partition创建一个链接),则mapPartitions效率比map高的多。

3.SparkSql或DataFrame默认会对程序进行mapPartition的优化。

mapPartition缺点：
一次性读入整个分区全部内容，分区数据太大会导致内存OOM

详细说明一下GC对spark性能的影响?优化

GC会导致spark的性能降低。因为spark中的task运行时是工作线程,GC是守护线程,守护线程运行时,会让工作线程停止,所以GC运行的时候,会让Task停下来,这样会影响spark

程序的运行速度,降低性能。
默认情况下,Executor的内存空间分60%给RDD用来缓存,只分配40%给Task运行期间动态创建对象,这个内存有点小,很可能会发生full gc,因为内存小就会导致创建的对象很快把内存填满,然后就会GC了,就是JVM尝试找到不再被使用的对象进行回收,清除出内存空间。所以如果Task分配的内存空间小,就会频繁的发生GC,从而导致频繁的Task工作线程的停止,从而降低Spark应用程序的性能。

优化方式：

​ 1.增加executor内存

​ 2.可以用通过调整executor比例,比如将RDD缓存空间占比调整为40%,分配给Task的空间变为了60%,这样的话可以降低GC发生的频率 spark.storage.memoryFraction

​ 2.使用Kryo序列化类库进行序列化

为什么要使用广播变量？

当RDD的操作要使用driver中定义的变量时,每次都要把变量发送给worker节点一次,如果这个变量的数据很大的话,会产生很高的负载,导致执行效率低;
使用广播变量可以高效的使一个很大的只读数据发送给多个worker节点,而且对每个worker节点只需要传输一次,每次操作时executor可以直接获取本地保存的数据副本,不需要多次传输

参考文章

​ 背包问题是指给定义一些候选集，在这些候选集中找出一些特定要求的组合，组合出目标值(也就是用一些大小不同的东西装满背包)。

​ 常见的背包问题问题有：能否组成一个值，组成一个值得最小元素个数，组成一个值可使用的最多元素个数等

​ 背包问题根据背包选用的物品是否可以复用，分为完全背包问题和0/1背包问题。根据背包的维度可以分为一维背包问题和二维背包问题。下面我们针对这些问题中的关键点进行总结：

0/1背包问题：

​ 1.遍历时一定要从后向前遍历目标值数组（dp），不能从前向后，从前往后会产生一个物品适用多次的问题

​ 2.要在最外层循环遍历物品，这样能保证在选择将物品是否使用在哪里使用

​ 3.dp数组长度为目标值得大小+1

完全背包问题：

​ 1.dp数组长度为目标值得大小+1

​

一点想法

对于从后到前的遍历动态规划每隔一段时间再看多会很难理解，这也是动态规划经常做的不是太好的原因吧，因此把从后向前整个流程梳理一下。

一维背包问题

1.零钱兑换(leetcode 232)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

1
2
3

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

1
2

输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

分析:这道题题目是标准的完全背包问题，用数目不定的元素组合成指定金额，因为各个值都可能有两种情况组成：1.直接由当前金额的硬币直接组成 2.由之前组成的金额再加上一个硬币组成，因此递推关系为:

​ dp[i] = min(dp[i],dp[i-c]) c为硬币的各个金额

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

def coinChange(self, coins: List[int], amount: int) -> int:
       MAX_INT = pow(2,32)-1
       
       dp = [MAX_INT for _ in range(amount+1)]
       dp[0] = 0
       
       for i in range(1,len(dp)):
           for c in coins:
               if i-c>=0:
                   dp[i] = min(dp[i],dp[i-c]+1)

       if dp[-1]==MAX_INT:
           return -1
       else:
           return dp[-1]

2.小米大礼包

小米之家是成人糖果店。里面有很多便宜，好用，好玩的产品。中秋节快到了，小米之家想给米粉们准备一些固定金额大礼包。对于给定的一个金额，需要判断能不能用不同种产品（一种产品在礼包最多出现一次）组合出来这个金额。聪明的你来帮帮米家的小伙伴吧。

输入描述:

1
2
3

输入 N （N 是正整数， N  <= 200）
输入 N 个价格p（正整数, p <= 10000）用单空格分割
输入金额 M（M是正整数，M <= 100000 ）

输出描述:

1
2

能组合出来输出 1
否则输出 0

示例1

输入：

1
2
3

6
99 199 1999 10000 39 1499
10238

输出：

1

1

分析：这是一个标准的一维0/1背包问题，最终目标看是否能完成组合。因此首先我们推断出递推公式

​ dp[i] = max(dp[i],dp[i-c])

注意：0/1背包问题必须要从后往前进行遍历，否则会出现已经当前c在前面使用dp[i] = max(dp[i],dp[i-c])已经更新过的结果，相当于使用了多次c

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

n = int(input())

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

target = int(input())

dp = [0 for i in range(target+1)]


dp[0] = 1

for c in nums:
    for i in range(target,c-1,-1):
        dp[i] = max(dp[i],dp[i-c])

print(dp[-1])

二维背包问题

1.一和零(leetcode 474)

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:

1. 给定 0 和 1 的数量都不会超过 100。
2. 给定字符串数组的长度不会超过 600。

示例 1:

1
2
3
4

输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4

解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。

示例 2:

1
2
3
4

输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2

解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

分析：这一题是比较典型的0/1背包问题,将翻译后的string看做一个物品，这个物品有两个value，value1为0

的个数，value2为1的个数，初始状态下你有用m个0和n个1，求最多能获取的物品总个数。

​ 核心依然是找到状态转移方程，因为题目具有两个变量，属于二维背包问题，因此创建一个二位数组，分别代表使用num0个0和num1个1时可以获得的最多字符串数。

​ dp[num0][num1] =max(dp[num0][num1],dp[nums0-zeros][nums1-ones]+1)

注意：这里的二重循环必须从m,n开始递减，而不能从0开始递增，因为在0/1背包问题中，每个物品只能被使用一次，如果从0开始向后，dp[num0][num1]可以获得的是这次循环中更新过的dp[num0][num1] =max(dp[num0][num1],dp[nums0-zeros][nums1-ones]+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

def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        
        tmp = []
        for i in strs:
            zeros = 0
            ones = 0
            
            for j in i:
                if j=='0':
                    zeros+=1
                else:
                    ones+=1
            tmp.append([zeros,ones])
            
        #m 行，代表0  n列代表1
        dp = [[0 for _ in range(n+1)]for _ in range(m+1)]
        
        for s in tmp:
            zeros = s[0]
            ones = s[1]
            for nums1 in range(m,zeros-1,-1):
                for nums2 in range(n,ones-1,-1):
                    dp[nums1][nums2] = max(dp[nums1][nums2],dp[nums1-zeros][nums2-ones]+1)

        return dp[-1][-1]

2.大礼包

在LeetCode商店中， 有许多在售的物品。

然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

示例 1:

1
2
3
4
5
6
7

输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释: 
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

最小车票花费

挑选代表

我们有很多区域，每个区域都是从a到b的闭区间，现在我们要从每个区间中挑选至少2个数，那么最少挑选多少个？

输入描述:

1
2

第一行是N（N<10000）,表示有N个区间，之间可以重复
然后每一行是ai,bi，持续N行，表示现在区间。均小于100000

输出描述:

1

输出一个数，代表最少选取数量。

输入例子1:

1
2
3
4
5

4
4 7
2 4
0 2
3 6

输出例子1:

1

4

思路分析：

​ 本题是一个贪心问题，即挑选最少的点，也就是在每一步种都选择可能和下一步公用的点。可以先把区间按照结尾去接进行排序，然后从第一个区间开始记录最后两个元素的值，

​ 如果下个区间中包含了这两个元素，那么挑选点数+0，x、y不变，

​ 如果下个区间中只包含了一个元素，那么挑选点数+1,y继承x的值，x变为当前区间的最后一个元素

​ 如果下个区间中不包含任何x、y一个元素，那么挑选点数+2，x、y更新为区间最大、次大值

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

n = int(input())

nums = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    nums.append(tmp)

nums = sorted(nums,key=lambda x:x[1])

ans = 2
x= nums[0][-1]   #最大的元素
y = nums[0][-1]-1    #次大的元素

for l in nums[1:]:
    if l[0]<=x<=l[-1] and  l[0]<=y<=l[-1]:
        ans += 0
    elif l[0]<=x<=l[-1] or l[0]<=y<=l[-1]:
        y = x
        x = l[-1]
        ans+=1
    else:
        ans+=2
        x = l[-1]
        y = l[-1] - 1

print(ans)