feat: $324, $710

robot · robot · commit 7336a99bee9c · 2022-07-19T00:27:20.000+08:00
diff --git a/README.md b/README.md
@@ -329,6 +329,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [0279. 完全平方数](./problems/279.perfect-squares.md)
 - [0309. 最佳买卖股票时机含冷冻期](./problems/309.best-time-to-buy-and-sell-stock-with-cooldown.md)
 - [0322. 零钱兑换](./problems/322.coin-change.md) 👍
+- [0324. 摆动排序 II](./problems/324.wiggle-sort-ii.md)
 - [0328. 奇偶链表](./problems/328.odd-even-linked-list.md)
 - [0331. 验证二叉树的前序序列化](./problems/331.verify-preorder-serialization-of-a-binary-tree.md)
 - [0334. 递增的三元子序列](./problems/334.increasing-triplet-subsequence.md)
@@ -360,8 +361,9 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [0611. 有效三角形的个数](./problems/611.valid-triangle-number.md) 👍
 - [0673. 最长递增子序列的个数](./problems/673.number-of-longest-increasing-subsequence.md)
 - [0686. 重复叠加字符串匹配](./problems/686.repeated-string-match.md)
-- [0718. 最长重复子数组](./problems/718.maximum-length-of-repeated-subarray.md)
+- [0710. 黑名单中的随机数](./problems/710.random-pick-with-blacklist.md)
 - [0714. 买卖股票的最佳时机含手续费](./problems/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md)
