春季四个月刷题

2.26 做题

242. Valid Anagram. 这个题目用了一个HashMap，首先去统计s字符串的每个字符的频次，然后再根据t字符串的出现的字符去HashMap里面进行减法，最后遍历一下这个HashMap，如果有不是0的，就说明字母频次不一样，因此就不行

49. Group Anagrams. 这个题目首先是建立一个HashMap，key是String，value则是这个key对应的list；那么方法就是遍历给定数组中的字符串，对于每一个字符串都先进行内部字符排序，然后看看是不是存在与HashMap当中，如果存在的话，那么就添加到这个排好序的key对应的list内部，否则就先添加key和空的list；最后，这个HashMap的values就是要返回的结果

87. Scramble String. 这个题目其实是类似tree的string的recursion题目，和tree的那个来回反转很类似；base case就是，如果s1和s2本身就是equal的那么肯定是true；如果s1和s2不equal的话，至少也要保证s1和s2拥有同样数量的每一个字母（s1和s2长度已经相等），这样才能至少可以让s1可以通过各种变换变成s2，字母不想等的话怎么变都没用；接下来就要开始调用recursion进行反转比较了，这里的原理就是检查左边的左和右边的右、左边的右和右边的左，或者检查左边的左和右边的左、左边的右和右边的右，只要这两组有一组是没问题的，那么就可以通过了；当然具体来说，这个所谓的左边和右边不像tree那样那么好分割，所以必须手动进行分割，那么对于一个字符串来说，中间的每一个间隔都可以分割左半边和右半边，因此要对给定两个数组的长度进行循环（从index为1开始，方便进行左边右边的substring分割）；对于每一个i，首先比较左边的左和右边的右（也就是s1的左也就是s1.substring(0, i)和s2的右也就是s2.substring(s2.length() - i)）、左边的右和右边的左（也就是s1的右也就是s1.substring(i)和s2的左也就是s2.substring(0, s2.length() - i)）；这里要注意理解为什么这样分割substring，因为要保证传入到recursion的两个string的长度相同才可以，也就是说如果以i为分割的话，s1的左就是从0到i，s1的右就是i以后，而s2的左就是从0到s2.length() - i，s2的右就是s2.length() - i以后；这里注意，i只分割s1，并不分割s2，分割s2的是s2.length() - i，这样s2的左边才能等于s1的右边，s2的右边才能等于s1的左边；那么对于左边的左和右边的左、左边的右和右边的右这种情况就更好理解一些

2.27 做题

179. Largest Number. 这个题目是给定了一个数组，对于这个数组内部包含一些数字，要求对这个数组中的数字进行任意拼接，使得组成的结果是最大的；这里要注意数组本身包含的数字，可能是个位数也可能是十位、百位，因此不能用简单对数组从大到小排序再从头到尾拼接，比如10肯定比9大，但是109却又比910小；但是仍然要对数组进行拼接，只不过拼接的标准要进行变化，对于10和9这个例子，在这个题目中应该是9的优先级大于10，比较的原则就是"9" + "10" = "910" > "109" = "10" + "9"，因此这个逻辑就需要在Comparator中的compare方法中进行实现；首先把给定数组转化称String，然后进行Arrays.sort(s_num, comp)进行排序；comp的实现方法就是，对于两个字符串o1和o2，首先进行拼接为s1 = o1 + o2和s2 = o2 + o1，然后直接返回s1.compareTo(s2)即可；排序后进行拼接返回

6. ZigZag Conversion. 这个题目找规律就好了，首先是第一行，i从0开始往后，间隔是i += numRows * 2 - 2；然后是中间的这几行，每次append两个，一个是i + j，另一个是i + numRows * 2 - 2 - j，其中j是对中间的numRows - 2行的纵向遍历，而i则是横向遍历；最后是最后一行，从i + numRows - 1开始，仍然是numRows * 2 - 2的间隔；挨个完成拼接即可

367. Valid Perfect Square. 这个题目是给定一个数字，让判断是不是完全平方数；最基本的方法就是一个一个判断，1、2、3、... 、i这样看看什么时候i * i可以等于num；这种方法比较慢，因此更简单的办法就是用binary search，因为从1开始到num是顺序的，因此left从0开始而right从num开始，中间的mid定位以后，判别标准就是mid * mid是否等于num；如果存在mid满足条件则返回true，否则就是false；但是这里要注意，可能会存在精度不够的问题，所以mid应该使用long类型，因为mid和mid可能会overflow

2.28 做题

