week 1

sunshead · sunshead · commit 6e7dea8049cd · 2020-06-14T01:48:36.000-04:00
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+.idea
diff --git a/Week01/NOTE.md b/Week01/NOTE.md
@@ -1 +1,19 @@
-学习笔记
+#第一周学习笔记
+
+##PriorityQueue源码分析
+
+###父类与接口
+PriorityQueue类（下称PQ）继承了AbstractQueue这一抽象类，因而具有Queue的所有方法；同时它也实现了Serializable这一接口，
+因而PQ对象可以被表示为字节序列存储或传输。
+
+###底层逻辑结构与构造函数
+PQ的逻辑结构是一个通过数组实现的完全二叉树/堆。默认情况下PQ实现最小堆，但是可以通过传入一个comparator来实现自定义顺序存储。
+找节点的父节点和子节点可以通过以下索引：  
+leftChild = 2 * index + 1;
+rightChild = 2 * index + 2;
+parent = (index - 1) / 2;
+
+###时间复杂度
+添加和删除由于都需要在操作后调整二叉树中元素的排列来重新达到有序的状态，时间复杂度均为O(nlogn)（此为最坏情况下的时间复杂度，
+即插入的元素要从叶子节点sift up到根节点；或删除根节点后每一层的节点都需要sift up）。PQ的插入的平均时间复杂度也可以理解为
+O(1)，因为只需要在堆的最后插入。
diff --git a/Week01/problems/189_rotate-array.java b/Week01/problems/189_rotate-array.java
@@ -0,0 +1,11 @@
+class Solution {
+    public void rotate(int[] nums, int k) {
+        int[] copy = new int[nums.length];
+        for (int i = 0; i < nums.length; i++) {
+            copy[(i + k) % nums.length] = nums[i];
+        }
+        for (int i = 0; i < nums.length; i++) {
+            nums[i] = copy[i];
+        }
+    }
+}
diff --git a/Week01/problems/1_two-sum.java b/Week01/problems/1_two-sum.java
@@ -0,0 +1,17 @@
+class Solution {
+    public int[] twoSum(int[] nums, int target) {
+        int[] res = new int[2];
+        if (nums == null || nums.length < 2) {
+            return res;
+        }
+        Map<Integer, Integer> map = new HashMap<>();
+        for (int i = 0; i < nums.length; i++) {
+            int complement = target - nums[i];
+            if (map.containsKey(complement)) {
+                res = new int[]{ map.get(complement), i };
+            }
+            map.put(nums[i], i);
+        }
+        return res;
+    }
+}
diff --git a/Week01/problems/21_merge-two-sorted-lists.java b/Week01/problems/21_merge-two-sorted-lists.java
@@ -0,0 +1,29 @@
+class Solution {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        if (l1 == null) {
+            return l2;
+        }
+        if (l2 == null) {
+            return l1;
+        }
+        ListNode dummy = new ListNode(0);
+        ListNode head = dummy;
+        while (l1 != null && l2 != null) {
+            if (l1.val < l2.val) {
+                dummy.next = l1;
+                l1 = l1.next;
+            } else {
+                dummy.next = l2;
+                l2 = l2.next;
+            }
+            dummy = dummy.next;
+        }
+        if (l1 != null) {
+            dummy.next = l1;
+        }
+        if (l2 != null) {
+            dummy.next = l2;
+        }
+        return head.next;
+    }
+}
diff --git a/Week01/problems/26_remove-duplicates-from-sorted-array.java b/Week01/problems/26_remove-duplicates-from-sorted-array.java
@@ -0,0 +1,14 @@
+class Solution {
+    public int removeDuplicates(int[] nums) {
+        if (nums.length <= 1) {
+            return nums.length;
+        }
+        int j = 1;
+        for (int i = 1; i < nums.length; i++) {
+            if (nums[i] != nums[i-1]) {
+                nums[j++] = nums[i];
+            }
+        }
+        return j;
+    }
+}
diff --git a/Week01/problems/283_move-zeroes.java b/Week01/problems/283_move-zeroes.java
@@ -0,0 +1,15 @@
+class Solution {
+    public void moveZeroes(int[] nums) {
+        int nonZeroStart = 0;
+        for (int i = 0; i < nums.length; i++) {
+            if (nums[i] != 0) {
+                swap(nums, i, nonZeroStart++);
+            }
+        }
+    }
+    private void swap(int[] nums, int i, int j) {
+        int temp = nums[i];
+        nums[i] = nums[j];
+        nums[j] = temp;
+    }
+}
diff --git a/Week01/problems/42_trapping-rain-water.java b/Week01/problems/42_trapping-rain-water.java
@@ -0,0 +1,17 @@
+class Solution {
+    public int trap(int[] height) {
+        int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0, res = 0;
+        while (left < right) {
+            if (height[left] < height[right]) {
+                leftMax = Math.max(leftMax, height[left]);
+                res += leftMax - height[left];
+                left++;
+            } else {
+                rightMax = Math.max(rightMax, height[right]);
+                res += rightMax - height[right];
+                right--;
+            }
+        }
+        return res;
+    }
+}
diff --git a/Week01/problems/66_plus-one.java b/Week01/problems/66_plus-one.java
@@ -0,0 +1,18 @@
+class Solution {
+    public int[] plusOne(int[] digits) {
+        if (digits == null || digits.length == 0) {
+            return digits;
+        }
+        for (int i = digits.length - 1; i >= 0; i--) {
+            if (digits[i] < 9) {
+                digits[i]++;
+                return digits;
+            } else {
+                digits[i] = 0;
+            }
+        }
+        int[] res = new int[digits.length + 1];
+        res[0] = 1;
+        return res;
+    }
+}
diff --git a/Week01/problems/88_merge-sorted-array.java b/Week01/problems/88_merge-sorted-array.java
@@ -0,0 +1,15 @@
+class Solution {
+    public void merge(int[] nums1, int m, int[] nums2, int n) {
+        int index1 = m - 1, index2 = n - 1, index3 = m + n - 1;
+        while (index1 >= 0 && index2 >= 0) {
+            if (nums1[index1] > nums2[index2]) {
+                nums1[index3--] = nums1[index1--];
+            } else {
+                nums1[index3--] = nums2[index2--];
+            }
+        }
+        while (index2 >= 0) {
+            nums1[index3--] = nums2[index2--];
+        }
+    }
+}
