刷题打卡

目标：4月份，SF，data scientist。
计划：2个月时间，熟练掌握easy到medium难度，200-300题。第一阶段，开始的20天，每天follow网络基础5题并总结，每种方法都要用Python和C++实现；第二阶段，按题型刷题并总结20天；第三阶段，根据面试刷面经。
阶段小目标：每天3小时能够完成算法计划。（注：题主coding算法基础较弱，所以一开始会花较多时间以保证完全掌握）
该帖子用来做每日打卡及总结，只包含算法题部分。

今天身体不适，没来及刷完题写总结，明天补上～

Day 2:

Q1. Array Partition I 【easy】
题目理解：1）输入：array of int。一共包含2n个元素
                2）输出：int。所有元素分成n组pair后，每组中最小数之的最大值
                3）n的范围：[1， 10000]，input数组中的元素范围为[-10000， 10000]
解决方法：1）根据数学层面分析，当原数组按大小排序后分组，可得到题目要求的最大值。也就是先排序，然后取index为偶数的元素直接求和，即得到答案。【Time：o(nlogn)】
                2）（C++）利用array。因为题目中给出了input元素的数值范围，所以我们可以直接初始化一个长度为2*10000+1=20001的数组，来记录每个元素出现的次数。这里我们利用数组的坐标将原来所有元素自然排序。在求和时，利用一个bool变量，每次操作后翻转，来决定那些元素需要求和。【Time：o(n)】

注：题主用Python和C++一起刷题，对于简单题目两种语言大多数只是体现在语法的不同l， 但是对于这道题而言，方法2）在python中的表现并不突出。

Q2. Range Sum Query – Immutable 【easy】
题目理解：1）输入：array of int 和若干（m）对[i，j]值（i、j为整数）
                2）输出：m个整数，分别对应每组[i，j]，表示原数组中从第i至j个元素的和
                3）（C++）题目中给出public和private两部分写代码，（python3）给出两个函数分别为初始化函数和计算i至j元素和的函数（SumRange）
                4）原数组不会改变，且有多对i、j值
解决方法：1）brute force：（python3）初始化原数组 ，之后在Sumrange中对每组i、j分别循环求和。（C++）在private中定义原数组，后在public中执行每次循环求和。 【Time：m*o(n)， Space： o(m)】
                2）引入一个额外的global/private 数组Sums，第k个元素用来储存原数组中前k个数之和。然后对每组i、j数对，若i=0，则直接返回Sums[j]，若i>0，则返回 Sums[j] – Sums[i-1]。 【Time：o(n)，Space：o(n)】

注：这道题的简单做法在于将原问题进行巧妙的转换，尤其是根据题目设定，可以了解到题目特点在于原数组不变，且对任意i、j，能够快速返回结果。

Q3: Student Attendance Record I 【easy】
题目理解：1）输入：String包含三种可能的字符：’A’代表Absent，‘L’代表Late，’P’代表Present
                2）输出：bool表示学生是否通过
                3）题目要求“多于1个A”或者“连续超过2个L”会不通过，其他情况则为通过
解决方法：1） 根据题目要求的不通过情况，对原字符串循环，直接数A的个数，以及连续的L的个数，任意一个条件满足直接返回False，若循环结束时还没返回，则返回True
                2）利用（python3）re.search/（C++）std::regex_search直接搜索即可。

Q4:  Base 7 【easy】
题目理解：1）输入：10进制整数
                2）输出：7进制下相应的表达，输出类型为string
解决方法：  数值转换时，直接做while循环，并不断模7，除以7取整。注意每次模7的结果要放在最前位。易错点在于一开始需要先判断原数的正负，用一个bool变量保存符号后，对元素取绝对值，一律用非负整数进行数值计算。最后，若原数为负，将“-”号添在最前面即可。

Q5: Island Perimeter 【easy】
题目理解：1）输入：矩阵（矩阵中仅包含0、1。1表示岛屿，0表示水）
                2）输出：整数（表示岛的周长，只有0，1交界处算作周长的一部分）
                3）岛屿连成一片，且内部不包含水。也就是说矩阵中的1都连成一片，且不会被0隔开
解决方法： 直接进行数学计算。每个方块有4条边，若岛屿面积为1，则周长为4。若两1相离，则相邻的边需要从周长中去掉，所以每个岛屿的贡献度-1。以此类推，我们可以通过数矩阵中1的个数，以及每个单位岛屿相邻的块的个数，即可通过4*area – neighbor得到周长。注意若a、b相邻，在计a的neighbor时为1，在计算b的neighbor时同样为1，也就是说neighbor总和为2（自然翻倍），不需要另外把neighbor数量乘二，也不需要去重。

Day 1:

Q1. Two Sum 【easy】
题目理解：1）输入：一组数列（int），目标sum值（int）
                2）输出：一对坐标（左大右小）。坐标在输入数组对应的两个数，加起来等于target
                3）输出结果存在且唯一，每个数仅可用一次。
