分享我的Lintcode题解，目前进度244/248

zhuli19901106

Sort Colors
题意：给定一个只包含0,1,2的数组，用线性时间排序。
解法1：数数。
代码1：

class Solution{
public:
/**
* @param nums: A list of integer which is 0, 1 or 2
* @return: nothing
*/
void sortColors(vector<int> &nums) {
auto &a = nums;
int n = a.size();
vector<int> c(3, 0);
int i;
for (i = 0; i < n; ++i) {
++c[a[i]];
}
int j, k = 0;
for (i = 0; i < 3; ++i) {
for (j = 0; j < c[i]; ++j) {
a[k++] = i;
}
}
}
};

复制代码

复杂度1：时间O(N)，空间O(1)。

解法2：题目要求one-pass，O(1)空间。于是我想了一下就有了下面这个思路，但是真的写起代码来才发现bug不少，调了半天才搞对。
代码2：

// How tricky...
// It took me over 20 minutes to put it right.
#include <algorithm>
using namespace std;
class Solution{
public:
/**
* @param nums: A list of integer which is 0, 1 or 2
* @return: nothing
*/
void sortColors(vector<int> &nums) {
auto &a = nums;
int n = a.size();
int i, j;
int ii, jj;
ii = i = 0;
jj = j = n - 1;
while (i < j) {
if (a[i] == 0) {
swap(a[i], a[ii]);
++ii;
i = max(i, ii);
} else if (a[j] == 2) {
swap(a[j], a[jj]);
--jj;
j = min(j, jj);
} else if (a[i] == 2) {
swap(a[i], a[jj]);
--jj;
j = min(j, jj);
} else if (a[j] == 0) {
swap(a[j], a[ii]);
++ii;
i = max(i, ii);
} else {
++i;
}
}
while (ii <= jj) {
a[ii++] = 1;
}
}
};

复制代码

复杂度2：时间O(N)，空间O(1)。

zhuli19901106

Best Time to Buy and Sell Stock
题意：给定股价，允许你至多买卖一次，求最大获利。
解法：不断更新最低价，不断更新最大获利。
代码：

class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
int n = prices.size();
if (n == 0) {
return 0;
}
int minVal = prices[0];
int ans = 0;
int i;
for (i = 1; i < n; ++i) {
minVal = min(minVal, prices[i]);
ans = max(ans, prices[i] - minVal);
}
return ans;
}
};

复制代码

复杂度：时间O(N)，空间O(1)。

zhuli19901106

Best Time to Buy and Sell Stock II
题意：给定股价，允许你买卖无数次，但手里不能同时有两笔交易进行。求最大收益。
解法：只要涨价就买。现实中哪有这好事。
代码：

class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
int sum = 0;
int n = prices.size();
int i;
for (i = 0; i < n - 1; ++i) {
if (prices[i + 1] > prices[i]) {
sum += prices[i + 1] - prices[i];
}
}
return sum;
}
};

复制代码

复杂度：时间O(N)，空间O(1)。

zhuli19901106

Best Time to Buy and Sell Stock III
题意：给定股价，允许你至多进行两次交易，并且不能同时进行。求最大收益。
解法：从左向右算一次，从右向左算一次。拼起来就是最大收益。
代码：

// O(n) time and O(n) space
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
auto &a = prices;
int n = a.size();
if (n == 0) {
return 0;
}
int i;
vector<int> dl;
dl.resize(n);
dl[0] = a[0];
for (i = 1; i < n; ++i) {
dl[i] = min(dl[i - 1], a[i]);
}
dl[0] = 0;
for (i = 1; i < n; ++i) {
dl[i] = max(dl[i - 1], a[i] - dl[i]);
}
int ans = dl[n - 1];
int maxVal = a[n - 1];
for (i = n - 2; i >= 0; --i) {
maxVal = max(maxVal, a[i]);
ans = max(ans, maxVal - a[i] + dl[i]);
}
return ans;
}
};

复制代码

复杂度：时间O(N)，空间O(1)。

zhuli19901106

Combinations
题意：从1-N选出K个数，求所有组合。
解法：DFS。
代码：

class Solution {
public:
/**
* @param n: Given the range of numbers
* @param k: Given the numbers of combinations
* @return: All the combinations of k numbers out of 1..n
*/
vector<vector<int> > combine(int n, int k) {
ans.clear();
v.clear();
this->n = n;
this->k = k;
DFS(1, 0);
return ans;
}
private:
vector<vector<int> > ans;
vector<int> v;
int n, k;
void DFS(int idx, int cc) {
if (cc == k) {
ans.push_back(v);
return;
}
int i;
for (i = idx; i <= cc + n - k + 1; ++i) {
v.push_back(i);
DFS(i + 1, cc + 1);
v.pop_back();
}
}
};

复制代码

复杂度：时间O(C(N,K))，空间一样。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-22 21:54 编辑

Combination Sum II
题意：给定一个正整数数组，求其中所有加起来等于T的组合，数组中每个元素至多用一次。结果中不能包含重复组合。
解法：先数个数。然后DFS，注意剪枝。
代码：