365. Water and Jug Problem. 这个题目要求的是，给定两个桶容量分别是x和y，问是否能够通过这x和y来somehow表示出z，这个z肯定只能由x和y来表示，因此可以确定z不能大于x和y之和；这里的思路就是这样，如果希望找到这样的z，那么肯定就可以表示成z = ax + by的形式，a和b则是系数，表示x和y应该进行某种组合才能表示成z；而想要满足这个z = ax + by的形式的话，就必须保证z是x和y的最大公约数GCD的倍数才可以；因此这个题目就变成了求x和y的最大公约数，然后再用z去对GCD取%看看是不是0，从而表示是不是GCD的倍数；求GCD的方法就是，当y不为0的时候，首先利用temp对y进行存储，然后用x % y去更新y，接下来再把x取temp存储的值；这样一步一步循环下来，当y为0的时候，x就是最大公约数了；以上这个GCD的过程一定要记住

204. Count Primes. 这个题目要求给定一个n，求所有比n小的Prime质数的个数；最简单的办法就是从2开始一个一个往大了找，对于每一个数都检查有没有除了1跟它自己以外的因子，如果没有的话就说明这个是Prime；但是这种方法过于麻烦，所以换一个思路；因为是从小到大进行检查，那么比如现在检查到了2，那么2是一个质数，因此就从2开始对所有的2的倍数都进行标记，说明这不是质数；标记完了以后才增大对3进行检查，发现3是一个质数，那么就从3开始对所有的3的倍数进行标记；完毕以后进行到4发现这已经标记过了（在2的时候），然后就进行对5的检查；这样从小到大进行检查，因为2、3显然都是质数，而对于小的质数的倍数检查完毕以后，到了后面的一个人数，如果它此前没被标记过的话，就说明它没有从2开始的任何一个数作为它的因子（因为没有被作为它们的倍数标记过）；这样就可以了

1. Two Sum. 这个题目的最基本思路就是，组建一个HashMap，key是value而value是index；对于数组中每一个位置的元素，都检查一下在HashMap当中有没有它的互补，如果有的话直接返回，如果没有的话，把value和index给put进HashMap当中，这样这一次的value就可能成为后面的某一个位置的元素的互补了

2.29 做题

167. Two Sum II - Input array is sorted. 这个题目是two sum的变种，在原有题目基础上添加了数组本身就是sorted的条件；既然是sorted的话，其实就可以使用双指针相向而行进行遍历；如果当前指针指向的两元素之和等于target则返回；如果大于target，那么右指针往左移从而能够下一次指向小的元素；如果小于target，那么左指针往右移

15. 3Sum. 这个题目是求三数之和为0的所有元素组合，要求不能重复；所以可以先进行排序，然后首先遍历一个i，接下来就是双指针相向而行和sorted array的two sum一样了；这里要注意，不可以重复，比如00000这种数组，最后的结果按照一般的做法肯定有很多个000的结果，但只要保留一个000即可；最直观的办法就是用一个hashset，没有技术含量；而另一个办法就是当确定了一组i和j和k以后，下一步应该是要进行j++和k--了，但是如果j的后面一个的元素和j的元素相同的话，那么仅仅j++是没有用的因为会产生重复，对k也是如此；因此这里就需要先进性检查，看看j后面的和k前面的是不是和j于k本身元素相同，如果不相同的话直接j++和k--即可，如果相同的话就先要进行一个循环，循环j++或k--，直到和后面一个元素不同，再进行本来要做的j++和k--；最后对于i也一样，对于当前的i如果它和它前面的i-1对应的元素相同，那么这次循环就不应该再进行下去

16. 3Sum Closest. 这个题目的要求就是，找到三个元素，使得这三个元素的组合在整个数组之内是对target最接近的；那么依然先进行排序，然后用i遍历、j和k双指针相向而行；对于每一组i、j、k都把他们的和于target比较，如果大于target就k左移、小于target就k右移；那么对于这个sum来说，要每次都和当前的res比较，是否距离target更近，如果更近就更新res

18. 4Sum. 这个题目就是在3 sum的基础上再套一层循环而已

231. Power of Two. 这个题目需要使用Bit，因为对于一个2的power来说，如果表示成bit的话，就是1000000，只有一个1后面都是0；而对于这种数来说，如果减去一个1的话，那就是0111111，只有一个0后面都是1；那么如果把这两个数进行&运算，那么就一定是0，因为对&来说，只有两个对应位置全是1结果才是1；因此，验证一个数是不是2的power就把这个数和它减1进行&运算，得到的结果是0就说明这是2的power

3.1 做题

