九章算法06面试高频2020课件121chapter

九章算法班2021 第7高频数章课程都有study3希表与归属于九章算法（杭州）科 盗版将 刑事责 第1题题数据结构可以认为是一个数据集合以及定义在这个集合上的若干操（功能）考法1：问某种数据结构的基本原理，并要求实例题：说一下Hash的原理并实现一个Hash考法2：使用某种数据结构完成事例题：归K个有序数

九章课程都有 考法3：多个数据结构配合在一起使用，提供一些特定的功例题归属于九章算法（杭州）科技，和盗版将被刑事责 第2set/创set0= set1={1,3, set2=set(‘])‘hSet<Integer>set1=newHashSet<>();Set<String>set2=newHashSet<>();set.remove(4)如果被移除的元素不存在于set中，报set.discard(4)如果被移除的元素不存在于set中，不报错，set不查1in遍forvalinfor(Objectval:set){…归属于九章算法（杭州）科技，和盗版将被刑事责 第3dict/

创dict0= dict=dict1={‘name’:‘amy’,‘age’:21Map<Integer,String>map=newdict[1]=‘January’dict[‘age’]=21 p.remove(1)查找key查找value1in21in遍forkeyinforvalueinforkey,valueinfor(Objectkey:map.keyset()){…}for(Objectvalue:map.values()){…}for(Entryentry:map.entrySet()){…归属于九章算法（杭州）科技，和盗版将被刑事责 第4双端队字双端队字典队数链Linked的并查Union的并查Union栈二叉Binary哈哈希Hash堆单调堆单调Monotone归属于九章算法（杭州）科技，和盗版将被刑事责 第5度度数据结构通常会提供“多个”对外接口（方法只用一个时间复杂度是很难对其进行正确评价所以通常要对每个接口（方法）的时间复杂度进行描哪个方案好哪个方案好fi方案 方案O(logN)O(logN)归属于九章算法（杭州）科技，和盗版将被刑事责 第6如如HashTableHashMapHashSet的区别是什么是HashFunction(产生HashCode的函数)，作用以及实现原什么OpenHashing什么Closed什么是Rehashing（重哈希九章 有 归属于九章算法（杭州）科 盗版将 刑事责 第7685FirstUniqueGivenacontinuousstreamofdata,writeafunctionthatreturnsthefirstuniquenumber(includingthelastnumber)whentheterminatingnumberarrives.Iftheterminatingnumberisnotfound,return-1.[1,2,2,1,3,3,4,5,33

[1,2,2,1,3,,,,]都有，53归属于九章算法（杭州）科技，和盗版将被刑事责 第8输入[1,2,2,1,3,3,4,5,3输出3时间复杂度两次O(N)循空间复杂度

分类计九章 2à23à1

分类定12à3à归属于九章算法（杭州）科技，和盗版将被刑事责 第9960FirstUniqueWeneedtoimplementadatastructurenamedDataStream.Therearetwomethodsrequiredtobevoidadd(number)//addanewintfirstUnique()//returnfirstunique我们需要实现一个叫DataStream的数据结构。并且这里有两个方法需要实现)输数 输11,1,11,2,1,2,21,2,1,1,2,1,2,1,2,1,2,3归属于九章算法（杭州）科技，和盗版将被刑事责 第10我们需要实现一个叫DataStream的数据结构。并且这里有两个方法需要实)要数据结构选决查找某个元素是否已出现用Hash进行查找记录插入顺 九章课有，diedList序插List/ArrayList删除中间为O(N)，插入最后为Hash插入LinkedList插入中间为O(N)——需要O(N)寻找插入点的置，需要O(1)插LinkedList插入最后为LinkedList插入最后为删除或标记重复元Hash删除为List/ArrayList删除中间为O(N)，删除最后为O(1)LinkedList删除中间为O(N)——需要O(N)寻找删除点的位置，需要LinkedList删除最后，需要用Hash可以O(1)查找需要删除的元素，LinkedList删除间或结尾为归属于九章算法（杭州）科 盗版将 刑事责 第11&

时间复杂空间复杂

九章 有 11222归属于九章算法（杭州）科技 盗版将 刑事责 第12&

时间复杂和和盗版将刑事责空间复杂1111222归属于九章算法（杭州）科技 第13&

1

时间复杂度

九章 有 112归属于九章算法（杭州）科技，和盗版将被刑事责 第14G657InsertGDesignadatastructurethatsupportsallfollowingoperationsinaverageO(1)time.insert(val):Insertsanitemvaltothesetifnotalreadypresent.remove(val):RemovesanitemvalfromthesetifgetRandom:Returnsarandomelementfromcurrentsetofelements.Eachelementmusthavethesameprobabilityofbeing设计一个数据结构实现在平均O(1)的复杂度下执行以下所有的insert(val如果这个元素不在set)::九章 有 归属于九章算法（杭州）科归属于九章算法（杭州）科 设计一个数据结构实现在平均O(1)的复杂度下执行以下所有的操insert(val):如果这个元素不在set中，则插入remove(val):如果这个元素在set中，则从set中移除getRandom:随机从set中返回一个元素。每一个元素返回的可能性必须相同要数据结构选决查找某个元素是否已出现Hash查找LinkedList查找List/ArrayList查找 九章 有 用Hash进行查找插List/ArrayList删除中间为O(N)，插入最后为Hash插入LinkedList插入中间为O(N)——需要O(N)寻找插入点的置，需要O(1)插LinkedList插入最后为出入到List/ArrayList最后删除元Hash删除为List/ArrayList删除中间为O(N)，删除最后为O(1)LinkedList删除中间为O(N)——需要O(N)寻找删除点的位置，需要LinkedList删除最后，需要删除最后元素随机获取元用List/ArrayList的index随机获取元归属于九章算法（杭州）科技，和盗版将被刑事责 第16insert

0123401234435170

0 0归属于九章算法（杭州）科技，和盗版将被刑事责 第17remove

012345435 01234501234543501234543570543570570012344357归属于九章算法（杭州）科 盗版将 刑事责 第18九章 有 归属于九章算法（杭州）科技，和盗版将被刑事责 第19134LRUCache,DesignandimplementadatastructureforLeastRecentlyUsed(LRU)cache.Itshouldsupportthefollowingoperations:getandget(key)Getthevalue(willalwaysbepositive)ofthekeyifthekeyexistsinthecache,otherwisereturn-set(key,value)Setorinsertthevalueifthekeyisnotalreadypresent.Whenthecachereacheditscapacity,itshouldinvalidatetheleastrecentlyuseditembeforeinsertinganewitem.Finally,youneedtoreturnthedatafromeachget.为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据和写入数据get(key)获取数据：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1set(key,value)写入数据：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位最终你需要返回每次get的数据输

有 输cache上限为set(2,加入set(1,(2,1)加入(1,1)set(4,(2,1)淘汰(1,1)，加入set(2,(4,1)把(2,1)更新为set(4,(2,3)(2,3)输出-1，key1归属于九章算法（杭州）科技，和盗版将被刑事责 第20归属于九章算法（）科，和归属于九章算法（）科，和盗版将刑事责第21为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据和写入数据get(key)获取数据：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1set(key,value)写入数据：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用腾出空闲位置。最终你需要返回每次get的数据要数据结构选决需要key->value查Hash查找List/ArrayList查找LinkedList查找用Hash进行查找查找某个元素是否已出现用Hash进行查找插LinkedList插入中间为O(N)——需要O(N)寻找插入点的置，需要O(1)插LinkedList插入最后为LinkedList插入最后为删Hash删除为List/ArrayList删除中间为O(N)，删除最后为O(1)删除中间为O(N)需要O(N)寻找删除点的位用HasO查找需要删除的元素，kt间或结尾为)州 set(3,

key=

key=

key=

key=

key=

3章

d322

key=

key=

key=

key=

key=

key=

set(2,

key=val=

key=

key=

key=

key=

key=

归属于九章算法（杭州）科 盗版将 刑事责 第22

时间复杂get:O(1)时间复杂get:O(1)空间复杂

key=

key=

key=

key=

key=

key=

九章 有

get:O(1)空间复杂归属于九章算法（杭州）科 盗版将 刑事责 第23

时间复杂get:

key=

key=

key=

空间复杂

key=

key=

key=

九章 有 归属于九章算法（杭州）科 盗版将 刑事责 第24set(3,

21key21key=key=key=key=key=

key=

key=

key=

set(2,key=key=val=key=key=key=key=key=key=d322231key=key=d322231key=key=key=312213用doublelinkedlist+hashmap求 时间复杂get:空间复杂九章 有 归属于九章算法（杭州）科技，和盗版将被刑事责 第26 set(3,

val= set(2,

归属于九章算法（杭州）科 盗版将 刑事责 第27归属于九章算法（杭州）科，和盗版归属于九章算法（杭州）科，和盗版将刑选择一个好的工具，会让工作大大简get:O(1)空间复杂责 第28Heap分为最小堆（最小元素在堆顶）和最大堆（最大元素在堆顶堆是一个完全二叉堆的底层实现结构一般是数孩子节点比父亲节点堆不是二叉查找树BinarySearch不同语言对Heap的实Python:C++:priority_queue

九章 有基本操构建堆遍历堆AddOPopO(logN)MinorMax归属于九章算法（杭州）科技，和盗版将被刑事责

第294UglyNumberIIUglynumberisanumberthatonlyhaveprimefactors2,3andDesignanalgorithmtofindthenthuglynumber.Thefirst10uglynumbersare1,2,3,4,5,6,8,9,10,符合条件的数如：1,2,3,4,5,6,8,9,10,12...输入输出

12345678912345678912345689归属于九章算法（杭州）科技，和盗版将被刑事责 第30可不可以BFS逐层遍历寻找第N1235第不可1235第：study3.

每层不是单调递增

第三层的元素4，比第二层的元素5要第四层的元素8，比第三层的元素10要 有重复，使用什么去重归属于九章算法（杭州）科技，和盗版将被刑事责 第31&1每次可以取出堆中当 5最小数字，这个最小 5

取出1，分别乘以235，加入取出2，分别乘以235，加入取出3，分别乘以235，6（重复），加入字的插入顺序未必是先

Min最小3

取出4，分别乘以235，加入（4是在5之后插入的，确被先拿了出来九章 4有 546546归属于九章算法（杭州）科 盗版将 刑事责 第32

每取出一个数，就会加入3个数。最后取出N数，加入了3N个数。总复杂度接近 归属于九章算法（杭州）科技，和盗版将被刑事责 第33& 512345678912345689有 时间复杂一个for循环，N次操空间复杂需要长度为N的array存放找出的N个丑归属于九章算法（杭州）科技，和盗版将被刑事责 第34离线（offline）算法vs（online）算离线普通算法问数据结构设计类问数据是一开始给定数据流问一次输入输多次输入和输九章 有 归属于九章算法（杭州）科技，和盗版将被刑事责 第35612KClosestPointsKGivensomepointsandanoriginintwo-dimensionalspace,FindkpointsfrompointswhichareclosesttooriginEuclidean.ReturntotheanswerfromsmalltolargeaccordingtoEuclideandistance.IftwopointshavethesameEuclideandistance,theyaresortedbyxvalues.Ifthexvalueisthesame,thenwesortitbytheyvalue. 里给定一些points和一个origin，从points中找到k个离origin 九章 输入points=origin=[0,k=输出

points=origin=[3,k=1归属于九章算法（杭州）科 盗版将 刑事责 第36时间复杂空间复杂把所有点都排序，然后选择最小的k把所有点都放入最小堆，然后从最小堆取出kO(N)+归属于九章算法（杭州）科技，和盗版将被刑事责 第37最小的三个

10,3,8,100,4,33Max最大842归属于九章算法（杭州）科技，和盗版将被刑事责 第38最大堆（最小堆+取负最小的三个

10,3,8,100,4,--Min--Min最小---时间复杂空间复杂把所有点都排序，然后选择最小的k把所有点都放入最小堆，然后从最小堆取出kO(N)+用最大堆一直维持topK最小元归属于九章算法（杭州）科技，和盗版将被刑事责 第39545TopkLargestNumbersIIKImplementadatastructure,providetwoadd(number).Addanewnumberinthedatatopk().Returnthetopklargestnumbersinthisdatastructure.kisgivenwhenwecreatethedata实现一个数据结构，提供下面两个接add(number)添加一个元topk()返回此数据结构中最大的k个数字。当我们创建数据结构时，k是给定的s=news.topk输出[103]s.add(-s.topk输出[100010s.topk输出[100010s.topk输出[1000100

九章 有 归属于九章算法（杭州）科技，和盗版将被刑事责 第40最大的三个

10,30,20,5,40,55Min最小add时间复杂topK时间复杂空间复杂归属于九章算法（杭州）科技，和盗版将被刑事责 第41最大的三个

10,30,20,5,40,5Min最小

九章 有 归属于九章算法（杭州）科 盗版将被刑事责 第42Related九章 有 归属于九章算法（杭州）科技，和盗版将被刑事责 第43数据结构知识点及频率CheatSheetPart面试算法情学习难最少刷题哪些九章中小公司考得多，大公司近年来考得低九章算法基础Binary题目一般不难，主要Reference低九章算法基础班、九章算法高频，经常会用到，原理必须