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

zhuli19901106

Assignment Operator Overloading (C++ Only)
题意：这题是针对C++的。给定一个含有动态分配数据的对象，请实现它的构造、析构和赋值。
解法：这题和算法无关，是考察语言特性。其实主要目的是要建立起内存管理的意识，要对内存泄漏、深拷贝、浅拷贝之类的概念心里有数。
代码：

#include <cstring>
using namespace std;
class Solution {
public:
char *m_pData;
Solution() {
this->m_pData = NULL;
}
Solution(char *pData) {
this->m_pData = pData;
}
~Solution() {
delete m_pData;
m_pData = NULL;
}
// Implement an assignment operator
Solution &operator = (const Solution &object) {
if (m_pData == object.m_pData) {
// No need to clone yourself
return *this;
}
if (m_pData != NULL) {
delete[] m_pData;
m_pData = NULL;
}
char *ptr = NULL;
if (object.m_pData != NULL) {
int len = strlen(object.m_pData);
m_pData = new char[len + 1];
strcpy(m_pData, object.m_pData);
}
return *this;
}
};

复制代码

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

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-25 17:20 编辑

Triangle Count
题意：hard难度。给定一个数组，求其中可以组成三角形的三元组有多少个。
解法1：暴力枚举，这也能AC，看来lintcode真宽容。
代码1：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param S: A list of integers
* @return: An integer
*/
int triangleCount(vector<int> &S) {
sort(S.begin(), S.end());
int i, j, k;
int ans = 0;
int n = S.size();
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
for (k = j + 1; k < n && S[i] + S[j] > S[k]; ++k) {
++ans;
}
}
}
return ans;
}
};

复制代码

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

解法2：前两维枚举，第三维二分。那么这题的hard体现在哪儿呢。
代码2：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param S: A list of integers
* @return: An integer
*/
int triangleCount(vector<int> &S) {
sort(S.begin(), S.end());
int i, j, k;
int ans = 0;
int n = S.size();
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
k = lower_bound(S.begin() + j + 1, S.end(), S[i] + S[j]) - S.begin();
ans += k - j - 1;
}
}
return ans;
}
};

复制代码

复杂度2：时间O(N^2 * log(N))。空间可以O(1)，如果二分自己手写的话，不过没必要那么钻牛角尖。

解法3：感谢stellari的提醒，我都没考虑还有O(N ^ 2)的做法，看来脑子又犯懒了。对于每个A{i}，可以用两个指针j个k直接向前移，而不需要二分搜索。这样总体复杂度是平方级别。
从运行时间可以看出三者的明显差距，所以轻敌是大忌啊。嘿嘿~
代码3：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param S: A list of integers
* @return: An integer
*/
int triangleCount(vector<int> &S) {
sort(S.begin(), S.end());
int i, j, k;
int ans = 0;
int n = S.size();
for (i = 0; i < n; ++i) {
j = i + 1;
k = j + 1;
while (j < n - 1) {
while (k < n && S[k] - S[j] < S[i]) {
++k;
}
ans += k - j - 1;
++j;
}
}
return ans;
}
};

复制代码

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

zhuli19901106

Add Binary
题意：二进制大数加法，用字符串表示。
解法：面试中的热身题，所以不能出bug。不知道怎么写才能比较简洁。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param a a number
* @param b a number
* @return the result
*/
string addBinary(string& a, string& b) {
if (a.length() < b.length()) {
return addBinary(b, a);
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string s = "";
int al = a.length();
int bl = b.length();
int i;
for (i = 0; i < bl; ++i) {
s.push_back(a[i] + b[i] - '0');
}
for (i = bl; i < al; ++i) {
s.push_back(a[i]);
}
int c = 0;
for (i = 0; i < al - 1; ++i) {
c = s[i] - '0' >> 1;
s[i] = (s[i] - '0' & 1) + '0';
s[i + 1] += c;
}
c = s[i] - '0' >> 1;
s[i] = (s[i] - '0' & 1) + '0';
if (c) {
s.push_back('1');
}
reverse(s.begin(), s.end());
return s;
}
};

复制代码

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

zhuli19901106