129. Sum Root to Leaf Numbers. 这个题目的要求就是，给定一个binary tree从root到每一个leaf都算作一个path，那么对于这个path就需要从根到叶的拼接成一个数字，最后把每一个path所对应的数字进行相加即可；对于这种一头扎到底的情况，首先要考虑当前的节点是不是leaf，如果当前节点的左右子节点均为空，那么这就是一个leaf；对于leaf节点，就需要把当前path的已经积累的数字乘10并且加上当前节点的value，然后再把获取到的结果加到全局sum当中；而如果这个节点不是leaf节点的话，就意味着这个节点存在于某个path当中，当然也需要把当前path累计的数字乘10再加上这个节点value，但是因为不是leaf节点所以所属的path还没有加完所以就不会加到全局sum中；此外，对于一个非leaf节点，它至少有一个左子节点或右子节点，也就是说它可能会存在于两个path，因此就分别对左右子节点进行recursion（当然这里应该实现验证是否存在左右子节点再进行recursion call，或者把检查当前节点是否为空的判断放在每一个recursion开始时的base case里也可以）；最后要注意的是，每一次随着recursion function往下传递的应该是每一条path的和，而全局sum应该是一个全局变量，因为这是一个primitive types，就算随着recursion往下传递，最后加的值也不会反应到结果中的；如果pathSum往下传递而全局sum是全局变量的话，那么到了leaf以后pathSum就可以加到全局sum中保存起来

111. Minimum Depth of Binary Tree. 对于这一题可以采取与path sum相同的套路，很多tree类型的题目都是这种套路；要求min depth的话，实际上就是比较从root到每一个leaf的path所对应的深度哪一个是最小的，因此同样要维护一个全局min，而每个path的深度应该从recursion中往下传递；在recursion当中首先判断是否为leaf节点，也就是左右子节点均为空，如果是leaf节点的话，就意味着到底了，就可以统计这个path的深度，也就是把当前recursion中传递的深度加1，然后再把这个结果去和全局min进行比较更新；而如果当前节点不是leaf的话，就说明这个节点存在于path中间，当然也需要统计depth，只不过这个depth加1以后不能和全局min进行比较罢了；那么对于非leaf节点的recursion call来说，要去判断左右子节点哪一个是存在的或是否都存在，然后再对这个节点进行recursion

104. Maximum Depth of Binary Tree. 这个题目和min depth完全类似的，只不过变成了max depth；同样，再recursion中，对于所有节点都应该进行当前path depth的更新+1；然后判断当前节点是否为leaf，如果是leaf的话，那么对于当前path depth就应该和全局max进行比较；如果不是leaf的话，那么就call recursion对与左右子节点（如果存在的话）；recursion function除了要有当前节点之外，还应该有path depth往下传递，而全局max则是全局变量

110. Balanced Binary Tree. 对于这个题目来说，一般的做法就是对于每一个节点，首先调用recursion去判断它的左右两个子树是否都是balanced、只要有一个不是那么就返回false；而如果左右两个子树都是balanced的话，那么就需要分别获取到左右子树的高度，然后进行比较看看高度差是否不大于1，如果大于1的话同样返回false；只有当前root的左右子树高度差不大于1、同时左右子树本身也同样是balanced的话，这个tree才是balanced的；那么另一种好的办法就是，希望recursion tree每次网上返回的是一个数字，这个数字既能代表它的高度，也能表示它是不是一个balanced的tree；方法就是，在一个节点所属的recursion当中，如果这个节点为root的子树是balanced的话，那就给它的parent节点返回该子树的高度；如果这个节点为root的子树不是balanced的话，那就给它的parent节点返回-1或者任意一个负数；那么同样在recursion当中，对left和right进行recursion call的时候，如果获取到的两个子树的高度都是正数，那么再比较高度差是否不大于1进而判断当前节点的子树是否balanced；而一旦有一个子树高度为负数，就说明这个子树不是balanced，那么也不用求当前子树高度了，直接同样向上返回一个负数

124. Binary Tree Maximum Path Sum. 这个题目的思路，就是搞清楚到底要从左右子树获取到什么、到底要在当前层做什么、到底要向上返回什么；从左右子树获取到的，就应该是左右子树对应的最大分支sum；在当前层所需要做的，就是以这个节点为连接点连接左右子树对应的最大分支的一整条路径，算出来这一整条路径的sum并且和全剧最优进行比较；向上返回的，则是包括当前节点在内的、加上左右子树分支更大的那个组成的新分支

3.2 做题

2. Add Two Numbers. 这个题目需要利用dummy node；对于给定的两个l1和l2来说，都是倒序的数字，dummy和cur准备好；首先开始对l1和l2的同步循环，获取到当前节点的值并相加，然后维护一个prev负责进位，加起来以后对于当前位置上的数字保留个位数也就是对10取余即可，然后prev更新为十位数；接下来就是在cur后面新建一个node然后赋值，并且cur和l1和l2同时往后next；同步循环停止之后，肯定有一个l还是没有循环玩完的，那么继续循环即可；注意不要忘了最后的prev可能会保留

