求树的深度，当深度差大于1时不平衡；同时还需要左子树和右子树也是平衡的。 class Solution { public: int height(TreeNode* pRoot){ if(pRoot==nullptr) return 0; int left_h=height(pRoot->left)+1; int right_h=height(pRoot->right)+1; int h=max(left_h,right_h); return h; } bool IsBalanced_Solution(TreeNode* pRoot) { if(pRoot==nullptr) re...

先把单链表拆分成结点，并将这些结点保存到vector中，自定义排序lambda对象，对vector进行sort，最后遍历vector把排序好的结点链接起来。注意拆分链表后，每个结点的next为空。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { ve...

双指针，相向而行。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param str string字符串 待判断的字符串 * @return bool布尔型 */ bool judge(string str) { for(int i=0,j=str.size()-1;i<=j;i++,j--){ if(str[i]!=str[j]) return false; } return true; } };

root的最大深度=max(左子树的最大深度+1，右子树的最大深度+1)，递归求解。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int maxDepth(TreeNode* root) { if(root==nullptr) return 0; int left_d=maxDepth(root->l...

深度优先dfs。遍历矩阵，从矩阵中的每个位置开始dfs周围是'1'的位置，dfs的同时修改'1'为'0'作为标记。思路在于每次走遍一块陆地，并将这一块陆地修改为海洋。 class Solution { public: /** * 判断岛屿数量 * @param grid char字符型vector<vector<>> * @return int整型 */ struct Pos{ int dx; int dy; }; vector<Pos> dir{{-1,0},{0,1},{1,0},{0,-1}}; void dfs(vector<vector&lt...

先建树，再层次遍历。根据前序遍历和中序遍历建树，递归左前序左中序，递归右前序右中序；通过队列层次遍历，并保存每一层的最后一个元素。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型vector 先序遍历 * @param zhongxu int整型vector 中序遍历 * @return int整型vector */ TreeNode* pre_in(vector<int>& pre_order,vector<int...

双指针法：除了第一列与最后一列不接雨水，计算其他每一列能接到的雨水，第i列能接到的雨水=min(i左边的最高值，i右边的最高值) – 第i列本身的高度。O(n^2)可能会超时。 动态规划：递推的计算两个数组，left_max保存左边最高的高度，right_max保存右边最高的高度。第i列能接到的雨水=min(left_max[i], right_max[i]) – height[i]。一下为动态规划代码。 class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 *...

回溯（深度优先搜索）。回溯求排列使用了一个标记数组used。最终的结果用set去重。 class Solution { public: void dfs(string& str,vector<string>& result,string& path,vector<bool>& used){ if(path.size()==str.size()){ result.push_back(path); return; } for(int i=0;i<str.size();i++){ if(used[i]) continue; used[i]...

先将k个有序链表的结点全部保存在vector中，注意在存结点的过程中保证每个节点的后继为空，使其称为独立的单独结点；然后自定义排序lambda对vector中的元素排序，最后将这些元素建成一个链表。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeKLists(vector<Lis...

动态规划：dp[i][0]表示第i天空仓情况下的最大盈利，dp[i][1]表示第i天满仓状态下的最大盈利，递推公式为：第i天的状态由第i-1天的空仓或者满仓两种状态递推而来。 class Solution { public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vector<int>& prices) { int n=prices.size(); vector<vector<int>> dp(n,vector<int>(2,0)); dp[0...

使用一个保存数据的栈和一个保存当前最小值的辅助栈，辅助的栈顶元素总是目前的最小值，在push和pop的时候维护两个栈就可以了。 class Solution { public: void push(int value) { stk.push(value); if(min_stk.size()==0 || min_stk.top()>value) min_stk.push(value); else min_stk.push(min_stk.top()); } void pop() { stk.pop(); min_stk.pop(); } int top() { return stk.to...

二分查找 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { int left=0; int right=nums.size()-1; while(left<=right){ int mid=left+(right-left)/2; if(target>...

二分法求根（向下取整） class Solution { public: /** * * @param x int整型 * @return int整型 */ int sqrt(int x) { long long int left=0; long long int right=x; while(left<=right){ long long int mid=left+(right-left)/2; if(mid*mid>x) right=mid-1; else if(mid*mid<x) left=mid+1; else return mid; } return right;...

贪心算法，遍历数组arr，每次都取尽量长的递增子序列，保存在result中；数组max_len用于保存arr[0,i]的元素中小于等于arr[i]的元素的个数。最后根据等式max_len[i]==j选择最终的结果，表示递增子序列的第j个元素应该这么选：它正好就是arr数组中的元素arr[i]，满足arr[i]的前面有j个元素小于等于arr[i]（也就是说此arr[i]是arr数组中的第j小元素）。 class Solution { public: /** * retrun the longest increasing subsequence * @param arr int整型vector t...