新人刷题打卡贴

已经刷了1个多月了才发现这里
发个打卡贴求大米

之前刷了200+题
现在再按花花酱的分类刷，觉得很不错：https://bit.ly/2E8yBHq

贴一个Binary index tree vs Segment tree的讲解
source: https://www.quora.com/How-does-o ... ree-or-Fenwick-Tree

Here are the things to keep in mind while deciding whether to use segment tree or binary indexed tree:
Anything that can be done using a BIT can also be done using a segment tree : BIT stores cumulative quantities for certain intervals. Segment tree stores cumulative quantities for those intervals and more. In particular, if we are creating a data structure to deal with an array of size N=2^K, the BIT will have cumulative quantities for N intervals whereas the segment tree will have cumulative values for 2N-1 intervals
There are things that a segment tree can do but a BIT cannot : A BIT essentially works with cumulative quantities. When the cumulative quantity for interval [i..j] is required, it is found as the difference between cumulative quantities for [1...j] and [1...i-1]. This works only because addition has an inverse operation. You cannot do this if the operation is non-invertible (such as max). On the other hand, every interval on a segment tree can be found as union of disjoint intervals and no inverse operation is required
A BIT requires only half as much memory as a segment tree : In cases where you have masochistic memory constraints, you are almost stuck with using a BIT
Though BIT and segment tree operations are both O(log(n)), the segment tree operations have a larger constant factor : This should not matter for most cases. But once again, if you have masochistic time constraints, you might want to switch from a segment tree to a BIT. The constant factor might become more of a problem if the BIT/Segment tree is multidimensional.
With practice, coding either will be very fast : If you have coded a segment tree 100 times, you will get it very fast the next time you do it. So no need to worry about code being long.

Personally, I invariably use segment trees to solve competitive programming problems. I have probably used BITs only 2-3 times in my entire life, and that was only because some sadist set problems with too tight time/memory constraints.

补充内容 (2019-3-16 12:56):
格式都没了，不好读的话可以去看原文

今天主要在看Kth largest/smallest
215. Kth Largest Element in an Array / 378. Kth Smallest Element in a Sorted Matrix / 668. Kth Smallest Number in Multiplication Table / 703. Kth Largest Element in a Stream
•        215. Brute Force – Sort:  Time: O(NlogN), Space: O(1)
•        215. Min Heap: keep K element min heap - Time: O(NlogK) / O(K+(N-K)logK), Space: O(K)
•        215. Max Heap: Build N element max heap, and pop K elements - O(N+KlogN), Space: O(N)
•        215. Quickselect: pivot and partition the array O(N)
o        Worst case O(N2), but can be resolved by randomization
•        Generally, use min heap for Kth largest. Keep K element in heap, then root is the answer.


补充内容 (2019-3-10 11:48):
378,668 Binary search 的performance 都会比heap 好

这周末打算做个challenge， 把这两门课的slides给过一遍
https://www.cs.princeton.edu/~rs/AlgsDS07/
https://web.stanford.edu/~ouster ... ring19/lectures.php
也欢迎大家推荐自己觉得比较好的课程

今天主要看BST
BST主要是inorder traversal, binary search, add/delete node

花花酱列表里的题：LC 98,530,700,701,230,99,108,501,450

补充内容 (2019-3-11 13:10):
晚上看了hashtable
2sum, 4sum, 560

今天时间不多
看了狗家的2道面筋
1. battleship
2. snapshot array

持續努力一起加油

今天刷了下linked list
2,445,24,206,141,142,21,23,147,148,707

linked list很多时候用一个slow,一个fast pointer找中点

先看了two pointer
11, 167, 977

Recursion
726,736,856

315 - BST and BIT
主要学习了binary index tree