160. Intersection of Two Linked Lists. 这个题目要找两个list的相交点；由于两个list的长度可能不一样，那么就可以长度比较长的那个list先往后走，走到和短的list同样的长度后，两个同步往前走，看看有没有在一个位置两个节点是相同的，这种方法就需要事先获取到list的长度才行，否则不知道长的list什么时候停；另一种方法就是，设置两个遍历节点对两个list进行遍历，并且同时往后走；如果某一个遍历到头的话，那么下一步就换到另一个list的头节点上去；这样的好处在于，实际上两个遍历节点遍历的长度就统一了，无非是先遍历a和先遍历b的顺序区别而已；那么对于这种遍历模式，如果有交点的话，就一定会出现两个遍历节点相遇相同的情况，可以自己用手试一下

21. Merge Two Sorted Lists. 这个就用dummy node，谁小移谁即可；也就是dummy和cur准备好，如果l1的value比l2小，那么cur的next就指向l1，然后l1和cur同步next，反之就是l2；最后循环结束要记得吧剩下的l1和l2给接上

234. Palindrome Linked List. 找中点，然后reverse后半段，注意list的node个数的奇偶，如果是奇数的话slow应该继续next一下，然后就一个一个比较即可

143. Reorder List. 第一步找中点，第二步reverse，第三步重组list

3.3 做题

337. House Robber III. 这个题目的思路很直接，就是如果偷了当前的root的话，那么它的左右子节点肯定就不能偷了，因此只能从以左右子节点的左右子节点为root的子树进行继续讨论；如果不偷当前root的话，那么左右子节点肯定就可以偷了，因此就从这里进行讨论；因此对于前一种情况，首先获取到当前root的value，然后对于左子节点的左右子节点进行recursion然后获取结果后相加、对于右子节点进行recursion然后也获取结果后相加，这样全部value加到一起就相当于是这一种情况的可能的值；对于后一种情况，不偷当前root的话，那就直接对左右子节点分别recursion然后获取结果相加；这两种情况取最大向上返回

107. Binary Tree Level Order Traversal II. 这个题目就是最一般的BFS层级遍历tree，只不过这里需要倒序，那么就把每一次遍历的层都加到当前res的首位即可

17. Letter Combinations of a Phone Number. 这个题目是DFS题目，给定了一个表示数字的字符串，每个数字对应键盘上的数字，也就对应键盘上的每个数字的字母；因此recursion当中传入当前组成的String、传入index，然后base case是如果index达到了当前给定字符串的长度，那么就把当前组成的String传入res当中；recursion当中是对于当前index所对应的字符串中的数字、所对应的键盘上的所有字母进行遍历，每遍历一个就加到组成String中然后call recursion

93. Restore IP Addresses. 这个题目跟之前的很类似，就是给一个字符串，要在里面添加"."来组成valid的IP地址；方法就是在recursion当中，参数是结果List、当前剩余的给定字符串、已经组成的部分IP字符串、index；这里的index不是只字符串每一个字符的index，而是IP地址的4；那么recursion的base case就是，如果剩余的给定字符串为空并且index为4，就说明已经用全部给定字符串组成了一个valid的IP，因此就放到结果中；而如果这两个条件有且仅有一个满足的话，就说明组成失败了；那么在recursion内部的遍历当中，肯定是对当前剩余的给定字符串进行遍历的，对于当前剩余给定字符串来说，如果开头位置的字符是0的话，那么就只取一个0作为这个位置的IP的part，然后调用recursion；如果不是0的话，那么就往后取3个位置的数字（当然不是一定取3个位置的数字，而是i < 3这样进行循环，可以取1个2个3个都可以），然后看看取到的数字是不是小于等于255的，如果是的话就说明这是valid的IP的part；那么不管是不是0、不管取了多少位置的数字，取完以后都要作为一个IP的part存在，调用recursion的时候，首先传入的剩余给定字符串要把这里取到的数字给去掉，然后已经组成的IP字符串要加上刚刚取好的IP的part，index当然也要往后+1

282. Expression Add Operators. 这个题目暂时没懂，复习的时候再看看

3.4 做题

142. Linked List Cycle II. 这个题目的意思就是检测出环的起点；方法就是，首先用一个fast和slow指针进行遍历，当fast和slow相遇的时候证明有环存在，否则返回null即可；那么在fast和slow相遇之时，slow并不一定停在环的起点；这里其实有一个路程的关系，因为fast的速度是slow的两倍，因此fast和slow再相遇的时候肯定走的路程就是slow的两倍；又因为既然他们能够相遇，他们相遇的位置肯定是在环之内的，所以假设slow走的路程在环外为A，环内为B，那么slow一共走了A + B，而fast一共走了2A + 2B；又因为是fast在环内从后面追上slow的，因此fast比slow多走的距离就正好是环的长度，也就是A + B；因此，现在slow已经在环内走了B的距离，只要在走A就可以到环的起点，而A也是从头节点到环的起点的距离；所以此时从头节点出发再来一个指针，同速度和slow往前，相遇的地方就是环的起点

