week01 assignment

Jane0111 · Jane0111 · commit 2ad68c368877 · 2020-06-14T23:55:30.000+02:00
diff --git a/.idea/.gitignore b/.idea/.gitignore
diff --git a/Week01/NOTE.md b/Week01/NOTE.md
@@ -1 +1,16 @@
-学习笔记
+#学习笔记 
++ 如果需要对一个数组变量，进行原地操作，要在数组变量名字的后面加上[:]
++ 如何实现链表\[python\]
+    + 链表的类
+    + 哑节点的使用可以避免代码进行冗余的判断
+```python
+class ListNode:
+    def __init__(self, val=0, next=None):
+        self.val = val
+        self.next = next
+
+dummy = ListNode(0) #作为头节点使用，具体的值不重要，最后输出dummy.next即可
+```
+
+    
+
diff --git a/Week01/assignment01_L26_Remove Duplicates from Sorted Array.py b/Week01/assignment01_L26_Remove Duplicates from Sorted Array.py
@@ -0,0 +1,9 @@
+from typing import List
+class Solution:
+    def removeDuplicates(self, nums: List[int]) -> int:
+        curr = 0
+        for i in range(1,len(nums)):
+            if nums[i] != nums[curr]:
+                curr += 1
+                nums[curr] = nums[i]
+        return curr+1
diff --git a/Week01/assignment02_L189_Rotate Array.py b/Week01/assignment02_L189_Rotate Array.py
@@ -0,0 +1,8 @@
+from typing import List
+class Solution:
+    def rotate(self, nums: List[int], k: int) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        nums[:] = nums[len(nums)-k%len(nums):]+nums[:len(nums)-k%len(nums)]
+        return
diff --git a/Week01/assignment03_L88_Merge Sorted Array.py b/Week01/assignment03_L88_Merge Sorted Array.py
@@ -0,0 +1,17 @@
+from typing import List
+class Solution:
+    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
+        """
+        Do not return anything, modify nums1 in-place instead.
+        """
+        p = m-1
+        q = n-1
+        while p >= 0 and q >= 0:
+            if nums1[p] < nums2[q]:
+                nums1[p+q+1] = nums2[q]
+                q -= 1
+            else:
+                nums1[p+q+1] = nums1[p]
+                p -= 1
+        nums1[:q+1] = nums2[:q+1]
+        return nums1
diff --git a/Week01/assignment04_L21_Merge Two Sorted Lists.py b/Week01/assignment04_L21_Merge Two Sorted Lists.py
@@ -0,0 +1,16 @@
+class ListNode:
+    def __init__(self, val=0, next=None):
+        self.val = val
+        self.next = next
+
+
+class Solution:
+    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
+        if not l1 or not l2:
+            return l1 or l2
+        if l1.val <= l2.val:
+            l1.next = self.mergeTwoLists(l1.next, l2)
+            return l1
+        else:
+            l2.next = self.mergeTwoLists(l1, l2.next)
+            return l2
diff --git a/Week01/assignment05_L1_two sum.py b/Week01/assignment05_L1_two sum.py
@@ -0,0 +1,10 @@
+from typing import List
+class Solution:
+    def twoSum(self, nums: List[int], target: int) -> List[int]:
+        d = {}
+        for i,n in enumerate (nums):
+            m = target - n
+            if m in d:
+                return [d[m],i]
+            else:
+                d[n] = i
diff --git a/Week01/assignment06_L283_Move Zeroes.py b/Week01/assignment06_L283_Move Zeroes.py
@@ -0,0 +1,34 @@
+from typing import List
+
+class Solution:
+    def moveZeroes(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+
+        # 统计0的个数，添在数组后面
+        # unzero_counter = 0
+        # for j in range(len(nums)):
+        #     if nums[j] != 0:
+        #         nums[unzero_counter] = nums[j]
+        #         unzero_counter += 1
+        # zero_counter = len(nums)-unzero_counter
+        # nums[unzero_counter:] = [0] * (zero_counter)
+
+        # 双下标
+        # unzero_counter = 0
+        # for i in range(len(nums)):
+        #     if nums[i] != 0:
+        #         nums[unzero_counter] = nums[i]
+        #         if i != unzero_counter:
+        #             nums[i] = 0
+        #         unzero_counter += 1
+
+        # 交换位置
+        j = 0
+        for i in range(len(nums)):
+            if nums[i] != 0:
+                nums[j], nums[i] = nums[i], nums[j]
+                j += 1
+
+        return nums
diff --git a/Week01/assignment07_L66_Plus One.py b/Week01/assignment07_L66_Plus One.py
@@ -0,0 +1,18 @@
+from typing import List
+class Solution:
+    def plusOne(self, digits: List[int]) -> List[int]:
+
+        # # string 解法
+        # str_digits = [str(i) for i in digits]
+        # new_digits = int("".join(str_digits))
+        # new_digits += 1
+        # res = [int(j) for j in str(new_digits)]
+        # return res
+
+        # recursion
+        if digits == []:
+            return [1]
+        elif digits[-1] < 9:
+            return digits[:-1]+[digits[-1]+1]
+        else:
+            return self.plusOne(digits[:-1])+[0]
