Merge pull request algorithm004-01#244 from laxlyt/master

melody-li · web-flow · commit 6a550a2051b6 · 2019-10-22T13:17:21.000+08:00
246-Week 01
diff --git a/Week 01/id_246/LeetCode_189_246.py b/Week 01/id_246/LeetCode_189_246.py
@@ -0,0 +1,32 @@
+'''
+rotate-array
+
+给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
+
+示例 1:
+
+输入: [1,2,3,4,5,6,7] 和 k = 3
+输出: [5,6,7,1,2,3,4]
+解释:
+向右旋转 1 步: [7,1,2,3,4,5,6]
+向右旋转 2 步: [6,7,1,2,3,4,5]
+向右旋转 3 步: [5,6,7,1,2,3,4]
+'''
+
+nums = [1,2,3,4,5,6,7]
+
+#解法一
+def rotate_1(nums, k):
+    k %= len(nums)
+    nums[:] = nums[-k:]+nums[:-k]
+    return nums
+
+
+
+#解法二
+def rotate_2(nums, k):
+    k %= len(nums)
+    for _ in range(k):
+        nums.insert(0, nums.pop())
+    return nums
+
diff --git a/Week 01/id_246/LeetCode_1_246.py b/Week 01/id_246/LeetCode_1_246.py
@@ -0,0 +1,25 @@
+'''
+two-sum_1
+
+给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，
+并返回他们的数组下标。
+
+你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
+
+示例:
+给定 nums = [2, 7, 11, 15], target = 9
+
+因为 nums[0] + nums[1] = 2 + 7 = 9
+所以返回 [0, 1]
+'''
+
+nums = [2, 7, 11, 15]
+target = 9
+
+def twoSum(nums, target):
+        seen = {}
+        for i, v in enumerate(nums):
+            remaining = target - v
+            if remaining in seen:
+                return [seen[remaining], i]
+            seen[v] = i
diff --git a/Week 01/id_246/LeetCode_21_246.py b/Week 01/id_246/LeetCode_21_246.py
@@ -0,0 +1,43 @@
+'''
+merge two sorted lists
+
+将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
+
+示例：
+输入：1->2->4, 1->3->4
+输出：1->1->2->3->4->4
+'''
+
+#迭代
+l1 = create_linked_list([1,2,3,4,5])
+l2 = create_linked_list([6,7,8,9,10])
+
+def mergeTwoLists_1(l1, l2) :
+    # maintain an unchanging reference to node ahead of the return node.
+    prehead = ListNode(-1)
+    prev = prehead
+    while l1 and l2:
+        if l1.val <= l2.val:
+            prev.next = l1
+            l1 = l1.next
+        else:
+            prev.next = l2
+            l2 = l2.next
+        prev = prev.next
+    # the non-null list to the end of the merged list.
+    prev.next = l1 if l1 is not None else l2
+    return prehead.next
+
+
+# 递归
+def mergeTwoLists_2(l1,l2):
+    if l1 is None:
+        return l2
+    elif l2 is None:
+        return l1
+    elif l1.val < l2.val:
+        l1.next = mergeTwoLists_2(l1.next,l2)
+        return l1
+    else:
+        l2.next = mergeTwoLists_2(l1, l2.next)
+        return l2
diff --git a/Week 01/id_246/LeetCode_26_246.py b/Week 01/id_246/LeetCode_26_246.py
@@ -0,0 +1,21 @@
+'''
+remove duplicates from sorted
+
+给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
+
+不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
+
+给定数组 nums = [1,1,2],
+函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
+
+你不需要考虑数组中超出新长度后面的元素。
+'''
+
+nums = [1,1,2]
+
+def removeDuplicates(nums):
+    if nums:
+        nums[:len(set(nums))] = sorted(set(nums))
+        return len(set(nums))
+    else:
+        return 0
diff --git a/Week 01/id_246/LeetCode_66_246.py b/Week 01/id_246/LeetCode_66_246.py
@@ -0,0 +1,30 @@
+'''
+plus-one_66
+
+给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
+
+最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
+
+你可以假设除了整数 0 之外，这个整数不会以零开头。
+
+示例:
+输入: [1,2,3]
+输出: [1,2,4]
+解释: 输入数组表示数字 123。
+'''
+
+digits = [9,0,9,9]
+
+def plusOne(digits):
+    sum_ = 0
+    carry_ = 1
+
+    for i in range(len(digits)-1, -1, -1):
+        sum_ = digits[i] + carry_
+        carry_ = sum_ // 10
+        digits[i] = sum_ % 10
+
+    if carry_ > 0:
+        return [carry_] + digits
+
+    return digits
diff --git a/Week 01/id_246/LeetCode_88_246.py b/Week 01/id_246/LeetCode_88_246.py
@@ -0,0 +1,65 @@
+'''
+merge sorted array_88
+
+给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
+
+说明:
+
+初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
+你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
+
+示例:
+输入:
+nums1 = [1,2,3,0,0,0], m = 3
+nums2 = [2,5,6],       n = 3
+
+输出: [1,2,2,3,5,6
+'''
+
+#合并后排序, 时间复杂度较高
+num1 = [1,2,3]
+num2 = [5,5]
+
+def merge_1(num1, m, num2, n):
+    num1[:] = sorted(num1[:m] + num2)
+    return num1
+
+
+#双指针，从前往后
+
+def merge_2(num1, m, num2, n):
+    num1_copy = num1[:m]
+    num1[:] = []
+    p1 = 0
+    p2 = 0
+    while p1 < m and p2 < n:
+        if num1_copy[p1] < num2[p2]:
+            num1.append(num1_copy[p1])
+            p1 += 1
+        else:
+            num1.append(num2[p2])
+            p2 += 1
+
+    if p1 < m:
+        num1[p1+p2:] = num1_copy[p1:]
+    if p2 < n:
+        num1[p1+p2:] = num2[p2:]
+    return num1
+
+
+#双指针，从后往前
+
+def merge_3(num1, m, num2, n):
+    p1 = m-1
+    p2 = n-1
+    p = m + n -1
+    while p1 >= 0 and p2 >= 0:
+        if num1[p1] < num2[p2]:
+            num1[p] = num2[p2]
+            p2 -= 1
+        else:
+            num1[p] = num1[p1]
+            p1 -= 1
+        p -= 1
+    num1[:p2+1] = num2[:p2+1]
+    return num1
diff --git a/Week 01/id_246/NOTE.md b/Week 01/id_246/NOTE.md
@@ -1,4 +1,34 @@
 # NOTE
 
-  
+第一次系统接触数据结构和算法
 
+第一周课程接触链表和跳表相关内容，用python实现了简单的链表结构
+
+class ListNode:
+     def __init__(self, x):
+         self.val = x
+         self.next = None
+
+def create_linked_list(nums):
+    if not nums:
+        return
+    head = prev = ListNode(nums[0])
+    for num in nums[1:]:
+        tmp = ListNode(num)
+        prev.next = tmp
+        prev = prev.next
+    return head
+
+def print_linked_list(head):
+    nums = []
+    while head:
+        nums.append(head.val)
+        head = head.next
+        print(nums)
+    return nums
+
+head = create_linked_list([1,2,3,4,5,6,7,8,9])
+
+print_linked_list(head)
+
+接下来会补充其他数据结构的python实现
