/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { if (intervals.empty() || intervals.si...

回溯 从第一行开始枚举皇后放在哪一列 递归函数：dfs(int x)   如果当前行 x 等于 n 表示所有行的皇后都已经放完了，则方案数 + 1，将当前棋盘加入到答案中。   枚举皇后应该放在 x 行的哪一列 y，y 从 0 枚举到 n - 1   判断：如果当前列 col[y]、当前对角线 dg[y - x + n]、当前反对角线udg[y + x] 上没有皇后  这个位置才可以放皇后 g[x][y] = 'Q'， 然后设置 col[y] = dg[y -x + n] = udg[y + x] = true， 递归枚举下一行 dfs(x + 1)， 最后别忘记回溯 col[y] = dg[...

(动态规划) O(n)O(n)O(n) 这道题目是 NC19 连续子数组的最大和 的升级版，增加了环形情况。 分两种情况考虑问题：   无环情况下：求出连续子数组的最大值 res   有环情况下：先求出无环情况下连续子数组的最小值 res2，然后用数组和 sum 减去最小值 res2 即为环形情况下的连续子数组最大值。    why? 因为数组的和是固定的，从中间挑一段和最小，那么剩下尾首相连的一段和就是最大的。这个说法应该是最容易理解的。  特殊情况：当 res < 0 时，观察状态转移公式：f[i] = max(f[i - 1], 0) + nums[i]，如果数组中有一个非负数，最...

序列化：按照前序遍历的顺序将二叉树序列化为字符串，空节点序列化为 #，非空节点将数字加到字符串中，每个节点之间用 , 分隔(在反序列化中需要得到每个节点的值)。序列化结束将字符串最后的 , 去掉。 反序列化：根据前序序列以及其中包含的空节点就可以还原一棵二叉树。根节点就是前序序列的第一个节点，从字符串中拿到当前节点的值，构建当前节点，递归构建左子树和右子树。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), righ...

迭代层序遍历，将空节点也加入到队列中，判断空节点之后是否还有非空节点，如果有说明不是完全二叉树，否则就是完全二叉树

递归前序遍历两根二叉树，将 t2 合并到 t1 中   递归出口条件：如果 t1 为空返回 t2，t2 为空返回 t1   单层递归逻辑：  说明 t1 和 t2 都不为空，则修改 t1 的值为两个节点值的和 递归遍历 t1 的左子树和 t2 的左子树 递归遍历 t2 的右子树和 t2 的右子树 最后返回 t1

编辑距离（一）的升级版 原来考虑的是最小步数（步数每次 + 1），现在需要考虑最小花费，对于每种操作加上对应的花费再取 min 代码逻辑是一样的。

动态规划（记忆化搜索） 状态表示：f[i][j]f[i][j]f[i][j] 表示走到 (i, j) 的最长递增路径的长度。 状态计算：可以从上下左右四个方向走到 (i, j)，但要满足前一个点的值小于当前位置的值 matrix[a][b] < matrix[i][j]，所以四种情况取一个 max 就是答案。 class Solution { public: int n, m; vector<vector<int>> f, g; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int dp(int x, int ...

解题思路 (数组,哈希表,原地交换) O(1)O(1)O(1) 如果没有空间限制的话，可以使用哈希表来解，先把所有元素放入哈希表 set 中，然后从 1 开始在哈希表中查询第一个未出现的正整数。 要求使用常数空间的话想到在原数组原地交换，而我们关心的是正数，所以如果 nums[i] 是正数 > 0 且 < n 且 nums[i] 的位置上不是当前数，就把他放到应该的位置上去（防止死循环，如果原来就在正确的位置上，一直交换）  每个正数 nums[i] 的位置在 nums[i] - 1 上，即 0 的位置上放 1，以此类推（因为数组的大小是 n，那如果出现 n 放在位置 n 上会越界...

位运算 异或：相同为 0，不同为 1   首先用 sum 记录所有数异或的结果，sum 初始值为 0。因为数组中除了只出现一次的数其他都是出现两次的数，那么异或之后的结果就是只出现一次的两个数字的异或结果，即 sum = x ^ y。   因为 x != y 那么 sum 必不为 0，所以必然可以在 sum 的二进制表示中找到最后一个 1，然后按照 sum 的二进制数的最后一个 1 所在的位置是 1 还是 0 为划分条件，将数组中所有的数分为两组（1）是 1 的（2）是 0 的，而 x 和 y 必然不在一个分组，对于每个相同的数肯定在一个分组   将分组（1） 的所有数进行或运算，得到一个结果...

首先要保证 m 在合法范围内，所以 m %= n 三次翻转得到答案   翻转整个数组   翻转 0 ~ m- 1 之间的数   翻转 m ~ n - 1 之间的数

前序遍历交换左右儿子

判断一棵树是否为对称二叉树只需判断左右子树是否为对称二叉树即可，所以将根节点的左子树和右子树传入递归函数即可  递归出口条件：如果 p 和 q 都为空，则对称，返回 true 单层递归逻辑：   如果 p 为空 或者 q 为空 或者 p->val != q->val 则不是对称二叉树，返回 false 否则说明 p 不空 且 q 不空 且 p->val == q->val，那么再递归判断（1）左子树的左孩子和右子树的右孩子是否对称 以及（2）左子树的右孩子和右子树的左孩子是否对称，一棵树为对称二叉树当前且当（1）（2）条件同时成立

因为二叉搜索树的中序遍历是有序的，所以选择中序遍历二叉树，在遍历的过程中将二叉搜索树转换为双向链表。 使用一个指针 pre 指向当前遍历节点的前一个节点。关键的三步操作   前一个节点 pre 的 right 指向当前节点（注意 pre 不能为空）pre->right = cur   当前节点的 left 指向前一个节点 root->left = pre   不要忘了 pre 指向当前节点 pre =root   就构成了双向关联，当然上面两步中的关联可能原二叉树中就有，但是不影响答案。