所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

思路是看出问题的数学本质，找到合适方便的公式。然后，理清楚一步步计算的数学思路，并模拟实现为代码。

常用的数学计算编程方法：

• 判断四个点能否组成矩形

先任意取三个点，看看能不能构造成直角三角形，然后计算第四个点是否是矩形缺的那个点就可以了。

看能否构造直角三角形的方法是勾股定理，也就是看三条边中最大的平方是不是等于较小两边的平方和，也可以使用点乘，看两个向量点乘是否为0。

之后在判断第四个点的时候，可以先计算出第四个点的坐标，利用的就是第四个点和直角三角形的直角点一定是和三角形斜边中点对称。

• 计算三角形面积

两条边的叉积除2就是三角形面积。

• 判断平行于x轴，y轴的矩形

取两个点作为对角线，然后验证剩余两点在不在set里面就可以了。O(n^2)。

具体题目

365. Water and Jug Problem

题意：给出两个容积为x和y的容器，看能不能测出z体积的水（水必须在容器中）。

解：参考http://www.cnblogs.com/grandyang/p/5628836.html

此题可以转化为这个问题：z ？= m*x + n*y。即答案是z是否是x和y最大公约数的倍数。另外根据题意还有一个限制条件x+y >= z。

使用辗转相除法求最大公约数。一个数x余另一个数y的值，递归的求y和x%y的最大公约数。

（1）不必担心x比y小，因为那样第二次时候就会换过来。

（2）当y为0时候，返回x作为结果。

672. Bulb Switcher II

题意：初始给出n盏亮着的灯。有4种操作，第一种：翻转（也就是开着的关闭，关闭的打开）所有灯；第二种：翻转偶数位置的灯；第三种，翻转奇数位的灯；第四种：翻转3k+1位置处的灯。 现在有m次操作，求灯出现的可能的情形的次数。

解：此题显然情形的次数是有限的，不可能出现无限多的情形。那么先尝试去组合来看有没有规律。1.首先，一个组合中一种操作只能选0次或者1次，因为选2次和选0次效果一样，也就是选偶数次和选0次效果一样，选奇数次和选1次的效果是一样的。所以，m种操作数必须遵从这个原则才能最大的去重，达到最多组合。所以总情况上限最多为2^C(4,0)+2^C(4,1)+2^C(4,2)+2^C(4,3)+2^C(4,4)。C(m,n)表示从m中选出n个数的组合数。 2.第一种和第二种操作的都选1的组合可以得出第三种操作选1的效果。同样的，第一种和第三种操作的都选1的组合可以得出第二种操作选1的效果，第二种和第三种操作都选1的组合可以得出第一种选1的效果。也就是说，如果第一、二、三种操作全选，那等价于一种操作进行两遍，效果是0。也就是说是如果四种操作全选，那么就相当于是只有一次第四种操作。所以4种全选的情况是重复的，可以去掉。再来看选三种为1的情况：1+2+3等价于全不选的情况；1+2+4等价于3+4；1+3+4等价于2+4。 也就是说，选三种操作的情况也是冗余的。现在来看选两种操作的情况：1+4，2+4，3+4不冗余，其余的和只选一种的操作冗余。 所以，n足够大(大于等于3)，即不考虑n的时候，只可能存在这几种情况： （1）m == 0，也就是全亮着的情况, 1种。 （2）m == 1：1，2，3，4， 4种。 （3）m == 2：1+4, 2+4, 3+4, 1+2 == 3, 1+3 == 2, 2+3 == 1, 1+1 == 2+2 == 3+3 == 4+4, 7种。 （4）m >= 3：在m == 2的基础上，可以多生成一种4。 注意， m == 2的时候，只能最多出现7种情况，例如，111可以生成000，101，010，然后结合操作4可以进一步生成100，001和110，此时发现无法生成011。 n < 3的时候，例如n == 2，只有4种情况。而m == 1的时候，因为此时3和4操作完全一样是冗余的，所以只有3种情况，而m == 2的时候，7种可以满足，但是n=2导致最多只有4种情况。

750. Number Of Corner Rectangles

题意：给出二维矩阵，如果四个1形成矩形的四个顶点，那么就算一个矩形。求所有矩形数。

解：此题暴力求解就是，对一个坐标当作矩阵左上角顶点，然后遍历剩余坐标考虑为矩阵右下角顶点。这样通过两个点其实就能判断是否是矩阵，但是总体扫描时间达到了O(m*n*m*n)。

现在需要把时间复杂度降下来，方法就是使用组合，这样一次就能计算出多个矩形。

具体实现是，选择两行，这样消耗了m*m时间，然后对这两行进行遍历，看是否同列的地方是否都为1，如果都为1，那么可选择的矩阵竖着着两个顶点就加1。这样，只需要在算完后的可选择点中任意选两个，就能组成一个矩形。所以这种方法时间复杂度降到了O(mmn)。

