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

8.4 打卡第3天
做了3道新题，其中两道hard题，脑阔秃了
（1）同向双指针，求subarray sum >= x的个数，到临界值可以判定后面的subarray全都满足，count += n - r
（2）二分答案，start=0，end=allSum
（3）two sum vii，按绝对值来二分搜索，注意最终要判断start, end, start-1, end+1四个值，因为start,end可能只是绝对值和target相等

今天打卡，写了4到，都是硬核题啊

Range Sum Query - Mutable 硬核写segment tree，还是一维的基本都写炸了
Minimum Height Trees 用类似拓扑排序的思想解决了，后来参考下答案发现可以过两遍bdfs然后找到最长路径的中点
Burst Balloons 用divide and conque解决，加个memo
Super Ugly Number 跟ugly number系列的题有仇，每次都会写炸

今天七道题， 大家加油！

Day 4

342. Power of Four, bit运算相关的trick
109. Convert Sorted List to Binary Search Tree, linked list中寻找middle point 从in order traversal recover bst

speed_secret20 发表于 2020-8-5 12:40
8月4号 刷题第四天 打卡第四天
刷题7道

有的，用二分，你咋知道我用的n^2...

Backtracking 相关题目：
factor combination : 两种思路， 时间复杂度注意
subset: 每一个数字取或者不取
Generate Parentheses： 注意左括号顺序

8.5打卡，leetcode 剑指Offer 45, 562, 337, 926

大家加油呀

主攻tree和一些需要数学知识的题
对于tree的traversal，要明确recursion方程的具体用途，千万别陷入无限循环的trap中

对于计算2个date之间的天数，找一个起始点1900-01-01，然后算各自与起始点的差值，利用差值再计算出2个date之间的天数。

38 Count & Say

Recursion

Time complexity: O(2^n)
Space complexity: O(2^(n-1))

Iteration的方法也要会

231 Power of Two

https://leetcode.com/articles/power-of-two/

recursion/ loop的写法是logN, space O(1)
熟练运用bit manipulation， time complexity O(1)

The idea is to discuss such bitwise tricks as
* How to get / isolate the rightmost 1-bit : x & (-x).
* How to turn off (= set to 0) the rightmost 1-bit : x & (x - 1)

Method 1: x & (-x) == x

x = 0,  0000000
x = 1,   0000001
x = 2,  0000010
x = 4,  0000100

-x = ~x+1
x = 1. -x = 111111110 + 1
Find right hand first available 0 to add on 1
Which is the first available 1 in x

After & operation,
The only nonzero digits is the first available 1 in x

特殊情况，0，要单独列出来

Method 2: x & (x-1) == 0
特殊情况，0， 要单独列出来

记得要int转换成long！！


359 Logger Rate Limiter

Java HashMap
Time Complexity: O(1), check, add, replace all O(1)
Space Complexity: O(N)

1    HashMap
Fast, but the disadvantage is memory usage.
Memory Usage never stops growing.
2   Two HashMaps
https://leetcode.com/problems/lo ... Map-Solution-with-O(1)-time-and-little-memory
One old, one new
Define the start time of new is latest

timestamp 和  latest之间小于10
所以我们可以很肯定 只要cache new 有message肯定不行

为什么我们需要一个old一个new?
当我们有timestamp-latest>10的时候，并不能清空new

3   Queue & Set
Set纯粹是保存所有的messages
queue给人一种时间的感觉

4    Radix Sort & Buckets
也是一个很有趣的解法
https://leetcode.com/problems/lo ... ilar-to-Hit-Counter

5 Concurrency & Thread Safety