-
第 41 楼 / webdriver
- 时间: 2014-9-23 13:33Now comes the solution (in C++) ...
Clime one step from last stair or clime 2 steps from the last last stair.
代码: class Solution {
public:
int climbStairs(int n) {
int last = 1;
int lastlast = 1;
for (int i = 2; i <= n; i++)
{
int step = last + lastlast;
lastlast = last;
last = step;
}
return last;
}
}; -
-
- 时间: 2014-9-23 13:35Problem Name: Clone Graph
Description:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled from 0 to N - 1, where N is the total nodes in the graph.
We use # as a separator for each node, and , as a separator for each neighbor of the node.
As an example, consider the serialized graph {1,2#2#2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
Connect node 0 to both nodes 1 and 2.
Connect node 1 to node 2.
Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/ -
-
- 时间: 2014-9-23 13:36Now comes the solution (in C++) ...
1. DFS. 2. BFS.
代码: /**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
typedef UndirectedGraphNode GraphNode;
typedef unordered_map<GraphNode *, GraphNode *> MAP;
GraphNode *cloneGraph(GraphNode *node) {
return cloneGraph_1(node);
}
// DFS
GraphNode *cloneGraph_1(GraphNode *node) {
MAP map;
return cloneGraphRe(node, map);
}
GraphNode *cloneGraphRe(GraphNode *node, MAP &map) {
if (!node) return NULL;
if (map.find(node) != map.end())
return map[node];
GraphNode *newNode = new GraphNode(node->label);
map[node] = newNode;
for (int i = 0; i < node->neighbors.size(); ++i)
newNode->neighbors.push_back(cloneGraphRe(node->neighbors[i], map));
return newNode;
}
// BFS
GraphNode *cloneGraph_2(GraphNode *node) {
if (!node) return NULL;
queue<GraphNode*> q;
q.push(node);
MAP map;
map[node] = new GraphNode(node->label);
while (!q.empty())
{
GraphNode *oriNode = q.front(); q.pop();
GraphNode *newNode = map[oriNode];
for (int i = 0; i < oriNode->neighbors.size(); ++i)
{
GraphNode *oriNeighbor = oriNode->neighbors[i];
if (map.find(oriNeighbor) != map.end()) {
newNode->neighbors.push_back(map[oriNeighbor]);
continue;
}
GraphNode *newNeighbor = new GraphNode(oriNeighbor->label);
newNode->neighbors.push_back(newNeighbor);
map[oriNeighbor] = newNeighbor;
q.push(oriNeighbor);
}
}
return map[node];
}
}; -
- 时间: 2014-9-23 13:37
-
- 时间: 2014-9-23 13:38Now comes the solution (in C++) ...
DFS.
代码: class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > res;
vector<int> com;
combineRe(n, k, 1, com, res);
return res;
}
void combineRe(int n, int k, int start, vector<int> &com, vector<vector<int> > &res){
int m = com.size();
if (m == k) {
res.push_back(com);
return;
}
for (int i = start; i <= n-(k-m)+1; ++i) {
com.push_back(i);
combineRe(n, k, i+1, com, res);
com.pop_back();
}
}
}; -
- 时间: 2014-9-23 13:41Problem Name: Combination Sum
Description:
Given a set of candidate numbers (C) and a target number (T), find all unique
combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] -
- 时间: 2014-9-23 13:42Now comes the solution (in C++) ...
Sort & Recursion.
代码: class Solution {
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
vector<int> com;
combinationSumRe(candidates, target, 0, com, res);
return res;
}
void combinationSumRe(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res)
{
if (target == 0) {
res.push_back(com);
return;
}
for (int i = start; i < num.size() && target >= num[i]; ++i) {
com.push_back(num[i]);
combinationSumRe(num, target-num[i], i, com, res);
com.pop_back();
}
}
}; -
- 时间: 2014-9-23 13:44Problem Name: Combination Sum II
Description:
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations
in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] -
- 时间: 2014-9-23 13:46Now comes the solution (in C++) ...
..Similar to Combination Sum I, except for line 42 && 44.
代码: class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &num, int target) {
vector<vector<int>> res;
sort(num.begin(), num.end());
vector<int> com;
combinationSum2Re(num, target, 0, com, res);
return res;
}
void combinationSum2Re(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res)
{
if (target == 0) {
res.push_back(com);
return;
}
for (int i = start; i < num.size() && num[i] <= target; ++i) {
if (i > start && num[i] == num[i-1]) continue;
com.push_back(num[i]);
combinationSum2Re(num, target-num[i], i+1, com, res);
com.pop_back();
}
}
}; -
- 时间: 2014-9-23 13:47
Leetcode Hacking Practice -- Solution in C++ Part 1
