与中间值比较，分前半段有序和后半段有序分别判断。比有序的二分查找多一些判定条件。1、 要么前半段有序，要么后半段有序。2、 当前半段有序时：即循环数组中间值比循环数组最左边值大 则 nums[left] <= nums[mid] 当target 比中间值小，比最左值（前半段最小值）大时，肯定在前面部分 则high = mid - 1 。 如果不在前半段，可能在后半段，low = mid + 1。3、同理后半段也一样。ps:分前半段有序后半段有序时，当nums[left] <= nums[mid] 则 left到mid有序。否则 mid到right 有序。 class Solutio...

转载大佬&自己增加解释 class Solution { public: vector<int> LIS(vector<int>& arr) { vector<int> res; // 贪心下，用res数组存储最长上升子序列 vector<int> maxLen;// maxLen[i]:加入arr[i]元素的最大长度。 if (arr.size() < 1) return res; res.emplace_back(arr[0]); // emplace_back(val)作用同push_back，效率更高...

class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> ans; if(matrix.empty()) return ans; int m = matrix.size(), n = matrix[0].size(); int left = 0, right = n-1, top = 0, bottom = m-1; while(left <= right && top <= bott...

应该说明查找的两个节点不能重复吧。很容易引起歧义。 class Solution { public: int lowestCommonAncestor(TreeNode* root, int o1, int o2) { return dfs(root, o1, o2)->val; } TreeNode* dfs(TreeNode* root, const int& p, const int& q){ if(!root || root->val == p || root->val == q) return root; TreeNode* ls = dfs(roo...

class Solution { public: int search(vector<int>& nums, int target) { int low = 0, high = nums.size(); while(low < high){ int mid = low + (high - low)/2; // mid = low + high>>1 nums[mid] < target ? low = mid + 1 : high = mid; } return low<nums.size()&&nums[low] == tar...

class Solution { public: /** dp[i][j]:下标i，j为结尾两字符串公共子串最大长度,且默认为0。 更新dp值只能从dp[i-1][j-1]中得到。 当str1[i] == str2[j] dp[i][j] = dp[i-1][j-1] + 1 dp初始化为0； 字符串数组从0开始，dp[i-1][j-1]不存在，都错一位存储。 */ string LCS(string str1, string str2) { int m = str1.length(), n = str2.length(); vector<vector<int> > d...

class Solution { public: string solve(string s, string t) { int l = s.length(); int r = t.length(); if(!l) return t; if(!r) return s; int carry = 0, tmp = 0; if(l < r){ // 将短的字符串补到同一个长度 for(int n = r-l; n > 0; n--){ s = '0' + s; } }else if(l > r){ for(int n = l - r; n > 0; n--){ t = '0' ...

用队列实现二叉树层次遍历。 同时设置一个flag标记， 来判断二叉树该一层节点的值是否翻转。 用stl中reverse函数翻转vector数组 使用异或， 实现flag一次是0，一次是1，来回变化。```class Solution {public: vector<vector<int> > zigzagLevelOrder(TreeNode* root) { vector<vector<int> > ans; if(!root) return ans; queue<treenode*> q; q.push(root); int fl...