8月刷题/Mock interview接龙活动（缺米刷题的来）

8/5 打卡169 229 274 275 243 244 245 多次查询用HashMap

8/5 打卡第5天， 刷了3道题

94. Binary Tree Inorder Traversal
recursive 和 iterative 两种解法

208. Implement Trie (Prefix Tree)
Trie的数据结构，每个节点有self.children =  collections.defaultdict(TrieNode)
和 self.value. value 可以根据需要定义

211. Add and Search Word - Data structure design
用stack存所有可能的children

8月5日刷题 5道
总结了之前一直困扰自己的String系列，8月的每个踏实的日子都是对自己负责的表现！

下面主要说说自己对于stringreplace 这道题的总结
StringReplace是指用target string去替代原来input string里面出现的某段或某几段subString

assumption:
all those three strings are not null or empty;
all operation must be fit in the memory;

High level:
Check how many repeated by using one time traversal
then use a list to store each repeated starting indices and we could use those for starting point, then to replace it.

//Firstly traverse the input string,
//check how many elements should we add at the end or how many elements
we need to subtract compare to the input string, use an int variable to store the string source repeated times
//at the same time, find all the starting indices of each string and put it into an ArrayList
//then to create a new Array(with its newLength) to store the updated string;

//Then in the matching process, use two pointers which are
slow pointers in the newArray,
i pointer which used for traversing the input string

//Finally to add the new String by traversing the input String again and put all the old char and all target elements into the new Array and finally output the new String.

刷题打卡第5天
46. Permutations 这题需要用backtrack递归来解，关键是设计好递归函数的收敛条件，input，用关键字in来判断每个数字是否在temp列表里，最后当temp列表长度与原始nums相等即可收敛。

47. Permutations II 这题比Permutation更加tricky，主要是因为有重复的数字，思路还是backtrack递归，关键是要设置boolean数组来记录每个变量有没有被使用过，对于和前一位一样但是没有被使用过的数字要略过，另外一开始要对数组进行排序。

48. Rotate Image 这道题是medium的，关键是想明白什么是rotate，它和行列的坐标的关系是什么，一开始想的是把第一行变成最后一列，第二行变成倒数第二列。。。后来发现要in place，想到的是设置一个temp，然后先选中4个角，再按顺序旋转后面的，后来发现还有更霸气的算法，先上下翻转再转置就行了，这样只要实现一个swap就可以in place旋转了，记得上下翻转和转置的时候设好行列指针的区间即可。

菜鸡八月

今天还是学stock
1. best time to buy and sell stock with cool down: 三个states，分别是可买，可卖，和cool down，要记得
    把s1 initialize 成-prices[0], 然后再存上一个s2的值，再从s2开始进行transition，s2 = s1 + prices，
    s1 = max(s1, s0 - prices)， s0 = max(s0, lastS2)。
2. best time to buy and sell stock IV: 限制k个transactions，如果k>n/2就和不限一样，不然的话用dp[j]来代表
    ith transaction和到jth price, 每行先用一个localmax记dp(i-1, 0) - price[0], 再用dp[i, j] =max(dp[i, j-1],  prices[j] + localMax)，
    来填dp array，再用localMax = max(localMax, dp[i-1，j] - prices[j])来updatelocalmax，最后return dp[k, n-1]
3. best time to buy and sell stock with transaction fee: 有两个states，一个是可买，一个可卖，记得initialize s1 = -price[0],
    然后可以用s0 = max(s0, s1 + price - fee), s1 = max(s1, s0 - price)来update

8.5 每日一题Add and Search Word - Data structure design
卡了一个小时！之前没接触过 Trie 结构，add到还比较好做，search卡了...感觉开始有挑战性了
另外今天找了很久投岗的公司职位之类的，感觉还是很迷茫.....希望这周结束之前能投出几份简历，争取早点 mock interview

8月day4今天三道题：
rotate array：insert and pop
best time to buy and sell stock: only add positive first derivatives
remove duplicates from sorted array: in-place replacement
求加米，谢谢！

8.5 第五天
一些hashtable的题
first unique number in data stream
  linked list 存只出现过一次的数，hastable 数到node的映射，一个set存duplicated 数
  用一个dummy node方便提取。linked list删除操作有些小细节比如删最后一个的时候。
复制linked list
  用克隆图的方法先建立映射。然后再走一遍，把next等关系填补上。
Insert Delete GetRandom O(1)
  用数组存数，用hashtable存数在数组里的下标。删除时和数组末尾元素交换然后删除。

打卡打卡，今天刷了好多题，一个屏截不下来。。。

8/5