思路：数组是非降序数组，此题 比较右端点,如果旋转则旋转后 [l,k] 非降序 ，[k,r] 非降序，且[l,k]内值 >= [k,r] 值 当 f[m] < f[r] 时，说明 m 到 r 非降序，最小值在左边，r = m; 当 f[m] == f[r] 时， r = r -1 ;缩小空间 当 f[m] > f[r] 时，说明旋转了，最小值在 [m,r]内， l = m + 1; 假设比较左端点： 当 f[m] < f[l] 时，说明 [m,r] 是非降序，最小值在 [l,m] 中，r = m; 当 f[m] > f[l] 时， 说明 [l,m] 非降序 （可...

数字在升序出现次数 class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int rb = 0, lb = 0; int l = 0,r = data.size(); while(l < r){//第一个大于k,最终l=r int m = (l + r)/2; if(data[m] > k) r = m; else// <= 时...

滑动窗口最大值 【思路】：利用双端队列通过（下标）维护来单调队列（单调递减），则每次的头即是滑动窗口最大值。 判断要进队列的数num[i]和队列的尾，如果队列的尾小于num[i]直接出队列 （因为如果当前进队的比之前进队的大之前进队的都可以不用） 如果队列头+size <= i 表示超过滑动窗口大小，队头出列 class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<in...

反转单词 【思路】：每个单词反转，然后整体反转 class Solution { public: string ReverseSentence(string str) { if(!str.size())return ""; int pre = 0; for(int i = 0;i < str.size();++i){ if(str[i] == ' '){ reverse(str.begin()+pre, str.begin()+i); while...

栈的压入和弹出 [思路]：用一个栈模拟入栈过程，分情况。（i表示pushv，j表示popv） 当popv[j] != pushv[i],即当前数入栈v。继续判断下一个 当pushv[i] == popv[j],当前入栈立即出栈，此时两种情况（1.前面入栈的出栈）（2.继续入栈） class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> v; int n = pushV.size(); ...

二叉树的最近公共祖先 思路一（逆向树）：o1和o2找到各自的父节点，直到公共的父节点（利用层序遍历找个各个节点的父节点，并把当前和其父节点映射，从而遍历o1和o2的父节点）。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param o1 int整型 * @param o...

二叉树和为某一值的路径 思路：每个节点进行dfs（深搜时节点必选），判断结果即可 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * ...

打印二叉树成多行 思路：简单的层序遍历 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { if(!pRoo...

对称二叉树判断 思路：利用先序依次判读左树和右树。左树是（根左右遍历），右树是（根右左遍历）,三种情况 左右树根节点都为空，返回true 左空右不为空或右空左不为空 返回false 左右值不等false，相等时继续判断后序节点。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class ...

排序 归并排序 归并思路：先分分到一个为止（单个默认有序），然后回溯排序。 如图（执行过程）： l=0,r=4,m=2，分为两组. l=0,r=2,m=1（上一组左分的继续左右分）,l=3,r=4,m=3（上一组右分的继续右分） l=0,r=1,m=0（上一组左分的继续左分，右分为一个了结束），（上一组右分结束） （左右分结束）（左右分结束） 单个时直接返回，如5,2单个返回到调用分它的上一层即（l=0,r=1,m=0）层，然后执行合并过程，，5,2进行排序，排序后重新复制到原数组（局部排序）。 5,2排序完后回到调用它的上一层（l=0,r=2,m=1）层，...

二叉树的下一个节点 方法一：暴力法 /* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; */ class Solution { public: vector<TreeLinkNode*> v...

判断是不是平衡二叉树 方法一：自顶向下，依次判断根是否，左子树是否，右子树是否 class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(!pRoot)return true; int l = high(pRoot->left); int r = high(pRoot->right); if(abs(l-r) > 1)return false;//判断根 return IsBalanced_Solution(pRoot-&...

二叉搜索树和双向链表（大佬的思路，萌新望尘莫及） 把原来大佬的指针引用传递改为，全局变量。（因为菜不理解 =-=）。 后来想通了,在此补充下。首先补充以下，引用传参特点（参数改变原值改变）相当于全局变量一般。 为啥要指针引用传参（fun(TreeNode * cur，TreeNode * &pre)） 分析代码执行过程。 首先到根节点8，左遍历传参 fun（cur，pre），此时pre为NULL 步骤1 到7节点，左遍历 fun(cur,pre) 此时pre为NULL 步骤2 到5节点，左遍历 fun(cur,pre) 此时pre为NULL...

dfs + 回溯 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<vector<int>> v; vector<vector<int>> FindPath(TreeNode* root,int expectNumber) { ...