一些LeetCode中等题做法（三）
记录一些LeetCode中等题解法。
148. Sort List
题目：O(NlogN)时间，O(1)空间对链表排序。
做法：思路是使用归并排序，并且在递归中使用常数空间，即使运行过程中实际记录的空间不是常数，也算O(1)空间。在将两个排序链表合并成一个时，可以使用一个临时节点简化代码，再用一个指针指向其尾部，两个排序链表头部的较小值连接在临时链表的尾部，然后移动排序链表的头部，最后把剩余的部分接在最后。在将当前链表拆分成两个链表时，可以使用两个指针指向链表头部，一个递增1，一个递增2，当递增2的指针或它的next为空时停止，这时递增1的指针就在链表的中间，截断就可以将原链表分成等长的两部分。
221. Maximal Square
题目：给定包含数字0和1的二维数组，找到其中最大的由1构成的正方形。
做法：比较明显的方式是对每个位置记录从矩形左上角到这个位置的所有1的数量，然后对每个值为1的位置，查看各个长度的正方形区域内的1的数量是否填满该正方形，如果已经找到某个符合条件的长度，则下次要递增。可以找到一个更好的方法，使用动态规划，第一行和第一列中值为1的点dp[i][j]=1，其余点如果值为1，dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1。dp数组的值表示，从该点开始往左上角看，最大的正方形的边长，如果当前点(i, j)值为1，并且它左边，左上，上边的三个点都可以找到某个边长为L的正方形，则恰好已经填满了从(i, j)往左上角看的L+1长的正方形。如果这三者某个小于L，分别会在长度为L+1的正方形的左下角，左上角，右上角缺某些格子。
229. Majority Element II
题目：找到数组中出现次数大于N/3的数，O(1)空间。
做法：需要使用两个变量m，n记录出现次数最多的两个数，变量cm，cn记录这两个变量当前出现的剩余次数，当发现三个互不相等的数时，这个剩余次数要减小。遍历数组，对当前数x，如果x等于已经记录的m或n，则增加对应的cm或cn，如果m和n都已经填了数字，而x不等于m或n，则cm和cn同时减1，如果m和n有空位，而x不等于另一个，则把x填到空位，增加对应cm或cn，如果m和n都是空的，则填到m里。
236. Lowest Common Ancestor of a Binary Tree
题目：给定二叉树，其中各值唯一，求两个节点的最低公共祖先。
做法：使用某种方式遍历树，找到根到这两个节点的路径，然后用两个指针指向路径头部，递增可以找到最低公共祖先。也可以用递归等方式，递归终止条件是当前节点为空，或当前节点等于要找的两个节点之一。在当前节点的左右分别寻找，如果左右子树之一包含了要找的两个节点，则该子树的根就是最低公共祖先，如果左右子树都没有同时包含两个节点，则它们分布在左右子树，应该返回当前节点。
238. Product of Array Except Self
题目：给定一个数组，对每个位置求除了该位置的所有数的乘积，不能用除法，并且在O(N)时间完成，进阶：O(1)空间，输出数组不算。
做法：数组为A，输出数组为B，临时变量初始为1，第一轮运算，数组B依次为1，A[0]，A[0]*A[1]，…，A[0]*A[1]*…*A[n-1]，可以发现得到的数组B与自己的逆序相乘，得到的就是输出，所以第二轮运算，重置临时变量，逆序乘一遍就得到结果。
241. Different Ways to Add Parentheses
题目：给定一个包含加减乘的表达式字符串，求所有可能的加括号方式对应的运算结果。
做法：首先把表达式字符串拆成多个数字或运算符号元素，递归计算当前元素数组，遍历当前元素数组的所有运算符号，拆分元素数组，拆分的左边或右边返回该部分所有可能的输出，合并时两两加减乘作为当前元素数组的输出。
274. H-Index
题目：给定一个研究者的N篇论文的引用数，求该研究者的最大h-index（如果有h篇文章的引用数至少为h，N-h篇的引用数小于等于h）。
做法：对该研究者，如果某篇论文的引用数大于N，将该论文引用数改为N，不会影响h-index，用一个数组A记录引用数是0…N的数量。如果A[N]>=N，则h-index是N，如果A[N-1]+A[N]>=N-1，则h-index是N-1，所以从N到0，对比与数组A后缀和的大小关系，可以找到h-index。
275. H-Index II
题目：给定一个研究者的N篇论文的引用数，按升序排列，求该研究者的最大h-index（如果有h篇文章的引用数至少为h，N-h篇的引用数小于h），进阶：O(logN)时间。
做法：考虑left=0和right=N-1，它们的中点mid，引用数数组为A，有N-mid篇论文的引用数大于等于A[mid]，对于其它的left、right、mid也满足。想要找的是这样一个h，A[h]>=N-h，但是A[h-1]<N-(h-1)，如果A[mid]>=N-mid，则h<=mid，否则h>mid。为了便于理解，可以在二分的时候分为[left,mid]和[mid+1,right]两个区间，暂时不对mid-1做处理，最后终止条件时要额外判断right-left等于1的情况。在二分的时候，如果想直接写right=mid-1和left=mid+1，表面上可能会导致left和right之间没有要找的值，while(left<=right)。这里要分几种情况，对于某个较大的区间[left,right]和它的mid，如果要找的值h恰好是mid，判断之后发现mid满足条件，应该在区间[left,mid-1]内找，那在找的过程中，每次都要执行left=mid+1，因为里面没有h，最后总会达到left=mid-1的情况，这时由于left==right，所以还要再加一次，left恰好又对应上了实际正确的值。如果对于某个一开始就是left==right的区间，它的mid满足条件，则只是right=mid-1，left依然对应的是正确的位置。
对应找到的代码来看，第一个判断表示对于所有满足条件的mid，right一定会在它的左边一格，那在最后输出的时候，right就是满足条件的最小mid减1，left是不满足条件的最大的mid加1。
class Solution {
public:
int hIndex(vector<int>& citations) {
int left=0, len = citations.size(), right= len-1, mid;
while(left<=right)
{
mid=left+ (right-left)/2;
if(citations[mid] >= (len-mid)) right = mid - 1;
else left = mid + 1;
}
return len - left;
}
};289. Game of Life
题目：给定值为0和1的二维数组，表示活细胞和死细胞，根据周围细胞的情况，两者可以转换，求转换后的结果，进阶：原地转换，边界。
做法：原地转换的关键在于，对每个值增加一个位表示下一个状态的值，可以用位运算得到某个位置的老状态和新状态，处理结束后用位移运算更新状态。
310. Minimum Height Trees
题目：给定N个点，N-1条边的可转换为树的图，求以哪些点作为根可以得到最小高度的树。
做法：找到所有叶节点删除，剩下的图中的叶节点再删除，直到剩下的点小于等于两个时输出。由于边相对来说较少，所以用邻接链表来存边，并记录每个节点相邻边的数量。首先找到相临边数量为1的点Ps，遍历这些点的相邻点Ns，减小它们的度1，如果度等于1，则加入到待探索列表中。对于每一轮寻找叶节点，有两种方式，一种是在邻接链表（或hashmap）中删除上一轮找到的边，然后找度为1的节点。一种是不对邻接链表进行删除，每轮准确维护没有当过叶节点的点的度，对于当前轮，假设所有点的度都是准确的。考虑每个当前待探索列表中的每个点，把这个点的所有邻居的点的度减1，其中分为两种情况，一种是它们上一轮的度是1，由它们使得当前节点被放入待探索列表，减1后就是0，相当于它们被删除了，还有一种是还没有被放入探索列表的节点，它们的度减1相当于删除了当前这个叶节点使得它们的度减小了，经过这一过程，度为1的点就是下一轮的叶节点。
318. Maximum Product of Word Lengths
题目：给定小写字母字符串数组，在其中挑两个没有重复字符的字符串，求可能的最大长度乘积。
做法：遍历字符数组，将每个字符串转换为最多26位的整数，每一位对应一个小写字母，双重循环遍历生成的整数数组，可以用位运算判断两个字符串是否有重复字母。
322. Coin Change
题目：给定一些面额的硬币无限量和想要凑的值，求需要的最少硬币数量。
做法：一维动态规划，dp[0]=0，表示凑0需要0个硬币，从1开始考虑直到需要凑的硬币面值amount，对应变量i，遍历所有硬币j，如果该硬币面额小于等于当前考虑的面额i，dp[i]=min(dp[i], dp[i-coins[j]] + 1)，最后dp[amount]就是需要的硬币数。
382. Linked List Random Node
题目：对单链表实现随机选取节点，各节点选中的概率相等，进阶：链表长度超大且未知，O(1)额外空间。
做法：遍历单链表，记录当前已经遍历的数量count，用一个变量out记录产生的随机输出，每次随机生成一个0~count-1的数，如果它为0，则修改out为当前遍历到的节点，也就是有1/count的概率修改out。遍历第一个点，必然修改out，遍历第二个点，有1/2的概率修改，则两个点作为输出的概率相等，遍历第三个点，有1/3的概率修改，则1/2*2/3=1/3的概率为第一或第二个点，1/2*1/3+1/2*1/3=1/3的概率为第三个点，第N-1个点时，各个点的概率均为1/(N-1)，第N个点时，有1/N的概率修改为第N个点，前面每个点出现的概率为1/(N-1)*(N-1)/N=1/N，修改为第N个点的概率为1/(N-1)*N*(N-1)=1/N。
390. Elimination Game
题目：给定数字N，相当于有1~N总共N个数字，第一次从前往后，去掉首个数字，隔一个去掉一个数字，第二次从后往前去掉数字，交替进行，求最后剩的数字。
做法：对于2N+1和2N，第一轮去掉数字后剩的结果是一样的，f(2N+1)=f(2N)，f(N)表示从1~N的数字，按照条件去掉数字后，剩余的数字。考虑123456->246->4，思考f(2N)与f(N)的对应关系，f(2N)去掉一轮数之后，剩余的数是2*(1…N)，接下来是要从后面开始去掉数字。考虑从N到1去掉数字与从1到N去掉数字的差别，将对应位置上的数X替换为N+1-X，则数组变为N…1，这时是先从后面开始去掉，所以最后剩下的数就是f(N)，假设它是从前往后数第M个位置上的数。所以如果不对1…N进行替换，最后剩的也是第M个位置上的数，而两次替换中，同一个位置上的数和为N+1，所以1…N从后面开始去掉数字，最后剩的数是N+1-f(N)，可以得到式子f(2N)=2*(N+1-f(N))。
392. Is Subsequence
题目：判断字符串s是否是字符串t的子序列。
做法：两个指针指向s和t的头，如果两者相等，同时递增1，如果不等，仅t递增1，如果s的指针超过末尾，则返回true，否则返回false。
436. Find Right Interval
题目：给定间隔数组，没有起点相同的间隔，如果间隔i与j不重合，并且整体在j的右边，则间隔i在间隔j的右边。需要对间隔数组中的每个间隔，找到它最近的右边的间隔的下标，如果没有则对应-1。
做法：由于各个间隔的起点不同，并且最后需要输出的是下标，所以需要建立间隔起点到下标的对应关系，可以使用map，也可以自定义结构，需要按照起点递增进行排序。对每个间隔，考虑它的末尾end，需要找到第一个大于end的间隔起点，也就是lower_bound，如果没找到，则对应-1，如果找到了则对应下标。
442. Find All Duplicates in an Array
题目：给定长度为N的正整数数组，其中所有数都在1~N之间，有的数出现两次，其他的出现一次，求所有出现两次的数，O(N)时间，O(1)空间。
做法：可以找到两个方法，一个是利用数组下标是0~N-1，值是1~N，遍历数组，如果当前位置P的数X与位置X-1的数不同，则交换这两个数的位置，使得位置X-1上的数是X，如果数组中没有重复的数，最后每个位置上的数都是下标加1。如果相同，实际上找到了一个出现两次的数X，继续遍历下一个数，这个位置之后有可能会被其他数换走，但是位置X-1上的数已经是X，不可能再被换。最后如果某个位置的值不等于下标加1，说明它没办法填充进想去的位置，是出现了两次的数。第二个方法是，由于所有的值都是正数，可以把它们转换为负数记录信息，每次取数的时候要用绝对值。位置与值是一一对应的，在遍历数组时，把当前值对应的下标上的数设置为负值，并且对每个当前值，需要查看对应下标的数是否已经是负值，如果是负值，说明它出现了两次。
445. Add Two Numbers II
题目：求以链表形式保存的两个数的和，以链表形式输出，进阶：不修改输入（不翻转链表）。
做法：可以用两个栈将链表存进去，然后依次计算，新的值插入链表头。可以找到一个不用栈的方法，就是第一次计算时，直接将对应位置的数相加，不进位，存链表尾部，第二次依次计算的时候，相当于从栈里获取两个数相加，插入链表头。但是这两个方法还是相当于从链表的尾部开始计算，和翻转链表很像，可以找到一个从前往后思考的方法。为了处理进位问题，首先使用一个值为0的节点dummy作为开头，并维护链表的尾部tail，增加一个指针，指向最后一个不是9的数lastnot9。根据链表L1和L2的长度区别，将较长的部分全部连接在dummy后面，维护tail和lastnot9，当剩余部分两者长度相等时，进行后续的计算。每次相加的结果，如果小于9，则直接链接在tail后面，并维护lastnot9，如果等于9，只要链接在tail后面，如果大于等于10，则lastnot9位置上的数要加1，并且lastnot9与当前位置中间都是9，需要全部设置为0，将lastnot9维护在最后一个0的位置，如果中间没有9，则lastnot9位置暂时不变，当前数减去10之后得到的数要链接在tail后面，对于当前两数和减去10之后，剩下的数最大是8，所以lastnot9还需要移动到当前位置。最后如果dummy是0，则输出它的next，否则直接输出dummy。
464. Can I Win
题目：给定整数S和N，两个人玩游戏，每次可以选一个1~N的数，已经选过的数不能选，如果选完之后所有已经选的数的和大于等于S，则胜利，求先选的人是否有必胜策略，S<=300，N<=20。
做法：可以使用DFS，需要利用N<=20，将每次已经选择的数用位运算转换为一个整数，已经算过的就不用算了。如果剩下的数有大于等于还缺的数时，则返回true，否则尝试选取每一个剩下的数，可选的数都无法返回true，则返回false。
467. Unique Substrings in Wraparound String
题目：给定一个小写字符字符串，假设字符a和字符z相连，例如“abcde”，“def”，“yzabcd”都是目标字符串，求给定字符串中总共有多少个目标字符串子串，重复的不计数。
做法：我想到的方法是，对每个字符，记录由它结束的最长递增子串长度，最后把26个字符的长度加起来就是结果。想出来的过程是写了两串，假设只有“abcde”5种字母，写“abcdeabcd”和“bcdeabcdeabcd”。如果某个字符与前一个字符不构成递增，则当前长度要刷新，如果构成递增，则修改当前长度，根据当前长度和当前字符之前记录的最长长度的大小关系，判断是否修改长度数组。
470. Implement Rand10() Using Rand7()
题目：由Rand7()随机获得1~7的函数，得到Rand10()随机获得1~10的函数。
做法：常见的方法是，执行两次Rand7()得到a和b，计算(a-1)*7+(b-1)，如果结果r小于40，则返回r/4+1，如果当r大于等于40时，重新计算。如果当r大于等于40时，不是直接丢弃，而是利用48与它的差值，可以得到一个0~8的数c，与一个新的rand7()=d，计算(c-1)*7+(d-1)，范围是0~62，然后得到0~2的数e，下一次的范围是0~20，只有20需要排除，概率较低，可以减少调用Rand7()次数的期望。在讨论里有人提到了一个平均调用次数期望很低的方法，连续调用Rand7()很多次，每次调用的结果减1再乘以7的次幂求和，就能得到一个很大的数，由这个数截断最后的一位，就能得到很多个Rand10()的结果，取完了再重新计算一批。
473. Matchsticks to Square
题目：给定正整数数组，表示多根一定长度的火柴棍，判断这些火柴棍是否可以恰好组成一个正方形，火柴棍数量不超过15。
做法：我想到的方法是暴力DFS，先对数组倒序排序，做了一些后发现不能每次凑Sum/4，要一起凑完才知道能不能组成正方形，实际需要凑的是3份Sum/4。记录哪些火柴棍已经用了，以及每份还缺多少。用了一些剪枝，一是如果当前还剩的最短火柴棍都超过了与Sum/4的距离，则返回false，二是得按照3份的顺序来凑，如果前一个没凑满，就不能凑下一个。看了答案发现有更简短的DFS方法，还有一个DP方法。DFS方法是对每根火柴棍，考虑放到4堆里面，放完如果4堆相等就可以组成正方形，当时我算了一下，415很大，估计时间会超就没用。刚刚用了答案里面的Java代码，执行时间114ms，我的DFS是16ms，不确定具体的差别。DP方法是利用最多15根火柴棍，使用位运算将每根火柴棍是否选取对应一个整数，火柴棍选取情况和当前选取情况已经凑了几条边作为key，该key是否成立作为value，建立hashmap进行持久化记录。递归的过程对每个可选的火柴棍进行尝试，还需要记录的值是当前已使用边的总和，根据这个就可以调整是否新凑完一条边。在对可选的火柴棍尝试时，如果当前选择的边大于当前在尝试凑的边的剩余值，则不能选择它进行递归，实际上每次选择边都是指定填充确定位置的边。
474. Ones and Zeros
题目：给定只包含0和1的字符串的数组，和整数m，n，表示有m个0，n个1，求最多可以组成多少个字符串。
做法：遍历字符串数组，对每个字符串计算其中有zeros个0，ones个1，如果zeros>m或ones>n则跳过，接下来有两种相似的DP方法，都是用大小为(m+1)*(n+1)的二维数组记录各种m和n可以组成字符串的数量。一是先复制一份dp数组，jk遍历0…m和0…n，如果dp[j][k]>0，并且j+zeros<=m，(k+ones)<=n，则dp[j+zeros][k+ones]=max(dp[j+zeros][k+ones], dp[j][k]+1)，遍历完之后，dp[zeros][ones]=1，把新生成的dp赋值给原dp数组。如果不复制一份，使用该方法时后面的数会受前面的数的值的变化影响，得出错误结果。第二个方法是倒序遍历，和上面相对应就是jk遍历m…zeros和n…ones，其中的j+zeros和k+ones要改成减号，这样就不用复制一份。