add 134, 135

selfboot · selfboot · commit 980203961d97 · 2015-11-27T17:45:56.000+08:00
diff --git a/BitManipulation/136_SingleNumber.py b/BitManipulation/136_SingleNumber.py
@@ -0,0 +1,19 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+
+
+class Solution(object):
+    def singleNumber(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        num = nums[0]
+        for i in nums[1:]:
+            num = num ^ i
+        return num
+
+"""
+[1]
+[1,2,3,4,4,3,2]
+"""
diff --git a/DepthFirstSearch/README.md b/DepthFirstSearch/README.md
@@ -1,8 +1,40 @@
-深度优先搜索策略
+深度优先搜索
 
 
+WikiPedia 里对 DFS 的说明如下：
 
+> Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.  One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible  along each branch before backtracking.
 
 
-注意复位当前节点属性。
+# 一般化实现
+
+递归实现
+
+
+    def DFS(G, v):
+        visited[v] = True
+        for cur_node in v.adjacentNodes():
+            if not visited[cur_node]:
+                # Do something for the current node
+                DFS(G, cur_node)
+                
+栈实现
+
+    def DFS(G, v):
+        nodes = stack()
+        nodes.push(v)
+        while not nodes.empty():
+            cur_node = nodes.pop()
+            # Do something for the current node
+            visited[cur_node] = True
+            for w in cur_node.adjacentNodes():
+                if not visited[w]:
+                    nodes.push(w)
+
+[Clone Graph](https://leetcode.com/problems/clone-graph/) 是一个图的复制问题，可以用 DFS 来遍历图中所有的顶点。
+
+
+更多阅读
+
+[Depth-first search](https://en.wikipedia.org/wiki/Depth-first_search)
 
diff --git a/DynamicProgramming/135_Candy.py b/DynamicProgramming/135_Candy.py
@@ -0,0 +1,38 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+
+
+class Solution(object):
+    def candy(self, ratings):
+        candies = [0 for i in ratings]
+        candies[0] = 1
+        children_nums = len(ratings)
+
+        # Scan from left to right
+        for i in range(children_nums-1):
+            if ratings[i+1] > ratings[i]:
+                candies[i+1] = candies[i] + 1
+            else:
+                candies[i+1] = 1
+
+        minimum_candies = 0
+        # Scan from right to left
+        for i in range(children_nums-1, 0, -1):
+            if ratings[i-1] > ratings[i]:
+                candies[i-1] = max(candies[i] + 1, candies[i-1])
+            else:
+                candies[i-1] = max(1, candies[i-1])
+            minimum_candies += candies[i]
+
+        return minimum_candies + candies[0]
+
+
+"""
+[0]
+[2,2,1]
+[3,4,8,6,7]
+[4,3,8,6,7]
+[1,2,4,4,3]
+[1,2,4,4,5]
+[4,4,4,4,4]
+"""
diff --git a/Graph/133_CloneGraph.py b/Graph/133_CloneGraph.py
@@ -0,0 +1,41 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+
+
+# Definition for a undirected graph node
+# class UndirectedGraphNode(object):
+#     def __init__(self, x):
+#         self.label = x
+#         self.neighbors = []
+
+class Solution(object):
+    def cloneGraph(self, node):
+        if not node:
+            return None
+
+        copyed_node_pair = {}
+        copy_head = UndirectedGraphNode(node.label)
+        copy_head.neighbors = []
+        copyed_node_pair[node] = copy_head
+
+        nodes_stack = []
+        nodes_stack.append(node)
+        while nodes_stack:
+            one_node = nodes_stack.pop()
+
+            for neighbor in one_node.neighbors:
+                if neighbor not in copyed_node_pair:
+                    copy_node = UndirectedGraphNode(neighbor.label)
+                    copy_node.neighbors = []
+                    copyed_node_pair[neighbor] = copy_node
+                    nodes_stack.append(neighbor)
+
+                copyed_node_pair[one_node].neighbors.append(
+                    copyed_node_pair[neighbor])
+
+        return copy_head
+
+"""
+{0,0,0}
+{0,1,2#1,2#2,2}
+"""
diff --git a/Greedy/134_GasStation.py b/Greedy/134_GasStation.py
@@ -0,0 +1,49 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+# Refer to http://blog.csdn.net/kenden23/article/details/14106137
+
+
+class Solution(object):
+    """
+    Consider we start at gas station i, and until j we firstly run out of gas.
+
+    That's say remain(i,j) = R(i) + ... + R(j) < 0, R(i) >= 0, R(j) < 0
+    and remain(i, m) >= 0, where i =< m < j,
+    We assume R(k) = gas(k) - cost(k) here.
+
+    Further more, we can make sure remain(m+1, k) < 0.
+    Just because remain(i,j) < 0 and remain(i, m) >= 0.
+    So, next we just need to start from index k+1.
+
+    So, firstly find all the (i,j) pairs, but just need to record the last j.
+    Then if there is an unique(it's guaranteed) solution, it must be (j+1)
+    """
+    def canCompleteCircuit(self, gas, cost):
+        station_num = len(gas)
+        mark_station = -1
+        all_remain = 0
+        remain_gas = 0
+        for i in range(station_num):
+            all_remain += (gas[i]-cost[i])
+            remain_gas += (gas[i]-cost[i])
+            if remain_gas < 0:
+                mark_station = i
+                remain_gas = 0
+
+        if all_remain >= 0:
+            return (mark_station + 1) % station_num
+        else:
+            return -1
+
+        return -1
+
+"""
+[4]
+[5]
+[1,10,2,3,4,5,6]
+[2,4,3,4,5,6,7]
+[1,2,3,4,5,6,10]
+[1,2,2,3,4,15,4]
+[2,0,1,2,3,4,0]
+[0,1,0,0,0,0,11]
+"""
diff --git a/README.md b/README.md
@@ -118,11 +118,13 @@
 * 121. [Best Time to Buy and Sell Stock](DynamicProgramming/121_BestTimeToBuyAndSellStock.py)
 * 123. [Best Time to Buy and Sell Stock III](DynamicProgramming/123_BestTimeToBuyAndSellStockIII.py)
 * 132. [Palindrome Partitioning II](DynamicProgramming/132_PalindromePartitioningII.py)
+* 135. [Candy](DynamicProgramming/135_Candy.py)
 
 # [Greedy](Greedy/)
 
 * 055. Jump Game
 * 122. [Best Time to Buy and Sell Stock II](Greedy/122_BestTimeToBuyAndSellStockII.py)
+* 134. [Gas Station](Greedy/134_GasStation.py)
 
 # [Stack](Stack/)
 
@@ -155,6 +157,7 @@
 # [Bit Manipulation](BitManipulation/)
 
 * 078. Subsets
+* 136. [Single Number](BitManipulation/136_SingleNumber.py)
 
 # DFA
 
