INCOMING TRANSMISSION

50桶水，其中1桶有毒。有n头猪，一天可以喝两次水，请问在一天内可以找出有毒的那桶水的最小的n。 同leetcode 458 有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。 喂猪的规则如下： 选择若干活猪进行喂养可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。 重复这一过程，直到时间...

问题 在一个圆环上随机取3点，求这3个点组成一个锐角三角形的概率 题解 如下图所示： 取单位圆上任意两点点A和B，A、B两点确定以后，点A、B、C三点要够成锐角三角形，点C必须在DE之间，否在将构成钝角三角形。设AB弧所对应的圆心角为θθ,则当且仅当 θ∈(0,π) 时有可能构成锐角三角形。 θ 的概率密度是 [Math] ，此时组成锐角三角形需要C点在AB对应的DE段间的概率是 [Math] 。故在一个圆环上随机添加3点，三个点组成一个锐角三角形的概率为 [公式] [代码] 运行结果如下： [代码]

计算几何（Computational Geometry），是一系列使用计算机解决几何问题的算法。与解析几何相比，计算几何更适合计算机运算，精度较高，运算速度较快，并且易于编写。 浮点误差 程序设计中，考虑到浮点数 double 有精度误差，在比较时，通常允许一定的误差，即对于两个数 a 、 b ，如果 [Math] ，则认为 a=b 。一般根据题目要求， d （代码中命名为 EPS）取一个较小值，如 10^{8} 。 [代码] 向量 向量（vector）是一个有大小和方向的量，在几何中，它被表示为带箭头的线段。向量可以用起点和终点的坐标来表示 —— 从点 A到点B 的向量表示为 [Math] 。 向量的书写，两个大写字母上加一个箭头（表示方向） [Math] 向量没有位置，即向量可以在平面内...

题意 给定平面上一个圆的圆心位置和半径，从圆中以均匀的概率随机选取点。 分析 拒绝取样 其实我的第一反应是用拒绝取样（Rejection Sampling）的思路来做：首先从这个圆的与坐标轴平行的外切正方形中均匀随机选取点，然后判断点是否位于圆中；如果不在，重新生成一个新的点，再次进行判断；否则直接返回。 直觉上来说，拒绝取样显然是正确的；不过我们可以用一种稍微更加形式化的方法来描述。（以下内容参考了拒绝采样（reject sampling）的简单认识，非常直观形象。） 下图是一个随机变量的密度函数曲线，试问如何获得这个随机变量的样本呢？ 如果你像我一样，已经把概率论与数理统计统统还给数学老师了，那么提示一下，概率密度函数（PDF）是累积分布函数（CDF）的导数，反映的是概率的“密集程度”。...

二叉树结构 [代码] 递归 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。 空间复杂度：空间复杂度：O(h)，h为树的高度。最坏情况下需要空间O(n)，平均情况为O(logn) 递归1: 二叉树遍历最易理解和实现版本 [代码] 递归2: 通用模板 可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值 [代码] 迭代 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。 空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n) 迭代1: 前序遍历最常用模板（后序同样可以用） [代码] 迭代2: 前、中、后序遍历通用模板（只需一个栈的空间） [代码] 迭代3：标记法迭代（需要双倍的空间来存储访问状态） 前、中、后、层序通用模板，只需改...

数组 链表 栈和队列 字符串 优先队列 树 图

根据一棵树的先序遍历和中序遍历，或者后序遍历和中序遍历序列，都可以唯一地确定一棵树。 树中的节点，分为度为0，1，2的结点。如果树中只有一个节点，那么可以唯一确定一棵树，即只有一个节点的树。 当树中结点个数大于等于2的情况，树中的叶子结点和它的父亲结点中，至少有一种存在如下的情况。（为方便起见，我们先从叶子节点入手） case 1: case2: case 3: A D F / \ / \ B C E G 即，叶子结点的父亲有两个孩子，只有左孩子，只有右孩子的情况。我们只需要证明，如果树存在这三种结构中的哪一种，可以唯一确定一棵树，什么情况下又不能唯一确定一棵树呢? 1. case 1: A / \ B C 前序遍历： ABC， 后序遍历： BCA 现在，我们根据遍历序列，看看能否得到另一种...

题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3： 输入：root...

题目 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 145, 134, 26 ] 将它们合并到一个有序链表中得到。 11234456 题解 1. 优先级队列 时间复杂度O(nlogk) [代码] 2. 两两合并 [代码]

题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2. Example: [代码] Constraints: 10^9 <= nums1[i], nums2[i] <...

给定一个单链表 L：L0→L1→…→Ln1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln1→L2→Ln2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1: 给定链表 1234, 重新排列为 1423. 示例 2: 给定链表 12345, 重新排列为 15243. [代码]

kmp算法用于字符串的模式匹配，也就是找到模式字符串在目标字符串的第一次出现的位置比如abababc那么bab在其位置1处，bc在其位置5处，我们首先想到的最简单的办法就是蛮力的一个字符一个字符的匹配，但那样的时间复杂度会是O(mn)。kmp算法保证了时间复杂度为O(m+n)。 基本原理 举个例子： 发现x与c不同后，进行移动 a与x不同，再次移动 此时比较到了c与y， 于是下一步移动成了下面这样 这一次的移动与前两次的移动不同，之前每次比较到上面长字符串的字符位置后，直接把模式字符串的首字符与它对齐，这次并没有，原因是这次移动之前，y与c对齐，但是y前边的ab是与自己的前缀ab一样，于是ab并不用再比较，直接从第三个位置开始比较，如图： 所以说kmp算法对于这种情况就直接使用当前比较字符之...