算法题笔记：2021年10月
2021.10.05
剑指 Offer 09. 用两个栈实现队列
题目
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )。
点击这里跳转至力扣查看原题。
思路
1、两个栈，stack1用于插入，stack2用于弹出。
2、插入直接插入，弹出时如果stack2有内容直接弹出，没有内容则将stack1中的元素依次弹出并插入stack2，直到弹空，然后从stack2中弹出元素。
注意
当且仅当两个栈都空时，队列为空。
剑指 Offer 30. 包含min函数的栈
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
点击这里跳转至力扣查看原题。
思路
1、正常情况下，min函数的复杂度应该为O(n)，因此用空间换取时间，使用辅助栈。
2、 栈A用于正常存储所有元素；栈B中存储栈A中所有 非严格降序 的元素，则栈A中的最小元素始终对应栈B的栈顶元素。
3、入栈时维护栈B：元素入A后与B栈顶比较，新元素小（或相等！）则入栈，否则不动。
4、出栈时维护栈B：若A弹栈，弹出的元素与B栈顶比较，相等则弹B，否则不动。
注意
入栈的时候相等的最小元素要重复入栈，否则可能漏掉重复的最小元素。
2021.10.06
剑指 Offer 24. 反转链表
题目
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
点击这里跳转至力扣查看原题。
思路
反转链表只需要把结点之间的指针反转就可以了。
注意
1、要保存上一个结点的指针，否则断开指针后没法处理了。
2、注意空链表的情况。
剑指 Offer 35. 复杂链表的复制
题目
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
点击这里跳转至力扣查看原题。
思路
1、由于链表的各个结点没有序号，因此很难确定这些结点谁是谁，那么考虑使用一个无序哈希表来存储原链表中的结点和新链表中的结点的一一对应关系。即unordered_map<Node*, Node*>，键为原链表中的结点，值为新链表中的结点。
2、将拷贝函数copyRandomList设计为递归的，对于传递进来的原链表结点，首先判断是否为空，若空直接返回空。
3、不为空则对该结点进行复制，复制之前首先查询哈希表中该结点是否已经复制过，如果没有复制过那就复制，首先由参数传来的原结点中的值新建结点，把新老结点键值对插入哈希表表示这个结点复制过了，然后递归地复制它的next和random，同时把递归返回结点的指针设置为当前复制结点的next和random。然后返回复制好的结点指针。
4、如果复制过了，就从哈希表中取出值（也就是复制的新结点的指针）直接返回。
注意
1、（重要！）创建完新结点一定要先把新老结点键值对插入哈希表，再递归地创建next和random结点，否则会出现栈区满的错误！因为如果不先把创建的结点插入哈希表，在递归创建后面结点的时候，一旦链表中出现环，查哈希表发现这个结点不在表中，以为这个结点还没有创建，就会再创建一遍再继续递归，这样就陷入了死循环，不断递归下去直到内存满。
2、复制好的结点指针已经插入哈希表，而复制过的结点指针也在哈希表中，所以无论复制过与否，两个分支都只需要返回从哈希表中取的值就可以，可以共用返回语句。
3、可以通过新老链表混排（一个原结点后跟一个新结点）的方式拆分重组，省去哈希表所需的空间。
2021.10.08
剑指 Offer 53 - II. 0～n-1中缺失的数字
题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
点击这里跳转至力扣查看原题。
思路
1、严格升序的数组中查找，自然要考虑二分法，但是不同的是，寻常二分法要找的是某个存在的数，该数的左边都是比它小的，右边都是比它大的，而这里找的是缺失的数。
2、可以发现数组被分成了两部分，左边部分的下标与值相等，右边部分的下标与值相差1（不等），因此实际是要找到这个边界。
3、惯例定义left和right，计算出mid判断nums[mid]与mid是否相等，相等说明mid属于左半边数组，那么让left=mid，不等则说明mid属于右半边，那么让right=mid，继续循环。
4、按理说一般的二分结束循环的条件是left==right或者left越过了right（left>right），而这里则不是，我们发现mid的下标与值相等的话，就让left=mid，不等就让right=mid，这样使得left永远在左半边数组，right永远在右半边数组，因此它们不可能相等或者left越过right，最终结束循环的条件应该是left在左半边数组的最后，而right在右半边数组的第一个，即left==right-1，它们俩夹着的空缺就是要找的缺失值，所以循环的条件应当为while(left<right-1)。
注意
1、需要注意处理特殊情况！比如左半边数组不存在，即缺失值是0的情况，以及右半边数组不存在，即认为缺失值是最后一个值。这种情况下是用二分得不到正确结果的，因为我们的假设是left永远在左半边，right永远在右半边，而这样的特殊情况使得赋初值的时候left和right同在一边了，一开始就错了。
2、解决的办法是在最开始就使用判断解决掉两个特殊情况，之后不是特殊情况的再用二分。缺失值是0的情况很好判断，只要nums[0]!=0，就说明缺失了0；缺失值是最后一个的也好判断，只要最后一个值也符合左半边数组的特征那么就意味着没有右半边数组，即nums[nums.size()-1]==nums.size()-1为判断条件。
2021.10.09
剑指 Offer 04. 二维数组中的查找
题目
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
点击这里跳转至力扣查看原题。
思路
1、左上角是最小的数，右下角是最大的数，要想效率高一些应当选一个中间值开始遍历，比如左下角和右上角的值。
2、选取从右上角开始遍历，如果恰好等于目标值，直接找到了，如果比目标值小，就往下遍历（下面的值更大），反之则往左遍历（左边的值更小）。直到找到目标值。
注意
1、要注意判断数组维度m,n是否为0，也就是空矩阵的情况。
2、循环时边界条件是当下标满足条件时继续循环。
剑指 Offer 11. 旋转数组的最小数字
题目
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
点击这里跳转至力扣查看原题。
思路
1、二分查找，数组分为了两个部分，以数组最后一个元素x作为参照，前半个数组都大于等于x，后半个数组都小于等于x。
2、如果mid小于x，说明它肯定属于后半部分数组，让right=mid，反之则属于前半部分，让left=mid+1（常规二分，舍弃一边的端点值）。
3、如果mid的值和x一样，那就不确定了，它可能属于前也可能属于后，这时mid要更新实际上可以通过更新区间来实现，更新区间的方法是抛弃最后一个x值，因为反正mid那里的值和x一样，我们的目的是找最小值，舍弃掉最后一个x并不影响结果，所以我们让right–，这样就可以缩小区间，重新计算mid了。
剑指 Offer 50. 第一个只出现一次的字符
题目
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
点击这里跳转至力扣查看原题。
思路
1、遍历一遍字符串，使用哈希表存储：第一次遇到该字符则存储下它的索引；第二次遇到该字符则将其对应值改为-1。
2、遍历一遍哈希表，找到值不是-1且索引最小的字母输出，如果全为-1，输出空格表示未找到。
2021.10.11
剑指 Offer 26. 树的子结构
题目
输入两棵二叉树A和B，判断B是不是A的子结构。（约定空树不是任意一个树的子结构）
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
点击这里跳转至力扣查看原题。
思路
1、定义一个用于迭代和回溯的函数recur用于判断给定的树A是否包含子结构树B。
2、其实这就是一个匹配问题，recur函数用于匹配两棵树：如果B为NULL了说明B树已经空了，那么不管A树是否还有结点，都已经匹配完成了，这时应该返回true，表示B是A的子结构。而如果B还没空，但是A却空了或者A的val和B的val不一样了，说明到这里失配了，返回false。以上两种情况分别是B匹配完了以及失配了的情况，如果不是以上情况，那就是最后一种情况，匹配成功了但是还没匹配完，那么就要继续往下匹配A和B的左右结点，即递归地返回recur(A->left, B->left)&&recur(A->right, B->right)。
3、以上是子递归，即从A和B开始匹配，如果失配了是要回退的，回退就是主递归的作用了，主递归是函数isSubStructure（也是求解函数）的内容：如果A和B都是NULL，那么直接返回false，如果不是，那么先匹配以A和B为根节点的树是否满足条件，即recur(A,B)，满足条件则匹配成功，不满足则回退并且A前进（包括向左前进和向右前进），即isSubStructure(A->left,B)和isSubStructure(A->right,B)，其中只要有一个匹配成功就成功了。
注意
这里的思想就像是字符串匹配一样，在主串中寻找模式串：先从主串的起始位置开始（先从A的根节点开始），调用匹配函数匹配主串和模式串（调用recur匹配A开始的树和B开始的树），如果模式串匹配到尾了（B的结点匹配到空了），就匹配成功了，模式串没匹配完主串先没了或者直接失配了（A的结点先空了或者A与B节点值不相等了），那这次匹配就失败了，如果成功了就接着匹配下去（递归调用recur匹配A和B的左右子树），失配了之后要回到主循环，让主串的下表前进1，再继续与模式串匹配（换A->left或A->right再与B匹配）。
这里换A->left或A->right再与B匹配之所以不调用recur而是调用主函数（isSubStructure）是因为recur只是一次匹配，失配了之后只返回而不会回溯、前进，isSubStructure则会接着使用A->left或A->right继续与B匹配。
2021.10.12
剑指 Offer 63. 股票的最大利润
题目
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
点击这里跳转至力扣查看原题。
思路
1、动态规划：如果在第i天以prices[i]的价格卖出，可以得到的利润为dp[i]，那么对于第i+1天，prices[i+1]如果大于prices[i]，那么就把在第i天卖出改为在第i+1天卖出，将得到更大利润，如果prices[i+1]比prices[i]小，那么就搜寻前i+1天的最低价格，假设在这天买，在第i+1天卖，得到的就是第i+1天卖的最大利润，因此转移方程：dp[i]=( (prices[i]-prices[i-1])+dp[i-1], prices[i]>prices[i-1] ) || ( prices[i]-min(prices[0:i]), prices[i]<=prices[i-1] )。
2、对于转移方程，我们可以看到当prices[i]>=prices[i-1]时，需要求前i天的最小价格min(prices[0:i])，同时转移方程只与前一天的价格有关，因此可以在时间和空间上同时优化，逻辑如下：对于prices[i]>prices[i-1]的情况，(prices[i]-prices[i-1])+dp[i-1]中dp[i-1]实际是prices[i-1]-min(prices[0:i-1])求得的，带入式子化简可得prices[i]-min(prices[0:i-1])，容易得知prices[i]>prices[i-1]时min(prices[0:i-1])即min(prices[0:i])，而prices[i]<=prices[i-1]的情况是prices[i]-min(prices[0:i])。因此在所有情况下需要求的都是prices[i]-min(prices[0:i])。
3、实现：迭代prices，使用一个变量m保存当前位置以前的最小价格，使用变量r保存当前得到的最大利润，当第i个价格加入之后，首先看它是否比第i-1天的价格高，高的话就更新最大利润r为prices[i]-m，否则看prices[i]是否比最小价格m还要低，低的话更新最低价格m为prices[i]，这样继续迭代下去，遍历一遍整个数组即可得到所求的最大利润r。
注意
对于转移方程中只涉及到dp[i-1]的动态规划，往往可以进行内存优化。
2021.10.13
剑指 Offer 42. 连续子数组的最大和
题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
点击这里跳转至力扣查看原题。
思路
1、动态规划，对于每一个nums[i]，考虑是把它加入以nums[i-1]结尾的子数组的末尾，还是让它单独成为一个新的子数组。
2、优化：依然是只涉及dp[i-1]的动态规划，考虑使用一个额外的变量pre存储上一状态，同时使用maxsum存储历史结果中最大的结果，每次更新maxsum为pre+x、x、maxsum中最大的，每次更新pre为pre、pre+x中最大的，将递归转化为迭代，从而节省空间。
2021.10.14
剑指 Offer 48. 最长不含重复字符的子字符串
题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
点击这里跳转至力扣查看原题。
思路
1、动态规划，对于每一个字符s[i]，考虑它能不能加入s[i-1]结尾的子字符串，可以加入的条件是在以s[i-1]结尾的子字符串中没有与s[i]相同的字符。
2、优化：依然是使用pre和maxsub两个额外变量，其中pre存储s[i-1]对应字串的长度，maxsub对应得到的子串长度中最大的那个。
注意
maxsub更新方式依然是变为maxsub和pre中较大的那个，而要注意的是这里的pre如何更新：
1、如果s[i]可以加入s[i-1]末尾，那么pre只需要+1即可。
2、如果不可以，那么说明s[i-1]对应的子串中有与s[i]相同的字符，那么只需要从这个字符后一位开始计算到s[i]的长度，即是s[i]对应子串的长度，而与s[i]相同的字符可以使用一个map来记录，每次遍历时，把当前字母的索引值更新到map中，每次查找map即可判断上一次出现s[i]字符是否在s[i-1]对应的子串内，在其中的话又是在哪个位置。
2021.10.16
剑指 Offer 52. 两个链表的第一个公共节点
题目
输入两个链表，找出它们的第一个公共节点。
点击这里跳转至力扣查看原题。
思路
1、可以先分别遍历一遍两个链表，得到它们的长度的差值，然后让长的链表指针先走这个差值的步数，然后再同时移动两个指针，直到找到公共的结点。
2、可以不计算两个链表的长度，让两个指针把两个链表都走一遍，指针pa走完A链表就紧接着从B开始走，pb指针走完B链表也紧接着走A链表，这样两个指针如果找到了同一个结点就是公共结点，如果同时指向了NULL就说明没有公共结点。
2021.10.17
剑指 Offer 57. 和为s的两个数字
题目
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
点击这里跳转至力扣查看原题。
思路
注意是排好序的数组，因此可以使用双指针，一个i从左边开始移动，一个j从右边开始移动，如果nums[i]+nums[j]>target，那么j–，小于的话i++，恰好等于的话则找到了结果，返回nums[i]和nums[j]组成的数组即可。
注意
特殊情况：nums数组长度为1时，不满足两个数的条件，直接返回空数组。
2021.10.18
剑指 Offer 12. 矩阵中的路径
题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
点击这里跳转至力扣查看原题。
思路
典型的深搜+剪枝：
1、设定全局的变量rows和cols来存储行和列数，在主函数里进行赋值，然后主函数里对每个网格里的格子为起点开始深搜，深搜返回搜索的结果为true则不必继续搜索，直接返回true，否则循环结束还是没有true，就返回false。
2、设计深搜函数，步骤为：剪枝、判断结束条件、递归。
3、剪枝就是剪掉明显不必要继续的岔路，正常的深搜应该每个岔路走到底的，但是本题这样的带有一定任务（字符匹配）的深搜就应当在任务不满足时结束当前岔路，具体为：走到网格边界时返回；失配时剪枝。
4、既没有走到头，也没有失配，那么就应该判断结束条件了，结束的条件是模式串word匹配完了，说明匹配完成，应当直接返回true了。
5、如果模式串也没匹配完，就该进行下一步匹配了，在模式串没完并且没有失配的情况下，进行上、下、左、右四个方向的匹配，匹配就是递归调用dfs函数，但在递归前要标记访问过的位置再继续，之后要恢复位置信息（回溯）。因为递归有四个方向，因此要将四个结果或运算作为最后结果返回，因为只要有一个路走得通就行。
注意
1、为节省空间，不需要使用额外的visited数组保存访问过的位置，直接在原数组board内保存即可，将访问过的元素置为0，恢复时恢复成word里对应的字符即可（因为是已经匹配过的）。
2、在判断匹配完成时，容易把k与word.size()比较是否相等，因为前面的i和j就超边界比较了，但这里的k不可以超边界比较，因为前面剪枝条件判断是否失配用到了word[k]，超边界的话就下标越界了！这样把k与word.size()-1比较也就是判断k是否是最后一位了，前面剪枝条件里已经能确保这一位匹配上了。
2021.10.19
剑指 Offer 13. 机器人的运动范围
题目
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
点击这里跳转至力扣查看原题。
思路
广度优先搜索，搜索的同时进行计数。
由于从左上角开始搜索，因此只向下和向右走就可以确保走遍所有的格子了，遇到不满足条件的位置停止继续深入。同时需要设立visited数组。
注意
在广搜中，不要等到真正访问元素时才置visited数组数组，否则会重复遍历，应当在将元素加入队列时就置visited数组，毕竟把它加入队列就说明它迟早会被访问的。
剑指 Offer 34. 二叉树中和为某一值的路径
题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
点击这里跳转至力扣查看原题。
思路
1、记录路径的深度优先搜索+回溯：
使用两个全局的vector，一个用来保存结果，一个用来保存路径，路径在每次递归后回溯。
2、使用哈希表存储父子关系的广度优先搜索+反向迭代出路径：
使用全局的结果vector和存储父子关系的map，在广搜时设立两个队列（双队列），一个存储结点，一个存储对应的累加值，两个队列同步操作以保证一一对应。
注意
结点可能有负数！
1、对于深搜：
这道题中路径必需到叶子结点，不能只走到一半，也就是target和root结点匹配两者要恰好同时匹配完。因此其实只有两个结束条件：root完了或者target完了。
在深搜时，不要使用大小比较target和root->val的值，因为这道题里val可能为负数，应当使target减去root->val然后和0比较。如果val全为正数的话，在这里可以剪枝（剪掉target已经小于0的分支），而这里就不行了，不能剪枝就只能等待正常结束，而root完了或者target完了两个结束条件中，target完了其实无法判断了，因为不能判断target是否小于0了以结束深入。因此只能根据“恰好匹配”的匹配成功条件，来等待结点匹配完，然后判断target是否为0。
还要注意不能遇到target为0就直接返回空vector，同样的道理，结点有正有负，可能某个路径上正负相加刚好就等于0了。
2、对于广搜：
对于每个结点在遍历时都要判断它是不是叶子结点，是的话就要通过哈希表迭代出它的路径，并存入结果vector，这一过程可封装为一个函数。
2021.10.20
剑指 Offer 45. 把数组排成最小的数
题目
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
点击这里跳转至力扣查看原题。
思路
1、自定义排序。定义排序规则：若拼接字符串x+y>y+x，则x>y，反之x<y。即尽可能找到使某个数放在前面使得整体更小的顺序。
2、定义比较函数，写快排即可。
2021.10.21
剑指 Offer 41. 数据流中的中位数
题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) ：从数据流中添加一个整数到数据结构中。
- double findMedian() ：返回目前所有元素的中位数。
点击这里跳转至力扣查看原题。
思路
维护两个优先队列（一个大根堆，一个小根堆），分别存储数据流的前一半数和后一半数，要保证两个队列里数的数量是相等的（总数为偶数）或其中一个比另一个的数量多1（总数为奇数），最后输出的结果就是两堆的根（总数为偶数）或数量多的那个堆的根（总数为奇数）。
注意
注意维护两个堆的数目均匀的方法：
1、常规容易想到的可能就是比较两堆堆顶元素，看新插入元素大小属于哪半边，就插入哪个堆，最后再调整均匀，这样做是麻烦的。
2、更高效的方法是：假如我们要维护在奇数个数据情况下堆1比堆2元素多一个，那么当两堆数目一样时，元素往堆1插入；堆1元素多时，元素往堆2插入补齐堆2。但是由于两堆应当分别保有所有元素的前半部分和后半部分，因此不能直接插入，要利用堆的性质，使用过渡法插入，即要插入某个堆，转为插入另一个堆，并把另一个堆的堆顶元素过渡到这个堆，即可满足要求。
3、大根堆：priority_queue<int>；小根堆：priority_queue<int,vector<int>,greater<int>>。
2021.10.22
剑指 Offer 55 - II. 平衡二叉树
题目
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
点击这里跳转至力扣查看原题。
思路
设计一个函数height，来计算数的高度，递归地访问左子树、右子树和当前结点，判断是否平衡。
注意
在递归时，先判断左右子树，再判断当前结点（即自底向上地判断）；否则的话，先判断当前结点再判断左右子树（自顶向下地判断），判断当前结点的时候也会判断一次左右子树，等于说判断多了，使用了几乎两倍的时间。
2021.10.23
剑指 Offer 64. 求1+2+…+n
题目
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
点击这里跳转至力扣查看原题。
思路
递归：看到题目要求很容易想到用递归，但是递归需要边界条件的判断，即判断n==0，这时要么用if，要么用条件判断语句，不符合题目要求。代替的方法是使用短路逻辑，即A&&B当A成立时才会执行B，A为false时直接就是false了，不会再去看B了，就像使用了if语句一样。在这里可以写成：
1 | |
即n是0时直接返回了0（边界条件），n非0的话继续递归。
注意
n&&(n+=sumNums(n-1))中第二个式子由于优先级问题必须要加括号。赋值运算符优先级比逻辑运算符低。
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
点击这里跳转至力扣查看原题。
思路
1、要注意这是二叉搜索树，要利用二叉搜索树的特性来做。
2、对于一个结点，它的左子树的结点都是小于它的，右子树的结点都是大于它的，因此从根结点开始，如果两个要找的结点在根的左右两侧，那么根结点就是它们的最近公共祖先，如果在同一侧，那么就往这一侧走，直到遇到某个结点，把它们分在两侧，这个结点就是要找的最近公共祖先了。
2021.10.24
剑指 Offer 07. 重建二叉树
题目
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
点击这里跳转至力扣查看原题。
思路
前序遍历的第一个元素是根节点，在中序遍历序列中确定根节点的位置，就可以递归地创建二叉树。
注意
如何在前序序列中分割出左右子树是需要注意的点，从中序遍历序列中很容易找到左右子树，根据前序遍历和中序遍历序列中左右子树长度相等来从前序序列中分割出左右子树。
这里为优化时间可以使用哈希表记录一下各结点在中序序列中的位置。
代码
1 | |
剑指 Offer 16. 数值的整数次方
题目
实现 pow(x, n) ，即计算 x 的 n 次幂函数。不得使用库函数，同时不需要考虑大数问题。
点击这里跳转至力扣查看原题。
思路
快速幂：将n转换为二进制b1,b2,b3……其中b1为最低位。那么计算x^n即计算x^bn(2^n-1)之积。
注意
循环时每次让n&1，n>>1，x=x*x。
还要注意这题数据范围会出现-2^31的情况，而最大int只有2^31-1，将负指数转为正指数处理时需要注意：对所有可能取值为-2^31的变量都不能直接加符号。
剑指 Offer 33. 二叉搜索树的后序遍历序列
题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
点击这里跳转至力扣查看原题。
注意
注意在左右子树其中之一为空时，数组下标的有效性判断。
2021.10.25
剑指 Offer 65. 不用加减乘除做加法
题目
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
点击这里跳转至力扣查看原题。
思路
（1）特殊情况：加数b为0时，直接返回a。
（2）模拟二进制加法：根据二进制加法规则，a&b为进位，a^b为非进位和，即a+b=a^b+a&b<<1，由于不能使用加法，因此需要递归调用add(a^b, (unsigned int)(a&b)<<1)。
注意
（1）C++不支持负数的左移，因此需要将a&b转换为unsigned int再进行移位。
（2）一定要将进位放在第二个参数，因为判断特殊情况b为0实际上也是在判断递归的结束条件，即进位为0。
2021.10.26
剑指 Offer 56 - I. 数组中数字出现的次数
题目
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
点击这里跳转至力扣查看原题。
思路
（1）对于只有一个单独的数，可以对所有数求异或，求出来的结果就是这个单独的数。
（2）而本题有两个单独的数，那对所有的数求异或，得到的结果实际上是这两个数的异或——此时使用分组求异或的方式来求出这两个数。
（3）如何分组：对于最后的异或结果，是这两个数的异或，如果这个结果的某一位为1，代表着这个位上两数的值不等，那么就可以根据此来给所有的数分组。此时可以找到异或结果为1的最低位，假设为第i位。
（4）遍历所有数，遇到第i位为1的异或在一起，遇到第i位为0的异或在一起，最终得到的两个异或值就是两个要求的数了。
注意
在判断二进制末位是否为0的时候最好转换为unsigned int来判断，否则容易出现问题。
剑指 Offer 56 - II. 数组中数字出现的次数 II
题目
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
点击这里跳转至力扣查看原题。
思路
（1）方法一：遍历统计。将每个数的各个二进制位上的数相加，保存在数组中，出现了三次的数对应位上的和必定是3的倍数，只要找出哪些位上%3后有余数，就知道这个多出来的数是多少了。
（2）方法二：有限状态自动机。
2021.10.28
剑指 Offer 14- I. 剪绳子
题目
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]*k[1]*…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
点击这里跳转至力扣查看原题。
思路
（1）数学推论：① 以相等的长度将绳子等分为多段，得到的乘积最大；② 尽可能将绳子以长度3等分为多段时，乘积最大。
（2）对于推论②，如果最后刚好分完或者余下的段为2，就刚刚好，如果最后余下的为1，那么就将最后两段3+1拆分为2+2，因为2×2>3×1。
注意
n=2或3时都是特殊情况，单独判断。
剑指 Offer 57 - II. 和为s的连续正数序列
题目
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
点击这里跳转至力扣查看原题。
思路
对于target，枚举x从1开始到target/2，通过求和公式方程(x+y)*(x-y+1)/2=target，解关于y的一元二次方程可得y，其中y必须是整数。
注意
计算两大负数相减或两大正数相加可能会导致溢出。
2021.10.30
剑指 Offer 20. 表示数值的字符串
题目
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
- 若干空格
- 一个 小数 或者 整数
- （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
- 若干空格
小数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（’+’ 或 ‘-‘）
- 下述格式之一：
- 至少一位数字，后面跟着一个点 ‘.’
- 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
- 一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（’+’ 或 ‘-‘）
- 至少一位数字
点击这里跳转至力扣查看原题。
思路
有限状态自动机。一个自动机，总能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。在本题中，条件 P 即为「构成合法的表示数值的字符串」。
- 状态集合：
- 起始的空格
- 符号位
- 整数部分
- 小数点
- 左侧有整数的小数点
- 左侧无整数的小数点
- 小数部分
- 字符e
- 指数部分的符号位
- 指数部分的整数部分
- 末尾的空格
下一步是找出「初始状态」和「接受状态」的集合。根据题意，「初始状态」应当为状态 0，而「接受状态」的集合则为状态 3、状态 4、状态 6、状态 9 以及状态 10。换言之，字符串的末尾要么是空格，要么是数字，要么是小数点，但前提是小数点的前面有数字。
2021.10.31
剑指 Offer 59 - I. 滑动窗口的最大值
题目
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
点击这里跳转至力扣查看原题。
思路
维护一个单调队列（双端队列）和结果数组，先对前k个元素创建好单调队列，方法是元素从右侧入队，入队之前从右侧删除掉所有比它小的元素，保证队列单调。建成队列之后把队首元素放入结果数组，接下来对剩余元素迭代，进入窗口的元素以同样方法入队，移出窗口的元素如果与队首相等，那么队首出队，然后把队首放入结果数组，以此类推。
