文科生学算法刷题打卡贴

基础真的好弱，刚才花一个多小时才模拟出一道简单的BFS是什么意思。
我理解的BFS recap:
1. 是用一根指针模拟在一个图形中的行走方法，用最快的时间让这根指针走最大的面积
2. 每当指针走到一个Node的时候，它的下一步就是同时扩散走到这个node对应的所有adjacent node,这一步其实是矛盾的，因为只有一个指针，不能同时走好几步，但是在有多个相临边的时候就可以
3.queue的作用是一个存储容器，因为当一个node有好几个相临边的时候，最后临界点这个指针在哪里呢？是这些相临边中的其中一边吗？即使记住了最后一个node，怎样记得最后第二个，后N个呢？这时候需要queue把同时踩到的node一起记录在queue中，等到遍历完所有adjancent node后，重新回到queue,queue.front()代表下一次从哪里出发。

993这题是判断一个Binary tree中两个node的值是否构成cousin, cousin的定义是:1)not share parents 2) of the same depth
这道题目可以用BFS做的原因是，BFS路径遍历graph的时候是按照每一个node对应的层次层级遍历的，binary tree正好是层次感很强的图形。

每经历一个node,就把他的left 和right放到queue里面，接着以queue中的left 和right为一次循环，分别检验left的left,right和right的left,right是否符合给定的参数。如果每一次循环对应的count==2， return true,otherwise设定boolean为false,重新开始新的循环。

我一开始没有把题目给的例子模拟清楚，就是忽略了3点：
1. 如何保证两个node属于相同的depth:BFS层级遍历，同一层级的一起看
2.如何保证不share一个parent? 如果一个Node左右两个孩子都是参数x,y,count只计算一次
3.每进入一个新的层次，cnt重新设置为0, boolean==false

70 rotting oranges:这是最后一道没做的BFS简单题目，看到题目我想的算法是：
1. 先找到所有的rotten orange,放入queue
2.每一个rot对应的相邻fresh orange变成rotten，count++;
3.取queue中的下一个rotten orange, update adjacent fresh orange;

写代码的时候我觉得困难的地方：
1.不知道怎么update相邻的fresh orange，其实很简单，就是grid[i][j]中i+1, i-1和j+1,j-1的update
2.另外queue中存储的是rotten orange的位置，用pair, pair.first, pair.second分别表示横纵坐标

我发现BFS是可以有模板可以用的，希望可以尽快写出属于自己的模板

0318打卡：
昨天晚上和朋友打了两小时电话，浪费了很多刷题的时间，刷题任务没完成公开课也没听完，今天上午直接荒废了。今日成就是跑步终于可以在1小时内跑到9公里了。平时要减少在线的时间还有闲聊时间，这学期课不多为啥这都做不完。

今天任务是停2节算法课（4小时），2节python课（2小时），记忆背诵算法课笔记，然后把老师paper看一遍。加油！

打卡：
今天把OOD听到第三节课，然后晚上8点开始然后花12小时刷一遍zju的data structure，上学期上的好多东西忘了。。。

看到第一个帖子就吓哭了。。看完了算法导论是认真的吗。。

SallyNotSilly 发表于 2019-3-25 09:33
看到第一个帖子就吓哭了。。看完了算法导论是认真的吗。。

鹅看了，但是记不太住。。。

雪狼88 发表于 2019-3-25 09:12
楼主哪个学校的cs？

还在持续观望offer，目前都不太理想的。。。

雪狼88 发表于 2019-3-26 01:19
哪个学校的cs应该不重要吧，还是看面试吧最后，这是很多过来人说的，我也不清楚

我也挺好多人这么说，不过还是想去排名高一些的，当然综合实力也很重要~~