人肉翻墙-脱产刷题-记录帖

04/19/19
1.Graph clone
要求深拷贝一个图，所以是要BFS一层层的扒开图。用queue就不用多说了。
用map建立对应关系。道理我都懂，但是还是看不明白：）

2.subset
无重复数字的subset，要点是每次dfs找到的都是以某个index开始的subset

3.subsetII
有重复数字的subset，去重一定要在计算当中进行.
注意dfs前，对数组进行排序。

4.wildmatching
判断两个字符串是不是能match上，'*'可以代表任何单个、多个字母，'?'可以取代一个字母。
S=“aaa” p="*?a" -> true
结合记忆化搜索和dfs。如果遇到'*'，那下一轮*可以当做0个字符去掉，也可以当做1~n个字符保留。遇到'?'并且当前字符相同时，下一轮将两个字符串的起始位置都右移以为。
循环终止条件：
1.访问过该组合，直接返回结果 2.s到终点，那么p后面只要全是*就可以 3.p到终点，那么s也到终点就可以。

5.Kth smallest in BST
BST的中序遍历为非递减数列。

04/20/19

复习Graph-based DFS, permutation DFS

1.N Queens

要点是Q的行、列以及正斜线方向的位置都不能有其他Q,否则会被攻击。

比如Q在r行c列，那么只要(a, b)满足a==r || b = c, 或者 a + b = r + c || a – b = r – c都不符合条件。

2.Permutation

用hashmap记录已经组合过的index.

去重方法和排列题类似。

3.Word LadderII

BFS求深度+求word的下一个词

DFS求路径。

04/21/19

1.LRUCache

两种方法，

1）使用std::list库

2）自己构造singly list

2.hashmap + hashfunction

想请教一下楼主，Deep Learning/TF这一块打算拿什么材料做练习呢？

Cveinnt 发表于 2019-4-25 07:54
想请教一下楼主，Deep Learning/TF这一块打算拿什么材料做练习呢？

我之前在看一本书《Tensorflow 实战google深度学习框架》，先跟着里面的例子把mnist数字识别问题先过了一遍。然后再用CNN写一遍。国内买的书，比较详细，但里面直接用TF的库函数比较晦涩。

建议先要把理论知识掌握好，我时常边看边写还要重新看看一些基本的概念，比较低效。
开始做项目了的话，你可以装一个Keras，Keras把TF又封装了一遍，简单易上手，可以更方便快速搭模型+迭代。
另外推荐做kaggle的项目，里面很多项目都有大神写的DOC，手把手教你怎么写。
先从最简单的mnist这类的做起，然后再挑战更难的或者找人组队一起参加里面的Competition。

04/29/19
1.Union find
经典的connecting graph。
一开始给定一些孤立的节点，不断的给节点加边，最后求一共有多少连通图/或求某节点和某节点是否相连/或求某个节点所在连通图的大小。
union find要点：
1）初始化父节点
2）查询集合root节点
查询的同时需要压缩图，即把路径中所有节点都指向root。
方法一：递归，方法二：循环。
3）合并两个集合
找到两个集合的root节点，让其中一个节点的父节点等于另一个节点。

2.Trie
也叫prefix tree。适用于词的存储。
每一个节点的next节点都可能有26个(26个字母)。通过next把树联通起来。
473. Add and Search Word - Data structure design
这道Tire+dfs比较经典。

3. Task Scheduler
给定一些用字母表示的task，给定每个task重复执行时中间需要空闲的时间n
task=[A,A,A,B,B,B], n = 2.
A->B->idle->A->B->idle->A->B->idle
ans=6.
思路：
最终需要多少时间是由最多的那个任务个数决定的，假设该任务个数为count。
不考虑最后一次执行，那么前面所有执行次数为(count - 1)x(n + 1)。
那是不是最后加上1就可以呢？不是。
如果有多个任务数量最大且相等，那么都需要最后执行一次。
比如[A,A,A,B,B,B,C,C,C] n =2
执行完(3-1)x(2+1)次后，最后各要执行ABC一次，所以++3次。

05/05/19

DP
哪些题可以用DP?
1.计数型
2.求最值
3.求可行性

两种实现方式：
1.循环(从小到大递推)
2.记忆化搜索(从小到大搜索)，一般结合dfs

几种类型：
坐标类(一、二维)
1.求最值
2.计数
3.可行性
博弈类
1.两方游戏，先手后手，满足条件则判断为胜，目标是取胜。
区间类:
1.求一段区间内的解(最值或计数）
2.转移方程通过区间更新
3.大区间的值依赖于小区间。

jiangqueque 发表于 2019-4-6 12:52
04/05/19

1.meeting rooms

天呐 看了楼主的记录帖感觉好励志！我也是因为老公工作原因来湾区的 但我是文科背景 感觉找工作无望本来很沮丧 但看到你这个帖子真的觉得受到鼓舞 加油呐！

carole_wang 发表于 2019-5-6 13:49
天呐 看了楼主的记录帖感觉好励志！我也是因为老公工作原因来湾区的 但我是文科背景 感觉找工作无望本来 ...

一起加油！！争取早日上岸！

629. minimum spanning tree
这道题要求把节点按照cost最低的方案连起来。如果可以变成全连通图，则返回所有的连接。不能则返回空。
比较难想到的点是要对输入先进行排序，按照cost、city字母顺序从小到大排列。
然后再用Union find.

1.对输入connection按照cost,以及city的字母顺序进行排序
[A,B,1] [B,C,3] [A,C,2] --> [A,B,1] [A,C,2][B,C,3]
是为了将city做一个编号，1~n，方便建图
2.用hashmap将city和其城市编号对应。
3.遍历排序后的connections，对于每一个connection，找这两个city是否有建立过连接。如果有，那么他们对应的father一定是一样的并且是最小cost（因为排过序），如果没有，则建立连接。
4.返回值。
如果边的数量刚好等于点的数量-1，则该图为连通图且没有冗余边。
否则返回空。