坐标波士顿，决定开个刷题贴激励下自己

已经过了一个学期了，还没找到实习
感觉主要是自己背景太弱了，没有和cs有关的项目，这个学期做了个网站，算是稍微补充了一点
刷题主要是刷leetcode，现在刷到了250道，但是感觉前面的题目掌握的并不牢固，打算再刷一段时间就从头刷起
决定从今天开始记录自己每天刷的题目

今日更新， 2H + 2E
269. Alien Dictionary（H）：很难，建立两个hashmap，一个存数和所有应该比这个数小的数，另一个存数和应该要比这个数大的数的数量，遍历一遍所有的string，根据字典规则更新两个hashmap，再从第二个hashmap中value为0的数开始，value为0代表这个数不依赖任何比它大的数，所以可以直接放入结果，当把一个数放入结果，根据第一个hashmap把所有应该比他小的数的依赖减一，重复步骤就能得到最后的结果，听起来就很绕。。
76. Minimum Window Substring（H）：我觉得不是很难，只是细节需要注意一下，思路就是sliding window，我这里是设了两个指针，当左右指针中间的所有字母（包括右指针）已经满足要求时，左指针往右移，直到中间的字母不满足要求为止，最后返回这个过程中左右指针最小的差值
349. Intersection of Two Arrays（E）：比较简单，我用的hashset
716. Max Stack（E）：比较简单，可以用stack + treemap，也可以用stack + pq，我两个都试了下，treemap快一点但空间会使用的比较多

第一天上课，神奇的更新一发，最近状态不太好，感觉刷的有点吃力，感觉进入了瓶颈期
253. Meeting Rooms II（M）：em...没想出来，但是看了答案又觉得挺简单，会给一个二维数组，表示需要用会议室的开始时间和结束时间，要求需要的最少的房间的数量，答案是用最小堆来做的，先将所有的时间安排按照开始时间排列，override一下comparator就能实现。然后再创建一个最小堆，这个堆比较的是结束时间，所以结束时间最小的会被放在堆顶，将遍历数组，将数和堆顶的数进行比较，如果数大于堆顶的数，说明有一个开始时间最早的时间安排和一个结束时间最早的安排不重叠，那么就可以把堆顶的这个数从堆中删掉，然后再把新的数放到堆里面，最后得到的堆的大小就是所需要的最少的房间数量。
560. Subarray Sum Equals K（M）：要求一个数组里面所有总和为k的subarray的数量，最简单的就是dp，o（N2）的复杂度，能刚刚过，最后也是用的dp，但是只用o（N）的复杂度，遍历数组，用一个变量sum得到[0, i]的数的总和，再用一个hashmap存目前所有presum，这样如果有一个subarray[j, i]满足条件，就一定能在hashmap中找到sum - k这个数，最后返回累加的结果就行
207. Course Schedule（M）：是一个拓扑排序的问题，给一个数组表示所有需要的先修课，求能否满足要求，但是我graph学的不太好，到时候补充下graph的知识再回来看下这题，我用的方法是hashmap加hashset，思想是dfs，就是从一门课出发，看他所有的先修课能否满足，这样就要用dfs先看先修课的情况，这里的关键是用一个visited数组存住所有已经找过的情况，然后用一个hashset存住所有目前在找的课，如果找的课已经再visited里面了，就代表ok，如果在hashset里面，就说明是个死循环，返回false

好久没有更新了，并不是去玩了hh，主要是寒假忙着做project准备春季的career fair，寒假做了两个full stack的项目
一个是用react + redux做前端，nodejs + express + mongodb做的后端，做了一个类似于论坛一样的网站，然后为了丰富这个project，用websocket给这个网站加上了online chat的功能，现在还在完善中，做完了准备用docker部署到ec2上
另一个也是一个网站，post二手物品，技术栈与第一个相同，react + redux的前端，nodejs + express + mongodb后端，这个网站我想了很多种方法处理图片，一开始是存储到本地，后来又改成了存进mongodb，最后是采用的上传到amazon s3上，然后图片使用url存储，感觉这样更好处理，API设计也比较清晰，同样还在完善中

现在手上ongoing的项目是用java spring做一个backend，这个项目比较复杂，估计career fair之前肯定做不完，只能慢慢来了

今天刷了Leetcode85(hard)，是给一个0和1的二维矩阵，求全是1的最大矩阵面积，我用的dp，时间复杂度是m * n2，因为要遍历每一个点，而且在遍历点的时候用一个循环求左上的最大面积，速度是70%， 答案有m * n的方法可以提高速度。
Leetcode817(medium)，给一个链表，要得到另外一个数组中所有在链表中连续点的数目，比如说链表是1-2-3-4，数组是[1,2,4]，数目就是2，因为1-2连续，4单独，这题感觉比较简单，用Hashset存储数组，然后遍历链表看后一节点是否在hashset中就行，速度是90%，感觉应该没有更快的方法了