398. Random Pick Index

题意：设计接口，给出值，返回数组中值对应的下标，如果该值在数组中不止一个，那么随机返回。此题要求是空间复杂度不能太高。

解：此题如果更关注时间，那么肯定用hash来做，但是此题是要求空间小。

那么时间可以多花点，也就是每次查找都要n的时间来遍历数组。

如何处理重复元素下标随机返回? 方法是这样的：遇到第一个值元素的时候，记录下标，概率为1的把该下标作为结果候选者，继续向后扫描，如果遇到相同大小的值，那么有1/2的概率把结果候选者替换成当前下标，之后就是1/3，1/4，1/5的概率依次类推，直到扫描结束。

这么计算的原理就是：第一个数被选的概率一开始是1，但是出现第二个的时候，应该有1/2的概率被替换，如果全部只有两个元素，这显然符合要求。如果出现了第三个元素，那么有1/3的概率选择第3个元素，有2/3的概率不选择当前元素，那么之前两个元素被选择的概率都变成1/2 * 2/3 == 1/3了。

382. Linked List Random Node

题意：从链表中随机的返回一个数。不允许使用额外空间，且链表长度一开始不知道。

解：此题和398区别在于此题是链表，398是数组。在整体链表很大且长度不知道的情况下，还是要使用和398一样的方法，也就是每次记录当前扫描过的candidate元素的个数，然后以1/个数的概率更新最终结果。 不许使用额外空间的意思就是当前数据其实是数据流，所以意思就是最好只能访问一次，且访问的过程中不能存储下访问的数据。

447. Number of Boomerangs

题意：求回旋镖的种类，具体来说，求两个点到一个点距离相等的组合数。

解：把每个点都当做回旋镖的中心来考虑：循环计算它到其他点的距离，每次计算时候，统计一下相同距离的点的数量，

也就是建立hash表，key是其他点到他的距离，value是该距离点的数量。

假设其他点到中心点的一个距离是为n个，那么从n个中任意选出两个，然后两个的排列顺序有两种，所以组合数量最终结果是n(n-1) / 2 * 2。

二重循环，对剩余的点进行相同的处理。

注意的是，每次处理的时候，要把自己排除掉。

PS. 组合的顺序有意义，也就是说，同一情况的3元组要算两倍: (a,b,c) == (a, c, b)。

389. Find the Difference

题意：串t比串s多一个元素，其余元素相同，现在要找到这个不同元素。

解：方法一：异或。在t串中选最后一个元素作为c。然后新建t长度的循环，每次循环c与s和t对应下标元素进行异或，就能得出答案。

409. Longest Palindrome

题意：给一个字符串，求从其中任选字母排列可以组成回文串的最大长度。

解：按字母出现次数奇数偶数来考虑，先使用hash表记录每种字母出现次数，如果次数是偶数，那么全部用到最终结果里面，如果次数是奇数，那么使用减1的数量用于结果。然后结果继续加1，表示还可以使用一个奇数次的字母。

注意边界情况是：如果最终长度超过了字符串总长度，那么总长度就是答案。

665. Non-decreasing Array

题意：最多只能修改一个元素，使得数组是非递减的数组。例如[4,2,3]，只需要修改4变为2，就可以做到，因此返回true；例如[4,2,1]，只能修改一个数不可能做到非递减，返回false。

解：此题主要考虑点就是发现递减的pair（A[i] < A[i - 1]）。

首先一点是：如果发现两个这样的pair，那么无论怎么改都不行，例如[4,2,1]中存在[4,2], [2, 1]两个pair。

第二点，也是此题最难考虑的点，就是如果只存在一个违规的pair，修改后也不一定行。

修改分两种情况，一种是将pair第一个元素减小，另一种是将pair的第二个元素增大。

第一种情况下，会对之前序列产生影响：例如[3, 3, 2]， 如果修改第二个3为2，那么之前的3和新的2会违规。

第二种情况会对后序序列产生影响：例如[1, 3, 2, 2], 如果修改第一个2为3，会违背规律，此例子应该是修改3变2就能满足条件。

然后，我们知道，如果合理的话，应该尽量修改pair第一个元素，因为把第二个元素提升会对后面产生负面影响；如果第一个元素无法修改，那么只能修改第二个元素，

第二个元素修改的时候，也是要尽量提升的小。

思路总结：只存在有一对递减pair[i -1, i]的时候，只要使得[i-2, i-1, i, i+1]四元组成为非递减就可以。

实例：[4,4,2,5] 和 [4,4,2,3]。

469. Convex Polygon

题意：检测一个图形是不是凸多边形。

解：此题使用向量叉积来判断，叉积使用右手定理，如果叉积结果为正数，那么说明向上，否则向下，如果是凸多边形，那么相邻两边的叉积永远是全正或者全负，而如果是凹边形，则会违反性质。选3个连续的点A,B,C。考虑向量BA x 向量BC。叉积为dx1 * dy2 - dx2* dy1。

