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

zhuli19901106

Update Bits
题意：给定整数N和M，请把M插到N的i~j位去。
解法：既然指明了是位操作，那这题就不要用循环。
代码：

class Solution {
public:
/**
*@param n, m: Two integer
*@param i, j: Two bit positions
*return: An integer
*/
int updateBits(int n, int m, int i, int j) {
if (i == 0 && j == 31) {
return m;
}
return (~(((1 << (j - i + 1)) - 1) << i) & n) | (m << i);
}
};

复制代码

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

zhuli19901106

Binary Representation
题意：hard难度。
解法：这题可以说是POJ1331和POJ1220的综合，考察数制转换。整数和小数部分的做法不一样。整数按照除2取余，小数按照乘2取整。我不知道这题的hard难度主要体现在哪，不过从写代码写得磕磕绊绊的过程看来，估计这题确实不算简单吧。
代码：

// What a mess...
#include <cstdlib>
using namespace std;
typedef long long int LL;
class Solution {
public:
/**
*@param n: Given a decimal number that is passed in as a string
*@return: A string
*/
string binaryRepresentation(string n) {
string s = "";
int len = n.length();
int dp;
for (dp = 0; dp < len; ++dp) {
if (n[dp] == '.') {
break;
}
}
int i = 0;
LL num = 0;
for (i = 0; i < dp; ++i) {
num = num * 10 + (n[i] - '0');
if (num > (1LL << 32) - 1) {
return "ERROR";
}
}
while (num != 0) {
s.push_back((num & 1) + '0');
num >>= 1;
}
if (s.length() == 0) {
s = "0";
}
reverse(s.begin(), s.end());
double d = atof(n.substr(dp, len - dp).data());
if (dp == len || d <= EPS) {
return s.length() <= 32 ? s : "ERROR";
}
s.push_back('.');
string f = "";
for (i = dp + 1; i < len; ++i) {
f.push_back(n[i] - '0');
}
while (f.length() > 0) {
if (f[0] >= 5) {
f[0] -= 5;
s.push_back('1');
} else {
s.push_back('0');
}
for (i = f.length() - 1; i >= 0; --i) {
f[i] *= 2;
}
for (i = f.length() - 1; i > 0; --i) {
f[i - 1] += f[i] / 10;
f[i] %= 10;
}
while (!f.empty() && f.back() == 0) {
f.pop_back();
}
if (s.length() > 64) {
// There is a bug here, but my code passed.
return "ERROR";
}
}
return s;
}
private:
const double EPS = 1e-3;
};

复制代码

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

zhuli19901106

Flip Bits
题意：给定两个32位整数，求把一个变成另一个，需要改变多少位。
解法：异或，数1的个数。
代码：

class Solution {
public:
/**
*@param a, b: Two integer
*return: An integer
*/
int bitSwapRequired(int a, int b) {
a ^= b;
int c = 0;
while (a) {
a = a & a - 1;
++c;
}
return c;
}
};

复制代码

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

zhuli19901106

Delete Digits
题意：有一个N位的正整数，现在要你从中删除掉K位，剩下的数字相对顺序不变。求能够组成的最小整数。
解法：这题有意思，我想了好一会儿都没思路。后来找到了这么个思路：1. 留下的数字当然越小越好。2. 高位的权重比低位要大，所以越是高位，越要尽量小。那么得到的就是一个贪婪的思路。其余细节，参见下面代码。
代码：

class Solution {
public:
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
string DeleteDigits(string A, int k) {
string ans = "";
int n = A.length();
int c = n - k;
int i, j;
i = 0;
while (i < n) {
j = i + 1;
while (j < n && k > 0) {
if (A[j] >= A[i]) {
++j;
continue;
}
if (k >= j - i) {
k -= j - i;
i = j;
}
++j;
}
ans.push_back(A[i++]);
if (ans.length() >= c) {
break;
}
}
i = 0;
while (i < c - 1 && ans[i] == '0') {
++i;
}
ans = ans.substr(i, c - i);
return ans;
}
};

复制代码

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

zhuli19901106

Wood Cut
题意：给定N根木条，长度不尽相同。现在你从这些木条中切出K根长度一样的。请问每根木条的最大长度。已知切割只能精确到整数，而且只能切不能拼。
解法：二分法。我本来没什么思路，以为这题有很巧妙的解法，后来看了题目下面的复杂度提示，就写了个二分。
代码：

