一些LeetCode中等题做法（二）
记录一些LeetCode中等题解法，少量分析。
116. Populating Next Right Pointers in Each Node I
题目：为二叉树实现记录next节点（层次遍历的下一个节点）。perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
做法：外层循环遍历每一层的最左节点，除了最后一层，对于每一个最左节点，由于不是最后一层，所以肯定有左节点和右节点。首先将该节点P的左节点的next指向右节点，如果每层处理结束后，该层下面一层所有的next节点都维护完毕（在初始遍历根节点时，只需要根节点的左节点的next指向右节点就维护完毕）。对于当前层的每一个节点P，如果它有next，P->right->next=P->next->left，这时此节点P的左右孩子的next都已经记录，然后由于此层的next已经记录，需要将当前节点P移动至next节点，继续进行即可。最后当前层遍历结束，就维护了下一层的next节点。
117. Populating Next Right Pointers in Each Node II
题目：为二叉树实现记录next节点（层次遍历的下一个节点），允许节点的左右节点不完整。
做法：外层循环需要从每一层的第一个节点开始，首先假设在遍历当前层的时候，当前层的next已经维护好，在遍历过程中，维护好下一层的next节点。每层的第一个节点需要在维护下一层next节点时，对于第一个非空的左节点或右节点进行记录。由于该节点最后需要返回，作为下一层的开始，但是该节点的next需要不断地链接在最后一个next后面，所以要用两个指针，一个记录链表头，一个记录链表尾，不断在链表尾插入新来的next节点。
173. Binary Search Tree Iterator
题目：O(1)时间，O(树高)空间，对BST设计迭代器next函数和hasNext函数。
做法：维护一个栈，栈顶是当前的最小值，如果栈为空，则没有next，初始情况的最小值是从根节点开始，找到最左节点，栈中记录了从根节点到该节点的路径。每次求next，需要弹出栈顶的元素作为返回值，然后需要维护栈，要用临时变量指向弹出的元素，进行一些操作。栈顶元素是没有左节点的（或者所有左节点都已经弹出），如果该元素没有右节点，则弹出该元素后，栈顶的左子树已经全部弹出，栈顶就是当前的最小值。如果该元素有右节点，则首先需要将右节点入栈，然后将这个右节点的所有左节点依次入栈，最后栈顶是当前的最小值。
192. Word Frequency
题目：使用Bash统计文本词频，按词频大小逆序分行输出词语和词频。
做法：
cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -nr | awk '{ print $2, $1 }'| 管道命令，将前一个操作的输出用于后一个操作的输入。
cat words.txt 显示文件内容
tr -s ' ' '\n' tr命令是字符替换命令，tr SET1 SET2表示在SET1中的字符被替换为SET2对应位置上的字符，-s表示连续的SET1中的字符缩减为1个。于是该命令表示将连续空格替换为’\n’。
sort 按行排序，sort -r 倒序，sort -nr 按数字倒序。
uniq 去除相邻重复行，uniq -c 去除相邻重复行并且计数，数量在前，行内容在后。
awk '{ print $2, $1 }' 对每行的元素，先输出第二个，再输出第一个。常用格式 awk ”模式”，awk {操作}，awk “模式” {操作}，输入文件每行作为一个元素，如果指定模式或操作，需要对匹配模式的行进行操作，默认操作是输出，默认样式是匹配所有字符串。$1对应分隔符划分的第一个元素，$2是第二个，分隔符默认是空格和制表符。如果没有用管道，末尾要加上操作哪个文件。
194. Transpose File
题目：使用Bash对一个多行由空格隔开的文本矩阵进行转置。
做法：
awk '
{
for (i = 1; i <= NF; i++) {
if(NR == 1) {
s[i] = $i;
} else {
s[i] = s[i] " " $i;
}
}
}
END {
for (i = 1; s[i] != ""; i++) {
print s[i];
}
}' file.txtawk '{操作}END{后操作}' 文件名，先执行前面的操作，这里的操作是以行为单位，$1和$2等对应的是行内的第一第二个元素，然后执行END内操作。NF是每行的元素个数，NR是当前累计的行数。所以该代码对第一行的每个元素，建立对应位置的数组，对后面的行的每个元素，找到相应的数组，加个空格再记录当前元素，得到的数组顺序输出就是原内容的转置。
142. Linked List Cycle II
题目：找到链表中的环入口，没环输出NULL，不能修改链表，进阶：O(1)空间。
做法：用map保存节点可以在O(n)空间完成，可以找到O(1)空间的解法。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return NULL;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};令x为链表入口到循环入口的距离，y为循环的长度，i为使得slow和fast相遇的在0到y-1范围内的值。slow走过的长度为x+ay+i，fast走过的长度为x+by+i，有2(x+ay+i)=x+by+i，可得x+i=(b-2a)y，将x转换为模y的形式可以发现必然有一个a=0的解，则时间复杂度是O(N)。现在对比从链表头移动x次和fast移动x次，x+by+i+x=x+by+(i+x)=x+by+(b-2a)y=x+2(b-a)y，和链表头移动x次是相等的，并且位于循环的入口。
287. Find the Duplicate Number
题目：O(1)空间，小于O(N2)时间，不修改数组，在长度为N+1的只包含1到N的数组中，寻找唯一的出现次数大于1的数，其他数只出现一次。
做法：我想到的办法是O(NlogN)的，二分查找left、right中间值mid，统计数组中位于区间[left,mid]和(mid,right]的数的数量L和R，如果L<=R，left=mid+1，否则right=mid。这题可以找到一个更优的O(N)的解法。
class Solution {
public int findDuplicate(int[] nums) {
// Find the intersection point of the two runners.
int tortoise = nums[0];
int hare = nums[0];
do {
tortoise = nums[tortoise];
hare = nums[nums[hare]];
} while (tortoise != hare);
// Find the "entrance" to the cycle.
int ptr1 = nums[0];
int ptr2 = tortoise;
while (ptr1 != ptr2) {
ptr1 = nums[ptr1];
ptr2 = nums[ptr2];
}
return ptr1;
}
}这题的做法和142. Linked List Cycle II的做法很像，用一个递增1的和一个递增2的指针找到它们相等的位置，然后把递增1的指针重置，然后和递增2的指针位置一起递增1，直到相等。这题考虑数组的下标与数组的值对，(i,v)表示节点i到节点v有一条边，下标范围是[0,N]，值范围是[1,N]，需要证明从0出发的链表一定有环。假设没有环，从0出发前进N+1次，每次得到的都得是不同的节点，而可选的边的末尾只有N个可能的值，矛盾，所以从0出发的链表一定有环。使用142题的方法可以找到环的入口，环的入口意味着有两个下标都能得到同一个值，也就是找到了数组中的重复值。
162. Find Peak Element
题目：对数时间，给定相邻数组值不等的数组，寻找任意一个大于左右邻居的数，数组边缘默认大于越界邻居。
做法：整体思路是二分不断获得更小区间，在递归或使用头尾指针二分时，对于一段位于数组内部的区间（不包含原数组头和尾），如果该区间中的元素构成递增数列或递减数列，则无法在该区间内找到所需的数，所以设计的方法要避免这种情况。另外，如果一段区间的头和尾都大于越界邻居时，就算该区间内部元素构成递增或递减数列，总可以在头或尾找到一个符合条件的数。首先考察数组的头尾，由于位于头尾的数默认是大于越界邻居的，于是在初始时限定了不是普通的递增或递减数列，并且满足头部递增，尾部递减。考察区间中间的元素，如果它大于该元素左侧一格的元素，则取右半边的区域，该区域满足头部递增（大于越界邻居），尾部递减，如果它小于左侧一格的元素，则取左半边区域，同样满足头部递增尾部递减，当区间只剩一个数时，它大于左侧和右侧越界邻居，则可以输出对应索引。
264. Ugly Nubmer II
题目：丑数是1和因子只含2、3、5的正整数，求第N个丑数。
做法：根据已有的丑数数组，求下一个丑数，需要把所有的丑数都乘以2、3、5，然后找到其中最小的数，这个数就是下一个丑数，依次计算就可以得到第N个丑数。但是如果所有丑数都要乘以2、3、5，效率太低，考虑当前已有丑数的最大值M，已有丑数中乘以2仍然小于等于M的不需要再考虑了，只有乘以2后大于M的第一个数是需要考虑的，3和5也同样。所以需要维护的是三个下标a、b、c，分别表示乘以2、3、5大于当前丑数数组最大值的三个数的下标，当前丑数数组初始值为一个数字1。每次遍历需要考虑下标为abc的数乘以235的最小值，取为下一个丑数，如果这个新的丑数等于下标为a的数乘以2，则a需要递增，对b和c也同样进行考察是否需要递增。
313. Super Ugly Number
题目：给定一个质数数组，超级丑数是1和能因子只在该数组中的数的正整数，求第N个超级丑数。
做法：与因子为2、3、5的丑数类似，为给定质数数组中的每个质数设置一个下标变量，遍历时考虑多个值。
307. Range Sum Query - Mutable
题目：整数数组单点修改，求指定区间和，线段树（树状数组）。
做法：明显的办法是O(1)修改，O(N)求和，可以找到一个稍微好一点的办法，是将原数组划分为sqrt(N-1)+1个sqrt(N)大小的区间，预处理O(N)，更新时对受影响的一个区间更新O(1)，区间和对包含的完整区间直接求和，不完整区间单个计算O(sqrt(N))。
更好的办法是用线段树，将原数组划分为长度为N、N/2、…、2、1的区间，每个区间记录区间和，修改时对根到叶节点的路径上的区间进行修改，区间求和需要将指定区间划分为已经记录和的多个区间求和。
线段树使用数组记录树形结构，每一个数组元素根据下标可以算出它在树形结构中的位置，数组元素表示对应区间内所有数的和。这里讨论的是递归形式的线段树，对于数组长度为N的数组，树的划分是固定的，接下来计算空间复杂度。假设给定的数组元素个数为2n，对应的线段树是一个完整的二叉树，每层节点数量分别为20，21，…，2n，每层节点对应的区间长度是2n ，2n-1，…，20，树总共有n+1层。对应树形结构，根节点下标为0，它的孩子下标为2*0+1和2*0+2（还有另一种方法是根节点是1，孩子下标2*1和2*1+1，浪费一个空间看着顺眼点，并且在计算的时候用位运算可以加速），下标为i的节点的孩子坐标为2*i+1，和2*i+2，总共能延伸n次，每次延伸获得的两个节点下标最大是2*i+2，令f(0)=0，f(n)=f(n-1)*2+2，可得f(n)+2=2*(f(n-1)+2)，则f(n)=2n+1-2，每层节点编号的最大值是0，2，…，2n+1-2。对于一个2n长度的数组，需要使用的空间是2n+1-1（要加上0），并且当数组长度在(2n-1,2n]内时，从根节点到叶节点在最坏情况下需要探索n次（探索n-1次最多获得2n-1个数），所以需要的空间倍数小于4（(2n+1-1)/( 2n-1+1)），当考虑数组长度是N时，对应的空间复杂度是4N。
现在稍微考虑一下极限空间是多少（如果是代码的话，建树的代码记录叶节点的线段树下标最大值就可以得到），在划分各个节点时，左右子树的节点数量差最大是1，所以左右子树高度差最大是1，需要考虑的是对应树形结构最后一层中最大的下标编号。原数组元素数量与所需空间的部分对应关系如下所示，2n-1+1->2n+1，2n-1+2->2n+2n-1+1，…，2n-1+2n-1->2n+2n-1，根据数组建树，然后根据递推关系找到最大的线段树节点下标加1就是所需的空间。原数组大小从2n-1开始，增加1，空间是2n+1，增加2，空间是2n+2n-1+1，增加4，空间再加2n-2，所以增加2m时，空间在上一次增加的基础上增加2n-m。需要注意的地方是，原数组大小在增加的过程中，对线段树的最下层的影响是，左边加一个，右边再加一个，交替进行，只有当增加到一定程度，才会影响最后的消耗空间，还有线段树的节点是占两个位置，在考虑的时候要取第二个位置，并且在计算的下标最大值的基础上加1才是消耗的空间。大概就是[2n-1+2m, 2n-1+2m+1)对应2n+2n-1+…+2n-m+1，也就是2n+1-2n-m+1，在边界m=n-1时，对应2n+1-2+1，也是成立的。
按照这个式子，可以得到一个O(loglogN)时间，O(logN)空间的计算方法，大小为10的数组，最多可以计算原数组大小为256的情况。
int z[10] = {1,2,4,8,16,32,64,128,256,512};
int get(int a){
int n=0, m=-1;
n = lower_bound(z,z+10,a)-z;
if(n>0){
int b = a-z[n-1];
m = upper_bound(z,z+10,b)-z-1;
}
return z[n+1] - z[n-m] + 1;
}线段树中叶节点的数量与原数组的大小相等，在单点更新时，从根节点到对应叶节点的路径上的所有区间都要更新。从线段树的根出发，根据要更新的点的索引和当前区间的中点的关系，探索相应的节点，递归栈中有从根节点到相应叶节点的所有节点（线段树数组中对应的位置），先修改叶节点，然后逐个修改递归栈中的节点。
在区间查询时，从线段树的根节点出发，根节点表示整个原数组，每次将当前节点分成两份，对应线段树中的左右节点。在划分时，如果当前节点与要查询的区间没有交集，则返回0，如果有交集，只有在当前节点完全被要查询的区间包围时，返回节点对应的区间和。递归的过程会尝试探索线段树所有的节点，在超出范围的地方剪枝返回0，在恰好包含的地方剪枝返回区间和。为了便于理解，可以将线段树区间[begin,end]划分点S与要查找的区间[L,R]的关系分为两种情况，如果S位于L和R两端，新的两个线段树节点有一个超出范围被剪枝，线段树查询的范围缩小了一半，如果S位于L和R中间，在下一轮操作时，相当于在两个更小的线段树区间[begin,S][S+1,end]内，查找两个更小的查询区间[L,S][S+1,R]，这样就不是在包含的时候输出，而是在精确对应的时候输出。证明时间复杂度是O(logN)较为复杂，可以参考https://www.cnblogs.com/AC-King/p/7789013.html。线段树经过修改可以实现O(logN)区间修改，之后如果有机会理解再做介绍，另外，对于这类问题，其中一部分可以使用树状数组记录前缀和，代码相对好写。
337. House Robber III
题目：正整数二叉树型结构，不能取相邻节点，取若干点求和，求所能取到的最大值。
做法：树形动态规划的基础题，从根节点开始，遍历整棵树，根据状态转移方程，由节点的子节点的信息得到父节点的信息。假设每个节点只记录一个信息，这个信息可以是选取该节点的子树的最大和，也可以是不选取该节点的子树的最大和，也可以是前两者的最大和，可以发现这三种信息都不足以由子节点推出父节点的信息。假设记录两个信息，不选取该节点的子树的最大和Sno是必须有的，另一个信息考虑以该节点为根的子树最大和Smax，Smax[root] = Sno[left] + Sno[right] + Val[root]，Sno[root] = Smax[left] + Smax[right]，Smax[root] = max(Smax[root], Sno[root])。使用深度优先搜索可以遍历所有节点，得到根节点的Smax，就是所能取到的最大值。
215. Kth Lagest Element in an Array
题目：求整数数组中第K大的数。
做法：维护一个大小为K的最小堆，保证堆里面是遍历过程中最大的K个数，遍历整数数组，如果堆的元素数量小于K，则直接插入，否则对比当前数与堆顶的大小，如果当前数大于堆顶，说明堆顶是当前已知的第K+1大的数，需要弹出，然后插入当前数，最后堆顶就是第K大的数。
347. Top K Frequent Elements
题目：找到整数数组中出现频率最高的K个数。
做法：与求第K大的数类似，需要维护一个大小为K的最小堆。建立一个结构或者类，包含数值与出现次数，遍历记录各个数值的出现次数。自定义compare函数，默认priority_queue是最大堆，定义a.m_count > b.m_count可以得到最小堆。
378. Kth Smallest Element in a Sorted Matrix
题目：每行每列都是递增的整数矩阵，找到其中第K小的数。
做法：比较明显的方法是用一个数组记录当前每一行已经探索了几个数，每次探索一个最小值，直到找到第K小的数。可以找到一个更好的方法，回顾一下行列递增矩阵的查找，初始选取整个矩阵，考虑要找的数N与当前矩阵右上角的数M的大小关系，如果N>M则第一行被排除了，这意味着去掉的部分有当前矩阵列数的数比要找的数小，如果N<M则倒数第一列被排除了，去掉的部分有当前矩阵行数的数比要找的数大。根据这个方法，选定一个数，在N>=M和N<M时都进行行列的删除，同时记录总共有多少个数小于选定的数。用二分每次在二维数组中找一个数，得到有几个数小于该数，对比与K的关系，修改要查找的数。