357. Count Numbers with Unique Digits

题意：给出数字的位数长度n，求满足该位数（可以小于长度n）的独特数字的个数。例如n为3，独特数字是指1，2，3，123，321这种的，而112，111，122不是，因为含有相同digit的数。

解：此题是数学题。考虑0到9，有10种选择，10到99有81种选择，所以在n==2时候，答案是10+81。同理考虑100到999，有9*9*8种选择，所以n==3时候，答案是9*9*8加上之前计算的10和81。公式就是每次新的位数会引入9*9*8*7*6….种选择。

356. Line Reflection

题意：给出若干点，求这些点会不会根据一条平行于Y轴的直线对称。

解：此题关键在于找出对称的线，一开始想到的是找到点的中位数，其实这个思路有缺陷，因为该直线不一定穿过某个点。

正确思路是先找到x坐标的最大最小值，然后取中间值就是应该要对称的线，接下来要做的就是验证所有的点是不是存在一个对称线另一边的点。

PS.此题难考虑到的就是对称轴可以使用双倍的mid来表示，因为对称轴的双倍等于rightM + leftM，必然是整数，化解了对称轴是double的尴尬。

729. My Calendar I

题意：不断的book区间，关键是求加入新的区间与之前区间是否重复。

解：判断两个区间有交集的技巧就是把握两个区间关系的特点：有一个区间总是在另一个区间的左边，通过比较两个区间的起始值就知道，然后在这个基础上，看左边区间的结尾，如果比右边区间的起始点大，那么一定 有交集。

这样新区间与之前每一个区间进行比较，就知道是不是可以加入。

另一个方法是将之前处理区间进行排序，这样，不需要比较每一个之前区间，而是进行二分，找到start下标的lower_bound以及之前一个区间，只需要和这两个区间做一次 比较就可以知道当前区间能否插入。

c++编码：例如可以将处理过的区间（pair）存入set，pair之间的默认排序是先按第一个元素排，如果第一个相等，那么按第二个来比较。

