Q1: pow(x,n) x是double 类型， n 是int 类型
======》》》》 divide and conquer思想： n 二分 求解
Q2 ： 求sqrt(x)， x>=1 int
======》》》》divide and conquer思想：binary search, 1 - n/2,
Greedy: 不作要求，面试中很难想，扩展思路
Q1: 买卖股票，最多只买卖一次，得到最大利益（差价）
Q2: 无限买卖股票，买之前必须卖光， 能得到的最大利益是多少？
Q3： 一组线段，线段i头尾 s(i) , t(i)，设计一个算法，挑出最多的线段组合，保证线段间没有重合。
interval ： 排序： 按start time 排序，按end time 排序
Q4: 一个数组每个元素代表一个文件的长度，把这些文件Merge，怎样merge 的cost 最小？
Haffman encoding， 小的元素要放成merge 次数最多的
Q5：Jump Game
1. 从起点能否走到终点：
2. 走的到终点的最短步数
Q6： coin问题， 钱数换成硬币， 怎样才能得到minimal num of coins 的换法， 硬币面值为（1，5，10，25），硬币不限量
1. DFS
2. Greedy的算法，从大的开始试， 但是，可能有些硬币系统是不work的，（1,3,4）这种硬币系统是不行的，比如说6
No comments:
Post a Comment