双指针。别用递归，字符串太长了会爆栈。 class Solution { public: bool judge(string str) { int len = str.size(); int left = 0, right = len - 1; while(left <= right) { if(str[left] != str[right]) return false; left++, right--; } return true; ...

最简单的DFS。 class Solution { public: int dfs(TreeNode* root) { if(root == nullptr) return 0; else return max(dfs(root->left), dfs(root->right)) + 1; } int maxDepth(TreeNode* root) { return dfs(root); } };

最基础的DFS了。 lass Solution { public: void dfs(vector<vector<char> >& grid, int i, int j, int w, int h) { grid[i][j] = '0'; if(grid[i - 1][j] == '1' && i - 1 >= 0) dfs(grid, i - 1, j, w, h); if(grid[i + 1][j] == '1' && i + 1 < w) dfs(...

先重构二叉树，后层次遍历。 class Solution { public: unordered_map<int, int> index; TreeNode* rebuild(vector<int>& pre, int pre_left, int pre_right,vector<int>& in, int in_left, int in_right) { if (pre_left > pre_right) return nullptr; int root_...

用双指针，从两边向中间收缩。思考一下为什么不能从一边往另一边走到头。 class Solution { public: long long maxWater(vector<int>& arr) { int len = arr.size(); if(len == 0) return 0; int left = 0, right = len -1; long long ans = 0L; while(left < right) { int...

递归，注意判断去重。 class Solution { public: vector<string> vec; void dfs(string ans, string str) { int len = str.size(); if(len == 0) vec.push_back(ans); else for(int i = 0; i < len; i++) if(i == 0 || str[i] != str[i - 1]) ...

思路和合并两个链表一样，多写个for循环而已 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == nullptr) return l2; if(l2 == nullptr) return l1; ListNode* pHead = nullptr; if(l1->val < l2->val) pHead = l1, l1 = l1->next; ...

双指针，遇到比left位置更小的值，就把left移到那里。 class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); int left = 0, right = 1, maxPro = 0; while(right < len) { maxPro = max(maxPro, prices[right] - prices[left]); ...

先找到翻转的起始下标，通过判断nums[0]与target的相对大小来决定在哪一段上进行常规二分。 class Solution { public: int binary_s(vector<int> nums, int target, int left, int right) { while(left <= right) { int middle = left + (right - left) / 2; if(nums[middle] == target) return middl...

第一步，通过动态规划找到最长公共子序列长度，并构建dp数组：dp[i][j]:s1[i]和s2[j]为止的最长公共子序列的长度。dp[0][0] = s1[0] == s2[0]dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0]dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1]dp[i][j] = dp[i - 1][j - 1] + 1, s1[i] == s2[j]dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]), s1[i] != s2[j] 第二步，根据dp反推最长公共子序列...

三种查找： 普通的二分class Solution { public: int binary_search(vector<int>& nums, int target) { int len = nums.size(); int left = 0, right = len - 1; while(left <= right) { int middle = left + (right - left) / 2; if(nums[middle] == target) r...

二分搜索模板，然后下标前移。注意：写成left + (right - left) / 2而不是(left + right) / 2可以避免溢出。 class Solution { public: int binary_search(vector<int>& nums, int target) { int len = nums.size(); int left = 0, right = len - 1; while(left <= right) { int middl...

二分查找。注意点： right直接设置为x/2因为当x>4时log2(x)<x/2。 注意int溢出！判断middle与x/middle的关系，而不是middle*middle与x的关系。class Solution { public: int sqrt(int x) { if(x == 0) return 0; else if(x == 1 || x == 2 || x == 3) return 1; else { int left = 1, right = x / 2; while(l...

递归。注意下标！先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素。先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素。 class Solution { public: unordered_map<int, int> index; TreeNode* rebuild(vector<int>& pre, int pre_left, int pre_right,vector<int...