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

因为老公的原因，我辞掉国内大厂工作，肉身翻墙过来也有4个月了。我的目标是，在2~3个月之内，找到Self-driving car领域的SDE工作。
4~5月计划

1.        刷题200道
Binary search, BFS, DFS, DP, etc.
Priority queue, LRUCache, List, BIT, etc.
每一道题时间复杂度、空间复杂度、多种解法吃透
2.        系统设计课
3.        Deep Learning + Tensorflow
自学看书、练习
4. Self-driving&&learning相关paper，熟看10篇。

5.        简历准备



希望和地里伙伴们相互督促，欢迎交流心得分享经验~
一起加油！

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

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

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

建议你上个xx算法的网课，比自己总结效率高太多……

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次。

今天复习了DFS两道题。
1.word break
Gieve s = codecode,
dict = ["de", "ding", "co", "code", "aa"].
A solution is ["code code", "code co de", "co de co de", "co de co de"].

解题要点：
记忆化搜索，用hashmap将“从某个index开头的substring”的所有结果都保存起来。
比如substring“decode”, 对应结果有“de co de” "de code"..
遍历该结果，与co相结合，就能得到以"co"开头的所有结果，"co de co de", "co de code"
...

2.word pattern
判断两个字符串的形式是否match
Given pattern = "abab", str = "redblueredblue", return true.
Given pattern = "aabb", str = "xyzabcxzyabc", return false.

解题要点：
记忆化搜索，用两个hashmap来存储对应关系以及使用过的substr
比如，a已经对应了red, 那么遇到a和其他词进行比较的时候就说明该string不match。
边界情况是，两个substring都变成""空了，说明他们是match的，其中一个不空都说明不match.
回溯时，erase掉hashmap里的对应关系，重新建立新的对应关系。

jtzc0123 发表于 2019-4-2 09:12
建议你上个xx算法的网课，比自己总结效率高太多……

谢谢~
我有上过那个算法班，没有上强化班。感觉现在还没有消化完所学的东西。。

04/02/19
1.Narcissictic number 水仙花数
Narcissistic Number is a number that is the sum of its own digits each raised to the power of the number of digits. See wiki
For example the 3-digit decimal number 153 is a narcissistic number because 153 = 13 + 53 + 33.
And the 4-digit decimal number 1634 is a narcissistic number because 1634 = 14 + 64 + 34 + 44.

解题要点
1.n等于几，说明该数就有几位。
a1a2a3..an = a1^n + a2^n + … + an^n
2.枚举10^(n - 1)到10^n区间的数，结合%10、/10得到数字每一位的值。


2.a+b problem
Given two integers, a and b, return the sum of a and b. no "+" operation.

解题要点
结合按位异或^和按位与&计算、左移，得到位的sum和进位值。
1^1 = 0, 1^0 = 1, 0^1 = 1, 0^0 = 0符合加法特性

04/03/19
1.Unique Characters
判断一个string是否由unique character组成。
2.First Unique Character in a String
2 pass, 第一次记录每一个character出现次数，第二次返回答案。
用int c[256] = {0}比hashmap快。
3.First Unique Number in Data Stream II
上一题的follow up,
方法1. 用Single Linked list记录single number，当add重复数字时，删掉list中的该数字。无重复则添加到list。
方法2.Single Linked list + hashmap.
4.Reverse Words in a String

04/04/19

1.Legal Identifier（easy）Lintcode CAT
判断一个字符串是否符合命名规则

2.word search II (hard 第二遍)
在一个给定的matrix里找给定的dict里存在的单词。
Dfs的方法能够掌握了，但细节还需要多考虑。
一开始没想到把dict的前缀作为一个筛选条件，只是用了单词长度作为筛选，结果在某个test case 超时了。

3.一些easy题。。

赞人肉翻墙-脱产刷题-

04/05/19

1.meeting rooms
给定一些会议时间，判断一个人能不能开完所有的会。
也就是要求会议时间无重叠。
注意会议时间是无序的需要sort
sort function
Public:
Static bool comparison (const Interval a, const Interval b) {
Return a.start <= b.start;
}



Sort(intervals.begin(), intervals.end(), comparison);



注意priority queue的comparison写法是不同的。都是从小到大排序。



Class comparison {

Bool operator () (const Interval a, const Interval b) {

Return a.start > b.start;

}

}

用priority queue和sort一样，都是O(nlogn)



2.multi-keyword sort

把班上同学的分数拿来排序，如果分数高在前，如果分数一样，则学号低在前。



直接用sort function，

Comparison还可以这么写：

static bool cmp (vector<int> a, vector<int> b) {

        return a[1] != b[1] ? a[1] > b[1] : a[0] < b[0];

}

AriesCar 发表于 2019-4-6 12:48
赞人肉翻墙-脱产刷题-

难度可想而知。。。
不抛弃不放弃哈哈哈。