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

水逼一枚

zhuli19901106 发表于 2015-7-22 00:57
Jump Game II
题意：跟Jump Game一样，不过这题求的是跳到终点的最少步数。
解法：只要跳到终点，就马上 ...

#135楼 Jump Game II似乎有点儿问题？lc上没法AC。

zhuli19901106

水逼一枚发表于 2015-7-26 09:37
#135楼 Jump Game II似乎有点儿问题？lc上没法AC。

确实，待我改改。这个错代码居然在lintcode上AC了，看来lintcode的数据很水。

zhuli19901106

Jump Game II
题意：跟Jump Game一样，不过这题求的是跳到终点的最少步数。
解法：只要跳到终点，就马上退出循环即可。感谢水逼一枚指出代码中的错误，lintcode的数据真水，错代码都给AC了。
代码：

class Solution {
public:
int jump(vector<int> A) {
int n = A.size();
if (n < 2) {
return 0;
}
int i;
int oldr, r;
int ans = 0;
oldr = r = 0;
i = 0;
while (i < n) {
if (r < i) {
// Unreachable
return -1;
}
if (r >= n - 1) {
break;
}
while (i <= oldr) {
r = max(r, i + A[i]);
++i;
}
oldr = r;
++ans;
}
return ans;
}
};

复制代码

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

zhuli19901106

Maximal Square
题意：给定一个只含有01矩阵，求其中全部为1的正方形的最大面积。
解法：考虑这题和Largest Rectangle In Histogram的关联性。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param matrix: a matrix of 0 and 1
* @return: an integer
*/
int maxSquare(vector<vector<int> > &matrix) {
v.clear();
dl.clear();
dr.clear();
n = matrix.size();
if (n == 0) {
return 0;
}
m = matrix[0].size();
if (m == 0) {
return 0;
}
v.resize(m, 0);
dl.resize(m);
dr.resize(m);
int i, j;
int ans = 0;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
v[j] = matrix[i][j] ? v[j] + matrix[i][j] : 0;
}
ans = max(ans, largestHistogram());
}
return ans;
}
private:
vector<int> v;
vector<int> dl, dr;
int n, m;
int largestHistogram() {
int i;
for (i = 0; i <= m - 1; ++i) {
dl[i] = dr[i] = i;
}
for (i = 1; i <= m - 1; ++i) {
while (dl[i] - 1 >= 0 && v[dl[i] - 1] >= v[i]) {
dl[i] = dl[dl[i] - 1];
}
}
for (i = m - 2; i >= 0; --i) {
while (dr[i] + 1 <= m - 1 && v[dr[i] + 1] >= v[i]) {
dr[i] = dr[dr[i] + 1];
}
}
int ans = 0;
int len;
for (i = 0; i <= m - 1; ++i) {
len = min(v[i], dr[i] - dl[i] + 1);
ans = max(ans, len * len);
}
return ans;
}
};

复制代码

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

zhuli19901106

Longest Words
题意：很无聊的一题。
解法：略。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param dictionary: a vector of strings
* @return: a vector of strings
*/
vector<string> longestWords(vector<string> &dictionary) {
int i;
int len = 0;
vector<string> ans;
for (i = 0; i < dictionary.size(); ++i) {
len = max(len, (int)dictionary[i].length());
}
for (i = 0; i < dictionary.size(); ++i) {
if (len == dictionary[i].length()) {
ans.push_back(dictionary[i]);
}
}
return ans;
}
};

复制代码

复杂度：不怎么复杂。

zhuli19901106

Space Replacement
题意：给定一个字符串，把其中的‘ ’替换成‘%20’，要求就地完成。
解法：首先顺着扫一次，确定有多少个空格。然后从尾到头扫一遍，进行替换。为什么从尾到头呢？因为这样避免了移动大量的元素。
代码：

#include <cstring>
using namespace std;
class Solution {
public:
/**
* @param string: An array of Char
* @param length: The true length of the string
* @return: The true length of new string
*/
int replaceBlank(char string[], int length) {
if (string == NULL) {
return 0;
}
int i, j;
char *s = string;
int n = length;
int m = n;
int ans;
for (i = 0; i < n; ++i) {
if (s[i] == ' ') {
m += 2;
}
}
ans = m;
s[m--] = 0;
for (i = n - 1; i >= 0; --i) {
if (s[i] == ' ') {
s[m--] = '0';
s[m--] = '2';
s[m--] = '%';
} else {
s[m--] = s[i];
}
}
return ans;
}
};

