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

zhuli19901106

First Bad Version
题意：猜数字。
解法：二分不解释。
代码：

/**
* class VersionControl {
* public:
* static bool isBadVersion(int k);
* }
* you can use VersionControl::isBadVersion(k) to judge whether
* the kth code version is bad or not.
*/
class Solution {
public:
/**
* @param n: An integers.
* @return: An integer which is the first bad version.
*/
int findFirstBadVersion(int n) {
int ll = 1;
int rr = n;
if (VersionControl::isBadVersion(ll)) {
return ll;
}
int mm;
while (rr - ll > 1) {
mm = ll + (rr - ll) / 2;
if (VersionControl::isBadVersion(mm)) {
rr = mm;
} else {
ll = mm;
}
}
return rr;
}
};

复制代码

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

zhuli19901106

Find Peak Element
题意：给定一个数组，保证相邻元素不相等，并且A[0] < A[1] && A[A.length - 2] > A[A.length - 1]。请找出一个大于左右邻居的元素。
解法1：顺着扫一遍。
代码1：

// The O(n) solution.
class Solution {
public:
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
int findPeak(vector<int> A) {
for (i = 1; i < n - 1; ++i) {
if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
return i;
}
}
return -1;
}
};

复制代码

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

解法2：为什么可以二分？因为左端小于，右端大于，至少会存在一个位置是小于和大于汇合的地方。
代码2：

// The O(log(n)) solution
class Solution {
public:
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
int findPeak(vector<int> A) {
int n = A.size();
int ll, rr, mm;
ll = 0;
rr = n - 1;
while (rr - ll > 2) {
mm = (ll + rr) / 2;
if (A[mm] > A[mm - 1] && A[mm] > A[mm + 1]) {
return mm;
} else if (A[mm - 1] < A[mm]) {
ll = mm;
} else {
rr = mm;
}
}
return (ll + rr) / 2;
}
};

复制代码

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

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-20 23:50 编辑

Longest Common Subsequence
题意：最长公共子序列，经典问题。解法1：DP
代码1：

// O(n ^ 2) solution using DP
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
int longestCommonSubsequence(string A, string B) {
int la = A.length();
int lb = B.length();
if (la == 0 || lb == 0) {
return 0;
}
vector<vector<int> > dp;
dp.resize(la + 1, vector<int>(lb + 1, 0));
int i, j;
for (i = 1; i <= la; ++i) {
for (j = 1; j <= lb; ++j) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[la][lb];
}
};

复制代码

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

解法2：空间可以优化到成O(M)。其实这题可以转化成最长递增子序列问题。不过转化后只能把时间的下限优化到O(N * log(N))，上限依然是O(N ^ 2)，实现也比较复杂，所以就不写了。
代码2：

// Space optimized to O(n)
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
int longestCommonSubsequence(string A, string B) {
int la = A.length();
int lb = B.length();
if (la == 0 || lb == 0) {
return 0;
}
vector<vector<int> > dp;
dp.resize(2, vector<int>(lb + 1, 0));
int i, j;
int f, nf;
f = 1;
nf = !f;
for (i = 1; i <= la; ++i) {
dp[f][0] = 0;
for (j = 1; j <= lb; ++j) {
if (A[i - 1] == B[j - 1]) {
dp[f][j] = dp[nf][j - 1] + 1;
} else {
dp[f][j] = max(dp[f][j - 1], dp[nf][j]);
}
}
f = !f;
nf = !f;
}
return dp[nf][lb];
}
};

复制代码

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

zhuli19901106

Longest Increasing Subsequence
题意：最长递增子序列。
解法：用二分查找，可以实现O(N * log(N))的解法，面试时务必写出来，否则必被刷。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
vector<int> &a = nums;
vector<int> v;
int n = a.size();
if (n == 0) {
return 0;
}
v.push_back(a[0]);
int i;
for (i = 1; i < n; ++i) {
if (a[i] >= v.back()) {
v.push_back(a[i]);
continue;
}
j = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
v[j] = a[i];
}
return v.size();
}
};

