add some leetcodes

Jack-Lee-Hiter · Jack-Lee-Hiter · commit c23ce0ec3c41 · 2016-08-25T19:10:21.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/二叉树中和为某一值的路径.py b/Target Offer/二叉树中和为某一值的路径.py
@@ -10,28 +10,36 @@ def __init__(self, x):
         self.right = None
 class Solution:
     # 返回二维列表，内部每个列表表示找到的路径
-    def FindPath(self, root, expectNumber):
-        if root == None or root.val > expectNumber:
+    def FindPath(self, root, sum):
+        if not root:
             return []
-        elif root.val == expectNumber:
-            if root.left or root.right:
-                return []                   # 因为路径的定义是从根节点到叶节点所经过的结点, 如果是根结点到任意可到达结点的和为待求值, 可以去掉这个判定
+        if root.left == None and root.right == None:
+            if sum == root.val:
+                return [[root.val]]
             else:
-                return [[expectNumber]]
-
+                return []
         stack = []
-        if root.left:
-            stackLeft = self.FindPath(root.left, expectNumber-root.val)
-            for i in stackLeft:
-                i.insert(0, root.val)
-                stack.append(i)
-        if root.right:
-            stackRight = self.FindPath(root.right, expectNumber-root.val)
-            for i in stackRight:
-                i.insert(0, root.val)
-                stack.append(i)
+        leftStack = self.pathSum(root.left, sum - root.val)
+        for i in leftStack:
+            i.insert(0, root.val)
+            stack.append(i)
+        rightStack = self.pathSum(root.right, sum - root.val)
+        for i in rightStack:
+            i.insert(0, root.val)
+            stack.append(i)
         return stack
 
+    # 优化写法
+    def pathSum(self, root, sum):
+        if not root: return []
+        if root.left == None and root.right == None:
+            if sum == root.val:
+                return [[root.val]]
+            else:
+                return []
+        a = self.pathSum(root.left, sum - root.val) + self.pathSum(root.right, sum - root.val)
+        return [[root.val] + i for i in a]
+
 pNode1 = TreeNode(10)
 pNode2 = TreeNode(5)
 pNode3 = TreeNode(12)
@@ -46,4 +54,6 @@ def FindPath(self, root, expectNumber):
 
 
 S = Solution()
-print(S.FindPath(pNode1, 22))
+print(S.FindPath(pNode1, 22))
+# 测试用例：[1,-2,-3,1,3,-2,null,-1]  -1
+# 测试用例：[-2, None, -3] -5
diff --git a/leetcode/112. Path Sum.py b/leetcode/112. Path Sum.py
@@ -0,0 +1,28 @@
+'''
+Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
+
+For example:
+Given the below binary tree and sum = 22,
+              5
+             / \
+            4   8
+           /   / \
+          11  13  4
+         /  \      \
+        7    2      1
+return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
+'''
+# Definition for a binary tree node.
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+class Solution(object):
+    def hasPathSum(self, root, sum):
+        if not root:
+            return False
+        if root.val == sum and root.left is None and root.right is None:
+            return True
+        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
diff --git a/leetcode/113. Path Sum II.py b/leetcode/113. Path Sum II.py
@@ -0,0 +1,46 @@
+'''
+Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
+
+For example:
+Given the below binary tree and sum = 22,
+              5
+             / \
+            4   8
+           /   / \
+          11  13  4
+         /  \    / \
+        7    2  5   1
+return
+[
+   [5,4,11,2],
+   [5,8,4,5]
+]
+'''
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+class Solution(object):
+    def pathSum(self, root, sum):
+        if not root:
+            return []
+        if root.left == None and root.right == None:
+            if sum == root.val:
+                return [[root.val]]
+            else:
+                return []
+        stack = []
+        leftStack = self.pathSum(root.left, sum - root.val)
+        for i in leftStack:
+            i.insert(0, root.val)
+            stack.append(i)
+        rightStack = self.pathSum(root.right, sum - root.val)
+        for i in rightStack:
+            i.insert(0, root.val)
+            stack.append(i)
+        return stack
diff --git a/leetcode/192.WordFrequency.sh b/leetcode/192.WordFrequency.sh
@@ -0,0 +1,27 @@
+#!/bin/bash
+:<<!EOF!
+Write a bash script to calculate the frequency of each word in a text file words.txt.
+
+For simplicity sake, you may assume:
+
+words.txt contains only lowercase characters and space ' ' characters.
+Each word must consist of lowercase characters only.
+Words are separated by one or more whitespace characters.
+For example, assume that words.txt has the following content:
+
+the day is sunny the the
+the sunny is is
+
+Your script should output the following, sorted by descending frequency:
+the 4
+is 3
+sunny 2
+day 1
+Note:
+!EOF!
+
+awk '{for(i=1;i<=NF;i++) a[$i]++} END {for(k in a) print k,a[k]}' words.txt | sort -k2 -nr
+:<<!EOF!
+注释：
+awk文本分析；NF的值是每行的总列数；--k2 表示按照第二列排序 -nr表示按照逆序排列
+!EOF!
diff --git a/leetcode/83. Remove Duplicates from Sorted List.py b/leetcode/83. Remove Duplicates from Sorted List.py
@@ -0,0 +1,26 @@
+'''
+Given a sorted linked list, delete all duplicates such that each element appear only once.
+
+For example,
+Given 1->1->2, return 1->2.
+Given 1->1->2->3->3, return 1->2->3.
+'''
+
+# Definition for singly-linked list.
+class ListNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.next = None
+
+class Solution(object):
+    def deleteDuplicates(self, head):
+        """
+        :type head: ListNode
+        :rtype: ListNode
+        """
+        pNode = head
+        while pNode:
+            while pNode.next and pNode.next.val == pNode.val:
+                pNode.next = pNode.next.next
+            pNode = pNode.next
+        return head
diff --git a/leetcode/words.txt b/leetcode/words.txt
@@ -0,0 +1,2 @@
+the day is sunny 
+the the the sunny is is

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,2 @@`
	`1`	`+the day is sunny`
	`2`	`+the the the sunny is is`