add

haoyang.shi · haoyang.shi · commit 8c191896f394 · 2019-05-17T11:28:01.000+08:00
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -176,3 +176,17 @@
 	- [矩阵中的路径](offer/hasPath.md)
 	- [机器人的运动范围](offer/MovingCount.md)
 	- [剪绳子](offer/CutRope.md)
+	- [正则表达式匹配](offer/PatternMatch.md)
+	- [表示数值的字符串](offer/IsNumeric.md)
+	- [链表中环的入口](offer/EntryNodeOfLoop.md)
+	- [对称二叉树](offer/IsSymmetrical.md)
+	- [序列化二叉树](offer/SerializeTree.md)
+	- [数据流中的中位数](offer/StreamMid.md)
+	- [数字序列中的某一位的数字]()
+	- [把数字翻译成字符串]()
+	- [礼物的最大价值]()
+	- [最长不含重复字符的子字符串]()
+	- [在排序数组中查找数字]()
+	- [二叉搜索树的第K大节点]()
+	- [滑动窗口的最大值]()
+	- [股票的最大利润]()
diff --git a/offer/EntryNodeOfLoop.md b/offer/EntryNodeOfLoop.md
@@ -0,0 +1,36 @@
+# 链表中环的入口结点
+
+## 题目
+
+给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
+
+
+## 解题思路
+
+  1. 首先通过 **快慢指针**（快：每次走两步；慢：每次走一步）确定是否有环
+  2. 当有环时，再从头节点出发，与快指针按 **相同速度** 向前移动，当 `cursor = fast` 则找到环入口
+
+```
+public ListNode EntryNodeOfLoop(ListNode pHead) {
+    if (pHead == null || pHead.next == null) return null;
+
+    ListNode fast = pHead, slow = pHead;
+
+    while (fast.next != null) {
+        slow = slow.next;
+        fast = fast.next.next;
+
+        if (fast == slow) break;
+    }
+
+    if (fast != slow) return null;
+
+    ListNode cursor = pHead;
+    while (cursor != fast) {
+        cursor = cursor.next;
+        fast = fast.next;
+    }
+
+    return cursor;
+}
+```
diff --git a/offer/IsNumeric.md b/offer/IsNumeric.md
@@ -0,0 +1,63 @@
+# 表示数值的字符串
+
+## 题目
+
+请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
+
+
+## 解题思路
+
+  1. 数字符合 `A[.[B]][e|EC]` 和 `.B[e|EC]` 的表达式，其中 `A` 表示整数部分，`B` 表示小数部分，`C` 表示指数部分
+  2. `A` 可以有正负，但是 `B` 没有
+  3. `e|E` 之前、之后都必须有数字
+
+```
+public boolean isNumeric(char[] str) {
+    if (str == null || str.length == 0) return false;
+
+    int index = scanInteger(str, 0);
+
+    boolean numeric = index != 0;
+
+    //小数
+    if (index < str.length && str[index] == '.') {
+        index++;
+        int pre = index;
+        index = scanUnsignedInteger(str, index);
+
+        //1. 小数可以没有整数部分
+        //2. 小数后可以没有数字
+        //3. 小数后可以有数字
+        numeric |= index != pre;
+    }
+
+    //指数
+    if (index < str.length && (str[index] == 'e' || str[index] == 'E')) {
+        index++;
+        int pre = index;
+        index = scanInteger(str, index);
+
+        //1. e或者E之前必须有数字
+        //2. e或者E之后必须有数字
+        numeric &= index != pre;
+    }
+
+    return numeric && index == str.length;
+}
+
+private int scanInteger(char[] str, int s) {
+    if (s < str.length && (str[s] == '+' || str[s] == '-'))
+        s++;
+
+    return scanUnsignedInteger(str, s);
+}
+
+
+private int scanUnsignedInteger(char[] str, int s) {
+    while (s < str.length && str[s] >= '0' && str[s] <= '9') {
+        s++;
+    }
+
+    return s;
+}
+```
diff --git a/offer/IsSymmetrical.md b/offer/IsSymmetrical.md
@@ -0,0 +1,57 @@
+# 对称的二叉树
+
+## 题目
+
+请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
+
+## 解题思路
+
+  1. 定义一个对称的前序遍历，即`root -> right -> left` 与普通的前序遍历进行对比
+  2. 相同则认为树是对称的
+
+```
+boolean isSymmetrical(TreeNode pRoot) {
+    LinkedList<Integer> scanner = new LinkedList<>();
+    LinkedList<Integer> symmetricalScanner = new LinkedList<>();
+
+    preScanner(scanner, pRoot);
+    symmetricalPreScanner(symmetricalScanner, pRoot);
+
+    return scanner.equals(symmetricalScanner);
+}
+
+/**
+ * 普通的前序遍历
+ * @param res
+ * @param root
+ */
+private void preScanner(LinkedList<Integer> res, TreeNode root) {
+    if (root == null) {
+        res.addLast(null);
+        return;
+    }
+
+    res.addLast(root.val);
+
+    preScanner(res, root.left);
+    preScanner(res, root.right);
+}
+
+/**
+ * 先右再左的前序遍历
+ * @param res
+ * @param root
+ */
+private void symmetricalPreScanner(LinkedList<Integer> res, TreeNode root) {
+    if (root == null) {
+        res.addLast(null);
+        return;
+    }
+
+    res.addLast(root.val);
+
+    symmetricalPreScanner(res, root.right);
+    symmetricalPreScanner(res, root.left);
+}
+
+```
diff --git a/offer/PatternMatch.md b/offer/PatternMatch.md
@@ -0,0 +1,44 @@
+# 正则表达式匹配
+
+请实现一个函数用来匹配包括`'.'`和`'*'`的正则表达式。模式中的字符`'.'`表示任意一个字符，而`'*'`表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串`"aaa"`与模式`"a.a"`和`"ab*ac*a"`匹配，但是与`"aa.a"`和`"ab*a"`均不匹配
+
+
+## 解题思路
+
+  1. 对于 `*` 有三种匹配模式：匹配0次，1次以及多次
+  2. 对于 `.` 只有一种匹配模式
+
+```
+public boolean match(char[] str, char[] pattern) {
+    if (str.length == 0 && new String(pattern).replaceAll(".\\*", "").length() == 0) {
+        return true;
+    }
+
+    return match(str, 0, pattern, 0);
+}
+
+private boolean match(char[] str, int i, char[] pattern, int j) {
+    if (i == str.length && j == pattern.length) {
+        return true;
+    }
+
+    if (j >= pattern.length) return false;
+
+    if (j + 1 < pattern.length && pattern[j + 1] == '*') {
+        if ((i < str.length && pattern[j] == str[i]) || (pattern[j] == '.' && i != str.length)) {
+            return match(str, i + 1, pattern, j + 2)
+                    || match(str, i + 1, pattern, j)
+                    || match(str, i, pattern, j + 2);
+        } else {
+            return match(str, i, pattern, j + 2);
+        }
+    }
+
+    if ((i < str.length && pattern[j] == str[i])
+            || (pattern[j] == '.' && i != str.length)) {
+        return match(str, i + 1, pattern, j + 1);
+    }
+
+    return false;
+}
+```
diff --git a/offer/SerializeTree.md b/offer/SerializeTree.md
@@ -0,0 +1,57 @@
+# 序列化二叉树
+
+## 题目
+
+请实现两个函数，分别用来序列化和反序列化二叉树
+
+## 解题思路
+
+  1. 通过前序遍历，进行序列化和反序列化
+  2. 对于空节点用 `$` 来代替
+
+```
+String Serialize(TreeNode root) {
+    if (root==null) return "";
+
+    LinkedList<String> res = new LinkedList<>();
+
+    serialize(res, root);
+
+    StringBuilder builder = new StringBuilder();
+    res.forEach(v-> builder.append(v).append(","));
+
+    return builder.toString();
+}
+
+
+private void serialize(LinkedList<String> res, TreeNode root) {
+    if (root == null) {
+        res.addLast("$");
+        return;
+    }
+
+    res.addLast(String.valueOf(root.val));
+    serialize(res, root.left);
+    serialize(res, root.right);
+}
+
+TreeNode Deserialize(String str) {
+    if (str == null || str.length() == 0) return null;
+
+    return deserialize(str.split(","), new int[]{0});
+}
+
+
+private TreeNode deserialize(String[] str, int[] index) {
+    if (index[0] >= str.length) return null;
+
+    String c = str[index[0]++];
+    if (c.equals("$")) return null;
+
+    TreeNode node = new TreeNode(Integer.valueOf(c));
+    node.left = deserialize(str, index);
+    node.right = deserialize(str, index);
+
+    return node;
+}
+```
diff --git a/offer/StreamMid.md b/offer/StreamMid.md
@@ -0,0 +1,54 @@
+# 数据流中的中位数
+
+## 题目
+
+[牛客网](https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&tPage=4&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking)
+
+如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用 `Insert()` 方法读取数据流，使用 `GetMedian()` 方法获取当前读取数据的中位数。
+
+
+## 解题思路
+
+  1. 同两个堆来表示中位数的左右两部分，左边是大根堆，右边是小根堆
+  2. 在插入元素时，两边元素个数最多只能相差1，并且要保证左边的元素均小于右边的元素
+  3. 当插入大堆的元素大于部分小堆元素时，需要将大堆的 top 元素移动到小堆，反之亦然
+
+```
+private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> -o1.compareTo(o2));
+
+private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+
+private int size = 0;
+
+
+public void Insert(Integer num) {
+    if (size % 2 == 0) {
+        maxHeap.add(num);
+
+        if (minHeap.isEmpty() || num > minHeap.peek()) {
+            minHeap.add(maxHeap.poll());
+        }
+
+    } else {
+        minHeap.add(num);
+
+        if (maxHeap.isEmpty() || num < maxHeap.peek()) {
+            maxHeap.add(minHeap.poll());
+        }
+    }
+
+    size++;
+}
+
+public Double GetMedian() {
+    if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0.0;
+    if (maxHeap.isEmpty()) return minHeap.peek() * 1.0;
+    if (minHeap.isEmpty()) return maxHeap.peek() * 1.0;
+
+    if (maxHeap.size() == minHeap.size()) {
+        return (maxHeap.peek() + minHeap.peek()) / 2.0;
+    }
+
+    return maxHeap.size() > minHeap.size() ? maxHeap.peek() * 1.0 : minHeap.peek() * 1.0;
+}
+```