#include <algorithm>
using namespace std;
typedef long long int LL;
class Solution {
public:
/**
*@param L: Given n pieces of wood with length L[i]
*@param k: An integer
*return: The maximum length of the small pieces.
*/
int woodCut(vector<int> L, int k) {
LL ll, rr, mm;
int n = L.size();
int i;
ll = 1;
rr = 0;
for (i = 0; i < n; ++i) {
rr = max(rr, (LL)L[i]);
}
if (calc(L, ll) < k) {
return 0;
}
if (calc(L, rr) >= k) {
return rr;
}
while (rr - ll > 1) {
mm = ll + (rr - ll) / 2;
if (calc(L, mm) >= k) {
ll = mm;
} else {
rr = mm;
}
}
return ll;
}
private:
LL calc(vector<int> &L, LL len) {
int n = L.size();
int i;
LL sum = 0;
for (i = 0; i < n; ++i) {
sum += L[i] / len;
}
return sum;
}
};

复制代码

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

zhuli19901106

Largest Number
题意：给定一些整数，把它们首尾相连起来，求能得到的最大整数。
解法：自定义排序。效率应该还可以更优，不过这个解法简洁易懂，所以比较推荐。
代码：

#include <algorithm>
using namespace std;
bool comp(const string &s1, const string &s2)
{
return s1 + s2 > s2 + s1;
}
class Solution {
public:
/**
*@param num: A list of non negative integers
*@return: A string
*/
string largestNumber(vector<int> &num) {
int n = num.size();
int i;
vector<string> a;
for (i = 0; i < n; ++i) {
a.push_back(to_string(num[i]));
}
sort(a.begin(), a.end(), comp);
i = 0;
while (i < n - 1 && a[i] == "0") {
++i;
}
string ans = "";
while (i < n) {
ans += a[i++];
}
return ans;
}
};

复制代码

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

zhuli19901106

Matrix Zigzag Traversal
题意：按照反对角线的Z字形方向逐个访问一个二维数组。
解法：按题意做。
代码：

class Solution {
public:
/**
* @param matrix: a matrix of integers
* @return: a vector of integers
*/
vector<int> printZMatrix(vector<vector<int> > &matrix) {
vector<int> ans;
int n, m;
n = matrix.size();
if (n == 0) {
return ans;
}
m = matrix[0].size();
if (m == 0) {
return ans;
}
int i, j;
int f = 0;
for (i = 0; i <= n + m - 2; ++i) {
if (f) {
for (j = i; j >= 0; --j) {
if (i - j < 0 || i - j > n - 1) {
continue;
}
if (j < 0 || j > m - 1) {
continue;
}
ans.push_back(matrix[i - j][j]);
}
} else {
for (j = 0; j <= i; ++j) {
if (i - j < 0 || i - j > n - 1) {
continue;
}
if (j < 0 || j > m - 1) {
continue;
}
ans.push_back(matrix[i - j][j]);
}
}
f = !f;
}
return ans;
}
};

复制代码

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

sun403

Lintcode上 space replacement 程序中return的是int数据，题目要求是输出最后的string，楼主怎么写的这部分。

zhuli19901106

Gas Station
题意：环形路上有N个加油站的位置，在每个加油站可以加油，在路上要耗油。如果允许你从任一加油站出发，从哪个出发能走完全程？
解法：O(N ^ 2)的做法就不提了。这题的O(N)做法需要理解一个道理：如果我从位置i出发，发现走到j的时候汽油变负数了（也就是走不到）。那么i~j-1必然都不可行。想想为什么？
代码：

class Solution {
public:
/**
* @param gas: a vector of integers
* @param cost: a vector of integers
* @return: an integer
*/
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int n = gas.size();
int i;
int sum = 0;
int j = 0;
for (i = 0; i < 2 * n - 1; ++i) {
sum += gas[i % n] - cost[i % n];
if (sum < 0) {
sum = 0;
j = i + 1;
}
if (i - j == n - 1) {
return j;
}
}
return -1;
}
};

复制代码

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

zhuli19901106

Maximum Product Subarray
题意：给定一个数组，求出乘积最大的子数组。
解法：这题我起初还考虑正数负数和0，后来发现想复杂了。因为负数会导致变号，所以我同时保存最大乘积跟最小乘积。这样就能写出比较简单的解法了。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param nums: a vector of integers
* @return: an integer
*/
int maxProduct(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int mm, MM;
int mm1, MM1;
int ans;
ans = mm = MM = nums[0];
int i;
for (i = 1; i < n; ++i) {
mm1 = min(nums[i], min(nums[i] * mm, nums[i] * MM));
MM1 = max(nums[i], max(nums[i] * mm, nums[i] * MM));
mm = mm1;
MM = MM1;
ans = max(ans, MM);
}
return ans;
}
};

复制代码

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

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

浏览过的版块