148. Sort List. 这个题目就是在链表数据结构上的merge sort；对于merge sort来说首先肯定需要找中点，然后分别调用recursion对前后部分的list进行merge sort，排序完毕以后merge这两个list即可；对于链表来说，这里涉及到的操作其实就是找中点，然后切断list形成前后两个独立的部分；分别对这两段进行recursion，获取到的sorted的两个list后就在进行merge操作就可以了

25. Reverse Nodes in k-Group. 这个题目在具体实现上还有一些不太明白的地方；思路是这样的，对于一个list来说，给定了k，就要找当前k group的最末尾的那个tail，然后大概就是这样prev -> ...... -> tail，prev后面开始到tail结束，这一段就是k group；定位到tail以后，就可以通过对prev和tail的一系列操作进行reverse了，也就是首先存储prev后面的节点temp，然后使得prev的next指向temp的next，而temp的next指向tail的next，最后tail的next指向temp；重复这个操作一直到prev的next指向tail的时候，就说明这个k group反转完毕了；接下来的操作就是，把prev定位到已经反转完毕的最末尾的位置，然后tail也可以顺便定位到那里；接下来重复以上所有的过程，知道在定位tail的过程中发现tail为空，这就意味着凑不齐k group了，那么后面的就不用管了

61. Rotate List. 方法就是定位，首先定位到list的末尾同时计算长度，然后利用k和长度找到中间应该切断的部分，最后接起来就可以了

350. Intersection of Two Arrays II. 使用HashMap对两个array进行遍历；第一次遍历记录元素和出现次数；第二次遍历看元素是否曾经出现并且看出现次数是否大于0，如果是的话就添加进结果，同时更新map中的统计

3.14 刷题

315. Count of Smaller Numbers After Self. 这个题目要求给定一个数组，希望对于数组中的每一个元素，都找出它右边所有比它还要小的元素个数，最终存储在一个结果数组里；那么这里的思路就是，对于该给定数组从右往左进行遍历，然后把遍历的结果存储在一个BST当中；对于一个元素，就应该插入到BST当中找到它应该存在的位置，而构建BST的过程就是找寻每一个元素右边更小元素的个数的过程；当遍历到一个元素的时候，就把这个元素放到BST当中，当沿着BST需要在某一个节点往左走的时候，就意味着这个正在遍历的元素比该节点所对应的元素更小，也就是意味着对于该节点所对应的元素来说，它在给定数组的左边出现了一个比它小的元素；这当然不是这一题目需要的结果（题目需要找到每一个元素右边更小的元素个数），但是仍然需要在该节点这里记录下来，也就是说每一个节点都要额外维护一个sum变量，以记录每一个节点的左子树的总节点个数；当沿着BST需要在某一个节点往右走的时候，就以为着这个正在遍历的元素比该节点所对应的元素更大，又因为这是从右往左遍历，也就是说当前正在遍历元素沿着BST经过的节点都代表着在给定数组中比位于该元素右边的节点，因此如果需要往右走的话，就意味着对于该元素来说发现了一个位于它右边且更小的元素；当然，这并不是说“仅仅”发现了一个元素，这是因为对于该节点来说，它自己本身的元素数值比当前正在遍历的元素小，那么它整整一个左子树上的节点所代表的元素，都应该比当前元素小，因此就应该加上这个左子树的总节点个数，也就是之前维护的sum变量，然后继续沿着BST走；另一方面，给定数组可能出现重复的元素，位置不确定，那么在BST中的每一个节点，就需要再额外维护一个dup变量，表示当前从右往左遍历过程中该节点所表示元素的重复次数，起始值为1，每次遇到同样的就加1；那么如果在对于一个元素沿着BST的过程中，遇到一个节点的数值跟它自己完全一样的话，除了dup加1以外，对于当前这个元素它右边更小的元素总个数，就应该是现在从BST根节点往下走的过程中已经加上的元素，再加上BST中当前节点的所有左子树总节点个数，这很好理解，因为当前节点的sum就代表着当前遍历过程中这个节点已经构建好的左子树总节点个数，也就代表着遍历到现在，在出现duplicate之间的这一部分构建到左子树的元素个数，比如24310436567这个，如果当前已经遍历到最左边的那个3的话，但是在BST中数值为3的节点是在遍历到最右边的那个3就构建了，那么这里的sum就代表着这两个3之间所有比3小的元素个数，当然要加起来；因此综上所述，从左往右遍历给定数组，对于某一个元素都去进行构建BST；如果在BST中需要往左走，那么对于当前BST节点的sum要+1，如果在BST中需要往右走，那么在recursion当中prefixSum需要加上当前BST节点的sum和dup；如果在BST中发现可以插入了，那么在最终结果数组中的对应位置上，放上迄今为止已经加好的prefixSum；如果在BST中发现有重复的元素节点，那么就把prefixSum加到结果数组中，还要额外把当前节点的sum也加进去，另外dup也要+1

