前言
LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题：
1、2、3题都是Medium的难度，大概是头条的面试题水准；
4、5题是Hard的难度，但是可以用取巧的做法，实现难度降到Medium和Easy的难度；
正文
1、3Sum
题目链接
题目大意：给出一个数组nums，数组包括n个整数（可能有重复）；
现在需要从数组中选择三个数a、b、c，使得a+b+c=0；
输出所有可能性的组合；（重复的只输出一次）
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
题目解析：
题目可以分解为两个子问题：
1、找到整数a、b、c，使得a+b+c=0；
2、重复的a、b、c只输出一次；
子问题1同样可以分解为两个问题：1、找到两个整数a、b，判断c=-a-b的数字是否存在；
那么可以用两个for循环确定a、b，再用一个for循环判断c=-a-b是否存在；
复杂度较高，但是可以解决，考虑子问题2；
子问题2可以通过缓存已经存在的解，每次进行遍历匹配解决；
至此，我们有一个不太优化的解决方案。
优化思路：
a、b、c重复因为有a+b+c=0的条件，只要a、b相同，则c必然相同；
那么可以先对数组nums排序，得到有序的数组；
接着对于每个数字nums[i]，从[i+1, n]区间选出两个数字x和y(x<y)，使得nums[i]+x+y=0；（a=nums[i], b=x, c=y）
可以知道，随着x的增大，y会不断变小；那么从i+1开始向右选择x，从n开始向左选择y，可以在O(N)的复杂度内遍历完所有组合；
当枚举完a=nums[i]的可能后，令a=nums[k]，k>i并且nums[k]!=nums[i]，这样也可以在O(N)的复杂度内遍历完a的所有可能；
总的时间复杂度是O(N^2)；
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int n = (int)nums.size();
int i = 0;
while (i < n) {
int x = i + 1;
int y = n - 1;
while (x < y) {
int sum = nums[i] + nums[x] + nums[y];
if (sum == 0) {
vector<int> tmp = {nums[i], nums[x], nums[y]};
ret.push_back(tmp);
while (x < n) {
++x;
if (tmp[1] != nums[x]) {
break;
}
}
}
else if (sum < 0) {
++x;
}
else { // sum > 0
--y;
}
}
while (i < n) {
++i;
if (nums[i] != nums[i - 1]) break;
}
}
return ret;
}
}leetcode;
2、Generate Parentheses
题目链接
题目大意：
给出一个整数n，求n对括号组成的，所有可能的合法字符串；
例如，n=3，则有：
Example:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题目解析：
合法的字符串指的是左右括号数量相同，并且每一个左括号，都能在其右边找到一个右括号；
类似")("这样就是不合法的字符串。
理解定义之后，考虑长度为2*n的字符串中第i个字符应该怎么填：
假设此刻已经具有的左括号有left个，右括号有right个；
如果left>right，比如说"(()"，则可以放左括号=>"(()("，也可以放右括号=>"(())"
如果left==right，比如说"(())"，那么只能放左括号=>"(())"
如果left<right，此时为不合法序列，我们不应该出现这种情况；
在此过程中，需要注意保证左右括号的数量不要超过n个；
class Solution {
public:
void dfs(vector<string> &ret, string &str, int left, int right) {
if (left > 0) {
str.push_back('(');
dfs(ret, str, left - 1, right);
str.pop_back();
}
if (left < right && right > 0) { // 必须保证right > left，这样的字符串才是合法的
str.push_back(')');
dfs(ret, str, left, right - 1);
str.pop_back();
}
if (left == 0 && right == 0) {
ret.push_back(str);
}
}
vector<string> generateParenthesis(int n) {
vector<string> ret;
string tmp;
dfs(ret, tmp, n, n);
return ret;
}
}leetcode;
3、Kth Largest Element in an Array
题目链接
题目大意：
一个存放乱序整数的数组，找到数组中第k大的数字；
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
题目解析：
从样例的数据可以看出，第k大就是从小到大排序，第k个的数字；
那么一种简单的办法就是对数组进行排序，然后输出第k个数字；
还有一种做法是建一个大小为k的最大堆，然后遍历数组，把每个数字放进堆中，如果堆大小超过k，则弹出堆顶的数字；
这样一轮过后，就有一个大小为k的最大堆，堆顶就是第k大的数字；
最后是一种理论（平均）最优解法，从数组中取第一个数字x，遍历数组，按照<x和>x分成两组left和right；
如果left==k-1，那么数字x就是第k大数字；
如果left<k-1，那么从right中继续这个筛选过程；（注意right中筛选不是第k个大，要去掉left+1的数量）
如果left>k-1，那么从left中继续这个筛选过程；
这里附上最简单的实现，两行代码；
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
4、Number of Digit One
题目链接
题目大意：
给出一个数字n（n<1000)，求出在区间[1, n]中所有数字中，1的数量。
Example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
题目解析：
因为数字n比较小，考虑直接通过数学方式来解决。
例如数字315，可以分割成个十百三个位数上1的数量来分别统计；
个位数：315个1;
十位数：31个10；
百位数：3个100；
每个位数上可能有0、1、大于1的情况，(x+8)/10可以过滤出大于1的情况；
在特别考虑每个位数为1的情况，比如315中的十位数；
上面的统计方式还漏掉了310~315的三种情况，这种情况可以用x%i + 1来过滤出来。
class Solution {
public:
int countDigitOne(int n) {
int ret = 0;
for (long long i = 1; i <= n; i *= 10) {
ret += (n / i + 8) / 10 * i; // 对应位数上1的数量；
if (n / i % 10 == 1) {
ret += n % i + 1;
}
}
return ret;
}
}leetcode;
其他解法：
题目正解的做法是采用 数位dp的思想。
先预处理出1, 10, 100, 1000 ... 这些数字以下的1的数量；
再从左到右遍历n的字符，求出1的数量。
这才是hard难度的解法，但是学习价值不大。
5、Find Median from Data Stream
题目链接
题目大意：
实现一个数据结构，其中有两个函数：
1、addNum 添加一个数字；
2、findMedian 找到已有数字的中位数；
Example:
addNum(1)
addNum(2)
findMedian() 返回 1.5
addNum(3)
findMedian() 返回 2
题目解析：
插入，可以用链表；
找中位数，可以用朴素的遍历；
这样，每次的时间复杂度O(N)。
另外一种简单的实现是：把链表分成两部分，维护一个最大堆，一个最小堆。
这样只要每次看看数字的大小，分别放到左右两个堆就行；
为了方便寻找中位数，要保证最大堆和最小堆的size大小差别不超过1；
每次操作的复杂度都是O(logN)；
struct Node {
int first, second;
Node(){}
Node(int f, int s) {
first = f;
second = s;
}
bool operator < (const Node tmp) const {
if (first != tmp.first) {
return first > tmp.first;
}
else {
return second > tmp.second;
}
}
};
class MedianFinder {
public:
priority_queue<int> little;
priority_queue<int, vector<int>, greater<int> > big;
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
little.push(num);
big.push(little.top());
little.pop();
if (little.size() < big.size()) {
little.push(big.top());
big.pop();
}
cout << findMedian() << endl;
}
double findMedian() {
double ret = 0.0;
if (little.size() == big.size()) {
ret = (little.top() + big.top()) / 2.0;
}
else {
ret = little.top();
}
return ret;
}
}leetcode;
其他解法：
老老实实用链表+遍历。
总结
做LeetCode的题目有一些数据结构一定要掌握，就是堆！
算法面试题无非就是问思路和实现，堆是一种高效的数据结构，解题的基础数据结构工具之一，同时具备使用非常简单的特点。
熟悉常用数据结构和具体使用场景，比如说题目2用到了栈的思想，题目3是堆的思想，题目5是链表的实现。
