week01-homework

zlWorkStudy · zlWorkStudy · commit b804f304e892 · 2020-06-14T21:44:15.000+08:00
diff --git a/Week01/NOTE.md b/Week01/NOTE.md
@@ -1 +1,41 @@
-学习笔记
+## 数据结构时间复杂度
+<br/>
+
+|  类型  |   add  | remove |  query | modify | peculiarity |
+| :----: | :----: | :----: | :----: | :----: | :----: |
+| Array  | O(n) | O(n) | O(1) | O(1) | 随机加速访问 |
+| Linked List | O(1) | O(1) | O(n) | O(1) | next指针 |
+| Double Linked List | O(1) | O(1) | O(n) | O(1) | pre,next指针 |
+| Skip List | O(logn) | O(logn) | O(logn) | -- | 元素有序 |
+| Stack | O(1) | O(1) | O(n) | -- | 后进先出 |
+| Queue | O(1) | O(1) | O(n) | -- | 先进先出 |
+| Deque | O(1) | O(1) | O(n) | -- | 两端都可进出的Quue |
+| Priority Queue | O(1) | -- | O(logn) | -- | 两端都可进出的Quue |
+<br/>
+
+## PriorityQueue分析
+```
+balanced binary heap:
+	父结点的键值总是小于或等于任何一个子节点的键值
+	基于数组实现的二叉堆，对于数组中任意位置的n上元素，其左孩子在[2n+1]位置上，右孩子[2(n+1)]位置，它的父亲则在[n-1/2]上，而根的位置则是[0]
+fields:
+	comparator--比较器，无此参数元素使用自然排序
+	queue--数组(存数据)
+	size--元素个数
+method:
+	#grow -- 数组扩容
+	#hugeCapacity -- 容量:0-Integer.MAX_VALUE
+	#add -- 调用offer(E e)
+	#offer -- size >= queue.length (扩容)，size == 0直接添加为根，否则从队尾开始上移 --> siftUp
+	#siftUp
+		#siftUpComparable -- 一直上移至找到父节点
+		#siftUpUsingComparator -- 操作类似，自然排序
+	#peek -- 查看队列首元素，空时返回null
+	#indexOf -- 查看元素对应下标
+	#remove -- 获取要移除元素下标i，--size,提取e = queue[size],queue[size] = null, i < size / 2将queue[i]不断下移，否则上移
+	#poll -- 移除根， --size,提取e = queue[size],queue[size] = null，queue[i]不断下移，直到queue[i]的最小孩子比e 大为止
+	#siftDown
+		#siftDownComparable	-- 以k为父节点找子节点(left, right),c = queue[left], 
+				如果left < right && queue[left] > queue[right] { c = queue[right] },交换父节点和c;直至队尾元素比c的子节点都要小
+		#siftDownUsingComparator -- 操作类似，自然排序
+```
diff --git a/Week01/homework.md b/Week01/homework.md
@@ -0,0 +1,129 @@
+## Week01 homework
+<br>
+
+### 删除排序数组中的重复项
+```java
+public int removeDuplicates(int[] nums) {
+    if (nums == null && nums.length == 0) {
+        return 0;
+    }
+    int left = 0;
+    for (int i = 1; i < nums.length; i++) {
+        if (nums[i] != nums[left]) {
+            nums[++left] = nums[i];
+        }
+    }
+    return ++left;
+}
+```
+<br/>
+
+### 旋转数组
+```java
+public void rotate(int[] nums, int k) {
+    // 使用环状替代，k %= nums.length
+    k %= nums.length;
+    int count = 0;
+    for (int start = 0; count < nums.length; start++) {
+        int current = start;
+        int pre = nums[start];
+        do {
+            int next = (current + k) % nums.length;
+            int temp = nums[next];
+            nums[next] = pre;
+            pre = temp;
+            current = next;
+            count++;
+        } while (start != current);
+    }
+}
+```
+<br/>
+
+### 合并两个有序链表
+```java
+public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+    ListNode preHead = new ListNode(-1);
+    ListNode pre = preHead;
+    while (l1 != null && l2 != null) {
+        if (l1.val < l2.val) {
+            pre.next = l1;
+            l1 = l1.next;
+        } else {
+            pre.next = l2;
+            l2 = l2.next;
+        }
+        pre = pre.next;
+    }
+    pre.next = l1 == null ? l2 : l1;
+    return preHead.next;
+}
+```
+<br/>
+
+### 合并两个有序数组
+```java
+public void merge(int[] nums1, int m, int[] nums2, int n) {
+    while (m > 0 && n > 0) {
+        nums1[m + n - 1] = nums1[m - 1] > nums2[n - 1] ? nums1[--m] : nums2[--n];
+    }
+    for (int i = 0; i < n; i++) {
+        nums1[i] = nums2[i];
+    }
+}
+```
+<br/>
+
+### 两数之和
+```java
+public int[] twoSum(int[] nums, int target) {
+    // 循环遍历数组，num[i]存在于map中，直接返回map中的value和i
+    // 否则，将key:target - nums[i]     value:i 存入map中
+    int length = nums.length;
+    Map<Integer, Integer> map = new HashMap<>(length);
+    for (int i = 0; i < length; i++) {
+        if (map.containsKey(nums[i])) {
+            return new int[]{map.get(nums[i]), i};
+        }
+        map.put(target - nums[i], i);
+    }
+    return null;
+}
+```
+<br/>
+
+### 移动零
+```java
+public void moveZeroes(int[] nums) {
+    if (nums == null) {
+        return;
+    }
+    int index = 0;
+    for (int i = 0; i < nums.length; i++) {
+        if (nums[i] != 0) {
+            if (index != i) {
+                nums[index] = nums[i];
+                nums[i] = 0;
+            }
+            index++;
+        }
+    }
+}
+```
+
+### 加一
+```java
+public int[] plusOne(int[] digits) {
+    // digits数组中所有位全进1，则新new一个digits.length + 1长度的数组，并把首位置为1
+    for (int i = digits.length - 1; i >= 0; i--) {
+        digits[i] += 1;
+        if (digits[i] % 10 != 0) {
+            return digits;
+        }
+        digits[i] = 0;
+    }
+    digits = new int[digits.length + 1];
+    digits[0] = 1;
+    return digits;
+}
+```