300. Longest Increasing Subsequence. 这个题目让求给定数组的最长增长子序列，而不是subarray；这里的思路就是，从左到右遍历给定数组，并且在遍历的时候不断对当前遍历到的元素进行binary search，通过binary search去构建一个新的数组，最后新数组的长度就是最长增长子序列的长度；具体来说，对于当前遍历到的元素，把它放到新的dp当中去构建，如果当前dp数组的有效长度（或者已经构建的长度为len），那么这里binary search所要寻找的就是当前这个元素应该放到当前dp数组的哪一个位置；比如如果当前dp数组已经是2 5 8的话，而当前遍历到的元素是7，那么这个7就应该替换掉8使得当前dp变成2 5 7；但如果仍然是这个dp数组2 5 8，但是当前遍历到的元素是12，那么这个12就应该放到dp数组的后面变成2 5 8 12，也就是说dp数组的长度加1；而dp数组总是增长的是sorted的，因此对于每一个遍历到的当前元素，都可以用binary search的方法，寻找在dp数组当中是否有dp[i - 1] <= num < dp[i]，如果有的话就把dp[i]替换成num，如果没有的话说明num太大了，那么num就放到dp[i]的后面，因此dp的长度就会增加；总而言之，就是遍历给定数组，对于每一个元素都去dp数组中寻找自己的位置，如果找到了位置就更新，没找到位置就往后增加一位，dp数组的长度也就在这个过程中慢慢增长

354. Russian Doll Envelopes. 这个题目是给一个数组，数组里面都是二元组，表示套娃的宽和高，希望找到一个符合原有顺序套娃序列，可以一个一个套起来套得最多；这个题目的做法就是，首先把这些套娃按照宽升序排序，然后再按照高降序排序，最后利用LIS的那种方法，即从左到右遍历给定数组元素、在用binary search对给定数组元素到dp数组当中寻找合适的位置、找得到就替换找不到就往后放并更新length；这里的binary search是基于所有套娃的高进行search的，而添加进dp数组中当然也是这些套娃的高；这里的原因就是，按照宽生升序就解决了一个纬度的自增序列问题，而高降序则可以break ties，比如[3, 3]和[3, 4]可以变成自增序列而[3, 4]和[3, 3]不行，事实上[3, 3]作为套娃也是放不进[3, 4]的

36. Valid Sudoku. 这个题目就分别按行按列按box各自建立9个hashset，然后对于每一个遍历到的9 * 9的元素都放到对应的三个Set里面，如果有重复就说明不valid；注意box的定位方式是(i / 3) * 3 + j / 3，这个的意思是说，根据行来判断当前处于从编号0开始还是3开始还是6开始的box，而j / 3则是根据列来判断到底要从0或3或6的基础上增加多少个

37. Sudoku Solver. 这个题目就是对于每一个空的位置，都从1到9挨个尝试，如果某一个数字当前是valid，那么就暂时在board当中设置好这个数字，然后对更新后的board进行dfs检查，如果通过就返回true，否则就把当前位置归位空，继续尝试；如果对于这个位置从1到9都没办法，那么就说明无法sudoku，返回false，停止这一分枝的dfs；对于检查valid的helper，要从1到9分别对行、列、box进行检查，对于传入的row和col，找到box的方法就是首先都把(row / 3) * 3和(col / 3) * 3一下，从而定位到这个位置所在的box的左上顶点，然后对于行来说加上i / 3，对于列来说加上i % 3，从而定位到box的具体位置

3.17 刷题

127. Word Ladder. 这个题目的要求是，给定一个beginWord和endWord，然后再给一个wordList，看看能不能把beginWord每次都只变换一个字母，然后成为wordList中提供的word，这样一步一步变换下去之后最终可以变换成endWord，如果可以的话返回变换次数；这里采用BFS的思路，也就是对于beginWord来说，首先对它所有位置上的字符、全部都从a到z替换一次，这样实际上就是只符合题目要求的变换一个字母的全部情况；那么对于这些所有得到的word，去wordList当中查看是否存在，如果存在就说明beginWord可以通过某一个位置上的字符的某一种变换，生成一个存在于wordList的另一个新word；对于全部的新word，都放到一个集合当中，下一次循环的时候，就把这个集合的所有新word，都做一遍和beginWord相同的操作，如果仍然得到新word的话就再放到一个集合当中；那么以上过程实际上就是expand和generate的过程，也就是BFS的过程，每次生成新的集合之后，都需要增加一次计数，表示又多变换了一次；而如果在某一次循环的时候，发现新的word所组成的集合中，包含了endWord，就说明现在已经通过beginWord经过若干次变换成生了endWord，那么就返回计数；而如果在某一次循环后，发现新的集合是空的，这就说明上一次的word们经过全部的变换，都没有生成出wordList当中包含的word，这就意味着不再能够通过wordList提供的word去生成endWord，就返回0就可以了

