在LintCode上刷题已经一个月了，一共AC了335道题。是时候开始总结一下了，顺便复习下刷过的题目。这篇总结会按照题目使用的算法进行分类，分别是Binary Search，Two Pointers，BFS，Binary Tree & Tree-based DFS，Combination-based DFS，Permutation-based DFS，Stack，Queue，Hash， Heap， Array，Matrix与Binary Indexed Tree。
Binary Search
先来看一道最经典的问题457. 经典二分查找问题，在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1。先来看下代码，这段代码就是二分查找的经典模板，后续所有二分查找题目我都是按照这个模板写的。
class Solution {
public:
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return: An integer
*/
int findPosition(vector<int> &nums, int target) {
// write your code here
if (nums.empty()) {
return -1;
}
int start = 0;
int end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] == target) {
return start;
} else if (nums[end] == target) {
return end;
}
return -1;
}
};
这个模板与其他写法的区别在于，while循环的条件为start + 1 < end，所以循环结束后要对最后剩下的两个位置进行分别的判断，得出最后答案。
下面来看另一个问题458. 目标最后位置. 这个问题与上一题的区别在于有多个满足条件的位置，返回第一个，类似的还有14. 二分查找。如何返回最后一个位置，其实只要对模板进行两处改动，第一处在while循环内，如果找到target，则让start = mid，第二处在while循环后的比较，先比较end位置的值，找到则返回，在比较start位置。代码如下。
class Solution {
public:
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return: An integer
*/
int lastPosition(vector<int> &nums, int target) {
// write your code here
int n = nums.size();
if (n == 0)
return -1;
if (nums[n - 1] < target or nums[1] > target)
return -1;
int start = 0, end = n - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] < target) {
start = mid;
} else if (nums[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (nums[end] == target) {
return end;
} else if (nums[start] == target) {
return start;
} else {
return -1;
}
}
};
同理对于查找第一次出现的位置，即14题，对这两处进行相应改动即可，代码如下。
class Solution {
public:
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
int binarySearch(vector<int> &nums, int target) {
// write your code here
int start = 0;
int end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] < target) {
start = mid;
} else if (nums[mid] > target) {
end = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
return start;
} else if (nums[end] == target) {
return end;
} else {
return -1;
}
}
};
类似的简单题还有如下这些，这些题均只要对模板进行少量改动即可通过。
458. 排序数组中最接近的元素
462. 目标出现总和
61. 搜索区间
二分查找类问题还有一种变形，即被查找数组不是一个排序数组，而是旋转排序数组，对于这种问题，来看一个例子62. 搜索旋转排序数组。对于这个问题，按照套路求出mid后，会出现四种情况，如果mid位置大于start位置，则如果target位置大小在start和mid中间，应该将end更新为mid，反之则说明target在mid和end中间，将start更新为mid。第二种情况类似，代码如下。
class Solution {
public:
/**
* @param A: an integer rotated sorted array
* @param target: an integer to be searched
* @return: an integer
*/
int search(vector<int> &A, int target) {
// write your code here
if (A.size() == 0) {
return -1;
}
int start = 0;
int end = A.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] >= A[start]) {
if (A[start] <= target and target <= A[mid]) {
end = mid;
} else {
start = mid;
}
} else {
if (A[mid] <= target and target <= A[end]) {
start = mid;
} else {
end = mid;
}
}
}
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
};
同样的问题还有159. 寻找旋转排序数组中的最小值。这题写起来并没有看起来那么麻烦，基本就是模板套路，代码如下。
class Solution {
public:
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
int findMin(vector<int> &nums) {
// write your code here
int start = 0;
int end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] < nums[end]) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] < nums[end]) {
return nums[start];
} else {
return nums[end];
}
}
};
补充两道题：
63. 搜索旋转排序数组 II
160. 寻找旋转排序数组中的最小值 II
另外一类题目是类似数学类的题目，像141. x的平方根，586. 对x开根II，428. x的n次幂，这类题目要求在一个连续的答案区间中进行搜索，这里给出586题的解法。
class Solution {
public:
/**
* @param x: a double
* @return: the square root of x
*/
double sqrt(double x) {
// write your code here
double left = 0.0;
double right = x;
double eps = 1e-12;
if (x < 1.0) {
right = 1.0;
}
while (right - left > eps) {
double mid = (left + right) / 2;
if (mid * mid < x) {
left = mid;
} else {
right = mid;
}
}
return left;
}
};
还有一类题目看起来并不会想到用二分查找，但其实使用二分会是解法变得非常简单，这类题目有时间会专门写一个专题。
网友评论