复制代码

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

zhuli19901106

Longest Common Prefix
题意：给定一些字符串，求它们的最长公共前缀。
解法：这题用字典树当然也可以做，但感觉代码更麻烦，效率也没提高多少，所以我就没写。还不如直接把当前的最长前缀和那些字符串逐个对比。反正前缀只会越变越短。
代码：

class Solution {
public:
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
string longestCommonPrefix(vector<string> &strs) {
int n = strs.size();
if (n == 0) {
return "";
}
string ans = strs[0];
int i, j;
for (i = 1; i < n; ++i) {
j = 0;
while (j < ans.length() && j < strs[i].length()) {
if (ans[j] != strs[i][j]) {
break;
}
++j;
}
while (ans.length() > j) {
ans.pop_back();
}
}
return ans;
}
};

复制代码

复杂度：时间O(字符总数)，空间O(1)。

zhuli19901106

Longest Common Substring
题意：给定两个字符串，求最长公共子串。注意子串是连续的，而子序列可以不连续。
解法1：首先想到的就是DP，定义DP{i}{j}为以A{i}和B{j}结尾的公共子串最长能有多长，于是有了以下代码。
代码1：

class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
int la = A.size();
int lb = B.size();
vector<vector<int> > dp;
dp.resize(la + 1, vector<int>(lb + 1, 0));
int i, j;
int ans = 0;
for (i = 1; i <= la; ++i) {
for (j = 1; j <= lb; ++j) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
ans = max(ans, dp[i][j]);
}
}
return ans;
}
};

复制代码

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

解法2：状态转移方程只涉及相邻状态，所以照例把空间优化成O(M)。
代码2：

// Space optimized to O(n)
class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
int la = A.size();
int lb = B.size();
if (la == 0 || lb == 0) {
return 0;
}
vector<vector<int> > dp;
dp.resize(2, vector<int>(lb + 1, 0));
int i, j;
int ans = 0;
int f = 1;
int nf = !f;
for (i = 1; i <= la; ++i) {
for (j = 1; j <= lb; ++j) {
if (A[i - 1] == B[j - 1]) {
dp[f][j] = dp[nf][j - 1] + 1;
} else {
dp[f][j] = 0;
}
ans = max(ans, dp[f][j]);
}
f = !f;
nf = !f;
}
return ans;
}
};

复制代码

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

zhuli19901106

Median
题意：给定一个数组，求中位数。
解法1：根据快速排序的代码，修改成快速选择算法。
代码1：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
int median(vector<int> &nums) {
// write your code here
int n = nums.size();
return quickSelect(nums, (n - 1) / 2, 0, n - 1);
}
private:
int quickSelect(vector<int> &a, int k, int ll, int rr) {
if (ll == rr) {
return a[k];
}
int i, j;
int piv = a[ll];
i = ll + 1;
j = rr;
while (true) {
while (i <= j && a[i] < piv) {
++i;
}
while (i <= j && a[j] > piv) {
--j;
}
if (i > j) {
break;
}
swap(a[i++], a[j--]);
}
swap(a[j], a[ll]);
if (k < j) {
return quickSelect(a, k, ll, j - 1);
} else if (k > j) {
return quickSelect(a, k, j + 1, rr);
} else {
return a[k];
}
}
};

复制代码

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

解法2：改成非递归，因为上面那个是尾递归。
代码2：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
int median(vector<int> &nums) {
// write your code here
int n = nums.size();
return quickSelect(nums, (n - 1) / 2, 0, n - 1);
}
private:
int quickSelect(vector<int> &a, int k, int ll, int rr) {
int i, j;
int piv;
while (true) {
if (ll == rr) {
return a[k];
}
i = ll + 1;
j = rr;
piv = a[ll];
while (true) {
while (i <= j && a[i] < piv) {
++i;
}
while (i <= j && a[j] > piv) {
--j;
}
if (i > j) {
break;
}
swap(a[i++], a[j--]);
}
swap(a[j], a[ll]);
if (k < j) {
rr = j - 1;
} else if (k > j) {
ll = j + 1;
} else {
return a[k];
}
}
}
};

