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

8. String to Integer (atoi) 这是一道medium题，想明白按照顺序处理string,先把空格都处理掉，然后正负号，然后找到第一个数值和最后一个数值，然后转换，转换的时候检查有没有越界。

10. Regular Expression Matching 这又是一道hard题，乍一看不难，但是仔细推敲发现无法通过顺序扫描和比较处理复杂的诸如abc.*abc.*这样的字符串，后来发现要通过dynamic programming，基本版可以通过二维数组来实现，高级版本可以通过一维数组，但是要设置临时变量存储之后将要覆盖的值。

11. Container With Most Water 这题一开始想的太复杂了，一定要先把思路理清，就是两边比较大小，然后遍历一遍找个最大的就行了。

Day 3 打卡

0 minutes ago        Maximum Product of Three Numbers        Accepted        6 ms        java
1 minute ago        Maximum Product of Three Numbers        Wrong Answer        N/A        java
23 minutes ago        Task Scheduler        Accepted        4 ms        java
4 hours, 49 minutes ago        Valid Triangle Number        Accepted        406 ms        java
5 hours, 45 minutes ago        Shortest Unsorted Continuous Subarray        Accepted        6 ms        java
6 hours, 9 minutes ago        Array Nesting        Accepted        1227 ms        java
6 hours, 19 minutes ago        Array Nesting        Wrong Answer        N/A        java

Day 8

1518. Water Bottles, 递归
1519. Number of Nodes in the Sub-Tree With the Same Label, dfs
210. Course Schedule II, 基于in degree的bfs

菜鸡七月第十九天

1. task scheduler: 先找最多的task是什么, 用maxCount来记如果有相同数量的最多的task，因为每个要n tasks apart，所以空出来的
    时间就是(max-1)*(n-(maxCount-1))，再往idle time里面填剩下的tasks，如果有剩idle time，就加到task length里面是最后总需的时间
2. reorganize string: 和前一道有点类似，也是先算letter和对应的frequency放到map里，同时记最多的letter，如果最多的letter比string的
    一半还长，就没法隔开放，可以的话就先把最多的隔开放，每次index+2，然后再把剩下的letter隔开放进去
3. best time to buy and sell stock with transaction fee: 学习用的dp，每天可以分hold和cash两种情况，cash取当前cash和之前hold+卖掉的
    价钱-transaction fee的最大值，如果当前没有持说明之前没有或今天卖掉了，hold取当前hold和之前cash-买的价钱，如果有持说明之前就有
    或者今天刚买
4. largest perimeter triangle: 这个比较简单，可以先sort再从高往低找最大的可组三角形的一组
5. word pattern: 先把str split成string array，如果两个长度不等就是false，然后可以用map来存每个letter/ word对应的最后出现的index，
    如果map.put(letter/ word, index)不相等的话，就说明pattern 对不上，如果都能存下来就是true

7月打卡第十天，4道 105， 96， 114， 572

7/18 打卡第18天， 刷了3道题

143. Reorder List
linked list, 先找到中点，reverse后半段，再依次插到前半段中

201. Bitwise AND of Numbers Range
Bit Manipulation， 找到开头相同的所有位数

203. Remove Linked List Elements
linked list， 用个dummy ListNode 起头

Day 18:今天刷了四题。都是回文串问题
Longest Palindromic substring：用expand from center的思想用O(n)。还实现了Manacher算法，是optimal O(n).
Longest Palindrome：用hash map的思想，但是为了速度快。implement一定要用vector或array做counter
Pseudo-Palindromic path in a binary tree:跟上一题非常像，就是再加上一个dfs的思想就可以搞定。
Valid Palindrome II：双指针算法的很好应用。

Day6 三道题
binary search & two pointers

07/18 继续继续
今天回顾了之前刷的题 还完成以下
换酒问题 利用循环 里面进行除法和取余数
加一 需要考虑几种特殊情况 然后其实就是利用数组遍历
戳气球 动态规划 此题的状态不太好定义

做了5题。 回顾了merge sort的应用 和 一些字符串的处理。