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

zhuli19901106

strStr
题意：实现strstr函数，也就是查找字符串s里是否出现了字符串t。考察字符串匹配。
解法1：暴力解法
代码1：

// The brute-force solution.
#include <cstring>
using namespace std;
class Solution {
public:
/**
* Returns a index to the first occurrence of target in source,
* or -1 if target is not part of source.
* @param source string to be scanned.
* @param target string containing the sequence of characters to match.
*/
int strStr(const char *source, const char *target) {
if (source == NULL || target == NULL) {
return -1;
}
int ls = strlen(source);
int lt = strlen(target);
if (lt > ls) {
return -1;
}
int i, j;
for (i = 0; i + lt <= ls; ++i) {
for (j = 0; j < lt; ++j) {
if (source[i + j] != target[j]) {
break;
}
}
if (j == lt) {
return i;
}
}
return -1;
}
};

复制代码

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

解法2：神器名叫KMP。最好能理解next数组的思想，这才是KMP算法的巧妙之处。next数组还可以用来解相关的变形题目。比如这题
https://leetcode.com/problems/shortest-palindrome/
代码2：

// The KMP solution.
#include <cstring>
using namespace std;
class Solution {
public:
/**
* Returns a index to the first occurrence of target in source,
* or -1 if target is not part of source.
* @param source string to be scanned.
* @param target string containing the sequence of characters to match.
*/
int strStr(const char *source, const char *target) {
if (source == NULL || target == NULL) {
return -1;
}
if (target[0] == 0) {
return 0;
}
ls = strlen(source);
lt = strlen(target);
s = source;
t = target;
if (lt > ls) {
return -1;
}
next = new int[lt + 1];
memset(next, 0, (lt + 1) * sizeof(int));
getNext();
int ans = KMPMatch();
delete[] next;
return ans;
}
private:
int* next;
int ls;
int lt;
const char *s;
const char *t;
void getNext() {
int i, j;
i = 0;
j = -1;
next[0] = -1;
while (i < lt) {
if (j == -1 || t[i] == t[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
int KMPMatch() {
int i, j;
i = j = 0;
while (i < ls) {
if (j == -1 || s[i] == t[j]) {
++i;
++j;
} else {
j = next[j];
}
if (j == lt) {
return i - lt;
}
}
return -1;
}
};

复制代码

复杂度2：O(N + M)时间，O(M)空间

zhuli19901106

Binary Search
题意：在有序数组中二分搜索一个元素，要求返回此元素首次出现的位置。
解法：既然要求首次出现的位置，那么就得用lower_bound，此处还是推荐自己实现一个。
代码：

class Solution {
public:
/**
* @param nums: The integer array.
* @param target: Target number to find.
* @return: The first position of target. Position starts from 0.
*/
int binarySearch(vector<int> &array, int target) {
int n = array.size();
if (target < array[0] || target > array[n - 1]) {
return -1;
}
if (target == array[0]) {
return 0;
}
int ll, rr, mm;
ll = 0;
rr = n - 1;
while (rr - ll > 1) {
mm = (ll + rr) / 2;
if (array[mm] < target) {
ll = mm;
} else {
rr = mm;
}
}
return array[rr] == target ? rr : -1;
}
};

复制代码

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

zhuli19901106

Permutations
题意：给定一个数组，求可以构成的所有排列。按结果来看，数组中应该没有重复元素。
解法1：元素个数为N，则共有N!个排列。先排好序，然后调用N次next_permutatio即可。
代码1：

// The iterative solution
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int> nums) {
ans.clear();
int n = nums.size();
if (n == 0) {
return ans;
}
sort(nums.begin(), nums.end());
int f = 1;
int i;
for (i = 2; i <= n; ++i) {
f *= i;
}
for (i = 0; i < f; ++i) {
ans.push_back(nums);
next_permutation(nums.begin(), nums.end());
}
return ans;
}
private:
vector<vector<int> > ans;
};

复制代码

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

解法2：使用递归实现，既不方便，也不高效。只是为了试试递归怎么写才刻意写的。
代码2：

// The recursive solution
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int> nums) {
ans.clear();
n = nums.size();
if (n == 0) {
return ans;
}
sort(nums.begin(), nums.end());
b.resize(n, false);
DFS(nums, 0);
return ans;
}
private:
vector<vector<int> > ans;
vector<int> p;
vector<bool> b;
int n;
void DFS(vector<int> &nums, int idx) {
if (idx == n) {
ans.push_back(p);
return;
}
int i;
for (i = 0; i < n; ++i) {
if (b[i]) {
continue;
}
p.push_back(nums[i]);
b[i] = true;
DFS(nums, idx + 1);
b[i] = false;
p.pop_back();
}
}
};

复制代码

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

补充内容 (2015-7-21 19:10):
回复水逼一枚：不用API也可以啊，自己实现next_permutation即可。另外，讨论最好用回帖的形式吧，否则我没地方回复。

zhuli19901106