Convert Sorted Array to Binary Search Tree With Minimal Height
题意：把一个有序数组转化为二叉搜索树，要求高度最小。
解法：其实也就是转换成平衡树，所以对半分，递归求解。
代码：

/**
* 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 A: A sorted (increasing order) array
* @return: A tree node
*/
TreeNode* sortedArrayToBST(vector<int> &A) {
if (A.empty()) {
return NULL;
}
return convert(A, 0, A.size() - 1);
}
private:
TreeNode* convert(vector<int> &a, int ll, int rr) {
int mm = (ll + rr) / 2;
TreeNode* root = new TreeNode(a[mm]);
if (ll < mm) {
root->left = convert(a, ll, mm - 1);
}
if (rr > mm) {
root->right = convert(a, mm + 1, rr);
}
return root;
}
};

复制代码

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

stellari

zhuli19901106 发表于 2015-7-25 16:24
Triangle Count
题意：hard难度。给定一个数组，求其中可以组成三角形的三元组有多少个。
解法1：暴力枚 ...

这个题有O(N^2)的解法，这应该就是体现Hard难度的地方了吧。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-25 17:22 编辑

stellari 发表于 2015-7-25 16:51
这个题有O(N^2)的解法，这应该就是体现Hard难度的地方了吧。

哦，还真有啊。容我再想想~~
已搞定，感谢提醒！

zhuli19901106

Plus One
题意：大数加1
解法：注意存储方式是反过来的。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param digits a number represented as an array of digits
* @return the result
*/
vector<int> plusOne(vector<int> &digits) {
vector<int> &a = digits;
reverse(a.begin(), a.end());
int i, n = a.size();
int c = 0;
a[0] += 1;
for (i = 0; i < n; ++i) {
a[i] += c;
c = a[i] / 10;
a[i] %= 10;
}
if (c) {
a.push_back(c);
}
reverse(a.begin(), a.end());
return a;
}
};

复制代码

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

zhuli19901106

Divide Two Integers
题意：给定两个整数，实现整数除法，但不能用*/%。注意判断溢出。
解法：既然不能用乘除模，那就加减位运算吧。
代码：

#include <climits>
using namespace std;
typedef long long int LL;
class Solution {
public:
/**
* @param dividend the dividend
* @param divisor the divisor
* @return the result
*/
int divide(int dividend, int divisor) {
LL f = 1;
LL a = dividend;
LL b = divisor;
LL base;
if (a == 0) {
return 0;
}
if (a < 0) {
a = -a;
f = -f;
}
if (b < 0) {
b = -b;
f = -f;
}
LL b2;
base = b;
b2 = 1;
while ((base << 1) <= a) {
base <<= 1;
b2 <<= 1;
}
LL ans = 0;
while (base >= b) {
if (a >= base) {
a -= base;
ans += b2;
}
base >>= 1;
b2 >>= 1;
}
ans *= f;
if (ans < INT_MIN || ans > INT_MAX) {
ans = INT_MAX;
}
return ans;
}
};

复制代码

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

zhuli19901106

Gray Code
题意：用代码生成N位的格雷码序列。
解法：考虑N位格雷码和N-1位格雷码的关联。
代码：

class Solution {
public:
/**
* @param n a number
* @return Gray code
*/
vector<int> grayCode(int n) {
vector<int> v;
v.push_back(0);
int i, j;
int b;
b = 1;
for (i = 0; i < n; ++i) {
for (j = b - 1; j >= 0; --j) {
v.push_back(b | v[j]);
}
b <<= 1;
}
return v;
}
};

复制代码

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

zhuli19901106

Reverse Integer
题意：给定一个整数，按其十进制表示，把这个数反转。
解法：注意符号和溢出。
代码：

#include <climits>
using namespace std;
typedef long long int LL;
class Solution {
public:
/**
* @param n the integer to be reversed
* @return the reversed integer
*/
int reverseInteger(int n) {
if (n == 0) {
return 0;
}
LL ans;
int sign = n > 0 ? 1 : -1;
ans = 0;
if (n < 0) {
n = -n;
}
while (n != 0) {
ans = ans * 10 + n % 10;
n /= 10;
}
ans *= sign;
if (ans > INT_MAX || ans < INT_MIN) {
return 0;
}
return ans;
}
};

复制代码

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

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

浏览过的版块