#include <map>
using namespace std;
class Solution {
public:
/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
v.clear();
a.clear();
c.clear();
ans.clear();
n = num.size();
if (n == 0) {
return ans;
}
map<int, int> mm;
int i;
for (i = 0; i < n; ++i) {
++mm[num[i]];
}
for (auto it = mm.begin(); it != mm.end(); ++it) {
a.push_back(it->first);
c.push_back(it->second);
}
n = a.size();
t = target;
DFS(0, 0);
return ans;
}
private:
vector<int> a, c;
vector<int> v;
int n;
int t;
vector<vector<int> > ans;
void DFS(int idx, int sum) {
if (sum == t) {
ans.push_back(v);
return;
}
if (idx == n) {
return;
}
int i, j;
for (i = 0; i <= c[idx]; ++i) {
if (sum + i * a[idx] > t) {
break;
}
for (j = 0; j < i; ++j) {
v.push_back(a[idx]);
}
DFS(idx + 1, sum + i * a[idx]);
for (j = 0; j < i; ++j) {
v.pop_back();
}
}
}
};

复制代码

复杂度：时间O(N!)，空间一样。

zhuli19901106

Regular Expression Matching
题意：hard难度。实现正则表达式中的‘.’和‘*’元字符。
解法：真是名副其实的难题，第一次碰见这题时可以说毫无思路，后来搜答案连答案都没看懂。对比了好几个人的解法，才明白关键的地方在于“回溯”。比如.*可以匹配任意字串，那么某个位置匹配不下去了，我们就找到最近的一个*，看看能不能让*多覆盖一个字符，然后回溯到被覆盖的字符的下一位，继续往前。这就好比DFS+回溯的思路，只不过形式用的是循环，而不是递归。当然，此方法效率并不算高，因为每次只是多覆盖一位。要更优化的算法，感觉需要学好编译原理才行了。目前我还不会NFA。
代码：

#include <cstring>
#include <vector>
using namespace std;
class Solution {
public:
/**
* @param s: A string
* @param p: A string includes "." and "*"
* @return: A boolean
*/
bool isMatch(const char *s, const char *p) {
if (s == NULL || p == NULL) {
return false;
}
int ls = strlen(s);
int lp = strlen(p);
if (lp == 0) {
return ls == 0;
}
int i;
for (i = 0; i < lp - 1; ++i) {
if (p[i] == '*' && (i == 0 || p[i + 1] == '*')) {
// Invalid pattern
return false;
}
}
vector<int> ai, aj;
int j;
i = j = 0;
while (i < ls) {
if (j + 1 < lp && p[j + 1] == '*') {
ai.push_back(i);
aj.push_back(j);
j += 2;
} else if (p[j] == '.' || s[i] == p[j]) {
++i;
++j;
} else if (!aj.empty()) {
while (!aj.empty()) {
if (p[aj.back()] == '.' || p[aj.back()] == s[ai.back()]) {
i = ++ai.back();
j = aj.back() + 2;
break;
}
ai.pop_back();
aj.pop_back();
}
} else {
return false;
}
}
while (j + 1 < lp && p[j + 1] == '*') {
j += 2;
}
return j == lp;
}
};

复制代码

复杂度：如果有NS个*号，那么时间复杂度应该有O(N ^ NS)，空间O(N)。

zhuli19901106

Minimum Depth of Binary Tree
题意：给定一棵二叉树，求最浅的叶结点的深度。
解法：递归解决。注意递归的终止条件是叶结点。
代码：

#include <algorithm>
#include <climits>
using namespace std;
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int minDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int ans = INT_MAX;
if (root->left != NULL) {
ans = min(ans, minDepth(root->left) + 1);
}
if (root->right != NULL) {
ans = min(ans, minDepth(root->right) + 1);
}
return ans;
}
};

复制代码

复杂度：时间O(N)，空间O(N)。

zhuli19901106

Unique Characters
题意：求一个字符串中是否有重复字符。
解法1：统计个数。用位向量节省空间也可以，不过感觉这题玩出一堆花样也没什么意义。
代码1：

#include <cstring>
using namespace std;
class Solution {
public:
/**
* @param str: a string
* @return: a boolean
*/
bool isUnique(string &str) {
char a[256];
memset(a, 0, sizeof(a));
int n = str.length();
int i;
for (i = 0; i < n; ++i) {
if (a[str[i]]) {
return false;
}
a[str[i]] = 1;
}
return true;
}
};

复制代码

复杂度1：时间O(N)，空间O(1)。

解法2：排序，然后看相邻字符是否相等。
代码2：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param str: a string
* @return: a boolean
*/
bool isUnique(string &str) {
sort(str.begin(), str.end());
int n = str.length();
int i;
for (i = 0; i < n - 1; ++i) {
if (str[i] == str[i + 1]) {
return false;
}
}
return true;
}
};

复制代码

复杂度2：时间O(N * log(N))，空间O(1)。

zhuli19901106

Two Strings Are Anagrams
题意：求两个字符串的字符组成是否相同。
解法1：排序之后是否相等。
代码1：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param s: The first string
* @param b: The second string
* @return true or false
*/
bool anagram(string s, string t) {
// write your code here
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};

复制代码

复杂度1：时间O(N * log(N))，空间O(1)。

解法2：数数。
代码2：

#include <cstring>
using namespace std;
class Solution {
public:
/**
* @param s: The first string
* @param b: The second string
* @return true or false
*/
bool anagram(string s, string t) {
int c[256];
memset(c, 0, sizeof(c));
int len = s.length();
int i;
for (i = 0; i < len; ++i) {
++c[s[i]];
}
len = t.length();
for (i = 0; i < len; ++i) {
--c[t[i]];
}
for (i = 0; i < 256; ++i) {
if (c[i]) {
return false;
}
}
return true;
}
};

复制代码

复杂度2：时间O(N)，空间O(1)。

分享我的Lintcode题解，目前进度244/248

浏览过的版块