-
第 31 楼 / webdriver
- 时间: 2014-9-29 23:55算法问题推荐解法来了...
You may refer to github.com/AnnieKim/IT...%9E%9C.cpp
1. traverse only once with O(1) space. 2. O(n) space.
解法（Python）
代码: class Solution:
def candy(self, ratings):
candies = [1 for i in range(len(ratings))]
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in reversed(range(1, len(ratings))):
if ratings[i - 1] > ratings[i] and candies[i - 1] <= candies[i]:
candies[i - 1] = candies[i] + 1
return reduce(operator.add, candies) -
-
- 时间: 2014-9-29 23:57
-
-
- 时间: 2014-9-29 23:59
-
- 时间: 2014-9-30 00:02S算法问题: Clone Graph
问题描述:
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-30 00:04算法问题推荐解法来了...
1. DFS. 2. BFS.
解法（Python）
代码: class Solution:
def cloneGraph(self, node):
if node == None:
return None
start = UndirectedGraphNode(node.label)
map, current = {node: start}, [node]
while len(current) > 0:
next = []
for x in current:
for neighbor in x.neighbors:
if neighbor not in map:
neighbor_copy = UndirectedGraphNode(neighbor.label)
next.append(neighbor)
map[x].neighbors.append(neighbor_copy)
map[neighbor] = neighbor_copy
else:
map[x].neighbors.append(map[neighbor])
current = next
return start -
- 时间: 2014-9-30 00:04S算法问题: Combination Sum II
问题描述:
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-30 00:05算法问题推荐解法来了...
..Similar to Combination Sum I, except for line 42 && 44.
解法（Python）
代码: class Solution:
def combinationSum2(self, candidates, target):
result = []
self.combinationSumRecur(sorted(candidates), result, [], 0, target)
return result
def combinationSumRecur(self, candidates, result, current, start, target):
if target == 0 and current not in result:
result.append(current)
else:
while start < len(candidates) and candidates[start] <= target:
self.combinationSumRecur(candidates, result, current + [candidates[start]], start + 1, target - candidates[start])
start += 1 -
- 时间: 2014-9-30 00:06S算法问题: Combination Sum
问题描述:
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-30 00:06算法问题推荐解法来了...
Sort & Recursion.
解法（Python）
代码: class Solution:
def combinationSum(self, candidates, target):
result = []
self.combinationSumRecur(sorted(candidates), result, [], 0, target)
return result
def combinationSumRecur(self, candidates, result, current, start, target):
if target == 0:
result.append(current)
else:
while start < len(candidates) and candidates[start] <= target:
self.combinationSumRecur(candidates, result, current + [candidates[start]], start, target - candidates[start])
start += 1 -
- 时间: 2014-9-30 00:08
Leetcode Hacking Practice -- Solution in Python Part 1