解决方法：1）Brute Force：用两个循环遍历数组中任意两数的和，判断两数和是否等于target，等于时输出两坐标。 【Time：o(n^2)，Space：o(1)】
                2）hashtable：因为原数组中每个数只能用一回，但每个元素不一定只出现一次，所以可以将原数组写入hashtable，key = number，value = index。然后重新遍历，在遍历num的同时寻找（left = target - num）是否在hashtable里面，并保证两者不是同一坐标。若满足则返回num和left的坐标。整个过程两次遍历时间均为o(n)，所以这种方法【Time：o(n)，Space：o(n)】
其它想法：1）因为这道题需要返回原坐标，所以不能进行排序。若原题中input为升序或降序排列，可以使用双指针，那么只需对数组遍历一次。
                2）若原数组的元素均可重复使用或元素不重复，则可以不必对数组中所有元素便携式hashtable，可以边编写hashtable边找答案。

Q2. Robot Return to Origin 【easy】
题目理解：1）输入：string。包含U（up），D（down），L（left），R（right），每个字母可以出现任意次
                2）输出：bool

解决方法：1）hashtable：因为一共只有4种移动情况，所以可以直接对UDLR赋值，eg：UD为y坐标+1，-1，RL为x坐标+1，-1。最后判断x， y是否同时为0。
                2）对UDLR四种情况计数，最后判断UD的个数和LR的个数是否相等。与1）类似。
                3）对于C++可以使用switch，对UDLR四个case定义x，y轴的移动情况。最后判断是否回到原点。

