finish the homework of week 1

jgan123 · jgan123 · commit 22c85b6eacf8 · 2020-06-13T14:33:33.000+08:00
diff --git a/Week01/NOTE.md b/Week01/NOTE.md
@@ -1 +1,44 @@
-学习笔记
+#第一周学习笔记
+
+## 学习方法论
+
+1. 五毒神掌，反复看视频，反复练习，职业化手法（手动狗头）
+2. 画出思维导图，方便记忆和复习
+3. 不要死磕，多看看别人的题解，理解大神的思路，写出简洁和fancy的代码
+4. 掌握一些固定的解题模板，比如：
+
+```javascript
+/*** 暴力求解 ***/
+// 双层遍历
+for (let i = 0; i < len - 1; ++i) {
+	for (let j = i + 1; j < len; ++j) {
+		...
+	}
+}
+
+// 三层遍历
+for (let i = 0; i < len - 2; ++i) {
+	for (let j = i + 1; j < len - 1; ++j) {
+		for (let k = j + 1; k < len; ++k) {
+			...
+		}
+	}
+}
+
+/*** 循环中移动指针（代码精简） ***/
+while (p1 >= 0 && p2 >= 0) {
+	nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
+	...
+}
+
+```
+## 知识点
+ 
+* 时间复杂度和空间复杂度
+* 数组 (数组是栈和队列的基础)
+* 链表
+* 跳表
+* 栈
+* 队列
+* 优先队列
+* 双端队列
diff --git a/Week01/arrayMerge.js b/Week01/arrayMerge.js
@@ -0,0 +1,20 @@
+/**
+ * 合并两个有序数组
+ * @param {number[]} nums1
+ * @param {number} m
+ * @param {number[]} nums2
+ * @param {number} n
+ * @return {void} Do not return anything, modify nums1 in-place instead.
+ */
+var merge = function(nums1, m, nums2, n) {
+    let p1 = m - 1;
+    let p2 = n - 1;
+    let p = m + n - 1;
+    while (p2 >= 0) {
+        if (p1 >= 0) {
+            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
+        } else {
+            nums1[p--] = nums2[p2--];
+        }
+    }
+};
diff --git a/Week01/mergeTwoLists.js b/Week01/mergeTwoLists.js
@@ -0,0 +1,26 @@
+/**
+ * Definition for singly-linked list.
+ * function ListNode(val) {
+ *     this.val = val;
+ *     this.next = null;
+ * }
+ */
+/**
+ * 合并两个有序链表
+ * @param {ListNode} l1
+ * @param {ListNode} l2
+ * @return {ListNode}
+ */
+var mergeTwoLists = function(l1, l2) {
+    if (l1 == null) {
+        return l2;
+    } else if (l2 == null) {
+        return l1;
+    } else if (l1.val < l2.val) {
+        l1.next = mergeTwoLists(l1.next, l2);
+        return l1;
+    } else {
+        l2.next = mergeTwoLists(l1, l2.next); 
+        return l2;
+    }
+};
diff --git a/Week01/moveZeroes.js b/Week01/moveZeroes.js
@@ -0,0 +1,19 @@
+/**
+ * 移动0
+ * @param {number[]} nums
+ * @return {void} Do not return anything, modify nums in-place instead.
+ */
+var moveZeroes = function(nums) {
+    // 双指针
+    // 与删除排序数组中的重复项原地算法类似
+    let j = 0;
+    for (let i = 0; i < nums.length; ++i) {
+        if (nums[i] != 0) {
+            nums[j] = nums[i];
+            if (i != j) {
+                nums[i] = 0;
+            }
+            j++;
+        }
+    }
+};
diff --git a/Week01/plusOne.js b/Week01/plusOne.js
@@ -0,0 +1,16 @@
+/**
+ * @param {number[]} digits
+ * @return {number[]}
+ */
+var plusOne = function(digits) {
+    let k = 1;
+    for (let i = digits.length - 1; i >= 0; --i) {
+        let temp = digits[i];
+        digits[i] = (digits[i] + k) % 10;
+        k = Math.floor((temp + k) / 10);        
+    }
+    if (k > 0) {
+        digits.unshift(1);
+    }
+    return digits;
+};
diff --git a/Week01/removeDuplicates.js b/Week01/removeDuplicates.js
@@ -0,0 +1,23 @@
+/**
+ * 删除排序数组中的重复项 
+ * 原地算法
+ * @param {number[]} nums
+ * @return {number}
+ */
+var removeDuplicates = function(nums) {
+    if (!nums || nums.length <= 1) return nums;
+    // 双指针法
+    let head = 0;
+    let tail = 1;
+    while (tail < nums.length) {
+        if (nums[head] != nums[tail]) {
+        	// 优化无重复项情况
+            if (tail - head > 1) {
+                nums[head+1] = nums[tail];
+            }
+            head++;
+        }
+        tail++
+    }
+    return head + 1
+};
diff --git a/Week01/rotate.js b/Week01/rotate.js
@@ -0,0 +1,27 @@
+/**
+ * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
+ * @param {number[]} nums
+ * @param {number} k
+ * @return {void} Do not return anything, modify nums in-place instead.
+ */
+var rotate = function(nums, k) {
+    if (!nums || nums.length <= 1) return nums;
+    const reverse = (start, end) => {
+        while (start < end) {
+            let prev = nums[start];
+            nums[start] = nums[end];
+            nums[end] = prev;
+            start++;
+            end--;
+        }
+    }
+    // 处理k大于数组长度的情况
+    k = k % nums.length;
+    // 反转数组
+    reverse(0, nums.length - 1);
+    // 反转前k个元素
+    reverse(0, k - 1);
+    // 反转第k个之后的元素
+    reverse(k, nums.length - 1);
+    return nums;
+};
diff --git a/Week01/twoSum.js b/Week01/twoSum.js
@@ -0,0 +1,17 @@
+/**
+ * 两数之和
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[]}
+ */
+var twoSum = function(nums, target) {
+    let map = new Map();
+    for (let i = 0; i < nums.length; ++i) {
+        if (map.has(nums[i])) {
+            return [map.get(nums[i]), i];
+        } else {
+            map.set(target - nums[i], i);
+        }
+    }
+    return [];
+};
