00:00
各位,我们现在用代码把刚才的集合问题给实现一把,打开eclipse。然后在这里呢,我们新建一个包。点G。就叫GOK。然后这边呢,我们写一个类。对叫GY,然后allgori对吧,Al就是贪心算法。在这里呢,我们怎么做呢?同学们,咱们这样来玩一把,首先第一我们按照刚才的思路来解决,首先我们先创建集,创建电台和集合,对不对,创建我们的。电台。或叫创建广播广。广播电台。广播电台。
01:00
那么我们把这个电台放到哪里呢?放到把它放入到一个哈希map中,或者放放到一个map里边去进行管理,大家看我这要写离离毕业啊,因为目前我们在做的过程中,我们首先得把广播电台保存起来,那广播电台大家可以看到这边呢,用一个K。这边呢是一个集合对不对,所以说我这样呢,用一个map k呢就是字符串,而它的值呢,就是一个哈希赛,这样就很好解决了,跟上我的思路。那我另一个哈希迈。咱们先溜一个哈希ma。哈希map OK,这里面我们放什么呢?K放字符串值,放的是哈希赛,因为这一个广播电台,它可以覆盖很多地区嘛,所以说这边我们放的set set呢,它也是不会重复数据的,所以说这样就比较方便一点。好的,然后我们把相应的包引进去,生成一个变量。
02:03
那这个变量的名字呢?我们就取一个叫broadcast好不好?Broad叫广播broad。Cast。Costs。第一步做完了,然后我们干什么呢?就往里边放入。各个电台将各个电台。电电台放入到这一个broadcasts里边去就完事了,那跟上我的思路,首先呢,我们六一个哈,Sets。Has she said。好,哈希塞的里面我们放的是地须,是不是好,我先写个名字,第一个呢,我们就叫哈西塞,一快速的写一下,往里面放东西了,哈西said1.a。我们跟上刚才的思路。OK,这电有点不足了,对吧,电有点不足了,把电弄一下。
03:01
接着。那现在我们往里面放什么呢?按照刚才第一个电台,我在这覆盖一下北京、上海和天津,往里面放就可以了。北京。第一个。第二个上海。上上海。对,上海天津。把天津也将去天津。嗯,好这样子。就是我们第一个北京上海天津这个就放好了,然后我们把它放到哪里去呢。呃,我们待会统一放吧,先把哈希赛第一个搞定对吧,待会我们统一放。然后紧接着我们再来放第二组。第二组复制一下就可以了,SET2哈希SET2哈希SET2是什么呢?就是广州北京和深圳,广州来写一个,那这边就换了。二。
04:00
二。广州。逛。广州,对,这个是上海。上海诶这个不行啊,上海,然后是深圳对不对,别写错了,广州北京和深圳广州。广州、北京和深圳,这写错了。北京。和深圳。深圳。深圳OK,第二组我们也有了,接着往下继续写。第三组。也就是我们第三个广播电台,第三个广播电台它能放什么呢?我们来看一看。广州北京深圳别写错了啊,广州北京深圳成都上海和杭州成都。成都。嗯,成都。第二个是。上海。
05:01
下一个是深圳、上海。上海,下一个是杭州。上海过了下,下一个是杭州,没问题,杭州。杭州。嗯,杭州OK,好,这是第三组,紧接着我们看第下一组,第四组。第四组呢,我们也把它给初始化一下,第四组应该只有两个城市了,对不对,所以说我把这个呢,就去掉一个。那第四组是哪两个城市呢?上海和天津?上海和天津对上海。上海。还有一个天津。OK,第四一组在第下一组就第五组了,第五组是我们的第五个广播电台,它覆盖的地区是哪两个城市呢?一个是杭州,一个是大连,对杭州。
06:00
行。杭州。还有一个是。大连大连,对,大连别写错了,但是错了这个就麻烦大连。大连。OK,好,同学们,现在呢,我们这几个城市都有了,然后把它加入到我们的加入,加入到map,加到map也很简单,一句话的事,哈希map。我们刚才的broadcast点什么呢?Put k k。K1呢,就是放到我们的哈希赛一没有问题吧?下面五句话,K2。K3K4K5下面呢,一样的进行一个编写K3。四五搞定。好,那现在呢?我们已然把这个电台创建起来了,下一步是不是就按照我们刚才的思路一步一步的玩,首先我们应该先建一个all errors。
07:06
那现在呢,我们就来建一个,建一个or or errors怎么创建呢?那我同样这样写,又一个哈希set。里面放的是字串。对不对,同学们分配一个变量,那这个名字呢,我们就叫奥,所有的A,哎,这个奥。A as就是所有的地区,这个地方是存的所有地区。All errors存放。存放。所有。所有的地区明白地区,但这个地区时间会不停的变化哈。下面这个创建好了,下一步我们应该做什么事情呢?是不是把所有地区的值把它加进去啊,第二。爱的,那这块呢,其实你们可以便利一下,到底里面有哪些城市,这里我就简单一点,直接把它放进去就完了,因为当时我们写的时候呢,一共有八个城市,对不对,八个城市我就快速的给写进去就行了,好吧。
08:11
这里我就偷偷一个来啊,你们自己去遍历一下,拿到这个值也是一样的,我就把它放进去就可以了,走。北京。快速的写下。八个。第二个是上海。第二个是上海。第三一个是天津没问题吧,第三个是天津。再下一个是。广州。广州也有了。按照这个顺序来,广州、北京已经有了,不要再放了深圳。深圳放进去。对,深圳完了过后,下一个是。成都。对不对,陈真,成都成都完了,下一个是。上海也有了杭州。杭州还没有放进去,是这样子的吧,杭州完了过后,下面是上海营业,天津。
09:05
啊,天津有了,杭州也有了,杭州也有了。呃,刚才这个杭州,那就下面是个大连了,好像对不对,是不是就大连就没有了,1234567不对,还有一个看看啊,北京上海天津北京上海天津。广州、北京、广州和深圳。广州啊,深圳少了一个。广州下面应该是我们的深圳冒险了。对。深圳。好,这就对了,北京、上海、天津、广州、深圳、成都、杭州和大连。这是我们把它加进去了,同学们当然也可以写一个写个方法把它,把它这个distinct一下就过滤一下也可以,我这里又简单处理了。当我们把这个写完过后,下一步我们应该做什么事情呢?根据刚才的思路分析,是不是要建一个select,里面存放我们将来选择的电台的集合,是这样子吧,好,现在呢,我们这样写。
10:08
创建创建。创建一个R。Or?那么存放什么呢?存放,存放,选择的存放。选择的。集合电台集合。电。胎。电台的集合,OK,那我就写了啊,那就六一个R。List,那这里面我们放什么东西呢?就放string。是不是把它选择好。然后这边我们给他一个名字,这个名字呢,就跟我刚才分析的取yellow名字。拿到这个时候,我们要引引下包。你进去。报也有了,下面我们应该做什么呢?好,同学们还记不记得,在刚才分析的过程中,我们有一个有一个就是不停的去选,去看,那他的这个交集的一个东西就是。
11:12
我们要知道。你当前这一个选择的这个集合。跟R o2里面这个集合,它的交集是几个,就说还记不记得我们说K1。K1和你当前的这个or,它到底有几个覆盖的,是不是我得用一个集合把它保存起来,所以说呢,我这还要定一个变量。注意听啊,我要干什么呢,我定义一个临时的什么呢集合。集合,这个集合呢,它干什么呢?它保存在便利过程中。注意听在。在便利的过程中干什么呢?它存放,存放便利过程中。
12:00
的电台。电台。呃,覆盖的覆盖的地区。地区。地区干什么呢?和当前还有没有覆盖的地区的一个什么呀交集。交警。交集也说的再直接一点,就是,呃,到时候你选一个K出来,和这个all orange的一个交集,那我先把它定起来,待会写的过程中大家慢慢就明白了,我留一个哈希set,同样放的是string。OK,同样放的string,那么这个变量的名字呢?我们就取一个临时叫temp。Set OK set拿到了。那么拿到这个过后呢,现在我们就可以开始便利了,同学们便利,在便利的过程中,大家有没有发现我们这有个max k,这个max k呢?它会记录你在一次便利过程中,它哪一个case能够覆盖。
13:09
未覆盖地区的最大的那个电台对应的K。是这个意思吧?同学们好,有点绕啊,那现在我们先再定义一个max。Max key。这个max可干什么呢?它这样子的,它是保存,注意听这句话啊,保存在一次便利过程中干什么呢?能够能够覆盖的,覆盖最多未未覆盖的地区。对应对应的电。电台要不电?电台的KOK,如果注意听,如果max k。
14:04
Max k不等于空,如果这个max不不等于空,不为空,则会,则会干什么呢?则会加入到这一个select里面,大家分析一下这句话什么意思,就是说我这个K不停的便利,便利,便利,最终是不是我会指向一个能够覆盖最大地区的这个电台,然后呢,这个max k呢,也会指向这个他,然后让这个max k对应的这这个他的那个K就放到我们这个release里面去,就这个意思明白了吧。好,现在呢,我们写段代码for循环,For循环,那我开始写了,我怎么写呢。好,这个地方咱们就这样写Y循环。外循环,只要我们这一个all all areas.size它不等于空,不等于零。同学们这句话表示什么意思,就说因为我们这个all all always,它是在不停的减少的嘛,大家还记不记得在我刚才分析的过程中,我找到一个K,我就把这个K覆盖的地区从这个or or or里面去掉啊。
15:16
对,现在是不是去掉,从这里面去掉。去去掉了过后,是不是它慢慢就all hours就会越来越少,越来越少,最后它就变成零了。那么只要它不为零,我们就可以继续看,如果输出就啊,如果all areas。二不为,不为零,则,则表示还没有。还就是还没有覆盖到所有的地区,是这意思吧,如果它等于零了,说明我们就我们这个select里面选择的这些电台呢,已经把所有的地区都覆盖到了。明白这意思,OK,那现在呢,下一步我们上来过后,先把这个max我们这样写啊,我一步写。
16:05
我们开始便利,那么便利什么呢?便利的就是我们这一个。是不是便利的broadcast呀?是不是便利的broadcast,这个大家能理解吗?便利的broadcast,那现在我们就开始便利把它K一个取出来,取出什么呢?取出,取出对应的K。这个K就是电台的那个那个。那个k for循环我写了是。K,没有问题吧,同学们,Broadcast。Broad broadcast什么呢?OK,注意听讲哈,那现在呢?现在我们就我们就可以取取出来了,那怎么取呢?Broadcast。点什么呢?Get k。大家想这句话代表什么意思?
17:01
这句话代表什么意思?这句话是不是代表iris,这句话就是代表当前这个KK就是当前这个K能够能够覆盖的地区,能理解吗?就当前你取出来这个K能覆盖的地区,好,那它那它能能覆盖的话,我们就把它先加到这个temp里边去at all,我一次性的把它加进去。那加到这里面的用处是相当于说temp set呢,也就把你这个当前这个K对应的这个应该还是处于debug状态,把它关掉就行了啊,就说你当前这个K对应的这个集合就放到temp里面去了。现在我要求交警。干什么呢?我要写这样一句话,Temp set,点。All,哦,和谁进行取交集呢?和all errors这句话大家理解什么意思吗?
18:03
就这句话,这句话的意思,我做一个解释,求出两个,就是temp。Temp set和这个all a集合的交集。集合的交集。交集什么意思,嗯。嗯,就是。就是你这个temp里面的集合和这一个当前的all is里面这个集合的共有的部分就会重新付给这个temp set,注意听啊,交集,这个交集它会什么交集会付给。付给谁呢?注意听这句啊,付。付给。付给这个ten。付给这个temp side能理解意思吧,付给这个temp side,也就是说现在temp side呢,就已经是你这选出来的这个areas和all as的一个交集了,那这个方法我就不,嗯,如果同学们不明白的地方可以可以在这试一下,我刚看一下这这个return all是什么意思,有些同学没有用过哈,我简单给大家,给大家做一个演示,很简单的一句话。
19:19
Test,我给大家演示一下,你们就明白了。这个return all是代表什么意思?比如说现在我有一个哈希。我有个哈希site,这里面呢,我放的是string。好的,我把这个写一下啊,不着急。一。放进去,然后呢,我们再来放一个二。再得到一个二,我把集合引一下,然后呢,我在哈希赛的一里面呢,我放一些数据进去,比如我放了一个一。好,我还放了一个二,看清楚了,我还放了一个100。OK,然后呢,我在这个哈希赛特二里面呢,我放的是什么呢?各位我也放的是一个一,然后呢,我还放了一个二,明白,我还放了一个200。
20:12
同学们看,现在呢,我用哈希set.return return return,哦,然后呢,我把哈希赛二写进去,同学们,这句话就代表什么意思呢?就是把一把哈希赛的一和哈希赛二共有的部分取出来,再重新付给哈希赛的一,也就是说这时如果我们输出这个哈希赛的一。哈西,SAT1,它应该等于多少呢?来,各位朋友,我给大家写到这,这时它其实就等于一二。就是说相当于把100和200去掉了,因为它保留共有的部分,那我们运行一下,大家看一下就一目了然了。是不是现在留下的就是一和二啊,同样的道理,如果我们翻译到这边,就是相当于说你把这个K取出来的这个集合。
21:10
对,先放,放到temp side temp side呢,再跟这个or always求一个交集,就得到它真实能够覆,能够覆盖的那个未覆盖地区的一个范围。好,下面的一个句话特别的重要,下面一句特别重要,我把这句话先写出来,再写注释,如果我们set。点size它是大于零的,说明你这次是有还存在没有一还就说你这次选的这个K呢,它还有没有覆盖的地区,同时还要满足一个条件。并且满足。如果我们max k。Max。Max。Max case上哪去了?Mac在这儿怎么没有写了呢?Max k。哦,大家看到我们现在这个max k还没有写出来呢,这个max k是必须要定义的,所以说我这里应该还有一个特别重要的一个东西定义max k,诶这个max k我这没有定义吗。
22:13
这忘了写了是吧?第一个max k,保存一次变量最大值,这个max k我还没写出来,我把它写进去,刚才已经说了,忘了写这句话了,就是max k。初始化。我们为空。对吧,好,现在如果说ma k它等于空,说明你现在还没有加进去,而这次呢,Temp set size还大于零,所以应该加,或者一种什么条件呢?或者还有一种情况,你也要把这个max k进行一个改变,什么呢?就是这个条件,大家看能不能看懂,就是temp set。呃,Temp set,它的赛制它大于了broadcast。点它的这个get mark。
23:00
Max size点什么呢?它的一个size。我看看是哪个写啊,点size。在这种情况下呢,我们就需要把这个max size进行一个重新复制。这样代码就行了,这句话大家看看能不能理解,我把这句话往这挪一下,下面这句话意思是什么呢?就是说如果注意听这话,如果当前这个集合,集合包含的包含的未。覆盖地区地区的数量。比,比什么呢?比你这个max,就是比你max指向的这一个集合还要多max。K指向。指向的集合未覆盖的地区还要多为。负。覆盖的。
24:01
的地区的地区还多。还多。OK,就说这样写吧,就说这样写,就是说你当前这个集合包含的未覆盖地区比max指向的集合的数地区还多,因为这个地方我写的是max size max k.size嘛,比它指向的集合的地区还多,那这个时候这个max size就需要变化,就需要干什么,就需要就需要重置这个max k就完了。也不难,是不是也不难,好整个写完了以后呢,同学们,这个时候我们到底要不要选这个K呢?要不要把这个k max size放进去,还有一个条件就是写上这句话啊,如果我们经过这一轮的,这一轮的这个便利,我如果我们发现max k它是不等于空的,说明什么?说明我们选中的有了。
25:00
好,也就是说在maxk不等于max k它不等于空的情况下,就应该干什么呢?就应该将这个max k加入到我们的select。Select这个集合中,明白那一句话的事就完了。点艾特谁?搞定。搞定,但是还有一句话特别的重要,我们刚才是不是在讲这个过程中,我们发现有一个匹配上了以后,比如说。呃,比如说我们第一次匹配的K,它原先匹配了三个,当我们把三个匹配完了过后,是不是要把这个这个K对应的地区从原先这个o orange里面把它清除掉啊,这句话不要忘了。叫什么呢?将max。Max。K指向的。这个广播。逛逛。
26:00
广播电台。电台包呃,把这几张广播电台覆盖的地区,覆盖的地区从从哪里去掉呢?从我们这一个哦。就是all errors里面清除掉。是不是要去掉啊,你不去掉,下次你还得继续匹配就麻烦了,那怎么去掉呢?非常的简单,二二.remove。是不是把谁清掉呢,就是broadcast。点get我们的max。K就清掉了。代码就写完还差一点点,大家有没有发现我这里还有一个地方是比较危险的哪个地方,你max ma,你现在第一次处理完了过后,它有可能是指向一个K,那你再进行下次for循环的时候,你这个max k呢没有清空。没有清空就意味着假如有一种情况下,就是max等于空,但是,但是。
27:03
就是这个条件不满足,但是temp side呢,还大于零,你就有可能不去复制了,因此你在这一步进来过,还有一句特别重要的话,要干什么呢?在while循环的下一次循环的时候,把这个max要制空。啊,每进行一次while。需要干什么呢?注,注意注,注意这句话啊,就要把max k吃空,因为你要为下一次。做一个准备。好,同学们,下面的代码这说完了,还大家想一想,还哪个地方有没有问题?你们有没有发现这个temp set,它你第一次处理完第一次这个temp set呢是空的,但是等到你下次再往里面来进行这个求交集的时候,是不是他们set里面已经有东西了,因此你每进行这一个。选取的时候,你还要把什么清空呢?还需要每进行一次for,我们需要把temp set干什么一下。
28:05
说老师,为什么你刚才不写呢?我说了啊,我讲课是按照大家思路走的,走到这你会发现必须清,如果我上来就清空,大家可能会觉得很奇怪,对不对?好,这两句话是很关键的。好的,同学们,那现在这个秀写完了,当我们整个这个Y循环结束,我们就OK了,哪里体现出它的一个贪婪呢?追星这句话。就体现出贪婪算法的一个特性,就他每次就选最好的,就体现出贪心算法或者贪婪算法。弹性算法的特点。我就说我每进行便利一次过后,我第一次选择的地区大,我发现第二次比你还大,我就选一个更好的。就每一次选一个最优的,每次都选择最优的,明白这意思吧,最优的OK。那这个整完了以后,整个这个Y循环,因为你不停的这remove,最终我们的ALL2就会变成零,那当我们这个Y循环推出以后,我们就选择到了按他能算法得到的一个结果。
29:11
OK。那么得到的。集合得到的。这个选择结果,结果OK。结果是什么呢?给同学们打印出来就可以了。写成一个。Select。好,各位朋友,我们运行一下,如果不出什么问题,就应该跟我们刚才分析的一样,应该是K1 K2K3和K5,是不是,如果你没有出什么问题,那就是K1K2K3和K5,代码就准备写完了,大家看能否理解。能否理解好,我们运行一把,我们运行一把。我们发现这个结果。我运行一下。
30:00
好,我们可以看到这个结果呢,跟我们想的一样,K1K2 K3K5。真是跟我们想的一样,那同学们学到这儿,可能有些同学是听懂了,那有些同学可能还是有点模糊,没有关系,如果你没有听懂的同学呢,待会呢,我们再debug一下,再深层次的追一下这个代码的一个过程就很清晰了。好的,同学们,那关于我们这一个探析算法的实现,就给大家先讲到这里。
我来说两句