-
楼主 / webdriver
- 时间: 2014-9-24 02:11LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.
To be successful in a technical interview, we believe it is mainly repeating these three important steps:
Code. Read. Discuss.
We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.
1. Code -> Code solution using the Online Judge system.
2. Read -> Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -> Discuss your thoughts about the problem with other LeetCoders.
We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !
This is Part 3 （第三部分）
第一部分： www.westca.com/Forums/...inese.html
第二部分： www.westca.com/Forums/...inese.html -
-
- 时间: 2014-9-24 02:12
-
-
- 时间: 2014-9-24 02:13Now comes the solution (in C++) ...
DFS.
代码:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<vector<int>> res;
vector<int> path;
pathSumRe(root, sum, res, path);
return res;
}
void pathSumRe(TreeNode *root, int sum, vector<vector<int>> &res, vector<int> &path)
{
if (!root) return;
if (!root->left && !root->right)
{
if (sum == root->val)
{
path.push_back(root->val);
res.push_back(path);
path.pop_back();
}
return;
}
path.push_back(root->val);
pathSumRe(root->left, sum - root->val, res, path);
pathSumRe(root->right, sum - root->val, res, path);
path.pop_back();
}
};
-
- 时间: 2014-9-24 02:13
-
- 时间: 2014-9-24 02:14Now comes the solution (in C++) ...
dfs...
代码:
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int> &num) {
res.clear();
vector<bool> avail(num.size(), true);
vector<int> pum;
permuteRe(num, avail, pum);
return res;
}
void permuteRe(const vector<int> &num, vector<bool> &avail, vector<int> &pum)
{
if (pum.size() == num.size())
{
res.push_back(pum);
return;
}
for (int i = 0; i < num.size(); ++i)
{
if (avail[i])
{
avail[i] = false;
pum.push_back(num[i]);
permuteRe(num, avail, pum);
pum.pop_back();
avail[i] = true;
}
}
}
};
-
- 时间: 2014-9-24 02:14Now comes the solution (in C++) ...
...
代码:
class Solution {
public:
string getPermutation(int n, int k) {
string num, res;
int total = 1;
for (int i = 1; i <= n; ++i)
{
num.push_back(i + '0');
total *= i;
}
k--;
while (n)
{
total /= n;
int i = k / total;
k %= total;
res.push_back(num[i]);
num.erase(i, 1);
n--;
}
return res;
}
};
-
- 时间: 2014-9-24 02:16
-
- 时间: 2014-9-24 02:17Now comes the solution (in C++) ...
dfs...
代码:
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permuteUnique(vector<int> &num) {
res.clear();
sort(num.begin(), num.end());
bool avail[num.size()];
memset(avail, true, sizeof(avail));
vector<int> pum;
permuteUniqueRe(num, pum, avail);
return res;
}
void permuteUniqueRe(vector<int> &num, vector<int> &pum, bool avail[])
{
if (pum.size() == num.size())
{
res.push_back(pum);
return;
}
int last_index = -1;
for (int i = 0; i < num.size(); ++i)
{
if (!avail[i]) continue;
if (last_index != -1 && num[i] == num[last_index]) continue;
avail[i] = false;
pum.push_back(num[i]);
permuteUniqueRe(num, pum, avail);
pum.pop_back();
avail[i] = true;
last_index = i;
}
}
};
-
- 时间: 2014-9-24 02:17
-
- 时间: 2014-9-24 02:18Now comes the solution (in C++) ...
...
代码:
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int carry = 1, N = digits.size();
for (int i = N-1; i >= 0 && carry; --i)
{
int sum = carry + digits[i];
carry = sum / 10;
digits[i] = sum % 10;
}
if (carry == 1)
digits.insert(digits.begin(), 1);
return digits;
}
};
Leetcode Hacking Practice -- Solution in C++ Part 3
