LeetCode刷题笔记（600-699）
LeetCode刷题笔记（600-699）
【605】种花问题
解题记录
顺序遍历代表花坛位置的数组，判断每个位置是否能够种花，要注意的是判断一个位置是否能种花使用的逻辑表达式需要化简，一开始我没有化简，代码写出来很臃肿也并不好理解，提交以后看了别人写的逻辑表达式感叹差距还是挺大的，好的逻辑表达式在别人读你的代码的时候都会让别人更轻松的知悉你的思路。
相关标签
数组
【606】根据二叉树创建字符串
解题记录
看见二叉树递归走起，这题递归的时候要注意如何处理不必要的空括号对，根据题意，右子树如果为空是一定省略括号对的，在右子树为空的前提下如果左子树也为空也省略括号对。
相关标签
树、字符串
【617】合并二叉树
解题记录
递归的合并两棵树的左子树和右子树，并将两棵树的根节点的值相加，如果一棵树为空就可以直接返回另一棵树。
相关标签
树
【628】三个数的最大乘积
解题记录
首先分析什么情况下会产生最大的乘积，直接选择最大的三个数相乘不一定是最大乘积，当最小的两个数都是负数，且乘积大于第二大和第三大数的乘积的时候，最大的数和最小的两个数的乘积才是最大乘积，比如这个数组：[3, 2, 1, -4, -5]，最大乘积是60而不是6。而最大的数不管是正数还是负数，都一定是组成最大乘积的三个数之一，如果最大的数是正数，只要数组长度超过4就一定可以选出两个正数或两个负数与之搭配形成最大乘积，如果最大的数是负数，说明所有数都是负数，这时候直接选择最小的两个负数组成最小的正数再与最大的数相乘就可以“负的最少”也就是最大了。分析完毕，也就是最大的乘积要么来自最大的三个数，要么来自最大的数和最小的两个数，我们只需要遍历数组找到最大的三个数和最小的三个数然后判断最大乘积的两种可能来源中谁的乘积大就能得出答案。
相关标签
数组、数学
【633】平方数之和
解题记录
判断一个数是否是两个平方数之和，首先构造第一个平方数之和，用这个数减去平方数之和，剩下的部分开方取整再平方如果没变，就说明这个数是平方数之和，否则构造下一个平方数之和继续测试。
相关标签
数学
【637】二叉树的层平均值
解题记录
有点类似于二叉树的广度优先遍历，也是使用一个队列存储还没有遍历到的二叉树节点，每遍历完一层队列中剩下的自然而然就是下一层的所有节点。一开始我没想到如何判断已经遍历完一层，因为要求层平均值就必须在遍历每层结束的时候进行计算。一开始我想到的是插入null节点，当读取到null节点的时候说明当前层遍历结束，这时候再在队列末尾插入一个null，就能将不同层的节点隔开。但其实每读取完一层的时候剩下的队列长度就是下一层节点的数量，只需要控制下一层读取此时的队列长度那么多的节点，读取够就进行平均数计算，并且重新计算队列长度就行。
相关标签
树
【643】子数组的最大平均数
解题记录
构造一个固定长度为k的窗口容纳k个元素，然后滑动这个窗口不断计算平均值更新最大平均数即可。
相关标签
数组
【645】错误的集合
解题记录
之前在【268】缺失数字这题中已经做过了如何寻找一个连续序列中缺失的数字，有两种方法都可以实现，我使用的依然还是等差数列法，这题除了寻找缺失的数字还要寻找重复的数字，寻找重复的元素可以用哈希表实现，或者在这题中由于是从1开始的连续数组，使用固定长度为n的数组也可以。
相关标签
哈希表、数学
【653】两数之和IV-输入BST
解题记录
一开始我使用的是用哈希表记录下二叉树中出现过的所有元素，然后判断是否存在两个key相加值为目标值，但是这么做没有利用BST的特征，对BST进行中序遍历可以得到有序的序列，判断有序序列是否有两数和为特定值可以使用类似于二分法的方法，两个指针指向有序序列的头和尾，判断指针所指元素之和的大小进而移动指针。
相关标签
树
【657】机器人能否返回原点
解题记录
遍历字符串根据字符进行坐标操作判断最后的坐标是否为(0,0)即可，或者统计每种字符出现的次数，两两相等也可以作为判断标准。
相关标签
字符串
【661】图片平滑器
解题记录
遍历数组求每个元素周围的平均值填充到新数组即可，主要的难点在于判断每个元素周围哪些元素有值。一开始我写了复杂的条件判断，还是遗漏了一些情况，很不理想。这题可以分类讨论，下面以一个3X3的方格继续讲解，这样的方格包括了所有情况的格子。
| (0,0) | (0,1) | (0,2) |
|---|---|---|
| (1,0) | (1,1) | (1,2) |
| (2,0) | (2,1) | (2,2) |
左上角有格子：x，y均不为0
正上方有格子：x不为0
右上角有格子：x不为0，y不为2，2与数组中子数组的长度有关，下面不再解释2的含义
正右方有格子：y不为2
右下角有格子：x，y均不为2
正下方有格子：x不为2
左下角有格子：x不为2，y不为0
正左方有格子：y不为0
有了这8个判断条件只需要写一组判断语句，符合条件的加上对应位置的格子，这样就可以清晰的将每个格子周围的元素不重不漏的相加在一起，最后求平均值很简单就不再说了。
相关标签
数组
【665】非递减数列
解题记录
首先搞明白什么情况下修改元素可以使数组非递减，再寻找数组中有多少处这样的情况即可。当一个非递减的数列出现了下降，有两种手段修改这种下降，我们将出现下降的地方的高点称为波峰，低点称为波谷。第一种是波谷提高到波峰的高度，第二种是将波峰的高度降低到波谷的高度。
观察一个数组，[0,1,4,2,5]，可以修改2为4（将波谷提高）或者修改4为2（将波峰降低）就能变成非递减数组。
再观察一个数组，[0,1,4,2,3]，此时仍然可以修改4为2达成目的，但是不再能修改2达成目的，因为低于波峰的元素不止有2，还有3，所以只能将波峰降低。
再观察一个数组，[0,3,4,2,5]，可以修改2为4，但是不能修改4，因为高于波谷的元素有3和4，波峰不能调整的比3还低。
最后观察一个数组，[0,3,4,2,3]，无法只调整一个元素实现目的。
我们可以整理出规律来，假设下降的元素为第i个元素，如果要修改波峰（形如第3个示例数组），也就是修改第i-1个元素，必须满足的条件就是第i个元素，也就是波谷，高于第i-2个元素。如果要修改波谷（形如第2个示例数组），需要满足第i+1个元素大于波峰。而第4个示例数组因为都不满足，所以无法修改。
知道了判断的规律，由于涉及了4个元素的比较，我们首先排除掉长度小于4的数组，长度大于4的数组中左右各掐掉一个元素从第二个元素开始判断直到倒数第二个元素。最后需要判断被掐掉的部分是否出现了下降，因为头尾处必定能只修改一个元素实现目的，所以很好判断，可以在一开始就进行判断。
相关标签
数组
【669】修剪二叉搜索树
解题记录
根节点大于右边界的树直接返回修剪后的左子树，根节点小于左边界的返回修剪后的右子树，如果根节点位于界限内直接递归的修剪左右子树即可。
相关标签
树
【671】二叉树中第二小的节点
解题记录
由于这颗二叉树的特殊性质，根节点一定是最小的节点，可以递归的比较所有子树，如果有某一棵树根节点值不等于整颗二叉树的根节点，也就是最小的那个节点，就将这个值记录下来，之后每次找到与根节点不相同的节点都进行比较，就能找到除了根节点以外最小的节点，也就是第二小的节点。
相关标签
树
【674】最长连续递增序列
解题记录
遍历数组，递增时令一个临时变量递增，停止递增时比较长度并清空临时变量即可。
相关标签
数组
【680】验证回文字符串II
解题记录
双指针指向字符数组的头和尾，如果发现两个指针指向的字符不一样，分三种情况，第一种，删除左指针指向的字符后可以成为回文字符串，第二种，删除右指针指向的字符可以成为回文串，第三种，删除哪一个都无法构成回文串。我们只需要判断第一种和第二种情况，当不一样的时候，另左指针右移一位，跳过这个不一样的字符继续比较，如果左右指针可以相撞说明删除左指针指向的那个字符可以构成回文串，同理可以判断另一侧的情况，两种情况只要有一种成立就可以返回true，否则返回false。
相关标签
字符串
【682】棒球比赛
解题记录
用栈保存每一步的得分，再对输入的字符串进行判断从而对得分进行相关操作即可。
相关标签
栈
【686】重复叠加字符串匹配
解题记录
首先判断组成两个字符串的字符集是否相同，也就是提前排除重复串中出现母串没有的字符的情况。排除之后确定母串需要叠加多少次才可能叠加出重复串，如果重复串长度正好是母串的倍数，那么母串要么叠加倍数次数（例如：abc与abcabc），要么叠加倍数次+1（abc与bcabca），如果重复串长度不是母串的整倍数，那么至少就要叠加倍数次+1（abc与abcabca），或者倍数次+2（abc与cabcabca）。所以判断这三种情况是否匹配即可。
相关标签
字符串
【687】最长同值路径
相关标签
这题据评论区说有中等或者困难的难度，我也确实没做出来看的解析······
二叉树的题目肯定也是递归求解，但是怎么递归是一个大问题，子树需要返回什么给父树？一棵树的最长同值路径与他的子树的最长同值路径有什么关系？解决这两个问题就能解决这个题。
如果根节点与左右子树根节点不同，那么这棵树的最长同值路径就是子树的最长同值路径。
如果根节点与左右子树根节点相同，并且子树的最长同值路径路过了根节点，就可以将子树的最长同值路径从根节点分为左右两部分，选长的部分与父树结合进行比较是否更长，更长则更新最长同值路径。
如何判断子树的最长同值路径路过了根节点呢？引入一个自己起名的概念，延伸长度，意思是父树可以向子树延伸多长。如果子树的根节点与父树根节点不相同，那么延伸长度显然是0，如果相同，延伸长度就是子树向子树的左右子树的延伸长度的最大值+1，只需要递归的求每棵树向其子树的延伸长度的最大值，再将最大值作为结果返回给父树，父树就知道向左和向右延伸分别可以延伸多长，也就是是否有路过父树根节点的同值路径。
而最长同值路径一定是路过某个根节点的，在递归求每个根节点的过程中，根节点的左右延伸长度之和就是路过该根节点的同值路径的最长值，记录下路过每个根节点的同值路径就能得到最大值，而根节点向它的父节点返回父节点在该方向上的延伸长度。
相关标签
树、递归
【690】员工的重要性
解题记录
一个员工的重要性和这个员工的直系下属都包含在员工对象的属性中，如果可以直接通过ID取到对应的员工对象，再使用队列保存员工的下属，每读取到一个下属就将该下属的下属插入队列，这题就很容易解决了。我们考虑使用哈希表保存员工ID和员工的关系，将员工ID作为key，对应的员工对象作为value，就可以用ID直接得到这名员工的所有属性。
相关标签
深度优先搜索、广度优先搜索、哈希表
【696】计数二进制子串
解题记录
设置两个变量记录0和1连续出现的次数，当1连续出现时每出现一个1可以与一个之前出现的连续的0组成一个符合要求的子串，所以遍历字符串每出现一个1就增加1出现的次数，减少0出现的次数，与此同时意味着子串的种类多了1种。
相关标签
字符串
【697】数组的度
解题记录
我们需要记下每个元素的出现次数、第一次出现的位置和最后一次出现的位置，然后再找出出现次数最多且第一次与最后一次出现间隔最小的元素。一般使用哈希表存储这种对应关系，将元素与一个元组作为key-value键值对存入哈希表，元组中存放我们需要的那三个数据。
相关标签
数组