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

今天的题

日期: 7/23/2020
题目: [4]
260. Single Number III
802. Find Eventual Safe States
1203. Sort Items by Groups Respecting Dependencies
1462. Course Schedule IV

每日一题，加油加油。

今天刷了七题

Day 12 + Day13 打卡

两道two pointers

708. https://leetcode.com/problems/in ... rcular-linked-list/
edge case很多的题。注意细节

855. https://leetcode.com/problems/exam-room/
很难的medium

166. https://leetcode.com/problems/fraction-to-recurring-decimal/
太多edge case

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

148. Sort List
merge sort, 参考merge two sorted list

278. First Bad Version
二分法

283. Move Zeroes
双指针，其中一个记录0的开始存放位置

第5天, 5道题。 求加米

901. Online Stock Span
- mono stack

907. Sum of Subarray Minimums
- mono stack

260. Single Number III
- bitmask

545. Boundary of Binary Tree
- 非常麻烦的traversal...😓
- 含有state的PreOrder Traversal

173. Binary Search Tree Iterator
- design
- 用stack进行in-order traversal

July 第十九天打卡

Single Number III  数学题真的烧脑，二个bitmask 借这道题，第一个for loop 能保留出 只有二个unique数的 bitmask，下一个bitmask 用来partition 这二个数 hard
Random Pick with Weight 用binary Search 来借，一个prefix sum array 然后 lower_bound with that Input，find the proper Index
Next Greater Node in linkedList 和数组的做法一样，用单调栈来做，
Insert Delete GetRandom O(1)        O1, insert 很好实现，可是O(1) delete 可以用linkedlist 实现，但是不支持 random access，需要其他办法，因为vector 的delete 需要shift 整个数组(ON) 或者把那个slot marked as invalid，但是这样做 random access的时候就不是 O(1)而且整个数组会有fragmentation problem，bad！worst case insert 99 个，删除 98个。 你的数组里面就会有 98个洞(invalid) -> Really bad for performance 也导致了 random的操作是 worst O(N)

7.23 今天学习了Union Find，基本做法就是提前处理一下放进一个class然后在遍历的时候Union， find