nature1995
diff --git a/‎Python3/035_Search_Insert_Position.py
Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions b/‎Python3/035_Search_Insert_Position.py
Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions
diff --git a/‎Python3/036_Valid_Sudoku.py
Copy file name to clipboardExpand all lines: Python3/036_Valid_Sudoku.py b/‎Python3/036_Valid_Sudoku.py
Copy file name to clipboardExpand all lines: Python3/036_Valid_Sudoku.py
diff --git a/‎Python3/039_Combination_Sum.py
Copy file name to clipboard
+46Lines changed: 46 additions & 0 deletions b/‎Python3/039_Combination_Sum.py
Copy file name to clipboard
+46Lines changed: 46 additions & 0 deletions
@@ -0,0 +1,42 @@
+#!usr/bin/env python3
+# -*- coding:utf-8 -*-
+'''
+Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
+
+You may assume no duplicates in the array.
+
+Here are few examples.
+[1,3,5,6], 5 → 2
+[1,3,5,6], 2 → 1
+[1,3,5,6], 7 → 4
+[1,3,5,6], 0 → 1
+'''
+
+
+class Solution(object):
+    def searchInsert(self, nums, target):
+        """
+        :type nums: List[int]
+        :type target: int
+        :rtype: int
+        """
+        length = len(nums)
+        start = 0
+        end = length
+        while start < end:
+            mid = (start + end) // 2
+            if nums[mid] == target or (nums[mid] > target and (mid == 0 or nums[mid - 1] < target)):
+                return mid
+            if mid == length - 1 and nums[mid] < target:
+                return mid + 1
+            if nums[mid] < target:
+                start = mid + 1
+            else:
+                end = mid
+
+
+if __name__ == "__main__":
+    assert Solution().searchInsert([1, 3, 5, 6], 5) == 2
+    assert Solution().searchInsert([1, 3, 5, 6], 2) == 1
+    assert Solution().searchInsert([1, 3, 5, 6], 7) == 4
+    assert Solution().searchInsert([1, 3, 5, 6], 0) == 0
@@ -0,0 +1,46 @@
+#!usr/bin/env python3
+# -*- coding:utf-8 -*-
+'''
+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]
+'''
+
+
+class Solution(object):
+    def combinationSum(self, candidates, target):
+        """
+        :type candidates: List[int]
+        :type target: int
+        :rtype: List[List[int]]
+        """
+        if not candidates:
+            return []
+        candidates.sort()
+        result = []
+        self.combination(candidates, target, [], result)
+        return result
+
+    def combination(self, candidates, target, current, result):
+        s = sum(current) if current else 0
+        if s > target:
+            return
+        elif s == target:
+            result.append(current)
+            return
+        else:
+            for i, v in enumerate(candidates):
+                self.combination(candidates[i:], target, current + [v], result)
+
+
+if __name__ == "__main__":
+    assert Solution().combinationSum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]