nature1995
diff --git a/‎Python3/017_Letter_Combinations_of_a_Phone_Number.py
Copy file name to clipboard
+52Lines changed: 52 additions & 0 deletions b/‎Python3/017_Letter_Combinations_of_a_Phone_Number.py
Copy file name to clipboard
+52Lines changed: 52 additions & 0 deletions
diff --git a/‎Python3/018_4Sum.py
Copy file name to clipboard
+52Lines changed: 52 additions & 0 deletions b/‎Python3/018_4Sum.py
Copy file name to clipboard
+52Lines changed: 52 additions & 0 deletions
diff --git a/‎Python3/019_Remove_Nth_Node_From_End_of_List.py
Copy file name to clipboard
+68Lines changed: 68 additions & 0 deletions b/‎Python3/019_Remove_Nth_Node_From_End_of_List.py
Copy file name to clipboard
+68Lines changed: 68 additions & 0 deletions
@@ -0,0 +1,52 @@
+#!usr/bin/env python3
+# -*- coding:utf-8 -*-
+'''
+Given a digit string, return all possible letter combinations that the number could represent.
+
+A mapping of digit to letters (just like on the telephone buttons) is given below.
+
+Input:Digit string "23"
+Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
+Note:
+Although the above answer is in lexicographical order, your answer could be in any order you want.
+'''
+
+
+class Solution:
+    digit2letters = {
+        '2': "abc",
+        '3': "def",
+        '4': "ghi",
+        '5': "jkl",
+        '6': "mno",
+        '7': "pqrs",
+        '8': "tuv",
+        '9': "wxyz",
+    }
+
+    def letterCombinations(self, digits):
+        """
+        :type digits: str
+        :rtype: List[str]
+        """
+        if not digits:
+            return []
+        result = []
+        self.dfs(digits, "", result)
+        return result
+
+    def dfs(self, digits, current, result):
+        if not digits:
+            result.append(current)
+            return
+        for c in self.digit2letters[digits[0]]:
+            self.dfs(digits[1:], current + c, result)
+
+
+if __name__ == "__main__":
+    assert Solution().letterCombinations("23") == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
+
+
+
+
+
@@ -0,0 +1,52 @@
+#!usr/bin/env python3
+# -*- coding:utf-8 -*-
+'''
+Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
+
+Note:
+Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
+The solution set must not contain duplicate quadruplets.
+    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
+
+    A solution set is:
+    (-1,  0, 0, 1)
+    (-2, -1, 1, 2)
+    (-2,  0, 0, 2)
+'''
+
+
+class Solution(object):
+    def fourSum(self, nums, target):
+        """
+        :type nums: List[int]
+        :type target: int
+        :rtype: List[List[int]]
+        """
+        if len(nums) < 4:
+            return []
+        result = set()
+        sumsIndexes = {}
+        for i in range(len(nums)):
+            for j in range(i + 1, len(nums)):
+                if nums[i] + nums[j] in sumsIndexes:
+                    sumsIndexes[nums[i] + nums[j]].append((i, j))
+                else:
+                    sumsIndexes[nums[i] + nums[j]] = [(i, j)]
+
+        for i in range(len(nums)):
+            for j in range(i + 1, len(nums)):
+                sumNeeded = target - (nums[i] + nums[j])
+                if sumNeeded in sumsIndexes:
+                    for index in sumsIndexes[sumNeeded]:
+                        if index[0] > j:
+                            result.add(tuple(sorted([nums[i], nums[j], nums[index[0]], nums[index[1]]])))
+        result = [list(l) for l in result]
+        return result
+
+
+if __name__ == "__main__":
+    assert Solution().fourSum([1, 0, -1, 0, -2, 2], 0) == [[-1, 0, 0, 1], [-2, 0, 0, 2], [-2, -1, 1, 2]]
+
+
+
+
@@ -0,0 +1,68 @@
+#!usr/bin/env python3
+# -*- coding:utf-8 -*-
+'''
+Given a linked list, remove the nth node from the end of list and return its head.
+
+For example,
+
+   Given linked list: 1->2->3->4->5, and n = 2.
+
+   After removing the second node from the end, the linked list becomes 1->2->3->5.
+Note:
+Given n will always be valid.
+Try to do this in one pass.
+'''
+
+
+# Definition for singly-linked list.
+class ListNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.next = None
+
+    # Define this to check if it works well
+    def myPrint(self):
+        print(self.val)
+        if self.next:
+            self.next.myPrint()
+
+
+class Solution(object):
+    def removeNthFromEnd(self, head, n):
+        """
+        :type head: ListNode
+        :type n: int
+        :rtype: ListNode
+        """
+        if not head:
+            return head
+        point = ListNode(-1)
+        point.next = head
+        prev = point
+        cur = point
+        while prev and n >=0:
+            prev = prev.next
+            n -= 1
+        while prev:
+            prev = prev.next
+            cur = cur.next
+        cur.next = cur.next.next
+        return point.next
+
+
+if __name__ == "__main__":
+    n5 = ListNode(5)
+    n4 = ListNode(4)
+    n3 = ListNode(3)
+    n2 = ListNode(2)
+    n1 = ListNode(1)
+    n1.next = n2
+    n2.next = n3
+    n3.next = n4
+    n4.next = n5
+    result = Solution().removeNthFromEnd(n1, 5)
+    result.myPrint()
+
+
+
+