问题描述：给定一个包含 n + 1 个整数的数组，数字范围在 1 到 n 之间，其中有一个重复的数。 找出这个重复的数。

解法1: 平平无奇的思考结果，我想大部分人都会想到这个解法。

相似题目，参考：力扣 645. 错误的集合

def findDuplicate2(nums):
    nums_sum = sum(nums)
    sets_sum = sum(set(nums))
    return nums_sum - sets_sum

解法2: 这个解法如果没有个十年脑血栓，恐怕很难会想到把数组元素当成索引来变成链表耍，然后 还能想到环状链表的环起点是重复的那个元素。

相似题目，参考：力扣 LCR 022. 环形链表 II （单链表找环的入口节点）

def findDuplicate(nums):
    # 初始化慢指针和快指针
    slow = nums[0]
    fast = nums[0]

    # 快慢指针移动直到相遇
    while True:
        slow = nums[slow]       # 慢指针每次走一步
        fast = nums[nums[fast]] # 快指针每次走两步
        if slow == fast:
            break

    # 重置一个指针到起点，寻找环的入口
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    # 返回重复的数字
    return slow

# 快速排序算法（quick sort）

下文简称“快排”。

快排算法的实现，在Python中有偷懒的做法，就是不对传入数组进行原地分区，show me the code:

# 快排实现之邀请面试官拷打版本
def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[-1]
    less = [x for x in arr[:-1] if x <= pivot]
    greater = [x for x in arr[:-1] if x > pivot]

    return quick_sort(less) + [pivot] + quick_sort(greater)

Ier：您这个实现看起来挺简洁嘛，说说看这么做有什么不足的地方？最差情况是什么？

Iee：嗯，您是指，啊，对了，嗯（笑容逐渐凝固.gif，磨磨叽叽假装思考...）

Ier: 我是指您代码里使用了额外的存储空间，`less` 和 `greater`，可以不用它们吗？

Iee：哦，您是指要对数组进行原地分区吗？（那些追求速度和基情的编程语言通常都是原地操作：应该是问这个吧？）

Ier: 对。

Iee：（心里嘀咕，就是怕那个 `partition()` 函数，怕啥来啥是吧:(，墨菲）

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    low, high = 0, len(arr)-1
    quick_sort_inplace(arr, low, high)

def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx-1)
        quick_sort_inplace(arr, pivot_idx+1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i + 1]
    return i+1

Ier: 嗯，好。您的pivot是怎么选择的啊？

Iee：我是选了数组的最后一个元素。

Ier：嗯，那我有个问题请教一下，如果最后一个元素恰好是最大值或最小值的话，会怎么样？

Iee：（是啊，我也不太理解为什么这么草率地用最后一个元素呢？）嗯，啊，这个，应该是会导致分区效果不好吧。

Ier: 那还可以优化吗？

Iee：随机选择一个元素作为pivot？

好，要的就是这个“随机选择“。（顺便结束面试拷打模拟：)

# 刷题和刷题的副作用

我在刷题的时候，很搞笑，是先接触到对二叉树进行各种骚操作。意思是说，牛客或者力扣这些平台 已经默认给你的就是一棵二叉树，你只需要完成诸如前中后序各种遍历二叉树节点的算法。如果你对 这些概念感到陌生，没关系，成年人游戏喜欢吗？

(李沐-BERT论文精读的个人整理笔记)

BERT论文标题: Pre-training预训练 of Deep Bidirectional Transformers深度双向Transformer for Language Understanding语言理解

预训练(pre-training)：先在一个大的数据集上训练一个模型(从零开始得到一组权重值W0)，这个模
型的主要任务是被用在其他任务（或下游任务上）进行训练(training：以W0初始化模型然后训练)
（以解决下游任务问题）。

BERT本身含义：Bidirectional Encoder Representations from Transformer，使用了 Transformers 模 型(Transformer论文精读)的编码编码器组件，学习一个双向的嵌入表示。与 ELMo 和 Generative Pre-trained Transformer 不同：

• BERT 从无标注的文本中（jointly conditioning 联合左右的上下文信息）预训练词嵌入的双向表征。
• pre-trained BERT 可以通过加一个输出层来 fine-tune，不需要对特定任务的做架构上的修改就 可以在在很多任务（问答、推理）有很不错的、state-of-the-art 的效果
• GPT unidirectional，使用左边的上下文信息预测未来；BERT bidirectional，使用左右侧的上下文信息
• ELMo based on RNNs, down-stream 任务需要调整架构
• GPT, based on Transformers decoder, down-stream 任务只需要改最上层
• BERT based on Transformers encoder, down-stream 任务只需要调整最上层