51. N-Queens. 这个是N-Queen问题，意思是给一个n*n的棋盘，然后在每一行都放一个Queen，使得所有行都放一个放完以后，所有的Queen可以不互相伤害；首先要建立起一个n*n的char数组作为棋盘，然后对这个棋盘进行DFS；DFS的意思就是，每一次都对棋盘的当前行的所有位置进行检查，如果检查通过这个位置可以放一个Queen的话，那么就把char数组的这个位置设置成Q，然后调用recursion去设置下一行；就这样一路扎到底到棋盘的最后一行就相当于设置完毕了，但是每一次调用完recursion后，还需要把这个位置设置回空，这就是recursion tree每一分枝返回后的复原；而如果扎到底，也就是当前行数已经越界的话，就把当前已经构建好的棋盘放到结果当中；对于棋盘的当前行的所有位置进行检查的意思就是，遍历当前行的所有位置，对每一个位置都向上检查（因为这时只设置了上面，不和上面冲突就好），向上就是45度、90度、135度，具体来说就是找到当前点的左上方、正上方、右上方的那个点，然后往上一步一步循环检查是否这条线上有一个点已经是Q了就好；那么如果通过了检查，就进行DFS的过程，即设置Q、recursion、取消Q，对这一行的所有点都检查，因此这里的recursion tree的每个节点的分支数就是n；而要扎到底才能够加到结果中，因此recursion tree深度就是n；对于每一行的位置都要检查是否能够放置Q，如果不通过检查就过、通过检查就recursion，这就是剪枝；另外注意检查的过程中左上和右上的循环需要同时循环i和j

52. N-Queens II. 这个题目是给一个n，要求出来能够拼成的N-Queens问题的解法数量；那么仍然用DFS的方法，这里就不需要建立一个真的二维char棋盘了；DFS是对每一行都进行recursion，对于这一行进行遍历每一个位置，对于被遍历到的这个位置，现在可以确定的是recursion的当前行row，以及被遍历到的这一个位置也就是这一列col；那么就希望对于row col这个点，它的垂直方向、45度方向、135方向都没有Q存在（不需要检查水平方向，因为DFS是一行一行进行recursion的，每一行只会设置一个Q），但是现在又没有一个真的二维char数组作为棋盘，并不能向上对这三个方向进行遍历检查Q；但是另一方面，可以发现对于这个棋盘来说，一共有n个90度线（列）、2 * n个45度对角线、2 * n个135度对角线，那么对这些线来说，每一个只需要维护一个boolean的变量就可以了，这个boolean变量就表示这个线上已经有Q了，那么这条线上在其他行、也就是dfs进行到后面步骤时会遍历到的这条线上的点，就不能再设置为Q；这里采用的方法是，设置三个boolean数组，分别表示90度、45度、135度的线的boolean变量的集合，数组中每一个元素就代表着每一条具体的线；在dfs的过程中，对于每一个row和col，都去获取到它们所存在的45度线、90度线、135度线，也就是获取到它们对应这三个boolean数组中是哪一个变量；然后看看这些变量是否是true，如果有一个是true那么就说明当前行的这个点不能放Q，就continue；如果都不是true，那么就在当前行放Q，具体操作就是在三个boolean数组中的对应位置变量设置为true，然后recursion下一行，最后再回头设置这三个变量为false；base case当然就是，如果recursion的行数已经到了n，那么就说明到了棋盘底下，也就是说构建完毕了，那么count要+1；最后找到三个数组对应的变量的方法就是，对于当前的row和col，首先col本身就是代表了90度线的变量，而row + col则代表了135度线，row - col + n又代表了45度线，这就意味着，135度线上的横纵坐标之和总是相等，而45度线上的横纵坐标之差总是相等

