题目 思路 做这道题首先要知道什么是回溯法。 设数组大小为$n$，这个问题可以视为有$n$个排成一行的空格，依次为每个位置选择一个未被选的数来填充。那么可以直接想到一种穷举法，就是从左往右依次往空格中填入数字，全部空格填完就是一种答案。这里我们就可以使用回溯法来完成这一过程。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: vector<vector<int>> ans; vector<int> output; // 存储当前的组合 void backtrace(vector<int>& nums, vector<bool>& used) { // 判断是否已经组合完毕 if (output.size() == nums.size()) { ans.emplace_back(output); return; } // 依次将每个元素放到当前位置 for (size_t i = 0; i < nums.

题目 思路 读完题后发现：所谓的路径就是指以某一个结点为根，往左和右各走一边，路径和就是这条路径上的结点值之和。要寻找最大路径和就需要计算每个结点为根时的路径和，选取其中的最大值，这就需要遍历，而且很明显应该使用后序遍历来处理，因为只有当节点的左右子树都处理完了，我们才能计算以当前节点为根的最大路径和是多少，即： $$ 以当前结点为根的最大路径和 = 当前结点值 + 左边的贡献 + 右边的贡献 $$ 那么左右贡献是什么呢？想一想处理完一个结点，要向它的父节点返回什么信息呢？那就是以当前结点为根时的最大单边路径和（因为路径不能分叉），这样才能计算其父节点为根时的最大路径和。但需要注意的时，如果最大单边路径和为负，则需要丢弃，因为其会拉低父节点的最大路径和，父节点是不会考虑连接这条路径的。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int dfs(TreeNode* root, int& ans) { if (!root) { return 0; } int left = dfs(root->left, ans); // 存储左边的贡献 int right = dfs(root->right, ans); // 存储右边的贡献 ans = max(ans, left + right + root->val); // 寻找最大路径和 /** * max({ left, right, 0 }) 是为了找到当前结点的左右最大贡献值(因为只能取一边)，如果都为负，则丢弃 * max(max({ left, right, 0 }) + root->val, 0) 是为了判断以当前结点为根时的最大路径和，丢弃负值 * 因为我们要寻找的是最大路径和，负值就会使得路径和变小 */ return max(max({ left, right, 0 }) + root->val, 0); } int maxPathSum(TreeNode* root) { int ans = INT_MIN; dfs(root, ans); return ans; } };

题目 思路 看到题目首先想到的是暴力法，让每一个点为起点，穷举该点向下延伸的所有路径，将符合要求的路径累加起来，就是以该点为起点满足要求的路径数，将每个点符合要求的路径数累加起来就是答案。 暴力法的时间复杂度为$O(N^2)$，能不能进行优化呢？有的，兄弟。回顾暴力法，我们发现存在大量重复计算，比如说示例1中的 5→3 这一条路，以10为起点会计算一次，以5为起点又会计算一次。那么有什么方法可以让每条路只被计算一次呢？那就是 前缀和 ，既然以每个点为起点向下探索会存在大量重复计算，那么逆转一下思路，以每个点为终点向上探索。 我们想要计算以当前节点为终点的任意路径的和，那么就需要借助第560题学习到的前缀和方法。用一个哈希表 $presum$ 来记录当前子路径中每种路径和的个数，当走到结点$node$时，我们只需要获得路径和为 $curr\_presum - targetSum$ 的路径数就可知道以$node$为终点，路径和为$targetSum$的路径数了。 那么来整理一下整体思路：使用递归来遍历每个节点，用$currSum$来记录从根节点到当前节点的路径和(即前缀和)，同时用哈希表来记录从根节点到当前节点的父节点的所有路径和的出现次数。这样，每当走到一个新节点，就可以用减法快速判断以当前节点为终止节点的所有路径中有多少是符合要求的。最后，使用一个变量来累加全部结果。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 // 解法一，暴力法： class Solution { public: // 累加每个点符合要求的路径数 long pathSum(TreeNode* root, long targetSum) { if (root == nullptr) { return 0; } long ret = rootSum(root, targetSum); ret += pathSum(root->left, targetSum); ret += pathSum(root->right, targetSum); return ret; } // 计算以root为起点，符合要求的路径数 long rootSum(TreeNode* root, long targetSum) { if (!

题目 思路 首先，搞一发暴力，对于每个查询的时刻，根据题目所给公式计算其核酸有效时间范围，判断计划出行时间是否在这个有效时间范围内。提交后发现果然超时，只能过7个样例。 暴力法是拿每个查询的时间去依次处理每个出行计划，再判断每个计划是否可以出行。想了一下，对于暴力法没有什么大的优化点，那么能不能逆向一下处理流程呢？先处理每个出行计划，计算出每个出行计划最早和最迟做核酸的时刻，再处理每个查询的时刻。当然可以！我们可以先将每个出行计划都转化成一个时刻区间 $[start, end]$ ， $start$表示要满足该出行计划的最早做核酸的时刻。 $end$表示要满足该出行计划的最迟做核酸的时刻。 「只要开始做核酸的时刻$q$包含在该出行计划的时刻区间里，那么必定能满足该出行计划」。 通过上面的分析可知，可以用一个$time$数组存储每个时刻（下标$i$表示时刻i）被多少个出行计划所覆盖，那么在获取要查询的时刻$q$后，就可以直接返回$time[q]$，在$O(1)$的时间内就能知道该时刻做核酸能满足多少个出行计划。 但是修改时刻区间 $[start, end]$的每个时刻对应的值时(即修改每个$time[i]，i \in [start, end]$)，仍需遍历，最坏的时间复杂度仍然为$O(2 \times 10^5 \times m)$。有什么方法可以不用遍历就能让指定区间对应的值都加1呢？那就是差分法。这样一样，就可以在$O(1)$时间内让指定区间对应的每个值都加1。 那么来梳理一遍流程： 创建一个时刻数组 $time$，用来记录每个时刻被多少个出行计划所覆盖。 将每个出行计划转化成对应的时刻区间 $[start, end]$，使用差分法让time[i]都加1，其中$i \in [start, end]$。 查询时刻$q$时，直接返回$time[q]$。 差分法 差分法经常应用于「要将不同区间内的值都加上一个相同的值」。 例如，将区间$[l, r]$的每个数都加上一个$k$，只需要让 $b[l] += k, b[r+1] -= k$; 这样就可以让$a_l$到$a_r$都加上$k$，因为$a_i$的值是$b_i$的前缀和。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 #include <bits/stdc++.

题目 思路 看到这题直接暴力法，但时间复杂度为$O(m*n)$，不够快。考虑到每一行的元素都是升序排列，那么可以在遍历每一行的元素时使用二分查找法，时间复杂度为$O(m * log_{}{n})$（当然也可以在遍历每一列时使用二分查找法）。 二分查找法我们只用到了行有序或列有序这两个中的一个条件，能不能同时应用这两个条件来实现更快的算法呢？设「$num$为某一行的最后一个元素」，观察发现： 如果$num$比$target$大，那么该元素所在列的后续元素都将比$target$大，所以可以直接抛弃掉这些元素。 如果$num$比$target$小，那么该元素所在行的前驱元素都将比$target$小，所以可以直接抛弃掉这些元素。 这意味着：我们可以一次性跳过当前搜索范围中的一整行或一整列，快速减少搜索空间！ 每次移动会排除一行或一列，最多移动$m+n$次，时间复杂度为 $O(m+n)$ 理清了思路，那么起始点该选择哪里呢？开始时能覆盖全部值的只有右上角和右下角，那么该选哪个呢？分析一下： 右上角 值比target大时：可以跳过当前列。 值比target小时：可以跳过当前行。 右下角 值比target大时：无法跳过当前行和列。 值比target小时：target不存在。 通过分析发现，起始点只能选择右上角。这里采用的是分析行的最后一个元素，当然也可以分析列的最后一个元素，该方法就请读者自行思考了。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int x = 0, y = matrix[0].size() - 1; while (x < matrix.

题目 思路 这道题的难点主要在于不能使用辅助数组，空间复杂度必须为$O(1)$。通过观察示例，我们可以发现以下规律： 「第 $i$ 行」元素旋转到「第 $n−1−i$ 列」元素。 「第 $j$ 列」元素旋转到「第 $j$ 行」元素。 即 $(i, j)$ 要放置的位置为 $(j, n - 1 - i)$，只要我们提前使用一个临时变量$temp$来存储$matrix[j][n - 1 - i]$，即可完成$(i, j)$这个位置的旋转操作。那么$(j, n - 1 - i)$又旋转到哪个位置呢？继续应用规律，发现其旋转的位置为$(n - 1 - i, n - 1 - j)$，同样的，如果使用$temp$来存储$matrix[n - 1 - i][n - 1 - j]$，即可完成$(i, j)$和$(j, n - 1 - i)$这两个位置的旋转。按照前面的逻辑继续推理，我们可以发现： $(i, j) → (j, n - 1 - i)$ $(j, n - 1 - i) → (n - 1 - i, n - 1 - j)$ $(n - 1 - i, n - 1 - j) → (n - 1 - j, i)$ $(n - 1 - j, i) → (i, j)$ $A→B$表示位置A的元素顺时针旋转$90°$后的位置为B。观察上面的式子，发现这四项处于一个循环中，使用一个临时变量$temp$即可完成这四个元素的原地交换！

题目 思路 看题第一眼想到的是先计算给定数组所有元素的乘积，然后对数组中的每个元素 $x$，将总的乘积除以 $x$ 来求得除自身值的以外数组的乘积。但当数组中出现$0$时，这个方法就失效了，且题目说明了不能使用除法。 不能使用除法，又怎么计算除自身值以外数组的乘积呢？考虑到 该数对应的乘积 =其左边的乘积 * 其右边的乘积。所以，可以通过两次遍历依次计算每个数的左右乘积即可得到答案。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { vector<int> ans; // 计算每个数的左侧乘积 for(int i = 0; i < nums.size(); ++i) { if(i == 0) { ans.