复制代码

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

zhuli19901106

Data Stream Median
题意：hard难度。不断输入一些数，每读入一个返回当前的中位数。
解法：利用最大堆，最小堆，保证一半小的，一般大的分开存放。用map也行。
代码：

#include <queue>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of numbers
*/
vector<int> medianII(vector<int> &nums) {
vector<int> &a = nums;
int n = a.size();
// The smaller half
priority_queue<int, vector<int>, less<int> > small;
// The larger half
priority_queue<int, vector<int>, greater<int> > large;
int i;
vector<int> ans;
small.push(INT_MIN);
large.push(INT_MAX);
int vs, vl;
for (i = 0; i < n; ++i) {
if (i & 1) {
large.push(a[i]);
} else {
small.push(a[i]);
}
vs = small.top();
vl = large.top();
if (vs > vl) {
small.pop();
small.push(vl);
large.pop();
large.push(vs);
}
ans.push_back(small.top());
}
return ans;
}
};

复制代码

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

zhuli19901106

Single Number
题意：数组中有个数出现了一次，其他数都出现两次，把那个单独的找出来。
解法：异或。
代码：

class Solution {
public:
/**
* @param A: Array of integers.
* return: The single number.
*/
int singleNumber(vector<int> &A) {
int i;
int n = A.size();
int ans = 0;
for (i = 0; i < n; ++i) {
ans ^= A[i];
}
return ans;
}
};

复制代码

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

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-21 01:16 编辑

Single Number II
题意：一个数组中，除了一个数出现一次外，其他的都出现了三次。找出那个单独的。
解法1：把每个数按照32位分开考虑，每一位如果“1”的总个数是3的倍数，则那个单独的数的对应位就是“0”，反之则为“1”。所以用个长度32的数组来统计“1”的个数。
代码1：

#include <cstring>
using namespace std;
class Solution {
public:
/**
* @param A : An integer array
* @return : An integer
*/
int singleNumberII(vector<int> &A) {
const int NB = 32;
int c[NB];
int i, j;
int n = A.size();
memset(c, 0, sizeof(c));
for (i = 0; i < n; ++i) {
for (j = 0; j < NB; ++j) {
if (A[i] & (1 << j)) {
++c[j];
}
}
}
int ans = 0;
for (i = 0; i < NB; ++i) {
if (c[i] % 3) {
ans |= (1 << i);
}
}
return ans;
}
};

复制代码

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

解法2：这儿还有种比较欠揍的写法，可以用一个64位整数来代替数组，因为我们只关心1的个数是不是3的倍数，所以保存余数即可。鉴于代码可读性极差，所以不推荐把位运算当成装X利器。你指望你离职以后新同事读得懂这种代码？
代码2：

#include <cstring>
using namespace std;
typedef long long int LL;
class Solution {
public:
/**
* @param A : An integer array
* @return : An integer
*/
int singleNumberII(vector<int> &A) {
const int NB = 32;
LL c = 0;
LL i, j;
LL bit;
int n = A.size();
for (i = 0; i < n; ++i) {
for (j = 0; j < NB; ++j) {
if (A[i] & (1 << j)) {
bit = (c >> (j << 1)) & 3;
bit = bit == 2 ? 0 : bit + 1;
c = (c & ~(3LL << (j << 1))) | (bit << (j << 1));
}
}
}
int ans = 0;
for (i = 0; i < NB; ++i) {
bit = (c >> (i << 1)) & 3;
if (bit) {
ans |= (1 << i);
}
}
return ans;
}
};

复制代码

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

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

浏览过的版块