# 前言

LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题： 1、2、3题都是Medium的难度，大概是头条的面试题水准； 4、5题是Hard的难度，但是可以用取巧的做法，实现难度降到Medium和Easy的难度；

### 正文

#### 1、3Sum

```Example:
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 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

```Example:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]```

```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

```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```

```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

```Example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.```

```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;```

#### 5、Find Median from Data Stream

```Example:
findMedian() 返回 1.5
findMedian() 返回 2```

```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() {

}

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;```

172 篇文章86 人订阅

0 条评论

2692

2099

1523

36010

31710

1312

4058

3433

834

2966