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

zhuli19901106

Number of Islands
题意：给定一个01数组，如果1表示陆地，0表示水的话，按照4邻接规则，求有多少块陆地？
解法：这题检查的是连通性，所以既可以用并查集，也可以用DFS、BFS来做。我就选了DFS。
代码：

class Solution {
public:
Solution() {
d.resize(4, vector<int>(2));
int i;
d[0][0] = -1;
d[0][1] = 0;
d[1][0] = +1;
d[1][1] = 0;
d[2][0] = 0;
d[2][1] = -1;
d[3][0] = 0;
d[3][1] = +1;
}
/**
* @param grid a boolean 2D matrix
* @return an integer
*/
int numIslands(vector<vector<bool> > &grid) {
n = grid.size();
if (n == 0) {
return 0;
}
m = grid[0].size();
if (m == 0) {
return 0;
}
int ans = 0;
int i, j;
b.resize(n, vector<bool>(m));
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (grid[i][j] && !b[i][j]) {
++ans;
DFS(i, j);
}
}
}
b.clear();
return ans;
}
private:
vector<vector<bool> > b;
vector<vector<int> > d;
int n, m;
void DFS(int x, int y, vector<vector<bool> > &grid) {
b[x][y] = true;
int x1, y1;
int i;
for (i = 0; i < 4; ++i) {
x1 = x + d[i][0];
y1 = y + d[i][1];
if (x1 < 0 || x1 > n - 1 || y1 < 0 || y1 > m - 1) {
continue;
}
if (grid[x1][y1] && !b[x1][y1]) {
DFS(x1, y1, grid);
}
}
}
};

复制代码

复杂度：时间O(N ^ 2)，一样。

zhuli19901106

Number of Islands II
题意：hard难度。和Number Of Islands一样，求有多少块大陆。不过这题要求每次把一块水填成陆地，要求没改变一次地形，就求一次。
解法：显然，这题由于地形会改变，所以flooding算法就不再适用了，所以放弃BFS和DFS。于是选用并查集作为解法，为了保证效率，路径压缩自然是必需品了。
代码：