Q3: Hamming Distance 【easy】
题目理解：1）输入：两个10进制整数x，y，范围为[0, 2^31）
                2）输出：int，两个输入值再次2进制下不同的位的个数。

解决方法：1）因为input上限为2^31, 所以可以直接进行循环，每次对x，y进行模2操作，然后/2取整。进行31次即可。
                2）直接对input的两个数进行“异或”操作，得到一个二进制数xor。计算xor中1的个数即可。可用While循环，以xor=0为跳出循环的条件，每次循环对xor进行模2，然后向右移位操作（或者/2取整）

其他资料：在做这道题时，需要了解的2进制相关知识。
& 按位“与”操作。特殊用法：指定位set 0）
| 按位 “或”操作 。特殊用法：指定位set 1）
^ “异或”（不同返回1，相同返回0）。特殊用法：指定位翻转
～“取反”操作
<< 向左移位操作（若首位不等于1时，二进制下的x2操作）
>> 向右移位操作（原数不为负时二进制下的/2取整操作）
“&=，|=，>>=，<<=， ^=”类似于平时用的+=操作，只是将+的功能改为“&，|，>>，<<，^”

Q4: Assign Cookies 【easy】
题目理解：1）输入：2个数组g，s，g中每个int分别表示每个小盆友的贪心值，s中每个int分别表示每个饼干所能满足的贪心值。
                2）输出：整数。表示这些饼干最多能够满足的小朋友的人数
                3）每个小朋友至多分一个饼干

解决方法：  将s，g分别排序。如果第i个饼干可以满足第j个小朋友，那么饼干i以后的所有饼干都可以满足这个小朋友，且饼干i可以满足j之前的所有小朋友。所以可以利用双指针，遍历饼干数组和贪心数组，其中任何一个数组遍历完后即可得到答案。（开始的排序Time：o(nlogn)，之后的遍历Time：o(n)，所以总体时间复杂度o(nlogn)。）

Q5: Sum of Left Leaves 【easy】
题目理解：1）输入：TreeNode* root
                2）输出：整个二叉树所有左叶子的和
                3）左叶子的定义：属于自己所在最小二叉树的左支，且其左右节点均为Null。

解决方法：递归方法。先考虑边界情况，定义左叶子，之后对于当前root下的子二叉树重复调用函数。

其他：感觉二叉树问题的corner case比较容易遗漏，之后做到其他相关题目再做进一步补充。

Q6: Reshape the Matrix
题目理解：1）输入：原始矩阵，r，c。（r、c分别代表想要重组的矩阵的行、列数）
                2）输出：如果reshape可以实现则返回重组后的矩阵；若却无法实现，则返回原矩阵。

解决方法：根据vectorization的概念，可以按照题目中样例reshape的方式，将矩阵中所有元素编号，使得二维矩阵变成一维向量。之后问题的关键在于新旧矩阵中每个元素坐标的表示。 一开始还是要先考虑特殊case（例如原矩阵为空等），防止坐标溢出。由于题目输出存在两种情况，第二种其实是新旧矩阵的元素数不同时要做的操作，判断不同后无需进一步计算。若可以进行reshape操作，可以对原矩阵安元素遍历，并定义好新旧坐标并赋值即可。

Day 3:

Q1. Average of Levels in Binary Tree 【easy】
题目理解：1）输入：非空二叉树
                2）输出：vector of double，表示二叉树从根结点开始向下，每一层所有节点的元素平均值。

解决方法：1）BFS宽度有限搜索：创建两个空的向量分别表示当前遍历层的节点集curr，和下一层需要遍历的节点集next。因为我们需要不断循环更新这两个集合，所以在最开始的curr中插入root节点作为初始情况，用curr不为空作为while循环进行的条件，对每个curr中的所有节点进行遍历（for node：curr），求sum，并在遍历时将每个node的左右节点均传入next中，每次遍历完当前层时，可以计算出均值sum/n（传入答案数组中），且得到下一层需要遍历的所有节点，将next传入curr，并将next清空，继续进行下一次循环，直至curr为空，得到最终答案。
                2） DFS深度优先搜索：先遍历整棵树得到完整信息再求解，整个过程利用递归的思想。创建两个数组分别记录每一层的节点和信息以及节点个数信息（因为这两个信息成对，所以C++中可以直接创建一个两维数组vector<pair<long long, int>>实现）。在private函数中进行先序遍历（个人习惯，中、后序遍历应该都行），记录下每个节点所在深度，元素和以及节点个数，并在public中调用，最后循环我们创建的数组，集中求平均值得到答案。

方法比较：1）这两种方法都是二叉树问题较为常见的经典方法
                2）从这道题而言，我个人比较喜欢BFS，因为整个过程比较直接，较为容易理解和掌握，且在有些逐层进行的查找等不需要遍历整个二叉树的问题中，或许BFS能够较快得到答案，没有多余的操作，且代码的可读性较强。
                3）相应地，利用递归想法的DFS可以将整个code变得更简介美观。
                4）个人对递归的掌握还不够好，希望能通过不断的练习慢慢提高。

Q2. Maximum Product of Three Numbers 【easy】
题目理解：1）输入：array of int
                2）输出：int
                3）题目要求从输入数组中选出的三个数，使得他们的乘积最大，并输出
                4）原数组长度范围[3, 10000]，所有原数组中的整数范围[-1000, 1000]
                5）原数组中可能出现负数、正数和0，所以需要考虑负负得正的情况

解决方法：1）先对原数组排序，并在“最大的三个数之积”和“最小的两个数与最大数之积”中输出较大的结果。【Time：o(nlogn)】
                2） 对原数组进行遍历，手工定义最大的三个数和最小的两个数个数。初始化最大的前三个数为-1000，最小的两个数为1000。分别考虑每个大于最大前三个数的情况和小于最小的两个数的情况，在遍历的过程中不断更新这五个数，最终输出“最大的三个数之积”和“最小的两个数与最大数之积”中输出较大的结果【Time：o(n)】

Q3: Merge Two Binary Trees 【easy】
题目理解：1）输入：两个二叉树跟节点的指针（t1，t2）
                2）输出：一个二叉树
                3）要求输出的二叉树中，每个元素为原来两二叉树对应元素之和

解决方法：递归：先对input为空的情况做好保护措施（t1为空时返回t2，t2为空时返回t1）。接下来把t2指针对应节点的值加在t1指向的节点值上，并对t1的左右节点做相同的操作（递归）。最后直接返回t1即可。

Q4: Sum of Square Numbers 【easy】
题目理解：1）输入：整数c
                2）输出：bool结果
                3）判断给定的整数是否为两个整数的平方和

解决方法：  这是一道比较简单直接的数学问题，需要从0开始循环不断尝试至n，我们需要将n最小化，否则可能会超时。假设我们循环的元素为a，n的最大值为sqrt(c)，因为最极端的情况为c = n^2 + 0^2。每次循环中不断计算b = sqrt(c – a^2)，并判断c是否得等于a、b的平方和即可。若相等返回true，若循环结束仍未返回，就返回false。


Q5: Construct String from Binary Tree 【easy】
题目理解：1）输入：二叉树
                2）输出：string，用来表示题目给出的二叉树
                3）每个节点（除了根节点）值都用（）包裹（null空节点直接用（）表示）；子节点包含在相应小根节点的（）内；若一个节点没有左右节点，则可以省略两个空节点（）；若节点只有左节点没有右节点，则右节点可以省略；所有二叉树可以得到唯一的表示
                4）不必要的（）必须省略

解决方法：递归：先考虑边界情况（跟节点为空时单独考虑）。对于一个单独节点t，分别计算t、t的左、右节点对应的string表达（递归调用解函数）。求完后根据题目中给出的（）省略条件，分别返回相应的结果即可。

其他：通过二叉树的练习，对于递归有了更进一步了理解和掌握，在之后的练习中希望能够继续熟练递归、递推思想的掌握和应用。

Day 4:

Q1. Linked List Circle 【easy】
题目理解：1）输入：ListNode* head。题目给定一个链表的起始指针。
                2）输出：bool。表示给定链表中是否存在环。
                3）对于链表而言，每个node的信息包含node本身的value，以及node所指向的next node的地址

解决方法：1）hashmap：初始化一个空的hashmap来表示已经访问过的节点。利用while循环，从head开始遍历列表，并将未访问过的节点插入hashmap，直到出现重复节点（返回true），或者遍历完所有节点都未出现重复（返回false）。（注意特殊情况，在程序最开始做好保护措施。）
                2）快慢指针：自定义两个指针，快指针每次走两步，慢指针每次走一步，若没有环，则快慢指针直接距离越来愈远，两者同时对应的节点不可能相同，整个过程在快指针遍历完全部列表时结束，输出false。若存在环，则快慢指针在执行next操作时永远不可能到达链表尽头，当快慢指针同时进入环后，进行追及运动，快指针一定会重新追上慢指针，过程在快慢指针相遇时结束，输出true。

Q2. Climbing Stairs 【easy】
题目理解：1）输入：整数n，表示需要攀登的台阶总数量
                2）输出：整数，表示一共有几种方式完成攀登
                3）攀登策略：要求每次只能攀登1阶或者2阶

解决方法：1）递推：根据台阶的攀登策略要求，可以知道在完成最后一次攀登时可以攀登1或2阶，当n>1时有：f(n) = f(n-1) + f(n-2)，而对于n = 0，1均各只有一种，说明整个过程为斐波那契数列。所以除了n = 0、1时需单独列出，其他情况可以通过逐步计算斐波那契数列的每一项直至第n项得到答案。
                2）递归：从1）中我们知道这道题存在一个传递关系f(n) = f(n-1) + f(n-2)，所以和递推相应的，我们也可以反过来考虑递归实现。相当于通过传递关系直接多次调用答案函数。可能存在的问题：递归时因为是层层嵌套可能时间较长，所以我们需要对递归进行优化。可以利用一些多余的空间对已经计算过的结果进行记忆化储存，以此来节省递归时间。

优化：整个过程为斐波那契数列，但是我们每次进行下一步计算时仅需要前面两次的结果即可，并不需要将所有非波那契数列元素都记录和储存。因此我们只需记录当前值，前面一次，以及前面两次的结果。这样的改进可以在有效的利用空间，在时间允许范围内，对更大范围的input进行计算。

Q3: Maximum Subarray 【easy】
题目理解：1）输入：array of int。原数组为nums
                2）输出：整数，表示元素和 （数列拥有的所有连续子序列中，元素和的最大值）

解决方法：将原问题进行一定的转换。我们引入一个新的空数组Sums，记录以第i个元素结尾的连续子序列和的最大值，并分别存入相应位置，新数组填写完毕后，找到最大元素即可。具体操作：首先进行初始化，以第一个元素结尾的只能是自身，所以Sums[0] = nums[0]，从第一位元素开始，若Sums[i-1] < 0，Sums[i] = nums[i]，否则Sums[i] = Sums[i-1] + nums[i]

Q4: Same Tree 【easy】
题目理解：1）输入：两个二叉树的根节点
                2）输出：bool结果
                3）判断给定的两个二叉树是否相同。相同条件为结构相同且每个相应节点有着同样的值

解决方法：递归：首先设置保护条件，讨论两个跟节点是否为空的情况。之后判断根节点值是否相同，若不同直接返回false；若相同，进一步对两根的左右节点调用判定函数进行递归即可。

Q5: Balanced Binary Tree 【easy】
题目理解：1）输入：二叉树跟节点
2）输出：bool结果，判断输入的二叉树是否为平衡二叉树
3）每个节点或者没有子节点，或者左右节点都不为空
4）平衡二叉树满足条件：左、右子树均为平衡二叉树；左右子树的高度差小于等于1

解决方法：1）递归1：在private中自定义二叉树的高度函数int height(TreeNode* root) ，并在public中对左右子树都调用来计算高度。将（两个高度差的绝对值）&&递归调用原函数实现左右子树是否平衡的判断，来实现。整个过程相当于存在两个不同的递归过程：一个是在计算左右子树高度，另一个是返回时判断左右子树是否平衡

                2）递归2:为了对1）进行改进，我们在private中添加一个balanced指针变量作为输入，int height(TreeNode* root,  bool* balanced)，这样我们就可以在private中，在计算左右子树高度的同时，直接判断两者之间的高度差。只有一次递归操作，在public 中，初始化一个bool变量Balanced后，只需直接调用height 函数，传入Balanced相应指针作为输入即可。

相关内容：指针a的指向的value为 *a，变量b所在的地址（指针）可以表示为&b。

总结：今天的练习接触到了一些简单的动态规划，并用到了多次递归思想。整体而言递归操作会使我们的代码更加简洁明了（尤其是在二叉树相关问题上的应用，我觉得非常广泛广泛。虽然递归思想非常巧妙，但也会存在运行时间长的问题。此外，通过今天的练习，我对于指针有的一些比较初步的了解，希望以后可以掌握得更好。加油！再接再厉！

Day 5:

Q1. Merge Two Sorted Array 【easy】
题目理解：1）输入：两个排好序的Linked list
                2）输出：一个链表，表示将两个输入的链表安从大到小的顺序合并。

解决方法：1）分别遍历两个列表中的每一个元素，逐一比较大小。
                2）递归 ：同样先建立保护程序，之后利用递归思想，将两列表开头较小的元素单独取出后，在对剩下的列表调用原函数求解。

Q2. Second Minimum Node in a Binary Tree 【easy】
题目理解：1）输入：二叉树（root）
                2）输出：整数，表示输入的二叉树中第二次小的元素值。
                3）给定的二叉树特点：每个节点要么没有子节点，要么同时拥有左右节点；若根节点有两个节点，那么这个根节点元素值等于两子节点中的较小值（根节点元素值小于等于子节点元素值）

解决方法：1）BFS：对原二叉树进行逐层搜索 。将整棵树的根节点设置为最小值，之后不断逐层遍历节点，寻找并更新第二小的节点值。操作进行到某个大于原根节点值时，其子树无需进一步计算，可以一定程度上简化计算时间。
                2） DFS：定义一个private函数来寻找二叉树中的最小元素值，在public中对原跟节点的左右子树分别进行最小元素递归计算，最后返回二者中的较小值。需要遍历整棵二叉树，但是整体代码十分简洁。

其他：在这道题中，第一次接触到deque结构及其相关操作，包括访问、添加、删除等。

Q3: Trim a Binary Search Tree【easy】669？？？？？？？？？？？
题目理解：1）输入：二叉搜索树（root），两个整数L、R，且L <= R
2）输出：简化过的二叉搜索树（root），满足新的二叉树中所有元素范围为[L, R]
                3）二叉搜索树特点：左子树的所有节点值都小于等于跟节点值，跟节点值小于右子树的所有节点值

解决方法：递归：根据二叉搜索树的特点可以将问题分成三大类，（1）根节点值小于L，此时跟节点和左子树跟节点需要被同时裁减掉，因此原问题变为对右子树进行裁剪；（2）跟节点值大于R，此时跟情况（1）类似，跟节点和右子树需要被扔掉，只需对左子树进行裁剪；（3）当跟节点值在[L, R]区间内时，需要分别对左子树、右子树进行裁剪操作次。最后返回root即可      

Q4: Count Primes 【easy】
题目理解：1）输入：整数n
                2）输出：整数，表示小于n的正整数中质数的个数

解决方法：  直接遍历从2到n的所有元素，将其中的各个质数的倍数（>=2）减去，剩下的就是质数的数量。具体来讲就是，一开始我们先初始化一个长度为n的数组f，所有元素值为1，且第0、1位元素置0，之后开始循环。我们知道2是质数，那么我们将f中坐标为2的倍数（>=2）的值置0，对每个等于0的位置的值跳过，非0位进行同样的倍数位置0操作，直到遍历完f中的所有坐标。最后只需对f的所有元素求和即可（因为只有质数位的值等于1）

Q5: Missing Number 【easy】
题目理解：1）输入：array of int，包含0～n中的n个整数（不重复，未排序）
                2）输出：整数，表示0～n中被遗漏的整数

解决方法：1）直接进行数学计算。因为已知所有元素范围为0～n，每个数都不重复，有且仅有一个数遗漏，我们可以用等差数列求和先求出0～n这n+1个数的和，然后将原数组中的元素逐一减去，减剩下的结果直接输出即可。

                2）利用“异或”位运算。异或的性质：A^0 = A，A^X^X = A。就是说任何数异或0仍为本身；任何数异或同一个数两次，效果抵消，结果仍为本身。输入数组的元素范围0～n，数组长度为n。所以初始化X = 0，之后不断循环异或原数组nums中的所有元素，并异或1～n，最后会有一个数仅异或一次，直接返回即可。

方法比较：个人认为第一种方法更加直接，代码简单，且容易理解。第二种方法虽然比较fancy，但是讲解和理解起来都较为繁琐。

总结：今天第一次在3h内完成任务，mark一下hh！继续努力！

Day 6:

Q1. Longest Continuous Increasing Subsequence 【easy】
题目理解：1）输入：array of int，未排序
                2）输出：int，表示原数组的最长、连续、递增序列的长度

解决方法：类似于之前Day 4 - Q3 Maximum Subarray，将为题做一个简单的转换，计算以每个元素为结尾的最长连续子序列的长度。那么在对原数组nums遍历时，初始值可设定为1（因为若前面元素比该元素小，那么我们要中的子序列仅包含它本身）。为了节省额外空间，我们仅使用ans记录结果，并根据每次访问数组元素时的curr值对ans进行更新。第i个元素对应的最长子序列长度传递关系为：若nums[i]>nums[i-1]，curr++；否则，将 curr重置为1。并在for循环每一步更新ans = max(ans, curr)。最后返回ans即可。

Q2. Valid Palindrome II 【easy】
题目理解：1）输入：非空字符串s
                2）输出：bool结果，判断给定字符串是否符合题目要求
                3）题目要求：原字符串s可以通过至多删掉一个字符变成回文字符串
                4）回文字符串：字符串s在正、反方向访问时得到的结果相同。Eg：aba；abba等

解决方法：利用辅助函数isPalindrome(s, l, r)判断字符串s的第i位到第j位字符之间是否为回文字符串。我们通过双指针同时访问原字符串的最左、最右节点，对每一对字符判断，并不断向中间移位。因为题目中允许最多删掉一个字符，所以在遇到s[l] != s[r]时，要判断删掉s[l]或者s[r]时，剩下的元素是否对应相同。因此可以调用辅助函数，判断isPalindrome(s, l+1, r) 或isPalindrome(s, l, r-1)。最后以l<r作为while循环结束条件。具体代码（C++）为：

class Solution {
public:
    bool validPalindrome(string s) {
        int l = 0;
        int r = s.size() - 1;
        while(l<r){
            if(s[l] != s[r])
                return isPalindrome(s, l+1,r) || isPalindrome(s,l, r-1);
            else {
                l++;
                r--;
            }
        }
        return true;
    }
private:
    bool isPalindrome(string s, int l, int r) {
        while(l<r) {
            if (s[l] != s[r]) return false;
            else{
                l++;
                r--;
            }
        }
        return true;
    }
};

Q3: Longest Palindrome【easy】
题目理解：1）输入：字符串s，包含大小写字母
                2）输出： 整数，表示原字符串中的元素能够通过重组得到的最长回文字符串串的长度
                3）大小写字母表示不同字符，比如：“Aa”不能作为回文字符串
                4）s的长度不超过1010（不知道这个条件有什么用，欢迎感兴趣的小伙伴解答指导）

解决方法： 首先题目中未限定s不为空，所以需要将空字符串输入考虑进去。由于题目可以对元素位置进行重组，因此我们只需要考虑元素个数，只需将可以凑成对的元素取出即可。且题目中说明原字符串仅包含大写和小写字母，所以我们可以直接初始化一个长度为128的数组freqs，遍历原字符串s并记录每个字母出现的次数（直接存在字母对应的ASCII码位）。之后对freqs中的每个元素遍历，若为偶数直接加到结果中；若为奇数则取比之小的最大偶数加到结果中。在所有成对结果取出后，可最多再加入一个落单的元素，所以整个过程中若出现奇数，最后结果需再+1。

Q4: Baseball Game 【easy】
题目理解：1）输入：一组字符vector<string>，其中每个元素记录棒球比赛该局的得分情况。仅包含4种结果：（1）整数：直接表示本局得分值；（2）“+”：表示本局得分为前两局得分之和；（3）“D”：表示本局得分为前一局得分翻倍；（4）“C”表示上一次有效得分取消。
                2）输出：整数，表示整场比赛最终得分

解决方法： 自定义一个整数数组纪录每一局的有效得分，在遍历完所以输入字符串后，将自定义数组中的所有得分数求和即可。

Q5: Employee Importance 【easy】
题目理解：1）输入：公司的所有员工信息，和一个员工的id（整数）
                2）输出： 整数，表示输入id对应的总重要性
                3）每个员工的信息包括：（1）独一无二的id；（2）个人的重要性值；（3）他的手下的id列表
                4）所要求的某id的总重要性为“自己的个人重要性”+“他所有手下的重要性”+“所有手下的手下的重要性”+…
                5）每个员工至多有一个领导

解决方法：1）DFS：自定义一个dfs函数，用于计算每个id的手下所有id的重要性之和。在函数中对输入的id对应的每个手下循环并调用dfs，完成递归计算。
                2）BFS：利用queue逐层遍历输入id下的每一层手下，手下的手下，…，直到所有分支都被遍历完得到答案。

其他：这道题的整体思想和之前做过的二叉树类似，BFS，DFS的解法都和之前类似，唯一的区别在于输入的员工信息的数据结构，整体就像一个树林，不一定只有一个初始根节点，且每个节点可能存在多个分支，这也导致的在变成过程中的语法上的一些不同。

Day 7:

Q1. Longest Univalue Path 【easy】
题目理解：1）输入：二叉树（root）
                2）输出：整数，表示在二叉树中值相同的节点能连起来的最长边数
                3）最长边不一定要穿过根节点root
       
解决方法：递归。先建立辅助函数univaluePath(TreeNode* croot, int* ans)计算通过根节点且只通过根节点的某一个分支的最长边数。在辅助函数中利用递归计算给定root的左分支最大变长l和右分支最大长度r，并对左右节点值和根节点值进行比较，若root->val =root->left->val，则根节点向左延伸最大长度为pl = l+1， 根据对称性，若root->val =root->right->val， pr = r + 1，若左、右节点和root值都相等，这条最长边长度为pl + pr，用*ans = max(*ans, pl + pr)对结果进行更新。

Q2. Diameter of Binary Tree 【easy】
题目理解：1）输入：二叉树
                2）输出：整数，表示二叉树的直径
                3）二叉树的直径：二叉树中任意两点之间边长的最大值

解决方法：递归。这道题跟上一题很类似，同样借助辅助函数LP(TreeNode* root)，计算从给定根节点为起点向下延展的最大长度。分别计算节点root的左右子节点向下的最长长度l、r，那么通过这个节点的最长直径就是l+r，之后我们以同样的方式来对结果进行更新：ans = max(ans, pl + pr)

Q3: Majority Element 【easy】
题目理解：1）输入：一个整数数组nums，长度为n
                2）输出： 整数，若majority element存在，则数组该数的值，否则输出-1
                3）majority element：表示在原数组中出现超过n/2次，

解决方法：1）hashtable。对原数组建立一个哈希表来记录每个元素出现的次数，并遍历哈希表，若存在一个元素出现次数大于n/2，就返回这个元素值，否则返回-1
                2）先设定ans并不断更新。for循环直接遍历数组，一开始初始化ans = nums[0]，并初始化一个计数器count = 1，之后每次循环中，若nums[i]等于ans，计数器+1，反之，计数器-1。当计数器清零，更新ans，因为题目设定majority element有大于n/2个，所以只有在ans=majority element时，不会被重置。

Q4: Find Pivot Index 【easy】
题目理解：1）输入：整数数组nums
                2）输出：整数（index 或者 -1），表示第0到index-1位元素之和等于从第index+1到最后一位的所有元素和相同。如果不存在满足条件的index，返回-1
                3）若存在多个这样功能的index，返回值最小的一个（最左边的）

解决方法： Brute Force。这道题目是一个很直接的数学计算问题，我们用for循环之间遍历原数组，因为每次坐标移位至i时，在不越界的情况下左边元素和需要加上nums[i-1]，而右边元素需要减去nums[i+1]。若中间任何时候出现左、右和相同情况，直接返回相应index即可。若循环结束仍为返回，返回-1

Q5: Longest Word in Dictionary 【easy】
题目理解：1）输入：字符串列表words
                2）输出： 一个字符串，表示满足条件的最长字符串
                3）条件：这个单词从第一个字符开始“每次在最后增加一个字符”的全部组成过程都在words中出现。 若两个同样长度的单词都满足，那么输出相应ASCII最小的字符串。
                4）例如：words = [“w”, “wo”, “wor”, “worl”, “world”]，输出“world”；words = [“a”, “app”, “appl”, “apple”, “apply”]，输出“apple”

解决方法： Brute Force 结合hashtable。先将原列表写入哈希表（之后用于判断元素是否存在），初始化一个空的best字符串用于存放结果，之后直接遍历words中的单词，并在循环进行过程中不断更新best。因此，在每次循环开始时先进行一次剪枝，将所有“长度小于best”或者“长度和best相同但ASCII大于best”的单词排除。之后引入一个空prefix用于纪录当前循环中的单词的每一位增加的过程，进入当前word的循环。对当前word，prefix每添加一个字符都在hashtable中进行查找，若某一步不存在，则跳出对当前单词循环，继续在words中的循环；如果prefix更新后长度超过best，或者长度相同ASCII更小，则将best更新为prefix。两重循环都完成后，返回best即可。

注：因为包含两重循环，所以讲起来稍微有点拗口，具体代码如下：

class Solution {
public:
    string longestWord(vector<string>& words) {
        string best;
        unordered_set<string>dict(words.begin(),words.end());
        for(auto word:words){
            if((word.length() < best.length()) ||
               (word.length() == best.length() && word > best))
                continue;
            string prefix;
            //bool valid = true;
            for(int i=0;i<word.length();i++){
                prefix+=word[i];
                if (!dict.count(prefix)) break;
                if ((prefix.length()>best.length()) || (prefix.length() == best.length() && prefix<best))
                    best = prefix;
            }
        }
        return best;
    }
};

一星期咯

Day 8:

Q1. Self Dividing Numbers 【easy】
题目理解：1）输入：两个整数left、right，表示上下限
                2）输出：整数，表示从left到right之间的数所有满足“Self Dividing”的个数
                3）其中1 <= left <= right <= 10000
                4）Self Dividing：该整数的每一位数字（1～9），都能整除这个整数，（不能包含0）
       
解决方法： Brute Force。遍历从left到right的每个整数num，并对每个整数进行模自己的每一位数字的操作进行while循环：每次令curr = num，a = curr%10 若curr%a != 0 跳出while循环，之后每次curr/=10，如果最后直到curr=0都没有跳出，ans+=1，之后对下一个num操作。

注：最开始也考虑过对每一个能整除的1～9的整数分别判断，但是实现起来比较麻烦，且不会使整个计算过程更快，所以直接循环每个数字，循环每个数的每一位直接计算即可。

Q2. My Calendar I 【Medium】
题目理解：1）输入：整数对start、end，表示时间的起始和结束时间
                2）输出：bool结果，表示给定的事件是否可以被执行
                3）日程表要求不能在同一个时间段，同时执行两个事件

解决方法：Brute Force。循环所有已安排在日程中事件，并分别判断跟待定事件是否存在重叠。根据题目要求可知，两个事件存在非零交集的关系为：start1<end2 且start2<end1。在循环中，若出现任一事件与待定事件重叠，返回False；若已安排所有事件全部遍历均无重叠，那么将新事件加入日程列表，并返回True。

class MyCalendar(object):

    def __init__(self):
        self.calendar = []

    def book(self, start, end):
        for s, e in self.calendar:
            if s<end and start<e: return False
        self.calendar.append((start, end))
        return True

Q3: My Calendar II 【Medium】（第二题的升级版）
题目理解：1）输入：整数对start、end，表示时间的起始和结束时间
                2）输出： bool结果，表示给定的事件是否可以被执行
                3）日程表要求不能在同一个时间段，同时执行三个事件

解决方法：跟第二题类似，同样要对每个已安排事件遍历比较，不同点在于因为可以同时进行两个事件，所以需要记录任何存在overlap的两事件之间重叠的时间。在判断是否可以添加新日程时 ，若新事件的开始结束时间与我们已经记录的overlap有重叠时，要返回False；当新日程跟所有overlap都不重叠时，在更新日程的同时，还要更新overlap，最后返回True 。

class MyCalendarTwo(object):

    def __init__(self):
        self.calendar = []
        self.overlap = []

    def book(self, start, end):
            for so, eo in self.overlap:
            if start<eo and so<end: return False
            
        for s, e in self.calendar:
            if start<e and s<end:
                self.overlap.append((max(s,start),min(e,end)))
        self.calendar.append((start, end))
        return True

注：Q2、Q3虽然标注 为Medium，但整体解题思路和代码实现过程都很简单明了，二者的解题方法也十分类似。

Q4: Flood Fill 【easy】
题目理解：1）输入：二维矩阵image（元素均为整数，不同数字代表不同颜色），sr，sc（表示给定矩阵内的坐标），newColor（整数）
                2）输出：新的二维矩阵（跟原输入尺寸相同）
                3）规则：对原数组中坐标为(sr，sc)的点进行染色操作，该操作会赋予给定坐标一个颜色newColor，并会对跟(sr，sc)点原来颜色相同且上、下、左、右连通的所有坐标点进行同样的操作。

解决方法： 递归。根据3）中描述的染色规则，可以发现对于给定点周围所有同等地位的坐标进行同样操作。因此，我们首先自定义一个染色函数fill(image, x, y, m, n, orgColor, newColor)，其中m、n为原矩阵的行、列数，x、y表示将要进行染色的横、纵坐标，在写函数时需要注意横纵坐标的范围问题，以及染色边界（不同颜色交界处），并在内部不断调用原函数，对原色相同的上下左右方向进行染色，完成递归调用。
最后调用自定义函数，并输出递归过后的新image即可。具体代码非常简洁（Python）：
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        if image[sr][sc]==newColor: return image
        m,n = len(image), len(image[0])
        def fill(image, x, y, m, n, orgColor, newColor):
            if image[x][y] == orgColor:
                image[x][y] = newColor
                if x>0: fill(image, x-1, y, m, n, orgColor, newColor)
                if y>0: fill(image, x, y-1, m, n, orgColor, newColor)
                if x<m-1: fill(image, x+1, y, m, n, orgColor, newColor)
                if y<n-1: fill(image, x, y+1, m, n, orgColor, newColor)
        fill(image, sr, sc, m, n, image[sr][sc], newColor)
        return image

Q5: House Robber 【easy】
题目理解：1）输入：整数数组nums，表示某条街上每个house里可以盗取的财产数量
                2）输出： 整数，表示可以在不触发警报的前提下，能够盗取的所有财产数量
                3）不触发警报的条件：不能连续盗窃两个相邻的house
               
解决方法： 递归/递推。因为递归和递推为同一种思想的正反实现，我这里就只详细写一种。以递推为例，首先要考虑起始条件，如果没有house（n=0），就没得偷，返回0；只有一家的话，至多只能偷一家，直接输出nums[0]；若有两家，那么偷钱多的。之后我们可以考虑一下递推关系。我们需要将问题稍做转换，我们假定每次都从左向右偷东西，我们来考虑偷到第i家结束时，强盗能够得到的最多财产数。这样对于抢到每个住户结束都会有的此时的最大值，所以当i=n-1（最后一个住户）时，就是我们要的答案。在不越界的情况下，中间的传递关系可以表示为：sums[i]  =  max（sums[i-1]，sums[i-2]+ nums[i]）