1. longest increasing sequence
意思就是给你一个数列 找出最长连续字串的长度
比如 -1 2 -2 5 3 9 8 10
答案 是5, -1 2 3 9 10
I DP, 用S[i] 代表 以数组元素a[i]结尾的最长sequence的长度, 很好列出 规律表达式, Time Complexity O(N^2), 这个方法虽然时间复杂度不是最优, 但是好处是 我们可以逆向回去打印出 这个longest increasing sequence的元素分别是什么, 这也是我下面要介绍的方法所不能做到的.
II 如果考虑用 S[i] 代表 长度为 i 的 increasing sequence的 结尾元素 的最小值, 那么我们知道肯定有 S[k+1]>S[k]>S[k-1]>….S[0], 所以每次我们有新的元素插入, 其实都相当于插入一个有序数组, 那么就用binary search找到要插入的那个index就好了. 所以时间复杂度是 O(nlogn)
一般对于这个数组的赋初值都是赋一个很大的值, 所以其实每次不是要对整个长度n进行 binary search, 只要对你修改到的最大index之内的数组进行binary search就好了, 时间复杂度的计算其实是 log 1+ log 2+….log n = log(n!), which is O(nlog), 这样其实相当于把常数项降低了.
2. 给你一个int 数, 找出其中 bit pattern 中’1’的个数
a. count = count + n>>1;
n = n>>1; 和int 的 总bit数目线性关系
b. for( ; n; n = n&(n-1))
count ++; 和这个数中有多少个’1′ 线性关系
3. Reverse a single linked-list
4. Reverse a double linked-list
5. How to implement using memory without initialization
编程珠玑column1 exercise 8
具体的应用是 用空间来换时间
FYI:
每日5题 is back, and I will try my best to keep on, thanks