1. Overarching Philosophy
(1) 用while loop缩小答案区间（问题规模），最后缩小到两个数
(2) 解决只剩下两个数的情况
2. 经典题型
找到(某一个)/第一个/最后一个 满足某种条件的 值/位置
2.1 二分答案 Binary Search on Target Number
给定一个排序（注意有可能有重复的element）数组，返回target出现的index
2.1.1 Classical
target出现的任意位置
2.1.2 First Position
target第一次出现的位置
2.1.3 Last Position
target最后一次出现的位置
2.2 二分位置 Binary Search on Index
2.2.1
2.2.2
2.3 模板(题型2.1.3)
public class Solution {
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return an integer
*/
public int lastPosition(int[] nums, int target) {
// Write your code here
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2; // !!!
// 3 cases to consider
if (nums[mid] == target) {
start = mid; // !!!
}
else if (nums[mid] < target) {
start = mid;
}
else {
end = mid;
}
}
if (nums[end] == target) {
return end;
}
if (nums[start] == target) {
return start;
}
// return -1 if none is found
return -1;
}
}
3. 时间复杂度 Time Complexity
3.1 计算
n - 规模为n的input
T(n) - 代表算法复杂程度的一个方程
O(1), O(n) - 可以看做所需时间常量
1. T(n) = T(n/2) + O(1) = O(lgn)
2. T(n) = T(n/2) + O(n) = O(n)
即"通过O(n)的时间把规模为n的问题变为n/2."
e.g., k^th largest element
3.2 面试中出现概率
O(1) 极少
O(logn) 几乎都是二分法
O(sqrt(n)) 几乎都是分级质因数
O(n) 高频
O(n*logn) 一般都需要排序，或和logn相关的数据结构：heap, Priority Queue
O(n^2) 数组、枚举、动态规划
O(n^3) 数组、枚举、动态规划
O(2^n) 组合(subset)
O(n!) 排列
面试中常常需要由时间复杂度倒推优化方法。
4. Recursion vs. While Loop
二分法上没区别，因为时间复杂度和空间深度都是logn
链表一定不要recursion，除非面试官要求! —> 避免stack overflow
以上为我在九章算法基础课程的学习小结，借此地与各位交流。
感谢九章算法的老师，成为了我coding interview preparation之行的灯塔，清晰明确地为我指明着方向。
明天更新2.2, 2.3。