/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
Solution() {
d.resize(4, vector<int>(2));
d[0][0] = +1;
d[0][1] = 0;
d[1][0] = -1;
d[1][1] = 0;
d[2][0] = 0;
d[2][1] = +1;
d[3][0] = 0;
d[3][1] = -1;
}
/**
* @param n an integer
* @param m an integer
* @param operators an array of point
* @return an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point> &operators) {
b.clear();
dj.clear();
this->n = n;
this->m = m;
b.resize(n * m, false);
dj.resize(n * m);
int i;
for (i = 0; i < n * m; ++i) {
dj[i] = i;
}
int cc = 0;
int x, y;
int x1, y1;
int r, r1;
vector<int> ans;
vector<int> adj;
int j;
for (i = 0; i < operators.size(); ++i) {
x = operators[i].x;
y = operators[i].y;
if (b[x * m + y]) {
ans.push_back(cc);
continue;
}
b[x * m + y] = true;
adj.clear();
for (j = 0; j < 4; ++j) {
x1 = x + d[j][0];
y1 = y + d[j][1];
if (inbound(x1, y1) && b[x1 * m + y1]) {
adj.push_back(x1 * m + y1);
}
}
if (adj.empty()) {
ans.push_back(++cc);
continue;
}
dj[findRoot(adj[0])] = findRoot(x * m + y);
for (j = 1; j < adj.size(); ++j) {
r = findRoot(x * m + y);
r1 = findRoot(adj[j]);
if (r != r1) {
dj[r1] = r;
--cc;
}
}
ans.push_back(cc);
}
return ans;
}
private:
vector<vector<int> > d;
vector<int> b, dj;
int n, m;
bool inbound(int x, int y) {
return x >=0 && x <= n - 1 && y >= 0 && y <= m - 1;
}
int findRoot(int x) {
int r = x;
while (r != dj[r]) {
r = dj[r];
}
int k = x;
while (x != r) {
x = dj[x];
dj[k] = r;
k = x;
}
return r;
}
};

复制代码

复杂度：时间O(K)，K为query次数。空间O(N ^ 2)。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-26 18:47 编辑

Find the Connected Component in the Undirected Graph
题意：求无向图的联通分量。
解法：使用并查集。
代码：

#include <unordered_map>
using namespace std;
/**
* Definition for Undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
/**
* @param nodes a array of Undirected graph node
* @return a connected set of a Undirected graph
*/
vector<vector<int> > connectedSet(vector<UndirectedGraphNode*> &nodes) {
int n = nodes.size();
int i;
dj.resize(n);
for (i = 0; i < n; ++i) {
dj[i] = i;
um[nodes[i]] = i;
}
int j;
int x, y, rx, ry;
for (i = 0; i < n; ++i) {
x = um[nodes[i]];
for (j = 0; j < nodes[i]->neighbors.size(); ++j) {
y = um[nodes[i]->neighbors[j]];
rx = findRoot(x);
ry = findRoot(y);
dj[rx] = ry;
}
}
vector<vector<int> > ans;
unordered_map<int, vector<int> > cc;
unordered_map<int, vector<int> >::iterator it;
for (i = 0; i < n; ++i) {
findRoot(i);
cc[dj[i]].push_back(nodes[i]->label);
}
for (it = cc.begin(); it != cc.end(); ++it) {
ans.push_back(it->second);
}
dj.clear();
um.clear();
cc.clear();
return ans;
}
private:
vector<int> dj;
unordered_map<UndirectedGraphNode*, int> um;
int findRoot(int x) {
int r = x;
while (r != dj[r]) {
r = dj[r];
}
int k = x;
while (x != r) {
x = dj[x];
dj[k] = r;
k = x;
}
return r;
}
};

复制代码

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

zhuli19901106

Find the Weak Connected Component in the Directed Graph
题意：给定一耳光有向图，求出弱连通分量。弱连通分量也就是把这个图当成无向图之后的连通分量。
解法：还是并查集。
代码：

#include <algorithm>
#include <unordered_map>
using namespace std;
/**
* Definition for Directed graph.
* struct DirectedGraphNode {
* int label;
* vector<DirectedGraphNode *> neighbors;
* DirectedGraphNode(int x) : label(x) {};
* };
*/
typedef DirectedGraphNode DGN;
class Solution {
public:
/**
* @param nodes a array of directed graph node
* @return a connected set of a directed graph
*/
vector<vector<int> > connectedSet2(vector<DGN *> &nodes) {
dj.clear();
comp.clear();
ans.clear();
int n = nodes.size();
int i, j;
for (i = 0; i < n; ++i) {
dj[nodes[i]] = nodes[i];
}
int m;
DGN *x, *y, *rx, *ry;
for (i = 0; i < n; ++i) {
m = nodes[i]->neighbors.size();
for (j = 0; j < m; ++j) {
x = nodes[i];
y = nodes[i]->neighbors[j];
rx = findRoot(x);
ry = findRoot(y);
if (rx == ry) {
continue;
}
dj[rx] = ry;
}
}
for (i = 0; i < n; ++i) {
findRoot(nodes[i]);
comp[dj[nodes[i]]].push_back(nodes[i]->label);
}
for (auto it = comp.begin(); it != comp.end(); ++it) {
sort(it->second.begin(), it->second.end());
ans.push_back(it->second);
}
return ans;
}
private:
unordered_map<DGN *, DGN *> dj;
unordered_map<DGN *, vector<int> > comp;
vector<vector<int> > ans;
DGN *findRoot(DGN *x) {
DGN *r = x;
while (r != dj[r]) {
r = dj[r];
}
DGN *k = x;
while (x != r) {
x = dj[x];
dj[k] = r;
k = x;
}
return r;
}
};