最近在做一节课的project，是要完成一个wordbrain的游戏，会给一个字典，大概包含10w个word，然后给一个二维数组，类似于下面这样：
a d w s j
s v u e v
o q w v k
s i g n q
**** ****** ****
然后一个字母可以和邻接的字母连起来，需要所有满足*格式的组合，比如asos dwsjve qngi
解决一个word后，word里面的字母会被消掉，矩阵会重排，字母会掉下来
我现在的思路是建立一个字典树，然后用dfs遍历puzzle，而且每次会检查一下树的路径，如果有可能的情况就继续，没有就返回
不知道有没有更好的思路


补充内容 (2018-12-14 05:47):
还有一道380(medium)，建立一个数据结构要求插入和删除还有得到一个随机元素（每个元素概率一样）都满足o(1)时间复杂度，咋一看很简单，插入和删除要求o(1)，hashset就可以满足，但是得到一个随机元素这需要思考

补充内容 (2018-12-14 05:49):
我用的是两个hashmap，一个是元素为key，一个顺序为key，插入和删除用第一个map，找随机树用第二个map，但是删除的时候要进行元素的替换，把要删除的元素替换到最后一个，这样可以保持顺序

补充内容 (2018-12-14 06:07):
724(easy),找一个int数组是否存在pivot，就是左边元素的和等于右边元素的和，我的方法时间复杂度o(2n），应该说是dp，先从右到左存储右边元素的和，再从左到右遍历，速度是100%

今天刚考完最后一门，前几天都没有时间刷题，关于wordbrain的游戏，我最后的解法是word trie + dfs，方法和最后的solution差不多，但是效率还是会比老师给的标准慢个2～3倍，不知道为什么，最后时间在0.1ms~1000ms不等，取决于puzzle的复杂度

今天开始做题，但是寒假要上网课加做项目所以可能只有上午能刷刷题
519（M）：Random Flip Matrix， 会给一个row和一个col，要求在这个范围内随机取一个点的坐标，取了一次下次就不能再取，并且能够完成reset，由于给的数字很大，所以把每个点都存下来再随机取会memory exceed，这里只能把取出来的点的横坐标和纵坐标的特定乘积存下来，但是怎么实现取一次下次就没法再取呢？ 我这里一开始没想出来最优解，所以用的是Hashset + 循环，取到的点在hashset中就再取一次，能够过测试，速度在20%左右， 最优解是用Hashmap，比较巧妙， 取出来某一点后，把当前row的最大值更新到取出来的点上，row再-1，看了答案以后重新做了一遍，速度是80%。
625（M）：Minimum Factorization，给一个int，得到一个新int，新int的所有位的乘积是给定int，我这里用循环得到给定int的所有小于10的factor，可以用list存最后排序，也可以用PQ啥的直接存，最后把得到的factor加起来，速度是100%
722（M）：Remove comments，就是实现c++中字符串去除comment，字符串操作是我不太喜欢的，感觉每次都很麻烦，主要是细心和一些corner case，错了几次才通过，速度是100%
762（E）：Prime Number of Set Bits in Binary Representation，找到一个范围内的int，二进制bit的是‘1’的总和是质数的数量，由于给的int范围不大所以质数情况可以直接存到hashset中，然后再对范围内的树进行循环就行，具体看‘1’的数量，我用的是num & 1，然后再num <<= 1循环求，速度大概在60%左右，可能位操作上还有更简便的方法
876（E）：Middle of the Linked List，求一个linkedlist的中位node，不能更简单了。。由于linkedlist的长度不长，可以用数组存下所有node，这样可以用一次循环就得到中位node，速度是100%

miaoyuhang 发表于 2018-12-19 00:40
今天刚考完最后一门，前几天都没有时间刷题，关于wordbrain的游戏，我最后的解法是word trie + dfs，方法和 ...

看到wordbrain，发现原来是BU EE的啊，刷了不少啊，加油加油！

mccoder 发表于 2018-12-21 16:44
看到wordbrain，发现原来是BU EE的啊，刷了不少啊，加油加油！

哈哈，是的，加油加油

哈哈 BU EE岂不是我的学弟。。

Black Liu 发表于 2018-12-22 01:39
哈哈 BU EE岂不是我的学弟。。

哈哈，学长好

今天上午只刷了四道题：
497（M） Random Point in Non-overlapping Rectangles：这道题花了我最久时间，是要在N个不重叠的矩形中找随机点，我忽略了一个比较重要的信息就是分布在各个矩形的点的概率要和矩形的面积成正比，所以前面有几个test过不了一直在找原因，后来才发现，最后用treemap做的，速度不是很快，但是没时间继续改进了
328（M）：Odd Even Linked List， 一道很简单的medium题，就是按奇偶树重新排linkedlist
733（E）Flood Fill， 一道基本的DFS题
328（M）Design Tic-Tac-Toe： 这道题也挺简单的，用数组按player分别存各排各列还有对角的情况就行

有问题欢迎咨询哈哈，毕竟EE的不是很多