库函数的写法是 p1.first < p2.first or !(p2.first < p1.first && p1.second < p2.second，充分的利用了短路运算符。

对准备加入的区间，使用set的lower_bound函数查找区间迭代器，在–得到之前一个。也就是要比较的两个迭代器。 第一个区间是看当前区间开头是不是比该区间尾部大，如果是，那么有交集； 第二个区间是看当前区间的结尾是不是比该区间的开头大，如果是，说明有交集。

使用lowerbound相当于二分，时间复杂度降到了O(logn)。

Java编码：使用treeset，存入entry<Integer, Integer>，两个比较区间一个是floor找到，一个是ceiling找到。

PS.lower_bound的意思是找出第一个不比target小（也就是包括等于）的下标，c++里面，如果这样的数不存在，那么返回数组大小。 upper_bound是第一个比target大的数的下标。

731. My Calendar II

题意：729的基础上，区间之间允许重叠一次，但不允许重叠两次。

解：大致思路是：重叠一次的区间重叠部分记录下来存到单独数组B里，然后添加新区间A的时候，要先检查重叠区间数组里的区间是不是有和A重叠的，如果有，那么不能添加，

否则可以添加，添加后再看原来区间，如果存在重叠区间，那么记得将新区间A也要加入到B中。

732. My Calendar III

题意：729的基础上，此题区间可以多次重复，求每次新增区间后返回重叠次数最多的区间的次数。

解：暴力求解：对每个区间，检查其他所有区间和它重叠的数量，总时间复杂度是O(N^2)。

优化解：把握题目的数学规律，也就是，最多重复的地方一定可以出现在某个区间的开头或者结尾（理解：画出多区间图形实例就知道了）。如果可以知道每个区间端点时候对应的重叠区间数，选出其中最大的就可以，而重叠区间就是指有多少个区间还在进行。

如何计算当前端点有多少个区间还在进行呢？其实可以利用递归思路，也就是第n个节点的时候，看第n-1个节点，也就是说，如果我们知道了在第n-1个节点处有多少区间正在运行，那么在第n个节点的时候，只需要加上以这个节点为开头的区间数量， 减去在第n个节点结束的区间数量就可以了。而base case，也就是第一个节点处的情况一样，就是以该点为起始的区间数，减去该点为结束的区间数。

具体编码：使用treemap（c++里面就是map），先扫描所有区间，记录下每个区间开头和结尾对应的数量（开头使用正数，结尾使用负数）。然后对map进行遍历，过程中，

当前点的计算就是：之前点的结果，加上当前点的开头区间数减去结尾区间数。

PS. 此题类似meeting room的题目。

533. Lonely Pixel II

题意：孤独像素满足两个条件：（1）该点所在行列含相同N个B数，N已经由题目给出（2）对于该列，如果有B，那么含B的行是一模一样的。

解：暴力求解就是，先统计每行每列出现B的个数，然后一个一个扫描矩阵，如果行列相等，那么我们一行一行看是否行相等。这样时间复杂度达到O(m*n*m)。

再看一个O(m*n)的解法：把每行组成string，然后作为hashmap的key，如果该行刚好含有N个B的话，然后一遍下来，就知道每种string对应个数，然后看其个数是不是N，如果是，那么是答案，否则不是。

PS.此题编码时候注意的是，不能仅仅判断count个数，还要看当前点是不是’B’。

31. Next Permutation

题意：求下一个字典序排列。

解：模拟找下一个字典排列的过程，首先找到该更新的位数，然后在把该位数更新后，后面部分变为最小。

编程时候具体分三步：第一步从右向左看，找到一个递增的对，也就是 找到第一个nums[i - 1] < nums[i]。从右找的原因是保证尽可能小的去提升原来的数，所以从低位开始考虑，一旦发现了nums[i - 1] < nums[i]，说明i-1的位置是我们可以考虑下一个可以提升的位数，因为nums[i]到nums[j]是递减的。所以不可能提升了。 例如x = 121543321，第一个nums[i-1] < nums[i]是1 < 5，从5开始往后面看，发现是543321，是没有提升空间的。

第二步，使用nums[i]到nums[n]中的数尽可能小的去提升（替换）i-1位，x后半段543321中，显然最合适替换的是2。也就是从右向左看，第一个比nums[i-1]大的数，而且该数一定存在，因为至少有nums[i-1] < nums[i]做保证（nums[i - 1]是局部颠峰）。

替换完之后又如何呢？替换完之后nums[i]到nums[n]中的数仍然满足递减性质，进行第三步处理，将替换完更新的543311翻转过来，形成递减序列组成最小值。

406. Queue Reconstruction by Height

题意：给出一个pair数组，pair(h, k)的第一个元素代表高度，第二个元素表示排在自己前面且比它高（或等）的元素有几个。 现在要将这个数组进行还原（给出的pair符合规律）。

解：解空间看起来是排列，但是排列这种都是算法要尽量避免的，因为太消耗时间。

题目中给出了一种二维的，纠缠在一起的信息，其实就能想到一种常见套路，就是把其中一个维度进行排序来”降维”。

例如，按照高度，从小到大排列这些pair，发现一个特点，就是最后一个必然是最高的，且排在它之前的元素数量一定是0，也就是说这个元素已经在最终位置上了， 也就是不需要动的；

继续往左看倒数第二个元素，如果它的k = 0，那么也满足条件，因为左侧确实没有比自己高的； 如果k != 0，那么说明了原来序列里有k个元素比自己大的，这些元素应该从自己的右侧来选，所以如果是倒数第二个元素，它的k应该也是等于0的，不然非法； 在继续看，倒数第三个元素，这次，如果k = 1，那么说明需要把右侧某个元素移到自己的前面，具体来说，就是倒数第二个元素和它交换； 如果k = 2，那么后面两个元素平行移到自己的前面；

总结规律，从右向左看，每个元素，按道理，应该有k个比它大的元素，所以把右侧k个元素左移一步，把自己填进去，类似插入排序。 但是此处，由于每次被移动到后面的元素

高度相同则k小的排前面，然后扫描一遍排序数组来构建新数组，根据比自己高的元素个数k，把pair插入到新数组k的地方，就能还原最初的排序结果。时间复杂度O(n^2)，因为插入操作类似插入排序， 其中元素最坏情况下，需要移动1，2，3,…n次，加起来就是O(N^2)。

边界情况考虑：（1）身高相同时候，把k小的排后面，这样交换的时候，可以考虑等于自己的情况。

PS. （1）此题可以优化到O(NlogN)，目前本人不太会。 （2）多维度纠缠问题，解法往往是固定一个维度，也就是消除一个维度对影响，然后挖掘其中规律，得出答案。

780. Reaching Points

题意：(x, y)可以变换为(x + y, y)或者(x, x + y)。现在给出出发点(sx, sy)和目标点(tx, ty)，问是否有且只有一条变换路径可以到达目标结点。x, y均为正数。

解：此题看起来是很玄乎的数学题，但是可以先画下图：(sx, sy)作为根节点可以引申出两个子节点(sx + sy, sy)和(sx, sx + sy)，然后每个子节点也有两种变化。。。说明什么？说明是二叉树结构啊！

所以此题要求解的就是根节点到某个叶子节点的路径。所以理解了题意中的有且只有一条路径，因为明显可以看出，根到叶子的路径必然是有且只有一条的。

找根节点到叶子结点路径的解法并不是从根出发来找叶子，因为那是没有方向性的。而应该从叶子出发，不断的找自己的父节点，直到找到根节点。假如一个结点是(mx, my)，且我们知道mx > my, 由于都是正数，所以我们知道他肯定是属于(x + y, y)这种形式，也就是说他的父节点必然为(mx - my, my)。这样我们一步步找父节点，知道找到(sx, sy)，就是最终答案。但是这种一步步找父节点的方法效率不够。

观察(mx - my, my)，如果mx - my仍然大于my，那么父节点是mx - 2 * my。所以，可以一次走多步，而不只是一步，也就是说，一次可以走mx / my步，直到mx < my。

注意边界条件，如果某一步出现mx == 0或者my == 0，也就是说上一步mx == my，那么不能继续取余了，应该直接跳出循环。还有一种情况是假设mx > my，那么接下来计算mx % my之前，我们要看my是不是已经比sy小了，如果小于等于，那么意味着my不能在减小了，之后只能将mx减小了，所以只需要看mx - sx 是不是 ty的整数倍就知道能不能到达sx了。

391. Perfect Rectangle

题意：求给出的矩形能不能恰好组成大矩形。

解：先理解题意，题意蕴含的条件就是小矩形之间是不能重叠的，所以发现规律，如果能组成大矩形，那么：1.只有4个顶点只出现一次，其余点都成对（偶数次）出现；2.大矩形面积等于小矩形面积之和。

难点在于编程时候，如果使用hashset存pair，另一个就是知道四个点，求矩形面积。

第一个难点一个解决方法是先将pair转string再存，第二个难点一个解决办法是，一开始就维持四个边角的坐标，扫描过程中不断更新即可。

843. Guess the Word

题意：给出一个单词让人猜，可以猜的范围是给出的一个单词列表（里面单词和要猜的单词数量一致），现在求设计一个方法尽可能少次数去猜，每次猜单词返回其中命中的字母数量x（位置命中）。

解：大致思路是条件概率，在已知一个单词有多大几率被猜中的前提下，去选择下一个尽可能猜中概率大的单词，所以关键就是要提升在一个单词被猜，选择下一个单词这一环上。

简单的方法就是：不断缩减候选单词集的大小，例如候选者单词一定要有且只有x个字母数和猜测单词一模一样（位置也要一样），否则不可能是答案，这样就能缩减候选单词集的大小， 这样把候选集的一个单词放进去猜，然后根据该单词进一步缩减单词候选集。

PS.为什么单词要恰好等于猜测单词的x个字母一样：如果一个单词比x个字母少，说明该单词和答案间不能有x个相同字母，因此该单词不是答案； 如果一个单词比x个字母多，说明有和猜测单词多余的相同字母，但是可惜并不match答案单词，因此也不可能是答案。

还有一个优化的方法是把每步产生的候选者单词之间进行比较，选择一个最优的候选者去猜。

方法就是比较每个候选者与其他所有候选者之间的字母差距，如果两单词之间字母完全不一样，那么该候选者的优先级就要降低。

667. Beautiful Arrangement II

题意：给出1到n的数，现在又给出k，要求[|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] 中有k个独特的整数的排列。

解：此题可以找到规律。假设n=7，我们构造多种k，发现：

其中分割的部分之后都是相减绝对值为1的情况。

发现最大的k就是n-1，k等于多少就是说从最前面和最后面开始取数，取出k个数，之后的数按最后被选的数字保持递增递减顺序就可以了。

789. Escape The Ghosts

题意：吃豆人和鬼魂每次只能上下左右移动一步，求吃豆人能不能一定先到达某个目标。

解：此题理解关键是两点：一是鬼魂如果能先到达目标点，那么吃豆人一定赢不了，因为鬼魂可以在那边等吃豆人过来。

二是吃豆人和鬼魂都不能沿着斜线走，也就是说距离目标的距离不能计算对角线，而是要每次横竖各一步到达目标，也就是距离目标的横向距离加上纵向距离。

所以，只要所有鬼魂距离目标的曼哈顿距离小于等于起始点到目标点的曼哈顿距离就可以成功到达。

169. Majority Element

题意：给一个整数数组，其中有一个数数量多于总数量一半，求这个数。

解：简单方法就是使用hash表。但是hash表消耗线性空间。

有一个节省空间的算法，每次尝试从数组中找出一对不同的元素，删除，那么最终剩余的元素（至少一个）就是众数。

具体操作：count为0，且遇到新元素的时候，先把他作为答案，然后设置count = 1表示有一个数是独特的（候选者），然后下一次扫描新元素时候，如果与候选者不同，那么说明候选者和新元素是可以删除的，然后count减1变0表示目前没有候选者，如果相同，那么说明这两个数都能做候选者，count加1变2表示有当前候选者如果要被替换，那么至少要被抵消掉2次。遇到新元素的时候，如果此时count = 0，那么说明当前元素是特殊的，可以作为候选者，记录下来。

位运算方法：如果一个整数是大于总数量一半的，那么他的二进制表示中，每一位的是0或者是1，也一定是大于总数一半的，也就是说对于每一个位置，看大于元素总数的一半数字是0还是1，所有位置上的最终结果就组成众数。

PS.总体思路就是，不局限于数值大小的选择候选者（去掉不符合要求的非候选者），然后在验证候选者。

853. Car Fleet

题意：给出每个车的坐标，车看做一个点，然后给出每个车的速度。现在要求的是这些车分几波到达目标坐标，因为车不可以越过之前的车。

解：此题难想到的点：第一个是要使用时间来判断每个车到达，所以第一步是计算所有车达到目标需要的时间，然后按坐标的顺序考虑。

第二个是要反向考虑，也就是从目标看，哪个车队先达到，如果比之前达到的车队时间少，说明会同时到，直接跳过，否则就是新车队了。因为：正向考虑是存在问题的，例如需要的时间是{2，1，3}，中间的车会被后面的车干扰，也就是说中间的1不会比之前的2先到。

858. Mirror Reflection

题意：给出正方形，然后从左下角出发，选择一个角度，然后在确定一定会达到边角的前提下，问可以到达哪个边角。

解：参考https://buptwc.github.io/2018/06/26/Leetcode-858-Mirror-Reflection/

思路之一是模拟，但是此题更显然是数学题。直觉是不对的，例如p= 4, q =3，直觉觉得会折射回0角，但是答案是2角。

学做延长矩阵，然后观察延长几个矩形代表哪个边界，就可以求出答案。

首先，无论做了多少个辅助延长矩阵，我们知道，最终垂直和水平方向走过的距离都是p的倍数，且最终点在辅助矩形的右下角或者右上角。其中垂直方向走过的距离和水平走过的距离比例和q，p比例一样，所以可以知道垂直方向走的距离稍微小，所以他是等于p和q的最小公倍数的。 将每一次走的横向距离设为x。

观察博客中的图，右侧辅助矩阵中辅助线经过矩阵边缘，其实就是对应了在原来矩阵中的映射点，但是唯一不同的是，左右点和原矩型奇数位时候相反，偶数位时候相同，而顶点上下关系一直和原矩型相同。也就是说，如果走过的横向距离如果是x的偶数倍，那么一定落在了下侧，也就是一定会最终到达0接收器。

其中x是没办法计算的，编程时候是看竖直方向走的距离是不是q的奇数倍，如果是，那么是结果落在下侧。

如果是x的奇数倍，也就是落在上侧，那么看辅助矩形的个数，如果辅助矩形是奇数个的，说明是相反的，也就是答案是左上角接收器2。反之，就是右上角接收器1。

那么，如何求最终横向走过的距离呢？？其实是这样：无论最终落在右上角还是右下角，竖直距离一定是走过了q的整数倍，而横向距离走过的一定是p的整数倍，也就是说，计算出p和q的最小公倍数就是横向走过的距离。

求最小公倍数的方法就是：两个数的乘积除以他们的最大公约数。其中最大公约数可以使用辗转相除法来求。

此题中，p严格的大于q，而且需要知道p的倍数，也可以直接查看p的倍数是不是q的倍数来计算最小公倍数。

(lintcode)734. Number of Subsequences of Form a^i b^j c^k

题意：从串中找出所有匹配abc*的子序列数。

解：暴力求解就是先计算出所有的子序列，然后检测该序列满不满足abc的严格排序。求所有子序列不是求子集，子序列比子集多。

再来看数学解法：也是dp解法：考虑当前扫描的字符作为结尾的串对于各种类型（状态）的贡献，例如，以a结尾，那么该a可以让之前的空结尾变a，也可以让之前的a结尾进行翻倍（理解：多了一种选择的可能，答案翻倍），也就是说 dp_a = 1 + dp_a * 2；

同理，扫描到b，他可以让之前的a变ab，也可以让之前的ab翻倍，也就是说：dp_b = dp_a + 2*dp_b；

在考虑扫描到c，可以让之前的ab变abc，也可以让之前的abc翻倍，也就是说: dp_c = dp_b + 2 * dp_c。

96. Unique Binary Search Trees

题意：给出1到n个数，求所有BST个数。

解：此题想法关键在于知道，只要树满足中序是有序的，那么就是BST，所以，我们试着以每个结点为根，然后对剩余部分按大小分为左右子树，进行递归求解。

这当然存在大量重复，因此使用动态规划。

dp[i]表示对于i个结点的所有BST个数，所以dp[i]是考虑1到i所有结点作为根的情况总和，每个点的左右子树也是相同子问题，也就是dp[i] = dp[0]*dp[i-1]（1为根的情况） + dp[1]*dp[i-2]（2为根的情况） +…. + dp[i-1]*dp[0]（i为根的情况）。 i从1开始，累加向上计算。 其中dp[0] = 1表示空树大小也为1，dp[1]也等于1。

PS.此题本质是卡特兰数。参考：https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0 结果是2n里面选n个，除以n+1。

符合卡特兰数的题目就是：有n个元素，固定其中一个元素i，接下来拆解为两个子问题(1, i)和(i, n)的组合，而且i是有1到n种选择的。也就是说：dp[n] = dp[0]*dp[i-1] + dp[1]*dp[i-2] +…. + dp[i-1]*dp[0]。

他的对偶就是变成2n个元素进行“括号匹配”的问题。 举例： （1）出栈次序，n个数出栈序列可以有多少种？

把问题分割为前i个数和后n-i个数出栈序列的组合问题，那么发现是卡特兰数。

把n个数每个数都拆成0和1，那么发现结果就是长度为2n的，每一位都满足此时0的个数比1个数多的情况，也就是括号匹配问题，括号是合法的状况。

（2）nxn的grid爬格子，从左下角到右上角，不能越过对角线，只能向上和向右走，求路径数。

水平方向走n步，竖直方向走n步，但是有一个限制条件，那就是当前竖直方向走的距离不能大于水平方向走的距离，因为这样就会越过对角线。所以联想到括号匹配，也就是卡特兰数。

也可以以dp方式理解：走到右上角的情况中，有走到i-1 x i-1右上角的情况，然后把i-1, i-1处当作左下角，也就是拆成两部分的组合。

（3）n个人圆桌握手，没有交叉。

对于第一个人，有n-1种选择，每次选择后，分割为两个子问题的组合，因为不能交叉，两个子问题之间是独立的。

41. First Missing Positive

题意：找出数组中丢失正数中最小的。例如{1，2，0}, 丢失正数3，{3,4,-1,1,-4}丢失2。要求时间O(n)，空间O(1)。

解：如果没有要求空间，那么可以使用hashmap。

不使用额外空间的解决的方法是找规律。假设数组里面全部装满了正数，且是1，2，3,…那么丢失的最小正数一定是等于数组的长度。其他任何情况下，丢失的最小正数一定介于1到数组的长度之间。

所以，利用数组的下标，把找到的对应大小的数放进去。扫描两遍就可以了，第一遍，如果数字大小介于1到数组长度，那么放入相对应的位置，使用swap,之后下标不变，继续保证原地处理。第二遍时候，看下标和数字大小第一个不等的就是答案。

第一遍扫描的时候，要先检查是不是要交换到的位置和自己是相等的，如果相等，那么不用交换了，否则交换，并停留在当前，因为交换过来的数也需要处理。

1074. Number of Submatrices That Sum to Target

题意：求二维矩阵的子矩阵里面有多少个总和等于target的。

解：此题是数学题，二维矩阵的子矩阵有多少个呢？有O（N^4）个。

求子矩阵有两种思路：1）选取矩阵的左上角和右下角两个点，就可以得出一个唯一矩阵，注意右下角的坐标不小于左上角的坐标。

2） 矩阵中任选两行（或两列），然后在两行（两列）中的任意一行任选两个点，这样就能找出一个矩阵的四个顶点。

这样，我们知道，对于1）这种思路，我们可以利用下标前缀和的思路，在找到左上角和右下角的点组成的子矩阵后，O（1）的计算其面积。不过找矩阵需要O（N^4）的时间，总的时间也是O（N^4），会超时。

对于2）的这种思路，在两行中任选两点的这一方式，发现可以使用2Sum里面的O(N^2)变O（N）的技巧，但是进一步发现，任选两点似乎没有合适的前缀和来得到矩阵的面积。解决方法是：先选择两列，然后，从第0行开始，每次把扫过的行面积（也就是行前缀总和，计算方法是先计算每行的前缀和，然后按坐标相减）也计算前缀和，并使用hash技巧，这样每一行能够与之前行进行配合计算出矩阵面积的就可以O（1）计算出来了，这样O（N）的时间可以把两列中的所有子矩阵面积计算出来。总的时间复杂度是O(N^3)。

PS. 一维是连续子数组，二维就是子矩阵，求起来，都可以使用前缀和数组结合2Sum技巧。

1041. Robot Bounded In Circle

题意：机器人一开始在原点朝北，现在给出序列，表示机器人向左转还是向右转，走几步。 序列需要无限执行无数遍。现在给出一个序列，问机器人按此序列无限走是否最后会在一个圈内。

解：此题是数学题。结论是机器人一个序列执行完之后，如果不是面向北面，那么必然会在序列执行4次后回到原点，也就是所谓的在画圈。

理解：如果序列执行完一次后，机器人到达了某个点然后面朝东，我们先把原点和这个点用直线连接起来，表示机器人走了这样一个向量。 第二次执行的时候，可以知道，机器人还是会走一个向量，唯一的区别是一开始面向东的，说白了，这个向量的大小不变，方向是之前顺时针的多了90度。 且达到这个位置后，机器人的方向必然是朝南的。 依次类推， 第三次执行完后必然面向西，第4次回到原点。也就是4个向量刚好形成了一个正方形。

如果第一次执行完是面向北面，那么表示下次的向量会和这次的一样，也就是直线走下去。 注意，有一个例外，就是第一次执行完面向北面，但是还是在原点（向量大小为0），那么此时也是在圈内。

134.Gas Station

题意：给出gas数组和cost数组，gas代表到达该位置后进行加油多少，cost代表，从该位置到 下一个位置的消耗。一开始车没有油，现在求从哪个位置出发可以走完全程（假设解如果存在那么唯一）。

解：暴力求解：就是对每个点作为起点，看能否走完全程。

但是此题应该可以有优化解，应该有某种数学性质可以满足优化，例如我们可以不以每个点做起点，而是某些点做起点。

例如，从0位置开始，每走到一个地方，就把当前的剩余油量加上gas后，与cost进行比较，如果大于cost，说明可以继续走下去，那就继续；

如果没有cost大，说明下一个位置去不了，也就是说以0为起点无法走完全程。

假设这个去不了的位置是B，且之前一个位置是A，那么有gas0A(0到A gas总和) >= cost0A(0到A 路径消耗总和)，gas0B(0到B gas总和) < cost0B(0到B路径消耗总和)，

我们有这样一个结论，0到A之间的任意某站作为起点，那么它都是无法逾越B的，为什么呢？假设X（0到A间某个点）是新起点，由于0到X能够到达，所以最坏情况也是0到达X的时候油量是0（不加X之前） 因此X到达B并不比0到达B有上任何的优势。数学表述就是，0能到达X，那么有gas0X >= cost0X， 同时我们又知道 gas0X + gasXB < cost0X + costXB， 所以有costXB - gasXB > gas0X - cost0X >= 0，也就是 costXB > gasXB，无法从X出发到达B。

也就是说，时间复杂度省下来了，0到A是不需要计算就知道不能做起点的。

在从B作为新起点往后继续考虑：如果B能够一直走到最后一站，那么我们还是不知道最后一站能不能回到0，这里先不考虑，因为确实考虑不清楚；

但是如果B不能够走到最后一站，例如走到C的时候，发现走不到D，那么从D开始做新起点计算，注意！这里就是这个解法最有意思的地方：B到C（包括B）根据同理，由于无法逾越D，因此它们也不可能是起点！

总结，我们每次遇到走不到X的时候，那么就把X作为新起点，而在此之前的所有结点都不可能是起点（结果）了，然后对于新起点，把当前车油置为0，继续往后考虑。。。

最坏的情况下，每个路径都是很大消耗，而加油站油都是0，每站都不通。

另外，还要结合这样一个性质来解题：此题有解，当且仅当 gas总数 >= cost总数。

因此，如果本身就存在解，在之前的扫描过程后，那么最终起点就是可以走完全程的起点，否则，这个最终起点是无法走完全程的非法起点。

在扫描过程中，我们并行的进行一个操作，那就是计算总gas数和cost数，这样在最后面我们就知道此题有无解了。

PS. 此题非常有意思，虽然几乎想不到，而且题目性质苛刻，特殊，

但是它提供了一种N^2 降到 N的通用思路：也就是打破对于每个元素，需要它和其他所有元素比较的计算过程，而是它可以利用它之前元素的计算结果快速（O(1)）的计算出自己的解，例如此题，如果之前站0油能到达自己， 那么说明之前的站比自己强，因此如果之前的站都不能到达目的，那自己做起点也是没戏的。

166. Fraction to Recurring Decimal

题意：计算给出一个分数的分子和分母，求出分数的小数表示，小数循环部分用括号括起来。

解：首先，理解有理数的无限循环。例如一个数是0.（676），那么，首先可以根据数学推算把它转换为X／Y的有理数形式。 具体方法为：把无限循环的部分乘以10^N来变成整数，也就是有 1000X / Y = 676.(676)。再把这个公式减去X / Y = 0.(676)就可以得出 X / Y = 675 / 999。

其次，需要找到循环部分，关键是模拟4 ／ 333 的过程，发现，在上数后补足后，如果该数余分母之后的余数出现重复，那么意味着出现重复了。

再次，编程找到循环部分，并使用括号括起来。怎么加呢？需要使用哈希表，在每次存入新的余数的时候，同时把对应计算的小数计算的位置给存下来。

再次，安排编程流程，第一步，返回简单边界情况；第二步，计算数的符号，并将数转为long型（以防止负数变正时候越界）的正数；第三步，计算结果为整数的情况；

第四步；计算结果为整数加小数的情况。

最后，各种处理边界条件， 测试用例：

1. 4 / 333 ＝ 0.(012)

2. 0 ／ 100 ＝ 0

3. －4 / 333 ＝ 0.(012)

4. －4 / －333 ＝ 0.(012)

5. int负数最大数的情况

6. 2 ／ 1 ＝ 2

7. 1 ／ 2 ＝ 0.5

• Previous
  Leetcode按题目类型总结（十六）
• Next
  Leetcode按题目类型总结（十九）