复制代码

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

zhuli19901106

Scramble String
题意：hard难度。给定两个字符串S和T。如果把S分成左右两部分，而且如此递归下去，就可以用一棵二叉树来表示。求问，如果允许把这棵二叉树的一些节点的左右孩子反转，请问是否能够构成T的一种表示？
解法：题意还是看示例吧，文字描述挺绕口的。这题有O(N^4)的DP解法，网上流传很广泛。我这个也是，所以不用多解释了。至于O(N ^ 3)时间的解法，当时苦想一晚上也没想出来，上网搜也找不到。如果谁会，还请不吝赐教！
代码：

// O(n ^ 4) solution using DP
class Solution {
public:
/**
* @param s1 A string
* @param s2 Another string
* @return whether s2 is a scrambled string of s1
*/
bool isScramble(string &s1, string &s2) {
int n = s1.length();
if (n != s2.length()) {
return false;
}
if (s1 == s2) {
return true;
}
int i, j, k, ii;
vector<vector<vector<bool> > > dp(n, vector<vector<bool> >(n, vector<bool>(n, false)));
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
dp[0][i][j] = s1[i] == s2[j];
}
}
for (i = 1; i < n; ++i) {
for (j = 0; j + i < n; ++j) {
for (k = 0; k + i< n; ++k) {
for (ii = 0; ii < i; ++ii) {
if (dp[ii][j][k] && dp[i - ii - 1][j + ii + 1][k + ii + 1]) {
dp[i][j][k] = true;
}
if (dp[ii][j][k + i - ii] && dp[i - ii - 1][j + ii + 1][k]) {
dp[i][j][k] = true;
}
}
}
}
}
return dp[n - 1][0][0];
}
};

复制代码

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

zhuli19901106

Submatrix Sum
题意：给定一个矩阵，找到和为0的子矩阵，给出左上角和右下角。
解法1：暴力解法。直接求和，找找0在哪儿。
代码1：

// O(n ^ 4) solution
class Solution {
public:
/**
* @param matrix an integer matrix
* @return the coordinate of the left-up and right-down number
*/
vector<vector<int> > submatrixSum(vector<vector<int> > &matrix) {
vector<vector<int> > &a = matrix;
int n, m;
n = a.size();
m = n ? a[0].size() : 0;
vector<vector<int> > ans(2, vector<int>(2));
vector<vector<int> > s(n + 1, vector<int>(m + 1, 0));
int i, j;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j) {
s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i - 1][j - 1] - s[i - 1][j - 1];
}
}
int i1, j1;
int sum;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
for (i1 = i + 1; i1 <= n; ++i1) {
for (j1 = j + 1; j1 <= m; ++j1) {
sum = 0;
sum += s[i][j] + s[i1][j1];
sum -= s[i][j1] + s[i1][j];
if (sum != 0) {
continue;
}
ans[0][0] = i;
ans[0][1] = j;
ans[1][0] = i1 - 1;
ans[1][1] = j1 - 1;
return ans;
}
}
}
}
return ans;
}
};

复制代码

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

解法2：在一个数组中找出加起来等于0的子数组，这个可以在O(N)时间内做到。所以这个问题总体可以在O(N ^ 3)时间解决。
代码2：

// O(n ^ 3) solution
#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param matrix an integer matrix
* @return the coordinate of the left-up and right-down number
*/
vector<vector<int> > submatrixSum(vector<vector<int> > &matrix) {
vector<vector<int> > &a = matrix;
int n = a.size();
int m = n ? a[0].size() : 0;
vector<vector<int> > s(n + 1, vector<int>(m, 0));
int i, j, k;
unordered_map<int, int> um;
for (i = 1; i <= n; ++i) {
for (j = 0; j < m; ++j) {
s[i][j] = s[i - 1][j] + a[i - 1][j];
}
}
int sum;
vector<vector<int> > ans(2, vector<int>(2));
for (i = 0; i < n; ++i) {
for (j = i + 1; j <= n; ++j) {
um.clear();
um[0] = -1;
sum = 0;
for (k = 0; k < m; ++k) {
sum += s[j][k] - s[i][k];
if (um.find(sum) != um.end()) {
ans[0][0] = i;
ans[0][1] = um[sum] + 1;
ans[1][0] = j - 1;
ans[1][1] = k;
return ans;
}
um[sum] = k;
}
}
}
return ans;
}
};