+- [0718. 最长重复子数组](./problems/718.maximum-length-of-repeated-subarray.md)
 - [0735. 行星碰撞](./problems/735.asteroid-collision.md) 👍
 - [0754. 到达终点数字](./problems/754.reach-a-number.md)
 - [0785. 判断二分图](./problems/785.is-graph-bipartite.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -174,6 +174,7 @@
   - [0279. 完全平方数](./problems/279.perfect-squares.md)
   - [0309. 最佳买卖股票时机含冷冻期](./problems/309.best-time-to-buy-and-sell-stock-with-cooldown.md) 👍
   - [0322. 零钱兑换](./problems/322.coin-change.md)
+  - [0324. 摆动排序 II](./problems/324.wiggle-sort-ii.md)
   - [0328. 奇偶链表](./problems/328.odd-even-linked-list.md)
   - [0331. 验证二叉树的前序序列化](./problems/331.verify-preorder-serialization-of-a-binary-tree.md) 👍
   - [0334. 递增的三元子序列](./problems/334.increasing-triplet-subsequence.md) 👍
@@ -204,6 +205,7 @@
   - [0611. 有效三角形的个数](./problems/611.valid-triangle-number.md) 👍
   - [0673. 最长递增子序列的个数](./problems/673.number-of-longest-increasing-subsequence.md)
   - [0686. 重复叠加字符串匹配](./problems/686.repeated-string-match.md)
+  - [0710. 黑名单中的随机数](./problems/710.random-pick-with-blacklist.md)
   - [0714. 买卖股票的最佳时机含手续费](./problems/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md) 👍
   - [0718. 最长重复子数组](./problems/718.maximum-length-of-repeated-subarray.md)
   - [0735. 行星碰撞](./problems/735.asteroid-collision.md)
diff --git a/problems/324.wiggle-sort-ii.md b/problems/324.wiggle-sort-ii.md
@@ -0,0 +1,113 @@
+## 题目地址(324. 摆动排序 II)
+
+https://leetcode.cn/problems/wiggle-sort-ii/
+
+## 题目描述
+
+```
+给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
+
+你可以假设所有输入数组都可以得到满足题目要求的结果。
+
+ 
+
+示例 1：
+
+输入：nums = [1,5,1,1,6,4]
+输出：[1,6,1,5,1,4]
+解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
+
+
+示例 2：
+
+输入：nums = [1,3,2,2,3,1]
+输出：[2,3,1,3,1,2]
+
+
+ 
+
+提示：
+
+1 <= nums.length <= 5 * 104
+0 <= nums[i] <= 5000
+题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果
+
+ 
+
+进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
+```
+
+## 前置知识
+
+-
+
+## 公司
+
+- 暂无
+
+## 思路
+
+这是一道构造题目，一般来说构造题目的难度都偏大一点，这一道题目也不例外，尤其是进阶。关于进阶不在这里展开，因为[题解区](https://leetcode.cn/problems/wiggle-sort-ii/solution/)给出了很多优秀的解法了。
+
+这道题让我们重新排 nums， 使得奇数索引的数都比相邻的偶数索引大。
+
+我们可以先进行一次倒序排序。接下来先从小到大给奇数索引放置数字，然后再次从小到大给偶数索引放置数字即可。
+
+> 这里的从小到大指的是索引值从小到大，即先放索引较小的，再放索引较大的。
+
+为什么可行？
+
+因为我们是倒序排序的，因此后放置的偶数索引一定是不大于奇数索引的。但是能够保证严格小于相邻的奇数索引么？
+
+由于题目保证了有解。因此实际上按照这种放置方法可以，但是如果：先从小到大给奇数索引放置数字，然后再次从大到小给偶数索引放置数字。那么就有可能无解。无解的情况是数组中有大量的相同数字。但是题目保证有解的情况，**先从小到大给奇数索引放置数字，然后再次从小到大给偶数索引放置数字** 是不会有问题的。
+
+## 关键点
+
+- 排序后按照奇偶性分别放置
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+
+class Solution:
+    def wiggleSort(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        n = len(nums)
+        s = sorted(nums, reverse=True)
+
+        i = 1
+        j = 0
+        while i < n:
+            nums[i] = s[j]
+            i += 2
+            j += 1
+        i = 0
+        while i < n:
+            nums[i] = s[j]
+            i += 2
+            j += 1
+
+```
+
+**复杂度分析**
+
+令 n 为数组长度。
+
+- 时间复杂度：$O(nlogn)$ 主要是排序
+- 空间复杂度：$O(n)$ 拷贝了一个新的数组 s
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
diff --git a/problems/710.random-pick-with-blacklist.md b/problems/710.random-pick-with-blacklist.md
@@ -0,0 +1,120 @@
+## 题目地址(710. 黑名单中的随机数)
+
+https://leetcode.cn/problems/random-pick-with-blacklist/
+
+## 题目描述
+
+```
+给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
+
+优化你的算法，使它最小化调用语言 内置 随机函数的次数。
+
+实现 Solution 类:
+
+Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
+int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
+
+ 
+
+示例 1：
+
+输入
+["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
+[[7, [2, 3, 5]], [], [], [], [], [], [], []]
+输出
+[null, 0, 4, 1, 6, 1, 0, 4]
+
+解释
+Solution solution = new Solution(7, [2, 3, 5]);
+solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
+                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
+solution.pick(); // 返回 4
+solution.pick(); // 返回 1
+solution.pick(); // 返回 6
+solution.pick(); // 返回 1
+solution.pick(); // 返回 0
+solution.pick(); // 返回 4
+
+
+ 
+
+提示:
+
+1 <= n <= 109
+0 <= blacklist.length <= min(105, n - 1)
+0 <= blacklist[i] < n
+blacklist 中所有值都 不同
+ pick 最多被调用 2 * 104 次
+```
+
+## 前置知识
+
+- 哈希表
+- 概率
+
+## 公司
+
+- 暂无
+
+## 思路
+
+题目让我们从 [0, n-1] 随机选一个数，且要求不能是在 blacklist 中，且要求所有数被选中的概率相等。
+
+也就是说我们可以选择的数字的个数为 n - m，其中 m 为 blacklist 的长度。我们需要在这 n - m 中选择一个随机的数，每个数被选中的记录都是 1/(n-m)。
+
+我们可以随机一个 [0, n-m-1] 的数字。
+
+- 如果这个数不在黑名单，直接返回即可。 不难得出，此时的概率是 1/(n-m)，符合题意
+- 如果这个数在黑名单。我们不能返回，那么我们可以将其转化为一个白名单的数。 由于黑名单一共有 m 个，假设在 [0,n-m-1]范围内的黑名单有 x 个，那么[n-m+1,n-1] 范围的黑名单就是 m - x，同时在 [n-m+1,n-1] 范围的白名单就是 x。那么其实选中的是黑名单的数的概率就是 x/(n-m)，我们随机找 [n-m+1,n-1] 范围的白名单概率是 1/x。二者相乘就是映射到的白名单中的数被选中的概率，即 1/(n-m)
+
+综上，我们可以使用哈希表 b2w 维护这种映射关系。其中 key 为 [0,n-m-1] 中的黑名单中的数，value 为随机找的一个 [n-m, n-1] 的白名单中的数。
+
+具体实现看代码。
+
+## 关键点
+
+- 将黑名单中的数字映射到白名单
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+
+class Solution:
+    def __init__(self, n: int, blacklist: List[int]):
+        m = len(blacklist)
+        self.bound = w = n - m
+        black = {b for b in blacklist if b >= self.bound}
+        self.b2w = {}
+        for b in blacklist:
+            if b < self.bound:
+                while w in black:
+                    w += 1
+                self.b2w[b] = w
+                w += 1
+
+    def pick(self) -> int:
+        x = randrange(self.bound)
+        return self.b2w.get(x, x)
+
+```
+
+**复杂度分析**
+
+令 n 为 blacklist 长度。
+
+- 时间复杂度：$O(n)$
+- 空间复杂度：$O(n)$
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
