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

Report for duty

8/9 Day9

54
Spiral Matrix
用Layer to Layer 解

36
Valid Sudoku
数独 hashset和对于Array的掌握

38
Count and Say
StringBuilder

打卡
* Path Sum I
* Path Sum II
* Path Sum III
* Postorder (iterative way)
* Closest Binary Search Tree Value

八月day8:
今天3道题
replace element with the greatest element on the right side: 从后往前
valid mountain array
check if n and its double exist

打卡两题（貌似要点大图可以正常显示）~是leetcode facebook prep专区里的medium题

希望各种OA面试顺利 早日上岸啊啊啊啊

真诚求米.jpg

Day 6
最近系统设计，题都有些水。。。

337 House Robber 3
这个题上来就懵了。。。好久不刷题，看见树好像看见鬼一样。连recursion基本的都没写出来。打开答案一秒懂。。。就是recursion + memo，写dp的话要返回两个值用int[2] 存。

375 Guess Number Higher or Lower
这个MinMax第二次写了。写完发现上次根本没有懂。这个之所以要每一轮都特别悲观总也选不对，但是要取每一轮里最小的那个值，因为每次都可以从最小的开始查，比如最后剩下 2 跟 3，肯定猜 2，这样对了就完事，不对的话肯定是3， 也不用再继续给钱了. 所以永远猜小的，省钱。

415 Add Strings
非常水。。。凑个数。。。

补昨天的作业：8月8号  day 8

刷题3道
1. Binary search find an element in a sorted matrix
-把二维matrix转化成一个一维array，然后用对应的坐标取值；
2. find common element in two arrays;
-先排序，后用2个pointers分列在A/B两个array当中，然后再同时
从左到右进行扫描
3. Find all anagrams
这个题可以好好说说

Question:
Given string s1 and s2;
Find all the substring of s2 which could be one permutation of s1;

Assumption:
both strings are not null or empty;
all operation can fit in memory;

Analysis && High level:
No matter what the permutation is, for example the permutation string str of s1 can be find as the substring of s2, it must have the same number of characters; so Instead of using recursion to find all permutations of s1(eg: size = M), which could increase the time complexity to M!; in order to decrease the time complexity, so to use a hashMap, which used for storing all elements in s1.
For example: s1: "acdddd" -> hashMap :{ 'a', 1}, {'c', 1}, {'d', 4};
Then use two pointers slow and fast to traverse the string s2, at the same time, maintained a size M as a sliding window, use a list to store all qualified substrings in s2, after the whole traverse, return the list.

Details:
Use a hashMap with <K,V> pair to store all characters(as Key) and its duplicate times(as value);
Then linear scan the string s2 and maintained the size as M as a sliding window by using slow and fast pointers, also combining with an int variable match to record the matching status of the hashMap.
When the size of the sliding window is smaller than M, the substring range from slow to fast can not be the qualified one, so move the fast pointer to fulfill the size of sliding window first and keep tracking of the match status of the hashMap. Besides, if the sliding window is larger than M, it is also impossible to form a string that could be the permutation of s1. so it is necessary to move slow and fast dynamically to maintain a size M sliding window.
If match equals to the size of hashMap which represent already find the matched permutation,and put current substring into the final result.
until the whole string s2 has been traversed, return the result;

日期: 8/9/2020
题目: [3]
994. Rotting Oranges
1371. Find the Longest Substring Containing Vowels in Even Counts
1539. Kth Missing Positive Number

8.9 day9
今天头疼只写了每日一题

每日三题 day9
Rotting Oranges - 简单的遍历/图的存储，但是错在边界上，数iteration的时候是 while - do 还是 do - until
Merge Two Sorted Lists - 链表的基础操作，但是忘了挪current指针导致一直在刷新head。。。
Find First and Last Position of Element in Sorted Array - 二分查找的变种，算法和想法都没问题，但是又在边界条件上错了N次。。外加又一次把tail打错字成了target。。