复制代码

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

zhuli19901106

Word Break
题意：给定一个长字符串，和一个词典。判断字符串能否分割成若干段，每段都是词典里的单词。
解法：思路是DP。
代码：

#include <algorithm>
using namespace std;
typedef unordered_set<string> uss;
class Solution {
public:
/**
* @param s: A string s
* @param dict: A dictionary of words dict
*/
bool wordBreak(string s, uss &dict) {
int n = s.length();
if (n == 0) {
return true;
}
vector<bool> dp(n + 1, false);
int maxlen = 0;
for (auto it = dict.begin(); it != dict.end(); ++it) {
maxlen = max(maxlen, (int)it->length());
}
int i, j;
dp[0] = true;
for (i = 1; i <= n; ++i) {
for (j = i - 1; j >= 0; --j) {
if (i - j > maxlen) {
break;
}
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};

复制代码

复杂度：时间O(N ^ 3)，空间O(N)。需要指出，substr本身是O(N)级别的算法，所以总体复杂度应该算是O(N ^ 3)，而不是O(N ^ 2)。就算是换种写法，避免使用substr，在算hash key的时候，还是需要O(N)时间。

此处补充两个关于字符串hash key的链接：
来自byvoid大神
https://www.byvoid.com/blog/string-hash-compare
来自知乎
http://www.zhihu.com/question/25506718

zhuli19901106

Triangle
题意：给定一个三角形，从顶端走到底下，每次允许向左或向右，求能得到的最小和。
解法：基础的DP题目，在POJ上刚学编程时，就是做这种题。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int> > &triangle) {
vector<vector<int> > &a = triangle;
int n = a.size();
if (n == 0) {
return 0;
}
int i, j;
for (i = 1; i < n; ++i) {
a[i][0] += a[i - 1][0];
for (j = 1; j < i; ++j) {
a[i][j] += min(a[i - 1][j - 1], a[i - 1][j]);
}
a[i][i] += a[i - 1][i - 1];
}
int ans = a[n - 1][0];
for (i = 1; i < n; ++i) {
ans = min(ans, a[n - 1][i]);
}
return ans;
}
};

复制代码

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

zhuli19901106

Remove Duplicates from Sorted Array
题意：有序数组去重。
解法：参见代码。
代码：

class Solution {
public:
/**
* @param A: a list of integers
* @return : return an integer
*/
int removeDuplicates(vector<int> &nums) {
int n = nums.size();
int m = 0;
int i, j;
i = 0;
while (i < n) {
j = i + 1;
while (j < n && nums[i] == nums[j]) {
++j;
}
nums[m++] = nums[i];
i = j;
}
while (nums.size() > m) {
nums.pop_back();
}
return m;
}
};

复制代码

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

zhuli19901106

Remove Duplicates from Sorted Array II
题意：有序数组去重，但是每个元素允许至多两个。
解法：代码稍作修改即可。
代码：

class Solution {
public:
/**
* @param A: a list of integers
* @return : return an integer
*/
int removeDuplicates(vector<int> &nums) {
int n = nums.size();
int m = 0;
int i, j;
i = 0;
while (i < n) {
j = i + 1;
while (j < n && nums[i] == nums[j]) {
++j;
}
nums[m++] = nums[i];
if (j - i > 1) {
nums[m++] = nums[i];
}
i = j;
}
while (nums.size() > m) {
nums.pop_back();
}
return m;
}
};

复制代码

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