首先看十进制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算进位，得到2。 第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。 第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。 第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。 第三步重复上述两步， 各位相加 ...

堆的做法： 中位数是指：有序数组中中间的那个数。则根据中位数可以把数组分为如下三段: [0 ... median - 1], [median], [median ... arr.size() - 1]，即[中位数的左边，中位数，中位数的右边] 那么，如果我有个数据结构保留[0...median-1]的数据，并且可以O(1)时间取出最大值，即arr[0...median-1]中的最大值 相对应的，如果我有个数据结构可以保留[median + 1 ... arr.size() - 1] 的数据， 并且可以O(1)时间取出最小值，即 arr[median + 1 ... arr.size() - 1...

动态规划： 首先我们定义一个f[i][j]的状态转移方程，其中i 表示str中的第i个字符；j表示pattern中的第j个字符，然后判断是否匹配。我们需要判断两种情况： 第一种是当i、j指向的字符是同一个字母/点号（"."）的时候，我们只需要判断对应位置的字符是否相同，相同则转移状态去判断子问题f[i-1][j-1]是否匹配 然后当 j 为*的时候 ，可以把 b* 这样的看作一个整体,然后有两种子问题的情况: 第一种是b*匹配完 a 后，继续使用,此时的转移方程就是 f[i-1][j]； 第二种就是b*匹配完a后，就舍弃,此时的转移方程为：f[i][j-2]。 注意：|= “或操作”保...

动态规划的思路，但要注意：每次考虑的元素是包含当前元素的子数组 1. 如果当前子数组和为负数，即便加上当前元素，和也不会变大，因此从当前元素开始开辟新数组； 2. 否则当前子数组加上当前元素合并成新的子数组； 3. 过程中始终维护最大子数组的和及开始与结束的下标 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vec...

通过前序遍历或层次遍历（递归 或 非递归）去建树 注意char* 的使用 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(!root) ...

递归： 如果当前root是o1或o2，则当前root为要找的公共祖先； 否则： 如果o1和o2都在左（右）子树，则递归去子树中寻找； 如果o1和o2分散在左右子树中，则当前root为要找的公共祖先 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param o1 int整型 ...

这题首先需要遍历一遍树，把当前遍历的节点作为根节点出发，再去求符合条件的路径的个数。 第一次遍历可以用简单的层次遍历，利用队列实现；第二次遍历可以用dfs 方法一：非递归的dfs /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方...

数学方式解决 在做这题之前我们先来看这样一个问题: 一个整数先把他分成两部分，x+y=n（假设x>=y并且x-y<=1,也就是说x和y非常接近）那么乘积是xy。 然后我们再把这两部分的差放大(x+1)+(y-1)=n(假设x>=y)；他们的乘积是（x+1）(y-1)=xy-(x-y)-1，很明显是小于xy的，所以我们得出结论，如果把整数n分为两部分，那么这两部分的值相差越小乘积越大。 同理还可以证明如果分成3部分，4部分……也是相差越小乘积会越大。 根据上面的证明，如果我们把长度为n的绳子分为x段，则每段只有在长度相等的时候乘积最大，那么每段的长度是n/x。所以他们的乘积是...

时间复杂度要求O(lgn)，考虑二分法： 如果当前数组 v[l] < v[j]，则当前数组是有序的，返回最小值v[l]； 否则取数组中间mid： 如果v[l] < v[mid],则最小值在mid + 1 ~ r 中； 如果v[l] > v[mid],则最小值在l ~ mid 中； 3.如果v[l] == v[mid],则取l ~ mid 和mid + 1 ~ r 中的min。 注意： 如果数组中的两个元素i <j且v[i] < v[j], 则v[i]~v[j]间是有序的 二分法的迭代最好是Sl∪Sr=S，Sl∩Sr=∅(l ~ mid 和mid + 1...

初次版本：分层的层次遍历，常规层次遍历用一个队列，无法确定遍历节点的层次，可以考虑用两个队列分别存储奇偶层的节点，交替存储和遍历； class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> res; queue<TreeNode*> l ,r; int count = 1; if(!pRoot) ...

暴力解法当然就是按照中序遍历一遍，但这题中参数只给了待查找的子树根节点，中序遍历操作过于麻烦，最好是从子树根节点直接开始查找。 如果子树根节点存在右节点，则从该右节点开始，一路向左查找； 否则，子树根节点的中序遍历下一个节点只能在其父辈中查找，并且只有将当前根节点作为左节点的父节点符合条件： 往上查找，找到第一个把当前根节点当做左子节点的父节点； 如果不存在，则待查找子树根节点是该树中序遍历的最后一个节点，返回NULL。 class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { ...

刚开始考虑这题：从左到右遍历，考虑每次新进的一个元素： 如果i < min 或 i > max, 修改min 或 max； 再考虑当前值与最小值的差是否大于利润 最后考虑max<min的情况 class Solution { public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vector<int>& prices) { // write code here if(...