复制代码

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

zhuli19901106

Max Points on a Line
题意：给定N个整点，求出一条直线可以通过的最多点数。
解法：这题用O(N ^ 3)的时间可以暴力解决，就不提了。来想想O(N ^ 2)的解法。我们以每个点为中心，考虑其他所有点与这点构成的直线的斜率，而且为了避免精度问题，不用浮点数，而是用一个数对来表示。斜率相同，自然会落在一条线上。此处还要考虑到重合的点，这些点都要算进去。利用哈希表来保存斜率，可以做到平方复杂度。
代码：

#include <algorithm>
#include <map>
using namespace std;
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
typedef struct Term {
Term(int x = 0, int y = 0) {
this->x = x;
this->y = y;
}
int x, y;
bool operator < (const Term &other) const
{
if (x != other.x) {
return x < other.x;
} else {
return y < other.y;
}
}
bool operator == (const Term &other) const
{
return x == other.x && y == other.y;
}
} Term;
int gcd(int x, int y)
{
return x ? gcd(y % x, x) : y;
}
int abs(int x)
{
return x >= 0 ? x : -x;
}
void normalize(Term &t)
{
if (t.x == 0) {
t.y = t.y ? 1 : 0;
return;
}
if (t.y == 0) {
t.x = t.x ? 1 : 0;
return;
}
if (t.x < 0) {
t.x = -t.x;
t.y = -t.y;
}
int g = gcd(t.x, abs(t.y));
t.x /= g;
t.y /= g;
}
class Solution {
public:
/**
* @param points an array of point
* @return an integer
*/
int maxPoints(vector<Point>& points) {
int n = points.size();
if (n < 3) {
return n;
}
map<Term, int> mm;
map<Term, int>::iterator it;
Term t;
int i, j;
int zc;
int msum = 2;
int sum;
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
t.x = points[j].x - points[i].x;
t.y = points[j].y - points[i].y;
normalize(t);
++mm[t];
}
zc = mm[Term(0, 0)];
sum = 0;
for (it = mm.begin(); it != mm.end(); ++it) {
if (it->first == Term(0, 0)) {
continue;
}
sum = max(sum, it->second);
}
msum = max(msum, sum + zc + 1);
mm.clear();
}
return msum;
}
};

复制代码

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

zhuli19901106

Invert Binary Tree
题意1：问问Max Howell。
解法1：不会。
代码1：

/**
* 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: a TreeNode, the root of the binary tree
* @return: nothing
*/
void invertBinaryTree(TreeNode *root) {
if (root == NULL) {
return;
}
TreeNode *p = root->left;
root->left = root->right;
root->right = p;
invertBinaryTree(root->left);
invertBinaryTree(root->right);
}
};

复制代码

复杂度1：太复杂。

解法2：可以会。
代码2：

#include <algorithm>
#include <queue>
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: a TreeNode, the root of the binary tree
* @return: nothing
*/
void invertBinaryTree(TreeNode *root) {
// The iterative version.
if (root == NULL) {
return;
}
TreeNode *p;
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
p = q.front();
q.pop();
swap(p->left, p->right);
if (p->left != NULL) {
q.push(p->left);
}
if (p->right != NULL) {
q.push(p->right);
}
}
}
};

复制代码

复杂度2：还行。

zhuli19901106

又被吞掉一题：Invert Binary Tree

zhuli19901106

Find the Missing Number
题意：给定一个数组，其中0-N中除了一个数之外，其他的都出现一次。找出那个没出现的。
解法1：一个数组当两个用。
代码1：

class Solution {
public:
/**
* @param nums: a vector of integers
* @return: an integer
*/
int findMissing(vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int i;
nums.push_back(0);
for (i = 0; i < n; ++i) {
nums[nums[i] % (n + 1)] += n + 1;
}
for (i = 0; i <= n; ++i) {
if (nums[i] < n + 1) {
break;
}
}
return i;
}
};

复制代码

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

解法2：求和即可。
代码2：

typedef long long int LL;
class Solution {
public:
/**
* @param nums: a vector of integers
* @return: an integer
*/
int findMissing(vector<int> &nums) {
int n = nums.size();
int i;
LL sum = 0;
for (i = 0; i < n; ++i) {
sum += nums[i];
}
return 1LL * n * (n + 1) / 2 - sum;
}
};

复制代码

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

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

浏览过的版块