提交作业

Kerwin12 · Kerwin12 · commit e086afc12a47 · 2020-06-13T23:01:50.000+08:00
diff --git a/Week01/NOTE.md b/Week01/NOTE.md
@@ -1 +1,116 @@
-学习笔记
+## 学习笔记
+
+### 五毒神掌刷题法
+    1. 刷题第一遍：
+        - 五分钟：读题 + 思考
+        - 直接看解法：多解法要比较解法优劣
+    2. 刷题第二遍
+        - 马上自己写，LeetCode提交
+        - 多解法比较、体会 -> 优化
+    3. 刷题第三遍
+        - 过了一天后，再重复做题
+    4. 刷题第四遍
+        - 过了一周：反复回来练习相同的题目，不熟练的题目反复练习
+    5. 面试前一周恢复训练
+    
+### 数组
+
+#### 特点
+    1. 内存地址连续
+    2. 访问时间复杂度 O(1)
+    3. 插入中间或删除中间需要位移其他元素，修改的时间复杂度为 O(n)
+    4. 前插 O(1)，可采用申请稍大内存空间，数组最开始的地方预留的方式降低复杂度至 O(1)，正常是 O(n)
+    5. 后插 O(1)
+
+### 链表
+
+#### 特点
+    1. 内存地址不连续
+    2. 访问时间复杂度 O(n)
+    3. 插入或删除中间元素的时间复杂度 O(1)
+    4. 前插（头插）O(1)
+    5. 后插（尾插）O(1)
+    
+#### 标准实现
+```java
+class LinkedList {
+    Node head; // head of list
+    
+    /* Linked list node */
+    class Node {
+        int data;
+        Node next;
+        
+        // Constructor to create a new node
+        // Next is by default initialized 
+        // as null
+        Node(int d) {
+            data = d;
+        }   
+    }
+}
+``` 
+
+#### 链表插入元素的过程
+    1. 插入节点的 next 指针指向前驱节点的 next;
+    2. 前驱节点的 next 指针指向插入节点;
+
+
+java 中的 LinkedList (双向链表)
+
+
+
+
+### 跳表
+
+#### 特点
+    1. 只能用于元素有序的情况;
+    2. 插入/搜索/删除复杂度都是O(log n)
+    3. 空间复杂度为 O(n)，因为累加值收敛
+
+##### 对比平衡树
+
+###### 优势
+原理简单，容易实现，方便扩展，效率更高。
+
+###### 劣势
+插入删除元素时需要同时更新索引，也是增加删除时间复杂度为 O(log n) 的原因
+
+##### 应用
+Redis, LevelDB
+    
+##### 实现原理
+使用多级索引，通过空间换取时间的方式减少链表查询次数，查询方式类似二分查找。
+
+
+#### 链接:
+- [Java 源码分析（ArrayList）](http://developer.classpath.org/doc/java/util/ArrayList-source.html)
+- [Linked List 的标准实现代码](https://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/)
+- [Linked List 示例代码](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/code/LinkedList.java)
+- [Java 源码分析（LinkedList）](http://developer.classpath.org/doc/java/util/LinkedList-source.html)
+- [LRU Cache - Linked list： LRU 缓存机制](https://leetcode-cn.com/problems/lru-cache/)
+- [Redis - Skip List：跳跃表](https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html) 、[为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？](https://www.zhihu.com/question/20202931)
+
+
+
+### 栈
+
+#### 特点
+    1. 先入后出
+    2. 添加、删除皆为 O(1)
+    3. 查询为 O(n)
+    
+    
+### 队列
+
+#### 特点
+    1. 先入先出
+    2. 添加、删除皆为 O(1)
+    3. 查询为 O(n)
+
+
+### 双端队列
+
+#### 特点
+    1. 头尾都可以出入
+    2. 插入和删除都是 O(1)
diff --git a/Week01/加一.java b/Week01/加一.java
@@ -0,0 +1,25 @@
+/**
+ * 题目：加一
+ * 题目地址：https://leetcode-cn.com/problems/plus-one/
+ * 解法描述：从右往左遍历数组，加一余十存余数，若余数为零，则继续遍历，余数不为零则返回结果。
+ * 		边界值处理：若最后一个值（数组零位）也产生了进位，返回一个长度比原数组大一的新数组，零号位为一，其余填补零。
+ * 时间复杂度：O(n)
+ * 空间复杂度：O(n)
+ * 备注：若产生最高位进位，开辟了一块新的数组内存空间
+ * 0ms 37.8MB
+ */
+class Solution2 {
+	public int[] plusOne(int[] digits) {
+		int forward = 1;
+		for (int i = digits.length - 1; i >= 0; i--) {
+			digits[i]++;
+			digits[i] = digits[i] % 10;
+			if (digits[i] != 0) {
+				return digits;
+			}
+		}
+		digits = new int[digits.length + 1];
+		digits[0] = 1;
+		return digits;
+	}
+}
diff --git a/Week01/接雨水.java b/Week01/接雨水.java
@@ -0,0 +1,30 @@
+/**
+ * 题目：接雨水
+ * 题目地址：https://leetcode-cn.com/problems/trapping-rain-water/submissions/
+ * 解法描述：利用栈。
+ * 			遍历数组
+ * 			若当前值小于等于栈顶值，则当前索引位入栈
+ * 			若下一个值大于栈顶索引对应的值，则弹出当前栈顶。若此时栈不为空，算出弹出索引位的蓄水量。
+ * 		此时弹出索引位的左边界由弹出后的栈顶索引位对应的值决定，右边界由当前数组遍历的值决定。
+ * 时间复杂度：O(n)
+ * 空间复杂度：O(n)
+ * 3ms	39.4MB
+ */
+class Solution1 {
+	public int trap(int[] height) {
+		int ans = 0, current = 0;
+		Stack<Integer> st = new Stack<Integer>();
+		while (current < height.length) {
+			while (!st.empty() && height[current] > height[st.peek()]) {
+				int top = st.pop();
+				if (st.empty())
+					break;
+				int distance = current - st.peek() - 1;
+				int bounded_height = Math.min(height[current], height[st.peek()]) - height[top];
+				ans += distance * bounded_height;
+			}
+			st.push(current++);
+		}
+		return ans;
+	}
+}
