7月缺米的来刷题/Mock interview活动

谢谢各位大佬给分，继续努力 ：  周一，新的一周。

D4：  打卡第四天 (UTC: 06/07/2020)

学习： 图与搜索 DFS/BFS

1： Leetcode 133 :clone graph
   使用BFS 遍历图，得到所有的节点(辅助bfs的队列）
   创建新的节点，建立原图节点和新图节点点之间的映射关系存在HashMap中；
   复制边（遍历原图节点，利用上面的hashmap, 找到新点A ；遍历原图的邻居节点，利用hashmap, 找到新图对应的新节点， 加到新的节点A 的邻居列表。
   返回hashmap 原节点对应的新节点。

2：        Topological Sorting
        节点的入度的概念
        a: 计算每个点的入度， 生成入度表
        b: 入度为0的节点加到result。 将这些节点加入queue.
        c: 当queue 非空，将首节点出队 （加入结果），对应所有临节点入度-1.
            如果入度-1的节点入度为0，将该节点入队。
        d: 返回结果
       
3: LeetCode207：        Course Schedule
        BFS：
        利用上面拓扑排序的思想，如果最后所有的点都被访问到了，就是可以的。
        代码和拓扑排序很像。算是topological sorting 的应用题吧。
       
       

打卡第二天 2020.07.06
100329 在排序数组中查找数字 I
628 三个数的最大乘积
1013 将数组分成和相等的三个部分
896 单调数列
1287 有序数组中出现次数超过25%的元素
1502 判断能否形成等差数列
100158 判定字符是否唯一
100275 数组中重复的数字
63 不同路径 II
122 买卖股票的最佳时机 II

day6 #sql 3题
1. 创建唯一索引 create unique index... on ...()
2. 使用强制索引查询 select...from... indexed by/force index... where...

July day4

打卡Day2 7.7
8. Implement strStr()
使用滑动窗口。
for start in range(n-m+1):
            if haystack[start:start+m]==needle:
今晚太忙了。只写了一题。看看明天白天是否有时间。有的话再补两题。

7.6 打卡
Unique Paths
Spiral Matrix
Valid Sudoku
一个dp, 一个array，一个hashSet相关

Mock interview 打卡

Day 14, solved 6 very easy problems.

1. LC 1470. Shuffle the Array, need to find the pattern;
2. LC 1464. Maximum Product of Two Elements in an Array, look for the max 2 numbers;
3. LC 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence, split sentence into array and use String.startsWith().

DAY 2

十分感谢楼主昨天为我加米，今天继续加油⛽️

Day 5, 0705, 6道题。这个是补昨天的

Hamming Distance: 用了 x & 1 check最后一位，然后右移，做32次。挺简单。bit都不熟了有空可以重新看看。

Longest Word in Dictionary 一开始写了个简单的遍历，发现不行，然后一顿改还是不行，有个case是 o od odm om oml omlt 这种，不用每次都从一个o开始。所以改了个 set做的，这样sort一下之后，一个一个查，如果是只有一个字母，或者去掉最后一位的substring在set里，就put，update res， 不在就继续。小伙伴说这个可以trie tree然后bfs，感觉更intuitive一些

Smallest Sufficient Team 这个题学会了见到题先问数据范围。这里skill的范围是<=16， 所以做0 -1 背包的话是 2^16 ，是6万多，比用people的200做要或不要好多了。所以dp填表的时候， 先把技能转换成bit，就用skill list的index就行，然后i 从 0 到n，查每次i个人，达到每个技能格子的最小人数，这样每次多一个人进来，我们用前一行的技能 | 这个人的技能，就能看可以更新哪一排（这里可以一行一行做，但是因为是16，而且要打印路径，所以可以直接用skill idx存一堆list，直接每次比较看看能更新谁，然后长度变化直接更新就行，不用做完美的dp）

string transforms into Another String 这个题挺怪，一开始以为是一对一，都翻译成pattern就行了，感觉这也不是hard啊。。。然后被打脸。这个顺序有要求，每次a改成c之后，下次变c的话这个原来是a的c也会跟着变。。。所以其实变化非常自由，只要有没用到的字母当中介 + pattern一样，就可以随便换。所以记录一下pattern，然后判断是不是<26。挺怪的

Remove Duplicated Letters 这个有些像单调栈，但是不用stack，就是一个stringbuilder，然后存一个int[26]count，一个boolean[26] used，每次遇见一个字母就进sb，然后mark used，count--。 下一个进来，用一个while循环，把所有之前的字母count >0 的搞出去，然后自己进来。挺难分析的，需要非常非常稳。。。

mock了一道挺有趣的题，一个grid of 1 or 0, 1能走0不能，查能不能从第一行的任意位置到最后一行任意位置。我比较熟bfs就写了bfs。然后follow up要打印路径。。。我就懵逼了。一顿被提示我写了个hashmap记录每次的parent 坐标然后回去找。原来也可以用visited数组直接存就行。每次都忘了visited其实可以多存很多别的信息。还被教育了override hashcode function，感觉还是要多mock啊。

补充内容 (2020-7-7 13:21):
这个回复被审查了仿佛被跳过了。。。求米。。。