Permutations II
题意：给定一个可能包含重复元素的数组，求所有可能的排列。
解法：自己实现一个next_permutation。时间复杂度为O(N)。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
vector<vector<int> > permuteUnique(vector<int> &nums) {
ans.clear();
int n = nums.size();
if (n == 0) {
return ans;
}
sort(nums.begin(), nums.end());
do {
ans.push_back(nums);
} while (nextPermutation(nums));
return ans;
}
private:
vector<vector<int> > ans;
bool nextPermutation(vector<int> &a) {
int n = a.size();
int i, j;
for (i = n - 2; i >= 0; --i) {
if (a[i] < a[i + 1]) {
break;
}
}
if (i < 0) {
return false;
}
j = n - 1;
while (a[j] <= a[i]) {
--j;
}
swap(a[i], a[j]);
reverse(a.begin() + i + 1, a.end());
return true;
}
};

复制代码

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

zhuli19901106

Subsets
题意：给定一个集合，求它的幂集。
解法1：有N个元素，则有2^N个子集，从0~2^N - 1逐个遍历即可。
代码1：

// The iterative solution
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsets(vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return ans;
}
vector<int> s;
int i, j;
int n2 = 1 << n;
for (i = 0; i < n2; ++i) {
for (j = 0; j < n; ++j) {
if (i & (1 << j)) {
s.push_back(nums[j]);
}
}
ans.push_back(s);
s.clear();
}
return ans;
}
private:
vector<vector<int> > ans;
};

复制代码

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

解法2：使用递归，写法也比较简单。每个元素都有选或者不选两种。
代码2：

// The recursive solution
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsets(vector<int> &nums) {
n = nums.size();
if (n == 0) {
return ans;
}
DFS(nums, 0);
return ans;
}
private:
vector<vector<int> > ans;
vector<int> s;
int n;
void DFS(vector<int> &a, int idx) {
if (idx == n) {
ans.push_back(s);
return;
}
DFS(a, idx + 1);
s.push_back(a[idx]);
DFS(a, idx + 1);
s.pop_back();
}
};

复制代码

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

zhuli19901106

Subsets II
题意：给定一个multiset，求其所有子集。
解法：因为可以包含重复元素，所以此时子集的个数不一定是2 ^ N个了，所以改用递归。最好把诸如[2, 2, 2]这样的重复元素变成<2, 3>这样的键值对，因为可以在递归时提高效率。
代码：

// The recursive solution
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsetsWithDup(const vector<int> &S) {
ans.clear();
n = S.size();
if (n == 0) {
return ans;
}
int i, j;
int cc;
vector<int> ss;
for (i = 0; i < n; ++i) {
ss.push_back(S[i]);
}
sort(ss.begin(), ss.end());
a.clear();
c.clear();
i = 0;
while (i < n) {
j = i + 1;
while (j < n && ss[i] == ss[j]) {
++j;
}
cc = j - i;
a.push_back(ss[i]);
c.push_back(cc);
i = j;
}
n = a.size();
DFS(0);
return ans;
}
private:
vector<vector<int> > ans;
vector<int> s;
vector<int> a;
vector<int> c;
int n;
void DFS(int idx) {
if (idx == n) {
ans.push_back(s);
return;
}
int i, j;
for (i = 0; i <= c[idx]; ++i) {
for (j = 0; j < i; ++j) {
s.push_back(a[idx]);
}
DFS(idx + 1);
for (j = 0; j < i; ++j) {
s.pop_back();
}
}
}
};

复制代码

复杂度：如果每个不重复元素A{i}出现次数为C{i}，那么时间复杂度为PI(C{i})。（PI是连乘）

stellari

zhuli19901106 发表于 2015-7-18 15:50
A + B Problem
题意：求32位整数之和A + B
解法：直接相加就不提了。此处可以考虑用全加器的原理，纯位操 ...

这里没有使用循环。有什么特殊原因吗？

zhuli19901106

Search a 2D Matrix
题意：给定一个二维数组，每行都是有序的，而且每行的末尾都不大于下一行的行首。在这个数组中查找一个值。
解法：其实就是要我们展开成一维数组，然后二分搜索。
代码：

class Solution {
public:
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* [url=home.php?mod=space&uid=160137]@return[/url] a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int n, m;
n = matrix.size();
if (n == 0) {
return false;
}
m = matrix[0].size();
if (m == 0) {
return false;
}
if (target < matrix[0][0] || target > matrix[n - 1][m - 1]) {
return false;
}
int ll, rr, mm;
ll = 0;
rr = n * m - 1;
while (ll <= rr) {
mm = (ll + rr) / 2;
if (matrix[mm / m][mm % m] < target) {
ll = mm + 1;
} else if (matrix[mm / m][mm % m] > target) {
rr = mm - 1;
} else {
return true;
}
}
return false;
}
};

复制代码

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

stellari

zhuli19901106 发表于 2015-7-18 16:26
Kth Largest Element
题意：求一个数组中，第K大的数。允许交换数组中的元素。
解法：根据快排改造得到快 ...

quickSelect可以简单地写成迭代形式的啊。那样空间复杂度就是O(1)了。

zhuli19901106

stellari 发表于 2015-7-18 22:02
这里没有使用循环。有什么特殊原因吗？

因为题目要求不准用加法，用++i或者foreach之类的实质上都要用到加法，所以我特意按照verilog的风格写了32个函数。

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

点评

浏览过的版块