126. Word Ladder II. 这个题目比较有意思，在原来Word Ladder题目的基础上开展的，要找出所有最短的路径的集合，而不仅仅是一个最短路径长度；总的来说就是利用BFS构建好一个graph图，然后再在这个graph的基础上进行DFS去找到所有的路径；BFS的过程就是构建graph的过程，希望通过BFS构建出一个graph，使得这个graph上包含了所有的最短路径，那么DFS只需要进行遍历图就可以了；具体来说，BFS应该从beginWord开始，对于beginWord当然就是对它所有位置的字符进行从a到z的尝试，这样二重循环下得到的newWord，就应该去给定的wordList当中进行判断，看看是否存在于wordList，如果存在的话就把newWord也offer到BFS的queue当中；但是要注意的是，这里需要找到的路径是最短路径，而一步一步从beginWord去生成存在于wordList当中的newWord，本身其实就是路径长度的增加，因此在BFS的过程中，需要时刻记录下来，当前的这被generate出来的newWord，或者不管是否能够生成newWord、只要某一个存在于Queue中的word将要开始expand的时候，都要检查一下这个word从beginWord到达的距离，是否已经大于当前的全局最短路径的值了，如果已经大于min，就没必要对这个word进行进一步的bfs了，直接continue即可；这里就出现了一个问题，既然需要比较当前准备被expand的word和全局的min比较，就要记录下来每一个word，从beginWord开始一步一步按照wordList中的字符串变换到这个word，所需要的次数（也就是距离），因此这里准备使用一个Map，这个Map其实就是在前一题中基于wordList建立的dict的加强版，叫做dictMap；这个dictMap的key仍然是提供的这些word，而value则是从beginWord到这些word的变换次数（也就是距离），每一次某个word需要被expand的时候，都要从dictMap中获取到当前beginWord到这个word的距离再加1，如果这个distance数值不大于min才能往下做，否则continue；现在回到一般的BFS过程，由于已经有了dictMap实时检查距离作为辅助，那么每当一个word从Queue中被拿出来、然后通过二重循环的变换得到存在于wordList的newWord的时候，都需要去dictMap当中获取这个newWord对应的value，也就是从beginWord到newWord的变化次数，然后和这个变换出来newWord的word所对应的value+1（也就是上面说的那个distance数值）比较，如果这个distance数值大于这个newWord已经存在于dictMap的数值，就说明这个newWord之前已经被更短的变化次数所生成了，因此就没有必要再进行下去了；而如果这个distance数值小于newWord对应dictMap中的数值，就说明可以用新的路径从beginWord去generate出来这个newWord，那么当然要更新dictMap的value，同时offer进BFS的Queue当中；而如果相等的话，就什么都不要做，因为这就是一个殊途同归的情况，从newWord后面的路径都一样但前面的不一样，所以也算是一条新路径，只不过dictMap不用更新了，同时也不需要offer进BFS的Queue中了，因为既然相等就说明当前dictMap中的value已经是beginWord到这个newWord的最小路径了，而既然最小的已经被更新到dictMap中同样也说明这个newWord在之前已经被offer到Queue当中了，那么自然Queue中就不需要出现两个同样的word；那么接下来，在确定当前被generate出来的newWord是已知从beginWord变换出了的最短的以后，就可以去构建graph了；这种graph很简单，key是String而value是一个List的String，这表示了某一个word可以通过哪些word只变换一次就变换出来它，也就是可以构建ladder的过程，每个word和word之间通过Map相连接，连接关系就是只变换一次；因此这里put进graph的key是newWord，而value就是一个List，需要把当前生成newWord的word放进去；在BFS的最后，还要考虑去更新全局min，因为有可能被生成的new_word

332. Reconstruct Itinerary. 这个题目和之前的word ladder有些类似；首先是构建graph，题目给的是一个list的list的string，也就相当于是一个二维数组，内部包含的就是一张张飞机票，第一个位置是出发第二个位置是到达；只给了这个二维数组其实没有用，关键是要把每一个出发地可以到达的地点给收集起来，就相当于group by一下，那么建立的graph图就是一个Map，key就是一点地点，而value则是一个list的地点，表示从key出发可以到达value的list当中的所有地点；那么这个题目既然要求按照字母顺序，那么value就是一个PriorityQueue就好了，这样能够最先把字母顺序最优的地点给拿出来；在构建完毕图之后，就可以对图进行DFS了；DFS的过程也很简单，就是给定一个出发地，然后去graph中获取这个出发地能够飞到的地点列表，也就是那个priorityQueue；获取到以后，对这个PriorityQueue进行遍历，其实就是让它不断地往外poll，最先poll出来的当然就是字母顺序最先的；poll出来以后获取到一个到达地，然后再调用DFS去把这个到达地作为起飞地进行同样的操作；那么再上面一切操作结束以后，再把departure给添加到res的最前面一个位置；这里要注意起飞地放到res的时机，不是在dfs一开始就放进去，而是说，每一次遍历完优先队列并且进行dfs完毕以后，再放进去；如果一个地点是终点，那么它在图中没有对应的优先队列，那就可以直接越过去放了，这样从后往前放去构建res