offer two

haoyang.shi · haoyang.shi · commit e0451336ce94 · 2019-05-17T18:53:59.000+08:00
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -182,11 +182,11 @@
 	- [对称二叉树](offer/IsSymmetrical.md)
 	- [序列化二叉树](offer/SerializeTree.md)
 	- [数据流中的中位数](offer/StreamMid.md)
-	- [数字序列中的某一位的数字]()
-	- [把数字翻译成字符串]()
-	- [礼物的最大价值]()
-	- [最长不含重复字符的子字符串]()
-	- [在排序数组中查找数字]()
-	- [二叉搜索树的第K大节点]()
+	- [数字序列中的某一位的数字](offer/NOfNumberSerialize.md)
+	- [把数字翻译成字符串](offer/TranslateNumToStr.md)
+	- [礼物的最大价值](offer/MaxGift.md)
+	- [最长不含重复字符的子字符串](offer/LongestNoRepeatSubString.md)
+	- [在排序数组中查找数字](offer/CountOfSortedArray.md)
+	- [二叉搜索树的第K大节点](offer/BSTKthNode.md)
 	- [滑动窗口的最大值]()
 	- [股票的最大利润]()
diff --git a/offer/BSTKthNode.md b/offer/BSTKthNode.md
@@ -0,0 +1,41 @@
+# 二叉搜索树的第k个结点
+
+## 题目
+
+
+给定一棵二叉搜索树，请找出其中的第 k 小的结点。例如，`5，3，7，2，4，6，8` 中，按结点数值大小顺序第三小结点的值为4。
+
+[牛客网](https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11215&tPage=4&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking)
+
+
+## 解题思路
+
+  1. BST 中序遍历的结果就是排序后的结果
+
+```
+public TreeNode KthNode(TreeNode pRoot, int k) {
+    TreeNode[] nodes = new TreeNode[1];
+
+    int[] ints = {0};
+
+    KthNode(pRoot, k, nodes, ints);
+
+    return nodes[0];
+}
+
+private void KthNode(TreeNode root, int k, TreeNode[] res, int[] cursor) {
+    if (root == null) return;
+
+    if (res[0] != null) return;
+
+    KthNode(root.left, k, res, cursor);
+    cursor[0]++;
+
+    if (cursor[0] == k) {
+        res[0] = root;
+        return;
+    }
+
+    KthNode(root.right, k, res, cursor);
+}
+```
diff --git a/offer/CountOfSortedArray.md b/offer/CountOfSortedArray.md
@@ -0,0 +1,77 @@
+# 在排序数组中查找数字
+
+## 题目
+
+统计一个数字在排序数组中出现的次数。
+
+## 解题思路
+
+  1. 通过二分查找分别找到 n 的第一个位置和最后一个位置
+  2. 再进行计算就可以得出结果
+
+```
+public int countOfSortedArray2(int[] nums, int n) {
+    if (nums == null || nums.length == 0) return 0;
+
+    int firstN = getFirstN(nums, n);
+    int lastN = getLastN(nums, n);
+
+    return lastN - firstN + 1;
+}
+
+private int getFirstN(int[] nums, int n) {
+    int s = 0, e = nums.length - 1;
+
+    int mid = -1;
+    while (s <= e) {
+        mid = (s + e) / 2;
+
+        if (mid > 0 && nums[mid - 1] == n) {
+            e = mid - 1;
+            continue;
+        }
+
+        if (nums[mid] > n) {
+            e = mid - 1;
+            continue;
+        }
+
+        if (nums[mid] < n) {
+            s = mid + 1;
+            continue;
+        }
+
+        break;
+    }
+
+    return mid;
+}
+
+private int getLastN(int[] nums, int n) {
+    int s = 0, e = nums.length - 1;
+
+    int mid = -1;
+    while (s <= e) {
+        mid = (s + e) / 2;
+
+        if (mid < nums.length - 1 && nums[mid + 1] == n) {
+            s = mid + 1;
+            continue;
+        }
+
+        if (nums[mid] > n) {
+            e = mid - 1;
+            continue;
+        }
+
+        if (nums[mid] < n) {
+            s = mid + 1;
+            continue;
+        }
+
+        break;
+    }
+
+    return mid;
+}
+```
diff --git a/offer/LongestNoRepeatSubString.md b/offer/LongestNoRepeatSubString.md
@@ -0,0 +1,39 @@
+# 最长不含重复字符的子字符串
+
+## 题目
+
+[LeetCode](https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1012/)
+
+给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
+
+```
+输入: "abcabcbb"
+输出: 3
+解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
+```
+
+## 解题思路
+
+  1. 用 Map 记录字符所在位置，当遇到重复字符时，移动 `start` 指针
+  2. 替换 Map 中下标，并计算子串长度
+
+```
+public int longestNoRepeatSubString(String str) {
+    if (str == null || str.length() == 0) return 0;
+
+    HashMap<Character, Integer> temp = new HashMap<>();
+    char[] chars = str.toCharArray();
+
+    int res = 0, start = 0;
+    for (int i = 0; i < chars.length; i++) {
+        if (temp.containsKey(chars[i])) {
+            start = Math.max(temp.put(chars[i], i) + 1, start);
+        }
+
+        temp.put(chars[i], i);
+        res = Math.max(res, i - start + 1);
+    }
+
+    return res;
+}
+```
diff --git a/offer/MaxGift.md b/offer/MaxGift.md
@@ -0,0 +1,34 @@
+# 礼物的最大值
+
+## 题目
+
+在一个 `m*n` 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
+
+比如说现在有一个如下的棋盘:
+
+![image](images/d59a892b85e600aecc22e2eca74d517f.png)
+
+在这个棋盘中，按照`1，12，5，7，7，16，5`的顺序可以拿到总价值最大的礼物。
+
+## 解题思路
+
+  1. 动态规划，定义 $$f(x,y)$$ 表示`x,y`点上能获取的最大数
+  2. 状态转移方程：$$f(x,y)=\max(f(x-1,y),f(x,y-1))+g(x,y)$$
+  3. 可以考虑使用一维数组进行记录
+
+```
+public int maxGift(int[][] matrix) {
+    for (int i = 0; i < matrix.length; i++) {
+        for (int j = 0; j < matrix[i].length; j++) {
+            int a = i > 0 ? matrix[i - 1][j] : 0;
+            int b = j > 0 ? matrix[i][j - 1] : 0;
+
+            matrix[i][j] += Math.max(a, b);
+        }
+    }
+
+    System.out.println(Arrays.deepToString(matrix));
+
+    return matrix[matrix.length - 1][matrix[0].length - 1];
+}
+```
diff --git a/offer/MaxInWindows.md b/offer/MaxInWindows.md
@@ -0,0 +1,49 @@
+# 滑动窗口的最大值
+
+## 题目
+
+[牛客网](https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=4&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking)
+
+给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组`{2,3,4,2,6,2,5,1}`及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为`{4,4,6,6,6,5}`； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： `{[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}`。
+
+## 解题思路
+
+  1. 使用一个队列来保存最大值和次大的值
+
+```
+public ArrayList<Integer> maxInWindows(int[] num, int size) {
+    ArrayList<Integer> res = new ArrayList<>();
+
+    if (size == 0) return res;
+
+    LinkedList<Integer> queue = new LinkedList<>();
+
+    for (int i = 0; i < num.length; i++) {
+        while (queue.peekFirst() != null && i - queue.peekFirst() >= size) {
+            queue.removeFirst();
+        }
+
+        while (queue.peekLast() != null && i - queue.peekLast() >= size) {
+            queue.removeLast();
+        }
+
+        if (queue.isEmpty()) {
+            queue.addFirst(i);
+        } else {
+            if (num[i] > num[queue.peekFirst()]) {
+                queue.clear();
+                queue.addFirst(i);
+            } else {
+                while (num[i] > num[queue.peekLast()]) {
+                    queue.removeLast();
+                }
+                queue.addLast(i);
+            }
+        }
+
+        if (i >= size - 1) res.add(num[queue.peekFirst()]);
+    }
+
+    return res;
+}
+```
diff --git a/offer/NOfNumberSerialize.md b/offer/NOfNumberSerialize.md
@@ -0,0 +1,46 @@
+# 数字序列中的某一位的数字
+
+## 题目
+
+数字以`0123456789101112131415…`的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数，即从第0位开始）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。
+
+## 解题思路
+
+  1. 可以将 n 进行拆分，1位数一共10个数字、10位，2位数一共90个数字、180位，依此类推
+  2. 当确定 n 所在位数范围时，对位数取商，计算出 n 位对应的数字 a，再取余，计算出结果位于 a 的第几位
+
+```
+public int nOfNumberSerialize(int n) {
+    int i = 1;
+    int count = 0;
+    int nLeft = n;
+
+    while (true) {
+        nLeft -= count;
+        count = countOfIntegers(i) * i;
+
+        if (nLeft < count) {
+            break;
+        }
+
+        i++;
+    }
+
+    int a = nLeft / i;
+    String s = String.valueOf(a);
+
+    return s.charAt(nLeft % i) - '0';
+}
+
+private int countOfIntegers(int n) {
+    int sum = 0;
+
+    if (n == 1) {
+        sum = 10;
+    } else {
+        sum = (int) (9 * Math.pow(10, n - 1));
+    }
+
+    return sum;
+}
+```
diff --git a/offer/TranslateNumToStr.md b/offer/TranslateNumToStr.md
@@ -0,0 +1,31 @@
+# 把数字翻译成字符串
+
+## 题目
+
+给定一个数字，按照如下规则翻译成字符串：0 翻译成“a”，`1` 翻译成`“b”`… `25`翻译成`“z”`。一个数字有多种翻译可能，例如`12258`一共有`5`种，分别是`bccfi`，`bwfi`，`bczi`，`mcfi`，`mzi`。实现一个函数，用来计算一个数字有多少种不同的翻译方法。
+
+## 解题思路
+
+  1. 定义 $$f(i)$$ 表示第 `i` 位有多少种翻译的方法，动态规划方程：$$f(i)=f(i+1)+g(i,i+1) \times f(i+2)$$
+  2. 其中 $$g(i,i+1)$$ 表示 `i,i+1` 是否能组成 `10 ~ 25`
+
+```
+public int translateNumToStr(int num) {
+    char[] str = String.valueOf(num).toCharArray();
+    int[] res = new int[str.length];
+
+    for (int i = str.length - 1; i >= 0; i--) {
+        if (i + 1 >= str.length) {
+            res[i] = 1;
+            continue;
+        }
+
+        res[i] = res[i + 1];
+
+        if (i + 2 < str.length && str[i] <= '2' && str[i] >= '1' && str[i + 1] <= '5') {
+            res[i] += res[i + 2];
+        }
+    }
+    return res[0];
+}
+```
diff --git a/offer/images/d59a892b85e600aecc22e2eca74d517f.png b/offer/images/d59a892b85e600aecc22e2eca74d517f.png
