前言
先说一些题外的东西吧。受到春跃大神的影响和启发，推荐了这个算法公开课给我，晚上睡觉前点开一看发现课还有两天要开始，本着要好好系统地学习一下算法，于是就爬起来拉上两个小伙伴组团报名了。今天听了第一节课，说真的很实用，特别是对于我这种算法不扎实，并且又想找工作，提高自己的情况。 那就不多说废话了，以后每周都写个总结吧，就趁着这一个月好好把算法提高一下。具体就从：课堂笔记、leetcode和lintcode相关习题、hdu和poj相关习题三个方面来写吧。希望自己能够坚持下来，给大家分享一些好的东西。
outline：
- 第一境界：会写程序
- Find First Position of Target
- Find Last Position of Target
- 第二境界：找到第一个/最后一个满足某个条件的位置/值
- Search a 2D Matrix
- Find Minimum in Rotated Sorted Array
- 第三境界：保留有解的那一半
- Find Peak Element
课堂笔记
二分查找这类题以前接触的也算是比较多的了，所以还算相对熟悉，但今天听老师讲过以后，还是觉得有了很多新的认识，最有印象的就是令狐老师讲的三个境界：
1. 第一境界：会写程序
这个境界我自认为在刷了那么多leetcode之后算是没有问题的了，套了不少模版，虽然还有一些边界问题考虑不周全，但是经过调试，应该没有什么问题，经过几次面试，也面到过Binary Seach。想必大家也有很好的基础。 正如老师说的，这个境界还是存在一些问题，比如解决二分程序的三大痛点、权衡递归与非递归。 对于第一个问题，其实就是start和end的位置选取，比如容易进入死循环，或者容易分不清楚到底应该是start = mid还是start = mid+ 1等。以下给出一个代码模版，这个也是我之前写二分问题经常会写的样子：
int start = , end = nums.size() - ;
while (start < end){
int mid = (start + end)/;
if (...) {...}
else if (...) {...}
else {...}
}
想必大家都会把循环条件写成start < end或者start <= end这样的，这样在一些情况下也确实没有问题（这里直接上一个题）：
Find First Position of Target
http://www.lintcode.com/zh-cn/problem/first-position-of-target/
给定一个排序的整数数组（升序）和一个要查找的整数
target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。样例
在数组
[1, 2, 3, 3, 4, 5, 10]中二分查找3，返回2。
这个题应该是Binary Search最基础的题，直接套用模版就可以，以下是这个题的代码（Bug Free）：
int binarySearch(vector<int> &array, int target) {
if (!array.size()) return -;
int start = , end = array.size() - ;
while (start < end) {
int mid = (start + end) >> ;
if (array[mid] < target) {
start = mid + ;
} else if (array[mid] > target) {
end = mid -;
} else {
end = mid;
}
}
if (array[start] == target) return start;
return -;
}
因为比较简单，就不再多说了，这里需要注意的几个点是，int mid = (start + end) >>1;其实就是int mid = (start + end)/2;因为在面试中如果会位运算的话，还是能够给面试官留下很好的印象。有的人说直接加起来除以2会溢出，其实start和end不会大到超过int的最大值的，因为一个vector也不会去开辟那么大的空间，但是写成`int mid = (end - start)/2 + start;`也能显得你比较不错。综上，两种方法都可以。 在这个题中因为是找第一个与target相等的值，所以用这种方法不会出问题，但是在考虑下面的题，就会出现问题：
Find Last Position of Target
http://www.lintcode.com/zh-cn/problem/last-position-of-target/
给一个升序数组，找到target最后一次出现的位置，如果没出现过返回
-1样例
给出 [1, 2, 2, 4, 5, 5].
target =
2, 返回2.target =
5, 返回5.target =
6, 返回-1.
错误代码如下：
while (start < end) {
int mid = ( start + end ) >>;
if (A[mid] < target) {
start = mid + ;
} else if ( A[mid] > target) {
end = mid -;
} else {
start = mid;
}
}
这里如果这样写的话，代码就会进入死循环，因为在求mid的时候是向左边取整的。考虑这样的一个情况[...,5,5]，假设target为5，那么start就会一直向右靠近，最后到n-2的位置，而end此时为n-1，再次进入循环mid等于n-2，所以就进入了死循环。 根据课上老师所说的，建议大家写成start + 1 < end，最后再判断start和end（按照所需先后判断）即可，这种写法适用于所有的情况，不容易出现问题。 ps. 这里把条件写成如下也可行：
while (start + < end) {
int mid = (start + end)>>;
if (A[mid] > target) {
end = mid;
} else {
start = mid;
}
}
因为start和end不管是否包括mid值都不影响最后的结果。 这个境界需要理解一个重点： 二分法实际上就是把区间变小的问题，把一个长度为n的区间变为n/2，然后再变小，即：
T(n) = T(n/) + O() = O(logn)
通过O(1)的时间，把规模为n的问题变为n/2 当面试的时候，有O(n)的解，如果面试官需要你进一步优化，那么很大可能就是需要用二分O(logn)的方法来做。 实际上的步骤：
**区间缩小-> 剩下两个下标->判断两个下标**
**注：不要把缩小区间和得到答案放在一个循环里面，容易出问题，增加难度**
2. 第二境界：找到第一个/最后一个满足某个条件的位置/值
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数。
样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]给出
target = 3，返回true
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if (!matrix.size()||!matrix[].size()) return false;
int start = , end = matrix.size() - ;
while (start + < end) {
int mid = (end - start)/ + start;
if (matrix[mid][] < target) start = mid;
else end = mid;
}
int new_start = ,new_end = matrix[].size()-;
int index = matrix[end][] <= target ?end:start;
while (new_start + < new_end) {
int mid = (new_end - new_start)/ + new_start;
if (matrix[index][mid] > target) new_end = mid;
else if (matrix[index][mid] < target)
new_start = mid;
else return true;
}
if (matrix[index][new_end] == target) return true;
if (matrix[index][new_start] == target) return true;
return false;
}
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if (!matrix.size()||!matrix[].size()) return false;
int m = matrix.size();
int n = matrix[].size();
int start = , end = n * m - ;
while (start + < end) {
int mid = (end - start)/ + start;
int x = mid / n;
int y = mid % n;
if (matrix[x][y] > target) {
end = mid;
} else {
start = mid;
}
}
int x = start / n;
int y = start % n;
if (matrix[x][y] == target) {
return true;
}
x = end / n;
y = end % n;
if (matrix[x][y] == target) {
return true;
}
return false;
}
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。
样例
给出[4,5,6,7,0,1,2] 返回 0
int findMin(vector<int> &num) {
if (!num.size()) return ;
int start = , end = num.size() - ;
int target = num[end];
while (start + < end) {
int mid = (end - start)/ + start;
if (num[mid] <= target) {
end = mid;
}
else {
start = mid;
}
}
if (num[start] <= target) {
return num[start];
}
else {
return num[end];
}
}
给出一个整数数组(size为n)，其具有以下特点：
- 相邻位置的数字是不同的
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定P是峰值的位置则满足
A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。样例
给出数组
[1, 2, 1, 3, 4, 5, 7, 6]返回1, 即数值 2 所在位置, 或者6, 即数值 7 所在位置.
第一种情况：当前点就是峰值，直接返回当前值。
第二种情况：当前点是谷点，不论往那边走都可以找到峰值。
第三种情况：当前点处于下降的中间，往左边走可以到达峰值。
第四种情况：当前点处于上升的中间，往右边走可以达到峰值。
分析了四种情况，那么就容易把有答案的一半保留下来了，接下来就判断是否能够找到峰值即可。代码如下（Bug Free）:
int findPeak(vector<int> A) {
if (!A.size()) return ;
int start = ;
int end = A.size() -;
while (start + < end) {
int mid = (end - start)/ + start;
if (A[mid] > A[mid - ] && A[mid] > A[mid + ]) {
return mid;
} else if (A[mid] <= A[mid+] && A[mid] >= A[mid -]) {
start = mid;
} else if (A[mid] >= A[mid+] && A[mid] <= A[mid -]) {
end = mid;
} else {
start = mid;
}
}
if (start >= && A[start] > A[start - ] && A[start] > A[start + ]) return start;
if (end <= A.size()- && A[end] > A[end-] && A[end] > A[end+]) return end;
}
这道题的难点其实就是把各种情况考虑一下，然后把有答案的部分保留下来，基本上就没有问题了。
总结
本文只是挑选了一些比较好的课上的题进行了讲解，还有部分题没有写出来，也会在后续的博客中。
对于我个人而言，二分法算是比较熟悉的一个方法，之前在做微软校招第一题的时候用的就是二分的方法。在面试中也是比较常用到的一种方法，因为总有那么一种说法嘛：比0(n)还要快的算法复杂度，那必须就是0(logn)了（这里说的是在一般的面试情况下）那么O(logn)就必然要考虑二分的方法来做了。一般都会与一些排序的序列、在一段有规则的序列等情况中找到符合某个条件的位置/值。这个模块还是需要多练习，然后就能够很好上手了，如果想要能够在算法面试中有更好的突破，还是需要去解决一些难一点的题，诸如poj或者hdu这样的应用场景的题。
这也是本人第一次认真写一个技术长文，虽然也没有什么特别深奥的东西，读到这里说明你也是很给我面子的了，之后还会继续更新一些自己的想法和一些好的题目，希望大家多多支持！